Herzog Competition - 2008

Herzog Competition 2008

The grading will be harsh, because that is how the Putnam exam is graded. So make sure you justify as much as you can every step! Have fun and may the algorithm be with you!

Problem 1

(I. Mitrea) Consider 3 different coins (say a nickel, a dime and a quarter) and place them on a table so that the 3 of them are not on the same line. An allowable move consists of taking one of the coins, moving it along a straight line that crosses the line segment determined by the other two coins, until some point past that line segment (so that after the allowable move the three coins are still not on the same line.) Is it possible to perform exactly 2008 allowable moves and return to the original position? And with exactly 2009 allowable moves? Justify your answer.

Problem 2

(MMO) Three friends A, B, C play ping-pong two at a time. Whomever wins a given game plays the next game against whomever was not playing that given game. A plays 15 games, B plays 10 games and C plays 17 games. Who lost the second game? Justify your answer.

Problem 3

(MMO) Consider 7 arbitrary different points in the plane and the 21 line segments joining each pair of them. Prove that at least 3 of these 21 line segments have different length.

Problem 4

(J. Calcut, V. Peller) What is the maximum number of knights that can be placed in a regular chess board so that no two knights can attack each other in one single move? Justify your answer. (Note: recall that a regular chess board is a square where each side is divided into 8 equal segments, thus determining 64 equal squares, and each of these 64 squares is colored in black or white alternatively. I.e. if we placed the center of these 64 squares on the integer lattice in the plane, the set of centers of squares would be the set of points $\{(i,j):1\le i,j\le 8\}$, and the white squares are those such that $i+j$ is an even number, while the black squares are those such that $i+j$ is an odd number. If a knight is placed in the square $(i,j)$, then it can attack in a single move any single one of the squares $(i\pm 2,j\pm 1)$ and $(i\pm 1,j\pm 2)$, provided that these squares are in the regular chessboard.)

Problem 5

(P. Bates) Is it possible to find one point P and one square in the plane with vertices A, B, C, D such that the distances from P to A, B, C, D are respectively $d+1$, $d+2$, $d+3$, $d+4$ for some real number $d\ge 0$? Justify your answer. If you need to, you can assume as known that the set of points in the plane $(x,y)$ whose distances to the points $(-c,0)$ and $(c,0)$ differ by $2a>0$ is the hyperbola $\frac{x^2}{a^2}-\frac{y^2}{b^2}=1$, where $b^2=c^2-a^2>0$.