IMO 1997 Problem 6

For each positive integer $ n$, let $ f(n)$ denote the number of ways of representing $ n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $ f(4)=4$, because the number 4 can be represented in the following four ways: $4$; $2+2$; $2+1+1$; $1+1+1+1$.

Prove that, for any integer $ n \geq 3$ we have $ 2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}$.

==============================

We always sort powers of two in non-decreasing order. 

For $0\le k\le n$, denote by $g(n,k)$ the number of ways of representing $2^n$ with the largest term $2^k$. So $$f(2^n)=g(n,0)+\dots+g(n,n).$$ Unless the representation has a single term $2^n$, two copies of $2^{n-1}$ are represented separately where the largest term $2^j$ of the first copy is no more than the smallest term of the second copy. Moreover, the problem of representing the second copy is reduced by $2^j$. This gives recurrence $$g(n,k)=\sum_{j=0}^k g(n-1,j)g(n-1-j,k-j), 0\le k<n$$ with boundary conditions $$g(n,n)=1,n\in\mathbb{Z}_{\ge0}.$$

$\boxed{2^{\frac {n^2}{4}} < f(2^n)}$

Lemma: $2^{k(n-k)}\le g(n,k)$.

Proof: it is true for $k\in\{0,n\}$. By induction, for $n>k$ we have $$g(n,k)\ge\sum_{j=0}^k 2^{j(n-1-j)}2^{(k-j)(n-1-k)}=2^{k(n-k)}2^{-k}\sum_{j=0}^k 2^{j(k-j)},$$ which is at least $$2^{k(n-k)}2^{-k}\left(2^0+2^1+\dots+2^{k-1}+2^0\right)\ge2^{k(n-k)}.$$

With this we have $$f(2^n)=g(n,0)+\dots+g(n,n)\ge 2^{0(n-0)}+2^{1(n-1)}+\dots+2^{(n-1)1}+2^{(n-0)0}.$$ If $n$ is even then one term is exactly $2^{\frac{n^2}{4}}$. Otherwise there are two identical terms with sum $$2\cdot2^{\frac{n-1}{2}\frac{n+1}{2}}=2^{\frac{n^2-1}{4}+1}>2^{\frac {n^2}{4}}.$$

$\boxed{f(2^n)<2^{\frac {n^2}{2}}}$

We will show that $$\frac{f(2^{n+1})}{f(2^{n})}\le2^n,$$ as this enables us to prove the upper bound inductively: $$f(2^{n+1})\le f(2^n)2^n<2^{\frac{n^2}{2}+n}<2^{\frac{(n+1)^2}{2}}.$$

Let $S$ be the set of decompositions of $2^{n+1}$ and $T$ be the set of decompositions of $2^{n+1}$ without $1$-term. Define a mapping $h:S\mapsto T$ as replacing every pair of $1$-terms by a $2$-term. Every element of $T$ is mapped from at most $2^n$ elements of $S$, except for the all-$2$ element, which is mapped from $2^n+1$ elements. This is because the number of $2$-terms in any element of $T$ is at most $2^{n}-1$, except that all-$2$ element for which it is $2^n$. Also any element of $T$ without $2$-terms is not mapped from $2^n$ elements of $S$. Hence $$f(2^{n+1})=|S|\le 2^n+1+\left(|T|-2\right)2^n+2^n-1\le2^n|T|=2^nf(2^n).$$

IMO 1994 Problem 3

For any positive integer $ k$, let $ f(k)$ be the number of elements in the set $ \{ k+1, k+2, \ldots, 2k\}$ whose base $2$ representation contains exactly three 1s. 

(a) Prove that for any positive integer $ m$, there exists at least one positive integer $ k$ such that $ f(k)=m$.

(b) Determine all positive integers $ m$ for which there exists exactly one $ k$ with $ f(k) =m$.

============================

Call the numbers whose base $2$ representations have exactly three ones the good numbers. Let $$A_k:=\{k+1,\dots,2k\}.$$

