Consecutive Remainders

What is the smallest positive integer that when divided by 10,9,8,7, and 6 leaves the remainders 9,8,7,6, and 5, respectively?
Source: NCTM Mathematics Teacher, August 2006

Solution
If x/10 leaves a remainder of 9, the possible values of x are \{9,19,29,\cdots\}. The integers x form an arithmetic progression with first term = 9 and common difference = 10. The value of the n_1th term of x is
{x_n}_1= 9+(n_1-1)10=10n_1-1
Similarly, they form arithmetic progressions with first terms = \{8,7,6,5\} and common differences = \{9,8,7,6\}. The values of their respective {x_n}_ith terms are given below
{x_n}_2=8+(n_2-1)9=9n_2-1
{x_n}_3=7+(n_3-1)8=8n_3-1
{x_n}_4=6+(n_4-1)7=7n_4-1
{x_n}_5=5+(n_5-1)6=6n_5-1
Note that the {x_n}_i are multiples of 10,9,8,7,6. The smallest such multiple is the LCM of 10=(2\times 5),9=(3^2),8=(2^3),7=(7),6=(2\times 3) which is 2^3\times 3^2\times 5\times 7=2520. Thus, the smallest positive integer that when divided by 10,9,8,7,6 leaves a remainder of 9,8,7,6,5 respectively is 2520-1=2519.

Answer2519

Advertisements
Posted in Problem solving | Tagged , , , , , , | Leave a comment

Divisible by 3 or 7

Find the number of four-digit positive integers divisible by 3 or 7.
Source: NCTM Mathematics Teacher, August 2006

Solution
Consider A=\{1002,1005,1008,\cdots,9996,9999\}, the set of four-digit positive integers divisible by 3 and B=\{1001,1008,1015,\cdots,9989,9996\}, the set of four-digit positive integers divisible by 7. The count of A=(9999-1002)/3+1=3000 and the count of B=(9996-1001)/7+1=1286.
Some integers like 1008 and 9996 appear in both sets so we  subtract them as duplicates from the total count. Since 1008+(7\times 3)=1008+(3\times 7)=1029, starting from 1008 the duplicates occur  every 7th integer in set A or every 3rd integer in set B. If we use set A, the count of duplicates = (9996-1008)/(7\times 3)+1=429. The number of four-digit positive integers divisible by 3 and/or 7 is 3000+1286-429=3857.

Answer: 3857

Alternative solution
If we divide 9999 by 3, we get 3333 which means that there are 3333 integers \leq 9999 that are divisible by 3. But, if we divide 9999 by 7, we get 1428.43 which is not an integer. So we say there are 1428 integers \leq 9999 that are divisible by 7. To  avoid this problem we use the floor function \lfloor x\rfloor = the largest integer less than or equal to x for some real number x. In our example, \lfloor 1428.43\rfloor=1428.
Number of four-digit integers divisible by 3
\lfloor 9999/3\rfloor-\lfloor 999/3\rfloor=3000
Number of four-digit integers divisible by 7
\lfloor 9999/7\rfloor-\lfloor 999/7\rfloor=1286
Number of four-digit integers divisible by 21
\lfloor 9999/21\rfloor-\lfloor 999/21\rfloor=429
There are 3000+1286-429=3857 four-digit integers divisible by 3 and/or 7.

Posted in Problem solving | Tagged , , , , , , | Leave a comment

Area of Trapezoid

In a trapezoid ABCD with \overline{AB} parallel to \overline{CD}, the diagonals intersect at point E. The area of triangle ABE is 32, and the area of triangle CDE is 50. Find the area of the trapezoid.
Source: NCTM Mathematics Teacher, August 2006

Solution
image
Draw \overline{FG} perpendicular to the bases of the trapezoid through point E. Since \overline{AB} is parallel to \overline{CD}, triangles EAB and ECD are similar. The ratio of the lengths of their corresponding sides equals the square root of the ratio of their areas.
\dfrac{AB}{CD}=\dfrac{EF}{EG}=\sqrt{\dfrac{32}{50}}=\dfrac{4}{5}
For ease in computation, let AB=4x,CD=5x, EF=4y,EG=5y for some integer x,y.
Area of trapezoid
\dfrac{AB+CD}{2}FG=\dfrac{4x+5x}{2}9y=\dfrac{81xy}{2}
Area of triangle EAB
32=\dfrac{1}{2}AB\times EF=\dfrac{1}{2}16xy
xy=4
Area of trapezoid
\dfrac{81xy}{2}=\dfrac{81\times 4}{2}=162

Answer: 162 square units

Posted in Problem solving | Tagged , , , , , , , , | Leave a comment

Values From Three Coins

How many possible values can there be for three coins selected from among pennies, nickels, dimes, and quarters.
Source: NCTM Mathematics Teacher, August 2006

Solution
a) All three coins are the same
1\:1\:1
5\:5\:5
10\:10\:10
25\:25\:25
Number of ways = 4
b) Two of the coins are the same
1\:1\:-
-\:1\:1
1\:-\:1
\cdots
Number of ways = 3\times 4=12
c) All three coins are different
Number of ways = \dbinom {4}{3}=4
Total number of ways = 4+12+4=20
If we check the values of these 20 ways, the values are all different. There are 20 possible values when three coins are selected from among pennies, nickels, dimes, and quarters.

