Herzog Competition - 2006

Problem 1

All noble knights participating in a medieval tournament in Camelot used nicknames. In the tournament each knight fought with all other knights. Each combat had a winning knight and a losing knight. At the end of the tournament the losers reported their real names to the winners and to the winners of their winners. Can one be sure that there was a person who learned the real names of all knights? Justify your answer.

Problem 2

Find all four digit numbers $n$ such that the last four digits of $n^2$ coincide with the digits of $n$.

Problem 3

Consider the matrices A and B defined by

$$A=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)\text{and}B=\left(\begin{array}{cc}1& 0\\ -2& 1\end{array}\right)$$

Prove that if you take the product of any number of matrices A and B in an arbitrary order, you cannot obtain the identity matrix

$$I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$$

Problem 4

(a) Is there a continuous nonconstant function $f$ on $[0,1)$ such that

$f(x-x^2)=f(x),x\in [0,1)?$

(b) Is there a continuous nonconstant function $f$ on $(0,1)$ such that

$f(x-x^2)=f(x),x\in (0,1)?$

Problem 5

In a warehouse there are 99 boxes. Each box contains some apples and oranges. Prove that you can choose 50 boxes that contain more than 50% of apples and more than 50% of oranges.