Question bank Math Olympiad Vault 1997

Let $F_n$ be the Fibonacci sequence $F_1 = F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$. Put $V_n = \sqrt{F_n^2 + F_{n+2}^2}$. Show that $V_n$, $V_{n+1}$, $V_{n+2}$ are the sides of a triangle of area $1/2$.

$f$ is a map on the plane such that two points a distance $1$ apart are always taken to two points a distance $1$ apart. Show that for any $d$, $f$ takes two points a distance $d$ apart to two points a distance $d$ apart.

$A$ is a set of $n$ non-negative integers. We say it has property $P$ if the set $\{x + y \mid x, y \in A\}$ has $\frac{n(n+1)}{2}$ elements. We call the largest element of $A$ minus the smallest element the *diameter* of $A$. Let $f(n)$ be the smallest diameter of any set $A$ with property $P$. Show that $\frac{n^2}{4} \le f(n) \lt n^3$.
(If you still have time, try to improve these bounds. For example, try to prove that $f(p) \lt 2p^2$ for all primes $p$.)

Let $c$ be a rational. Let $f(x) = x^2 + c$. Define $f^{(0)}(x) = x$, $f^{(n+1)}(x) = f(f^{(n)}(x))$. Show that there are only finitely many rationals $x$ such that the sequence $f^{(0)}(x), f^{(1)}(x), f^{(2)}(x), \dots$ takes only finitely many values.

Let $R$ be the set of real numbers. Show that there are no functions $f, g: R \to R$ such that $g(f(x)) = x^3$ and $f(g(x)) = x^2$ for all $x$. Let $S$ be the set of all real numbers greater than $1$. Show that there are functions $f, g: S \to S$ satisfying the condition above.

Given a sequence $a_{1}, a_{2}, a_{3}, \ldots$ of positive integers in which every positive integer occurs exactly once. Prove that there exist integers $\ell$ and $m$, $1\lt \ell\lt m$, such that $a_{1}+a_{m}=2 a_{\ell}$.

The worlds in the Worlds' Sphere are numbered $1, 2, 3, \ldots$ and connected so that for any integer $n \geqslant 1$, Gandalf the Wizard can move in both directions between any worlds with numbers $n, 2n$ and $3n+1$. Starting his travel from an arbitrary world, can Gandalf reach every other world?

Twelve cards lie in a row. The cards are of three kinds: with both sides white, both sides black, or with a white and a black side. Initially, nine of the twelve cards have a black side up. The cards $1$-$6$ are turned, and subsequently four of the twelve cards have a black side up. Now cards $4$-$9$ are turned, and six cards have a black side up. Finally, the cards $1$-$3$ and $10$-$12$ are turned, after which five cards have a black side up. How many cards of each kind are there?

Find all triples $(a, b, c)$ of non-negative integers satisfying $a \geqslant b \geqslant c$ and $1 \cdot a^{3} + 9 \cdot b^{2} + 9 \cdot c + 7 = 1997$.

Determine all functions $f$ from the real numbers to the real numbers, different from the zero function, such that $f(x) f(y) = f(x-y)$ for all real numbers $x$ and $y$.

In the acute triangle $ABC$, the bisectors of $\angle A$, $\angle B$ and $\angle C$ intersect the circumcircle again in $A_{1}$, $B_{1}$ and $C_{1}$, respectively. Let $M$ be the point of intersection of $AB$ and $B_{1}C_{1}$, and let $N$ be the point of intersection of $BC$ and $A_{1}B_{1}$. Prove that $MN$ passes through the incentre of triangle $ABC$.

Let $x_{1}=1$ and $x_{n+1}=x_{n}+\left\lfloor\frac{x_{n}}{n}\right\rfloor+2$ for $n=1,2,3, \ldots$, where $\lfloor x\rfloor$ denotes the largest integer not greater than $x$. Determine $x_{1997}$.

a) Prove the existence of two infinite sets $A$ and $B$, not necessarily disjoint, of non-negative integers such that each non-negative integer $n$ is uniquely representable in the form $n=a+b$ with $a \in A, b \in B$.


b) Prove that for each such pair $(A, B)$, either $A$ or $B$ contains only multiples of some integer $k\gt 1$.

On two parallel lines, the distinct points $A_{1}, A_{2}, A_{3}, \ldots$ respectively $B_{1}$, $B_{2}, B_{3}, \ldots$ are marked in such a way that $|A_{i}A_{i+1}|=1$ and $|B_{i}B_{i+1}|=2$ for $i=1,2, \ldots$ (see Figure). Provided that $\angle A_{1}A_{2}B_{1}=\alpha$, find the infinite sum $\angle A_{1}B_{1}A_{2}+\angle A_{2}B_{2}A_{3}+\angle A_{3}B_{3}A_{4}+\ldots$

Prove that in every sequence of 79 consecutive positive integers written in the decimal system, there is a positive integer whose sum of digits is divisible by 13.

If we add $1996$ and $1997$, we first add the unit digits $6$ and $7$. Obtaining $13$, we write down $3$ and "carry" $1$ to the next column. Thus we make a carry. Continuing, we see that we are to make three carries in total:
$$
\begin{array}{r}
111 \\
1996 \\
+1997 \\\hline
3993
\end{array}
$$
Does there exist a positive integer $k$ such that adding $1996 \cdot k$ to $1997 \cdot k$ no carry arises during the whole calculation?

Prove that the arithmetic mean $a$ of $x_{1}, \ldots, x_{n}$ satisfies
$$
\left(x_{1}-a\right)^{2}+\cdots+\left(x_{n}-a\right)^{2} \leqslant \frac{1}{2}\left(\left|x_{1}-a\right|+\cdots+\left|x_{n}-a\right|\right)^{2} .
$$

On a $5 \times 5$ chessboard, two players play the following game. The first player places a knight on some square. Then the players alternately move the knight according to the rules of chess, starting with the second player. It is not allowed to move the knight to a square that has been visited previously. The player who cannot move loses. Which of the two players has a winning strategy?

A rectangle can be divided into $n$ equal squares. The same rectangle can also be divided into $n+76$ equal squares. Find all possible values of $n$.

Two circles $\mathcal{C}_1$ and $\mathcal{C}_2$ intersect in $P$ and $Q$. A line through $P$ intersects $\mathcal{C}_1$ and $\mathcal{C}_2$ again in $A$ and $B$, respectively, and $X$ is the midpoint of $AB$. The line through $Q$ and $X$ intersects $\mathcal{C}_1$ and $\mathcal{C}_2$ again in $Y$ and $Z$, respectively. Prove that $X$ is the midpoint of $YZ$.