Answer: 20

Posted in Problem solving | Tagged , , , , , | Leave a comment

Remainder of Division

What is the remainder when 7^{348}+25^{605} is divided by 8?
Source: NCTM Mathematics Teacher, August 2006

Solution
We arrange all the non-negative integers into 8 buckets depending on the value of the remainder when they are divided by 8. It works the same for negative integers too but we ignore them for this problem.
0\!:0,8,16,24,\cdots
1\!:1,9,17,25,\cdots
2\!:2,10,18,26,\cdots
3\!:3,11,19,27,\cdots
4\!:4,12,20,28,\cdots
5\!:5,13,21,29,\cdots
6\!:6,14,22,30,\cdots
7\!:7,15,23,31,\cdots
For example, 7^4+25^2 falls in the 2 bucket because 7^4+25^2=3026=378(8)+2. It is not practical to do the same direct calculation for large value like 7^{348}+25^{605} so we enlist the power of modulo arithmetic.
7^2\equiv 1\bmod 8
7^{348}=(7^2)^{174}\equiv 1^{174}\bmod 8\equiv 1\bmod 8
25\equiv 1\bmod 8
25^{605}\equiv 1^{605}\bmod 8\equiv 1\bmod 8
7^{348}+25^{605}\equiv 1\bmod 8+1\bmod 8\equiv 2\bmod 8
The remainder when 7^{348}+25^{605} is divided by 8 is 2.

Answer: 2

Posted in Problem solving | Tagged , , , , , | Leave a comment

Set of Primes

Let P be the set of primes that divide 200!. What is the largest integer k so that the set of primes that divides k! is equal to P?
Source: NCTM Mathematics Teacher, August 2006

Solution
200!=200\times 199\times 198\times\cdots\times 3\times 2\times 1
P=\{199,197,193,\cdots,3,2\}
The next prime greater than 199 is 211. If k=210, then 210! will have the same set P of prime divisors as 200!.

Answer 210

Posted in Problem solving | Tagged , , , , , , | Leave a comment

Largest 4-digit Integer x

Consider the equation 15x+14y=7. Find the largest four-digit integer x for which there is an integer y so that the pair (x,y) is a solution.
Source: NCTM Mathematics Teacher, August 2006

Solution
15x+14y=7
14y=7-15x
y=\dfrac{7-15x}{14}
For y to be an integer, 7-15x must be a multiple of 14.
7-15x=14k for some integer k
-15x=14k-7
-15x=7(2k-1)
\dfrac{-15x}{7}=2k-1
Thus, 7 divides -15x and the quotient is odd. Since 7 does not divide 15, it must divide x and x must be odd. The largest 4-digit x\leqslant 9999 that meets the requirement is 9989.

Answer: 9989

Alternative solution

image
(x,y)=(7,-7) is a point on the graph of 15x+14y=7. We want the largest 4-digit integer x such that (x,y) is a solution. Let x=7+\Delta x for some integer \Delta x.
y=\dfrac{7-15x}{14}
=\dfrac{7-15(7+\Delta x)}{14}
=\dfrac{-14(7)-15\Delta x}{14}
=-7-\dfrac{15\Delta x}{14}
For y to be an integer, 14 must divide 15\Delta x. Since 14 and 15 are relatively prime, 14 must divide \Delta x. Hence, \Delta x=14k for some integer k.
x=7+14k\leqslant 9999
14k\leqslant 9992
k\leqslant \dfrac{9992}{14}=713.71
x=7+14(713)=9989

Posted in Problem solving | Tagged , , , , , , , , , , | Leave a comment

Two Defective Tiles

An 8-by-8-ft area has been tiled with 1-foot-square tiles. Two of the tiles were defective. What is the probability that the two defective tile share an edge?
Source: NCTM Mathematics Teacher, August 2006

Solution
image
Area 2\times 2
Vertical shared edges 1\times 2=2
Horizontal shared edges 1\times 2=2
Total 4 shared edges
image
Area 3\times 3
Vertical shared edges 2\times 3=6
Horizontal shared edges 2\times 3=6
Total 12 shared edges
image
Area 4\times 4
Vertical shared edges 3\times 4=12
Horizontal shared edges 3\times 4=12
Total 24 shared edges
\cdots
From the pattern we derive the number of shared edges in a 8\times 8 area
Vertical shared edges 7\times 8=56
Horizontal shared edges 7\times 8=56
Total 112 shared edges
Instead of thinking of how many ways can we lay the two defective tiles so that they share an edge, equivalently we can think of how many shared edges there are — each shared edge corresponds to a way of laying the two defective tiles.
Number of desirable outcomes = 112
Number of possible outcomes = \dbinom{64}{2}=2016    — ways to choose 2 tiles out of 64
Probability (two defective tiles share an edge) = 112/2016=1/18

Answer: 1/18