(a) Since $f(1)=0$, it suffices to show that $$f(k-1)\le f(k)\le1+f(k-1).$$ Each time we remove $k$ and add $2k-1$ and $2k$ to obtain $A_k$ from $A_{k-1}$. If $k$ is good and so is $2k$, hence $f(k)\ge f(k-1)$. If $2k$ is good then so is $k$, hence $f(k)\le1+f(k-1)$.

(b) Equivalently, we seek $k$ such that both $2k-1$ and $2k+1$ are good, since $k$ is good if and only if $2k$ is good. In that case $m=f(k)$ is what we need.

Denote by $B\ge2C\ge4D$ the three powers of two in a good number $B+C+D$. Each time we jump from a good number to the next there are three types:

(i) $(B,C,D)\rightarrow(2B,2,1)$ when $B=2C=4D$. The good number increases by $D+3\ge4$.

(ii) $(B,C,D)\rightarrow(B,2C,1)$ when $B>2C=4D$. The good number increases by $D+1\ge2$.

(iii) $(B,C,D)\rightarrow(B,C,2D)$ when $C>2D$. The good number increases by $D\ge1$.

If $2k-1$ and $2k+1$ are consecutive good numbers, then the jump from $2k-1$ to $2k+1$ must be of type (ii) and hence $$2k-1=2^n+3,2k+1=2^n+5$$ where $n\ge2$. Then $k+1=2^{n-1}+3$ and it could be seen that $m=1+\binom{n-1}{2}$ for $n\ge3$. For $n=2$ it could be checked that there is exactly one good number $7$ in $[5,8]$. So $m=1+\binom{n-1}{2}$ is still valid since $\binom{1}{2}=0$.

If they are not consecutive good numbers, then $2k$ is also good. Hence both jumps from $2k-1$ to $2k$ and $2k$ to $2k+1$ are of type (iii), which is impossible because it requires that $2k+1$ is even.

Therefore we have $\boxed{m=1+\binom{\ell}{2},\ell\in\mathbb{N}.}$

IMO 1993 Problem 6

Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps $L_0, \ldots, L_{n-1},$ each of of which is either ON or OFF. Denote $L_{k+n}=L_k$. Initially all lamps are ON. We carry out a sequence of steps. At step $j$ if $L_{j-1}$ is ON then the state of $L_j$ is changed, otherwise do nothing. Show that:

(i) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again,

(ii) If $n=2^k$ then we can take $M(n)=n^2-1$,

(iii) If $n=2^k+1$ then we can take $M(n)=n^2 - n + 1$.

==========================================

(i) Combined with number of steps modulo $n$ there are finitely many states, and the transition function between states is one-one. Hence at some point we return to the initial state where all lamps are ON.

(ii) We use $L_i=1$ and $L_i=0$ to denote the state of lamp $i$ being ON and OFF, respectively. By a round we mean the process of potentially updating $L_0,L_1,\dots,L_{n-1}$. Every round has $n$ steps except for the first, which has $n-1$ steps. We prove these properties inductively

$$P_{n,a}: L_{n-1}=0 \text{ after step }1,2,\dots,n^2-2,$$

$$P_{n,b}:\text{ all lamps are ON after step }n^2-1.$$

$P_{n,b}$ is equivalent to that after round $n-1$ all lamps but the first are OFF. Now with $2n$ lamps, after step $1$ we see that $L_{i}=L_{i+n}$ for $i=0,1,\dots,n-1$, in particular $L_{n-1}=L_{2n-1}=0$. Combining the latter with $P_{n,a}$, we see that after round $n-1$ all lamps but $L_0$ and $L_{n}$ are OFF. After round $n$, the first and second $n$ lamps are all ON and OFF, respectively. It could be seen that in the next $n-1$ rounds all second $n$ lamps are OFF, and after that all lamps but the first are OFF. After the next round, i.e., round $2n$, all lamps are ON again. Clearly $P_{2n,a}$ and $P_{2n,b}$ hold.

(iii) After the first round plus an extra step, $L_0=L_1=0$. Because $P_{n-1,a}$ holds, until all lamps on ON again we see that $L_0=L_1=0$ and $L_2,\dots,L_{n-1},L_0$ behave same as $L_0,L_1,\dots,L_{n-2}$ with $n-1$ lamps. Hence it takes about $n-1$ rounds for all lamps to light up. More precisely, the last step is to update $L_1$ according to $L_0$. Thus $$M(n)=1+n(n-1)=n^2-n+1.$$

