Herzog Competition - 2009

Problem 1

(W. Brown & G. Ludden) Let ${\mathbb{R}}^2=\{(x,y):x,y\in \mathbb{R}\}$, i.e. the plane. Let $f:{\mathbb{R}}^2\to {\mathbb{R}}^2$ be a map that preserves distances (i.e. the distance between $f(x)$ and $f(y)$ is equal to the distance between $x$ and $y$.) By distance we mean the usual distance (i.e. Euclidean distance.) Prove that $f$ is onto, i.e. that for every point $z$ in the plane, there is a point $w$ in the plane such that $f(w)=z$.

Problem 2

(IMTT, proposed by M. Shapiro) There are forty weights: 1, 2, . . . , 40 grams. Ten weights with even masses were put on the left pan of a scale. Then another ten weights with odd masses were put on the right pan of the scale. The left and right pans of the scale are now balanced. Prove that on one pan of the scales there are two weights with difference in mass of exactly 20 grams.

Problem 3

(P. Magyar) Define the Fibonacci sequence as $F_1=1,F_2=1$, and in general, $F_{n+2}=F_{n+1}+F_n$ for $n\ge 1$. (So, e.g., $F_3=2,F_4=3,F_5=5,F_6=8,F_7=13,F_8=21$, and so on.)

(a) Prove that every third Fibonacci number is even, and the rest are odd.

(b) More generally, prove that $F_k$ divides $F_{nk}$ for any $n$ and $k$ positive integers.

Problem 4

(R. Shadrach) A battle ship is travelling on the number line. It starts at an unknown integer and moves at an unknown constant integer speed (integers per second.) You can fire a cannon once every second at an integer, destroying the ship if it is there. Come up with an algorithm for firing that is guaranteed to destroy the ship in a finite amount of time.

Problem 5

(Putnam 1965, proposed by Y. Wang) At a party, assume that no boy dances with every girl but each girl dances with at least one boy. Prove that there are two couples $gb$ and $g^{\prime }{b}^{\prime }$ which dance whereas $b$ doesn’t dance with $g^{\prime }$ and $b^{\prime }$ doesn’t dance with $g$.

Problem 6

(Putnam 1966, proposed by Y. Wang) Let a convex polygon P be contained in a square of side one. Show that the sum of the squares of the sides of P is less than or equal to 4.