## 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_1$th 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}_i$th 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$.

Answer$2519$

## 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 $7$th integer in set $A$ or every $3$rd 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$.

## 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

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

## 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$

## 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$

## 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$

## 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

$(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$

## 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

Area $2\times 2$
Vertical shared edges $1\times 2=2$
Horizontal shared edges $1\times 2=2$
Total $4$ shared edges

Area $3\times 3$
Vertical shared edges $2\times 3=6$
Horizontal shared edges $2\times 3=6$
Total $12$ shared edges

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

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$

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$

## 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}$

## 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

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$

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

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