IMO 1992 Problem 3

Consider $9$ points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of  $\,n\,$ such that whenever exactly $\,n\,$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

=================================

$n=33$. 

Rephrase as: what is the $9$-vertex simple graph $G$ with most edges that permits a $2$-edge-coloring without a chromatic triangle? 

First, we show that $G$ does not have $33$ edges. If it does, then $G$ has a vertex $v$ of degree $8$.

If $v$ is incident to $4$ red and $4$ blue edges, say edges $vx,vy,vz,vw$ are red. Then $x,y,z,w$ have at least $2$ absent edges, making a total of at least $4$ absent edges.

If $v$ is incident to $3$ red and $5$ blue edges, say $vx,vy,vz$ are red and $vw,va,vb,vc,vd$ are blue. Then $x,y,z$ have at least $1$ edge absent and $w,a,b,c,d$ at least $3$ edges, making a total of at least $4$ absent edges.

If $v$ is incident to $2$ red and $6$ blue edges, let $S:=\{x\in V(G):vx\text{ is blue}\}$. Since $R(3,3)=6$, at least $3$ edges, forming a triangle, are absent in $G[S]$, or else $G[S]$ has a red triangle. Clearly at least one more edge is absent in $G[S]$ or else it still has a red triangle.

Below is a construction showing that $n=33$ is sharp. The idea is to make $v$ incident to $4$ red and $4$ blue edges, say edges $vx,vy,vz,vw$ are red and edges $va,vb,vc,vd$ are blue. Then draw $4$ blue edges among $x,y,z,w$ and $4$ red edges among $a,b,c,d$, and then color edges between $\{x,y,z,w\}$ and $\{a,b,c,d\}$ without making any chromatic triangle.

IMO 1997 Problem 1

In the plane the points with integer coordinates are the vertices of unit squares. The squares are coloured alternately black and white (as on a chessboard). For any pair of positive integers $ m$ and $ n$, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths $ m$ and $ n$, lie along edges of the squares. Let $ S_1$ be the total area of the black part of the triangle and $ S_2$ be the total area of the white part. Let $ f(m,n):=| S_1 - S_2 |$.

a) Calculate $ f(m,n)$ for all positive integers $ m$ and $ n$ which are either both even or both odd.

b) Prove that $ f(m,n) \leq \frac 12 \max \{m,n \}$ for all $ m$ and $ n$.

c) Show that there is no constant $ C\in\mathbb{R}$ such that $ f(m,n) < C$ for all $ m$ and $ n$.

========================

(a) If both $m$ and $n$ are even then $f(m,n)=0$, otherwise $f(m,n)=1/2$. The former follows from symmetry and the latter from $2f(m,n)=1$.

(b) Let $n\le m$ and consider $m$ columns and $n$ rows. The idea is to consider the $2i+1$-th and $2i+2$-th columns as a group. It could be seen that the area difference in each group is at most $1$. Hence if $m$ is even it is obvious. If $m$ is odd, then the total difference from all but the last column is at most $(m-1)/2$, and adding the last column the difference is bounded from above by $$(m-1)/2+1/2=m/2.$$

(c) Consider the right triangle of sides $n$ and $n+1$ where $n$ is even. Within whole squares, whose total area is $n^2/2$, from (a) both colors have the same area. For the rest, whose total area is $n/2$, it could be seen that one color has area $$\left\{\left(\frac{n}{n}\right)^2+\dots+\left(\frac{1}{n}\right)^2\right\}\frac{n}{2(n+1)}=\frac{2n+1}{12}$$ and hence the other color has area $\frac{4n-1}{12}$. Thus $$f(n,n+1)=\frac{n-1}{6},$$ which is unbounded.

IMO 1999 Problem 3

Let $n$ be an even positive integer. We say that two different cells of a $n \times n$ board are neighboring if they have a common side. Find the minimal number of cells on the $n \times n$ board that must be marked so that any cell (marked or not marked) has a marked neighboring cell.