Alternative Solution 1
If the first defective tile is placed in a location in an upper row (there are seven upper rows), the second defective tile can occupy the adjacent location directly below it.
Probability = (7\times 8)/2016
If the first defective tile is placed in a location in a left column (there are seven left columns), the second defective tile can occupy the adjacent location directly to its right.
Probability = (7\times 8)/2016
Probability (two defective tiles share an edge)
(7\times 8)/2016+(7\times 8)/2016=112/2016=1/18

Alternative solution 2
image
The first defective tile may be placed within the interior  — probability = 36/64
Or in the four edges — probability = 24/64
Or in the four corners — probability = 4/64
image
Once the first defective tile is placed, the second defective tile must be placed in an adjacent location for them to share an edge.
If the first defective tile is placed in an interior location, the second defective tile can occupy four possible adjacent locations — probability = 4/63
If the first defective tile is placed in an edge location, the second defective tile can occupy three possible adjacent locations — probability = 3/63
If the first defective tile is placed in a corner location, the second defective tile can occupy two possible adjacent locations — probability = 2/63
Probability (two defective tiles shared an edge)
(36/64)(4/63)+(24/64)(3/63)+(4/64)(2/63)=(144+72+8)/4032
=224/4032=1/18

Posted in Problem solving | Tagged , , , , | Leave a comment

Choosing an Integer

An experiment consists of choosing with replacement an integer at random among the numbers from 1 to 9 inclusive. If we let M denote a number that is an integral multiple of 3 and N denote a number that is not an integral multiple of 3, arrange in order of increasing likelihood the following sequences of results: (a) MNNMN, (b) NMMN, (c) NMMNM, (d) NNMN, (e) MNMM
Source: NCTM Mathematics Teacher, August 2006

Solution
Let M denote 3,6,9 and N denote 1,2,4,5,7,8.
P(M) = probability of choosing M=3/9=1/3
P(N) = probability of choosing N=6/9=2/3

(a) P(MNNMN)=P(M)P(N)P(N)P(M)P(N)=(1/3)^2(2/3)^3=8/243
(b) P(NMMN)=P(N)P(M)P(M)P(N)=(1/3)^2(2/3)^2=12/243
(c) P(NMMNM)=P(N)P(M)P(M)P(N)P(M)=(1/3)^3(2/3)^2=4/243
(d) P(NNMN)=P(N)P(N)P(M)P(N)=(1/3)^1(2/3)^3=24/243
(e) P(MNMM)=P(M)P(N)P(M)P(M)=(1/3)^3(2/3)^1=6/243
The sequences in increasing likelihood are (c), (e), (a), (b), (d)

Answer: (c), (e), (a), (b), (d)

Alternative solution
(a) MNNMN
Number of desirable outcomes = 3\times 6\times 6\times 3\times 6
Number of possible outcomes = 9\times 9\times 9\times 9\times 9
P(MNNMN)=\dfrac{3\times 6\times 6\times 3\times 6}{9\times 9\times 9\times 9\times 9}=\dfrac{8}{243}
(b) NMMN
Number of desirable outcomes = 6\times 3\times 3\times 6
Number of possible outcomes = 9\times 9\times 9\times 9
P(NMMN)=\dfrac{6\times 3\times 3\times 6}{9\times 9\times 9\times 9}=\dfrac{12}{243}
(c) NMMNM
Number of desirable outcomes = 6\times 3\times 3\times 6\times 3
Number of possible outcomes = 9\times 9\times 9\times 9\times 9
P(NMMNM)=\dfrac{6\times 3\times 3\times 6\times 3}{9\times 9\times 9\times 9\times 9}=\dfrac{4}{243}
(d) NNMN
Number of desirable outcomes = 6\times 6\times 3\times 6
Number of possible outcomes = 9\times 9\times 9\times 9
P(NNMN)=\dfrac{6\times 6\times 3\times 6}{9\times 9\times 9\times 9}=\dfrac{24}{243}
(e) MNMM
Number of desirable outcomes = 3\times 6\times 3\times 3
Number of possible outcomes = 9\times 9\times 9\times 9
P(MNMM)=\dfrac{3\times 6\times 3\times 3}{9\times 9\times 9\times 9}=\dfrac{6}{243}

 

Posted in Problem solving | Tagged , , , , , | Leave a comment

Shift Left

Given the equation x^3-2x^2+x-3=0, find an equation whose roots are each 2 less than the roots of the given equation.
Source: NCTM Mathematics Teacher, August 2006

Solution
image
If we graph the given equation as a function y=x^3-2x^2+x-3, we see that it has one real root at x\approx 2.1746. The other two roots are complex and not shown. To get a new equation that has also three roots each 2 less than the roots of the given equation, all we have to do is shift the graph to the left by 2 units. Algebraically, it means replacing x by x-(-2)=x+2
y=(x+2)^3-2(x+2)^2+(x+2)-3
=x^3+4x^2+5x-1

image
The new equation is x^3+4x^2+5x-1=0

Answer: x^3+4x^2+5x-1

Posted in Problem solving | Tagged , , , , , , , | Leave a comment