BAMO Practice Session-Solutions February 18, 2001

1. Several one-digit numbers are written on a blackboard. One can replace any one of the numbers by the last digit of the sum of all of the numbers. Prove that there is a (nonempty) sequence of such operations, after which the original collection of numbers again appears on the blackboard.

   Solution: We keep replacing the first number. If $d$ is the initial value of the first number and $s$ is the initial sum, then replacing the first number increases it by $s-d$ modulo 10, and increases the sum modulo 10 by the same amount. So replacing the first number again increases it by $s-d$ modulo 10 again, and so on. After ten iterations, we are back where we started.

2. Two players play the following game on a $100 \times 100$ board. The first player marks a free square, then the second player puts a $1 \times 2$ domino down covering two free squares, one of which is marked. The first player wins if the entire board is covered, otherwise the second player wins. Which player has a winning strategy?

   Solution: The first player has a winning strategy. Let us say a position is stable if every square below or to the right of a free square is free. Then we claim the first player can always ensure that on his turn, either the position is stable or there is a free square with exactly one free neighbor (or both).

   Let us label the square in the $i$-th row and $j$-th column as $(i,j)$, with $(1,1)$ in the top left. We call a free square a corner if is not below or to the right of another free square. Let $(a_1,b_1)$, $(a_2, b_2)$, $\dots$, $(a_k, b_k)$ be the corners from top to bottom.

   First notice that if $(a,b)$ is a corner such that both $(a+1,b-1)$ and $(a-1,b+1)$ are nonfree (or off the board), then the first player may mark $(a,b)$, and however the second player moves, the result will be a stable position. More generally, if $(a,b),(a+1,b-1),\cdots,(a+k,b-k)$ are corners and $(a-1,b+1)$ and $(a+k+1,b-k-1)$ are both nonfree or off the board, the first player can be sure to return to a stable position.

   To show this, first note that we cannot have both $a=1$ and $b-k=1$, or else the number of nonfree squares would be odd, which is impossible. Without loss of generality, assume that $b-k \neq 1$ is not the final corner. The first player now marks $(a,b)$. If the second player covers $(a,b)$ and $(a,b+1)$, the position is again stable. Otherwise, the first player marks $(a+1,b-1)$ and the second player is forced to cover it and $(a+2,b-1)$. Then the first player marks $(a+2,b-2)$ and the second player is forced to cover it and $(a+3,b-2)$, and so on. After $(a+k,b-k)$ is marked, the result is a stable position. (Note that the assumption $b-k \neq 1$ ensures that the moves described do not cross the edge of the board.)

   To finish the proof, we need to show that such a chain of corners must exist. Write the labels $(a_1, b_1), \dots, (a_k, b_k)$ in a row, and join two adjacent labels by a segment if they are of the form $(a,b), (a+1,b-1)$. If two adjacent labels $(a,b), (a+i,b-j)$ are not joined by a segment, then either $i=1$ or $j=1$ but not both. If $i=1$, draw an arrow between the labels pointing towards $(a+i,b-j)$; otherwise draw the arrow the other way. Also draw arrows pointing to $(a_1,b_1)$ and $(a_k, b_k)$. There is now one more chain of corners (joined by segments) than arrows, so some chain has two arrows pointing to it. That chain satisfies the condition above, so the first player can use it to create another stable position. Consequently, the first player can ensure victory.

3. Fifty numbers are chosen from the set $\{1, \dots, 99\}$, no two of which sum to 99 or 100. Prove that the chosen numbers must be $50, 51, \dots, 99$.

   Solution: In the sequence

   $$99, 1, 98, 2, 97, 3, \dots, 51, 49, 50,$$
   any two adjacent numbers sum to 99 or 100, so both cannot occur. Grouping the numbers into 49 pairs plus one extra, we see at most 50 numbers can occur, and 50 must be one of them. Since we must step at least two terms along the list to make the next choice, the numbers must indeed be $50, 51, \dots, 99$.

4. Let $M$ be the intersection of the diagonals of the trapezoid $ABCD$. A point $P$ such that $\angle APM = \angle DPM$ is chosen on the base $BC$. Prove that the distance from $C$ to the line $AP$ is equal to the distance from $B$ to the line $DP$.

   Solution: Since $M$ lies on the internal angle bisector of angle $\angle APD$, it lies at the same distance from the lines $AP$ and $DP$. The ratio of this distance to the distance from $C$ to $AP$ is $AM/MC$, while the ratio of this distance to the distance from $B$ to $DP$ is $BM/MD$. But $AM/MC=BM/MD$ by similar triangles, so the distance from $C$ to $AP$ equals the distance from $B$ to $DP$.