================================

The answer is $n(n+2)/4$. Due to symmetry we show that for half of the board it takes $n(n+2)/8$ marked cells. It is not hard to use induction to see that $n(n+2)/8$ suffices. To see why we couldn't do any better, we tilt the board by 45 degrees and have rows of cells of lengths $$1,3,5,\dots,n-5,n-3,n-1,n-1,n-3,n-5,\dots,5,3,1.$$ We pick $1$ cell from row $1$, $3$ cells from row $3$, etc., and $2$ cells from the last row, $4$ cells from the 3rd last row, etc. such that no two picked cells have common neighbors. The number of picked cells is $$1+2+\dots+\frac{n}{2}=n(n+2)/8,$$so we need to mark at least $n(n+2)/4$ cells just to cover them.

IMO 1993 Problem 3

On an infinite chessboard, a solitaire game is played as follows: at the start, we have $n^2$ pieces occupying a square of side $n.$ The only allowed move is to jump over an occupied square to an unoccupied one, and the piece which has been jumped over is removed. For which $n$ can the game end with only one piece remaining on the board?

===================================

It is only possible when $n$ is not divisible by $3$. In these cases, apply an operation that removes $3$ consecutive pieces. If $n=3k+1$ we can delete the first and last columns and rows to reduce to $n$ to $3k-1$. If $n=3k+2$ then we delete the first two columns and rows to reduce $n$ to $3k-2$.

Suppose that $n$ is divisible by $3$, let $k:=n^2/3$. Color the squares with $1$, $2$, and $3$ so that every $3\times3$ grid has exactly $3$ squares of color $1$, $2$, and $3$. Suppose that we can end the game with only a piece of color $1$. Let $b_{12}$, $b_{13}$, and $b_{23}$ be the total number of jumps that increase the number of pieces of color $3$, $2$, and $1$, respectively. We then have $$b_{12}+b_{13}-b_{23}=k-1,$$ $$b_{23}+b_{13}-b_{12}=k,$$ $$b_{12}+b_{23}-b_{13}=k.$$ We get $b_{12}=b_{13}=k-1/2\notin\mathbb{Z}$, a contradiction.

IMO 1997 Problem 4

An $ n \times n$ matrix whose entries come from the set $ S = \{1, 2, \ldots , 2n - 1\}$ is called a silver matrix if, for each $ i = 1, 2, \ldots , n$, the $ i$-th row and the $ i$-th column together contain all elements of $ S$. Show that:

(a)  there is no silver matrix for $ n =1997$;

(b)  silver matrices exist for infinitely many values of $ n$.

=======================================

(a) Every number in $[2n-1]$ appears exactly $n$ times when we count the $i$-th column and row for every $i\in[n]$. There are at least $2n-1-n=n-1$ numbers not on the main diagonal, and each of them appears exactly $n/2$ times in the matrix. Hence when $n$ is odd no silver matrix exists.

(b) Given an $n\times n$ silver matrix $A_n$, we build an $2n\times2n$ silver matrix $$A_{2n}=\begin{pmatrix}A_n & B \\ C & A_n\end{pmatrix},$$where $B$ and $C$ are $n\times n$ latin squares with entries from $\{2n,2n+1,\dots,3n-1\}$ and $\{3n,3n+1,\dots,4n-1\}$, respectively. Hence, silver matrix exists for every $n$ that is a power of two.

IMO 1994 Problem 6

I feel ambiguity in the problem: whether $k$ should be identical for $m$ and $n$. My solution ends up settles the harder version. By the way, there are tons of other solutions.

Show that there exists a set $ A$ of positive integers with the following property: for any infinite set $ S$ of primes, there exist two positive integers $ m$ in $ A$ and $ n$ not in $ A$, each of which is a product of $ k$ distinct elements of $ S$ for some $ k \geq 2$.

================================

Proof:

For every $i\in\mathbb{N}$ associate the $i$-th prime $p_i$ with the binary representation of $i$. For every positive integer $k\ge2$, include in $A$ all products of $k$ distinct primes such that the sum of their respective $k-1$-th digits is odd. 

