NL-NWO 2000

Let $a$ and $b$ be integers. Define $a$ to be a power of $b$ if there exists a positive integer $n$ such that $a = b^n$ . Define $a$ to be a multiple of $b$ if there exists an integer $n$ such that $a = bn$ .

Let $x$ , $y$ and $z$ be positive integer such that $z$ is a power of both $x$ and $y$ .

Decide for each of the following statements whether it is true or false. Prove your answers.

(a) The number $x + y$ is even. (b) One of $x$ and $y$ is a multiple of the other one. (c) One of $x$ and $y$ is a power of the other one. (d) There exist an integer $v$ such that both $x$ and $y$ are powers of $v$ (e) For each power of $x$ and for each power of $y$ , an integer $w$ can be found such that $w$ is a power of each of these powers. (f) There exists a positive integer $k$ such that $x^k > y$ .

Three boxes contain 600 balls each. The first box contains 600 identical red balls, the second box contains 600 identical white balls and the third box contains 600 identical blue balls. From these three boxes, 900 balls are chosen. In how many ways can the balls be chosen? For example, one can choose 250 red balls, 187 white balls and 463 balls, or one can choose 360 red balls and 540 blue balls.

Isosceles, similar triangles $QPA$ and $SPB$ are constructed (outwards) on the sides of parallelogram $PQRS$ (where $PQ = AQ$ and $PS = BS$ ). Prove that triangles $RAB$ , $QPA$ and $SPB$ are similar.

Fifteen boys are standing on a field, and each of them has a ball. No two distances between two of the boys are equal. Each boy throws his ball to the boy standing closest to him.

(a) Show that one of the boys does not get any ball. (b) Prove that none of the boys gets more than five balls.

Consider an infinite strip of unit squares. The squares are numbered "1", "2", "3", ... A pawn starts on one of the squares and it can move according to the following rules: (1) from the square numbered " $n$ " to the square numbered " $2n$ ", and vice versa; (2) from the square numbered " $n$ " to the square numbered " $3n + 1$ ", and vice versa. Show that the pawn can reach the square numbered " $1$ " in a finite number of moves.