5. In a group of several people, some are acquainted with each other and some are not. Every evening, one person invites all of his acquaintances to a party and introduces them to each other. Suppose that after each person has arranged at least one party, some two people are still unacquainted. Prove that they will not be introduced at the next party.

   Solution: Notice that two people are initially connected by a chain of acquaintances if and only if they are connected by such a chain at the end. (Any party acquaints pairs of people who already have a common acquaintance.) We claim if $A$ and $B$ are initially connected, then afterwards they will be acquainted. Suppose $A, P_1, \dots, P_k, B$ is a chain of acquaintances of shortest possible length joining $A$ to $B$. Each time some person $P_i$ holds a party, he introduces his neighbors on either side of the chain to each other, so he can then drop out of the chain. After each $P_i$ has held a party, they have all dropped out of the chain, so $A$ and $B$ are acquainted.

   Conversely, if $A$ and $B$ are not acquainted after all of the parties, then they were not initially connected, and so are still not connected. In particular, they have no common acquaintance, so they will not be introduced at the next party.

6. Let $M$ be the intersection of the diagonals of a cyclic quadrilateral, $N$ the intersections of the lines joining the midpoints of opposite sides, and $O$ the circumcenter. Prove that $OM \geq ON$.

   Solution: We use vectors. If $A, B, C, D$ are the vertices of the quadrilateral in order, then $N = (A+B+C+D)/4$; in particular, if $E$ and $F$ are the midpoints of $AC$ and $BD$, respectively, then $N$ is the midpoint of $EF$. The circle with diameter $OM$ passes through $E$ and $F$, so $OM \geq OE$ and $OM \geq OF$; moreover, in any triangle, the median to a side is no longer than the average of the other two sides (rotate the triangle by $\pi$ about the foot of the median, so twice the median becomes a diagonal of a parallelogram, and use the triangle inequality). Hence $OM \geq ON$.

7. Prove that for every polynomial $P(x)$ of degree 10 with integer coefficients, there is an infinite (in both directions) arithmetic progression which does not contain $P(k)$ for any integer $k$.

   Solution: Since $P$ is not linear, there exists $x$ such that $\vert P(x+1) - P(x)\vert = n > 1$. Since $P(t + k) \equiv P(t) \pmod{k}$, each value of $P$ is congruent to one of $P(x), P(x+1), \dots, P(x+n-1)$ modulo $n$. However, since $P(x+1) - P(x) = n$, the values of $P$ cover at most $n-1$ distinct residue classes, and so there is an arithmetic progression of difference $n$ containing no values of $P$.

8. Find all positive integers $n$ such that $3^{n-1}+5^{n-1}$ divides $3^{n}+5^{n}$.

   Solution: The only such $n$ is $1$. Let $s_n = 3^n + 5^n$; then $s_n - 3 s_{n-1} = 2\cdot 5^{n-1}$, while $5 s_{n-1} - s_n = 2\cdot 3^{n-1}$. If $s_{n-1}$ divides $s_n$, then it must also divide $2\cdot 5^{n-1}$ and $2\cdot 3^{n-1}$, but the GCD of these two numbers is 2. Thus $s_{n-1}$ must divide 2; on the other hand, $s_{n-1} > 2$ for $n>1$. So we can only have $n=1$, and indeed, $3^0+5^0=2$ does divide $3^1+5^1=8$.

9. The points $A'$ and $C'$ are chosen on the diagonal $BD$ of a parallelogram $ABCD$ so that $AA' \parallel CC'$. The point $K$ lies on the segment $A'C$, and the line $AK$ meets $CC'$ at $L$. A line parallel to $BC$ is drawn through $K$, and a line parallel to $BD$ is drawn through $C$; these meet at $M$. Prove that $D, M, L$ are collinear.

   Solution: Let $M'$ and $M''$ be the intersections of $DM$ with $MK$ and $MC$, respectively. Since $M'K \parallel DA$, we have $LM'/LD = LK/LA$. Since $CK \parallel C'A$, we have $LK/LA = LC/LC'$. Finally, since $CM \parallel C'D$, we have $LM''/LD = LC/LC'$. Therefore $LM'/LD = LM''/LD$ and so $M' = M'' = M$. (Note: a solution using Cartesian coordinates is also possible.)

10. Several positive integers are written on a blackboard. One can erase any two distinct integers and write their greatest common divisor and least common multiple instead. Prove that eventually the numbers will stop changing.

    Solution: If $a, b$ are erased and $c < d$ are written instead, we have $c \leq \min(a,b)$ and $d \geq \max(a, b)$; moreover, $ab = cd$. From this we may conclude $a+b \leq c+d$ by writing $ab + a^2 = cd + a^2 \leq ac + ad$ (the latter since $(d-a)(c-a) \leq 0$) and dividing both sides by $a$. Thus the sum of the numbers never decreases, and it is obviously bounded (e.g. by $n$ times the product of the numbers, where $n$ is the number of numbers on the board); hence it eventually stops changing, at which time the numbers never change.