Let $S$ contain two primes $p$ and $q$ that differ in their $k$-th digits. Since $S$ is infinite, pick $k$ other primes $q_1,q_2,\dots,q_{k}\in S$. By construction, exactly one of $$pq_1q_2\dots q_{k}$$ and $$qq_1q_2\dots q_{k}$$ is in $A$. 

IMO 1991 Problem 4

Suppose $G$ is a connected graph with $k$ edges. Prove that it is possible to label the edges $1,2,\ldots,k$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to $1$.

=============================

Proof:

We show a stronger result, that every vertex of degree more than $1$ is incident to two consecutive integers except possibly a vertex incident to both $k$ and $1$. If $G$ has a vertex $v_1$ of degree $1$, then we remove the path $(v_1,v_2,\dots,v_m)$ from $G$ to obtain $G'$ where $\deg_G(v_2)=\deg_G(v_3)=\dots=\deg_G(v_m)=2$ and the neighbor of $v_m$ in $G'$ has degree at least $2$ in $G'$. By induction on $k$ we can first label $E(G')$, then label edges $v_1v_2,v_2v_3,\dots$ sequentially.

If every vertex of $G$ has degree at least $2$, then we pair and connect the vertices of odd degrees to obtain $G''$, which has an  Eulerian circuit $C$. We go through trails in $C$ composed of $E(G)$ and label the edges from $1$ to $k$. If a vertex $v$ has odd degree than it is at least $3$, and at least two of the edges incident to $v$ are labeled with consecutive integers.

IMO 1996 Problem 6

Let $ p,q,n$ be three positive integers with $ p + q < n$. Let $ (x_{0},x_{1},\cdots ,x_{n})$ be an $ (n +1)$-tuple of integers satisfying the following conditions :

(a) $ x_{0} = x_{n} = 0$, and 

(b) For each $ i$ with $ 1\leq i\leq n$, either $ x_{i} -x_{i - 1} =p$ or $ x_{i} - x_{i - 1}  = -q$. 

Show that there exist indices $ i < j$ with $ (i,j)\neq (0,n)$, such that $ x_{i} = x_{j}$.

===================

Proof:

We rephrase as follows. $n$ integers are placed on a circle such that when we go clockwise from one number to the next, the difference is either $p$ or $-q$. We want to show that some two integers are equal.

For every arc between two consecutive numbers $x_i$ and $x_{i+1}$, we color it red or blue if $x_{i+1}-x_i$ is $p$ or $-q$, respectively. We go through each of the $n$ windows of $p+q<n$ consecutive arcs. Let window $j$ has $r_j$ red arcs. We see that $$|r_{j+1}-r_j|\le 1,$$ so $r_j=q$ for some $j$, or else the total number of red arcs is not $nq/(p+q)$. Note that $r_j=q$ implies that the two endpoints of these $p+q$ consecutive arcs are associated with the same number.

IMO 1994 Problem 1

Let $ m$ and $ n$ be two positive integers. Let $ a_1$, $ a_2$, $ \ldots$, $ a_m$ be $ m$ different numbers from the set $ \{1, 2,\ldots, n\}$ such that for any two indices $ i$ and $ j$ with $ 1\leq i \leq j \leq m$ and $ a_i +a_j \leq n$, there exists an index $ k$ such that $ a_i + a_j = a_k$. Show that $$\frac {a_1 +a_2+\dots+a_m}{m} \geq \frac {n +1}{2}.$$

=================

Proof:

The orders of $a_1,\dots,a_m$ does not matter, so assume that $a_1<a_2<\dots<a_m$. It suffices to show that for every integer $i\in[(m+1)/2,m]$, we have $$a_i+a_{m+1-i}\ge n+1.$$ If not, then the $i$ distinct numbers $a_1+a_{m+1-i},a_2+a_{m+1-i},\dots,a_i+a_{m+1-i}$, all greater than $a_{m+1-i}$, are all in set $\{a_1,\dots,a_m\}$. The set has only $i-1$ elements greater than $a_{m+1-i}$, a contradiction.