Herzog Competition - 2010

Herzog Competition 2010

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

(A. Volberg) A convex set is a set such that for any two points in it, the line segment joining them is also contained in the set. For example, a circle or a square is a convex set, but a banana is not (if you join the tips of the banana by a line segment, the line segment is not inside the banana). The problem is: subdivide a square into convex pentagons (i.e. the pentagons do not intersect except for the sides or the vertexes, and they cover all of the square).

Problem 2

(B. C. Musselman) Are there any two irrational numbers (say $x$ and $y$) such that one raised to the power of the other ($x^y$) is rational? Remember a rational number is a number that can be written as $\frac{p}{q}$, where $p$ and $q$ are integers, i.e. 0, ±1, ±2, · · · , but of course $q\ne 0$. An irrational number is a number that is not rational, e.g. $\pi$.

Problem 3

(D. Zhan) 100 children stood in a line next to each other. The teacher asked them to turn right. Most of them turned right except for 30 of them who turned left. Then some children saw another child face to face. To correct the mistake, those children who found him/herself facing another child turned to the other direction. After this move, there were still some children facing his/her fellow. Then these children turned to the other direction. This process continues until there are no two children facing each other. Prove that after finitely many corrections, all children stopped turning.

Problem 4

(D. J. Newman, proposed by Y. Wang) Prove that every infinite sequence (of real numbers) contains a monotone subsequence. Recall that a sequence of real numbers is just an enumeration of some real numbers, e.g. $a_1=7$, $a_2=12\pi$, $a_3=-5.3$, etc. so that for every $n$, there is an $a_n$ defined. A subsequence is a sequence inside an initial sequence, following the same order of enumeration, e.g. the odd terms $a_1$, $a_3$, $a_5$, etc., or the even terms, or some other selection of the terms of $a_n$, but in the same order as $a_n$. A monotone sequence (or subsequence) is one that is either non-increasing (i.e. $a_n\ge a_{n+1}$ for all $n$) or non-decreasing (i.e. $a_n\le a_{n+1}$ for all $n$).

Problem 5

(Putnam 1992, proposed by Y. Wang) Prove that $\mathrm{f}(n)=1-n$ is the only integer valued function defined on the integers that satisfies the following conditions.

1. $\mathrm{f}(\mathrm{f}(n))=n$ for all integer $n$;
2. $\mathrm{f}(\mathrm{f}((n+2))+2)=n$ for all integer $n$;
3. $\mathrm{f}(0)=1$.

Problem 6

(Putnam 1988) If every point of the plane is painted one of three colors, do there necessarily exist two points of the same color exactly one inch apart?