IMO 2013 Problem 6

Let \(n \ge 3\) be an integer, and consider a circle with \(n + 1\) equally spaced points marked on it. Consider all labellings of these points with the numbers \(0, 1, ... , n\) such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels \(a\lt b\lt c\lt d\) with \(a + d = b + c\) the chord joining the points labelled \(a\) and \(d\) does not intersect the chord joining the points labelled \(b\) and \(c\).

Let \(M\) be the number of beautiful labelings, and let N be the number of ordered pairs \((x, y)\) of positive integers such that  \(x + y \le n\) and \(gcd(x, y) = 1\). Prove that \(M = N + 1.\)

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

Proof:

In the proof when necessary we use a sequence starting with \(0\) to represent a labelling.

Terminology:
Since we mainly rely on Mathematical Induction, denote \(S_n\) as the set of beautiful labellings described above. We say \(p\in S_{n-1}\) is extendable if there exists \(q\in S_n\) such that the latter is obtained by inserting \(n\) to the former.

A \(k-\)chord is a chord with end points summing up to \(k\). By saying \(q\) is \(k-\)symmetric we mean all its \(k-\)chords are parallel to each other.

When a beautiful labelling \(p\in S_n\) is \(n-\)symmetric, which we will prove is always the case, its axis is the line perpendicular to all \(n-\) chords in \(p\). Its pole is the intersection of the axis and the circle that has no mark, i.e. \(p\) has \(1\) pole if \(n\) is even and \(2\) otherwise.

We will have two inductions, where all initial conditions are easy to verify and therefore omitted below.

With Induction I we prove the followings.

(1) All beautiful labellings in \(S_n\) are \(n-\)symmetric and therefore have axis.
(2) All beautiful labellings could be extended in either \(1\) or \(2\) ways.

We will use (1p) to denote induction hypothesis of (1), and so on.

Induction I:
We start with some \(p\in S_{n-2}\) with numbers ranging from \(1\) to \(n-1\), and try to insert \(n\) and \(0\). By (2p) there is \(1\) or \(2\) places that we could insert \(n\), which we call \(s_1,s_2\) though \(s_2\) may not exist. If we flip every number \(k\in p\) to \(n-k\) to obtain \(p'\), we are equivalently finding place in \(p\) to insert \(0\), meaning that there is also \(1\) or \(2\) places to put \(0\), i.e. \(s'_1,s'_2\). Because of (1p) and the relation between \(p\) and \(p'\), \(s_i\) and \(s'_i\) are symmetric with respect to the axis of \(p\) for \(1\leq i\leq 2\).

This tells us a lot. We only need to further check \(n-\)chord, because there is no way that \(0+b=n+d\). So the only possible insertions are \(s_i\) together with \(s'_i\) for \(1\leq i\leq 2\) if they exist. Note that inserting \(s_1\) and \(s'_2\) will introduce a new \(n-\)chord that crosses existing ones. This establishes (1) and (2).

Induction II:
We will show that the number of cases where we can extend in \(2\) ways to obtain a beautiful labelling in \(S_n\) is equal to the number of ordered pairs \((x,y)\) such that \(x+y=n\) where \(x\) and \(y\) are positive integers and \(gcd(x,y)=1\).

When there are \(2\) ways to extend:
It happens if and only if we can insert a new number to the pole of \(p\in S_{n-2}\). After adding both \(0\) and \(n\) at the same pole, suppose they are immediately surrounded by \(x\) and \(y=n-x\). We will prove that the necessary and sufficient condition is \(gcd(x,n)=1\). Note that \(gcd(x,n)=1\) if and only if \(gcd(x,y)=1\). Let the sequence be \(0,n,x,\ldots,y\).

If \(gcd(x,n)\neq1\), then \(x\neq1\) and \(x\neq n-1\). Due to number \(1\) and \((n+1)-\)chord, \(x+1\) comes somewhere after \(1\). Similarly \((2x+1 \pmod{n})\) is somewhere after \(x+1\), etc. until we hit \(y+1\) because we will never see any of \(\{0, n, x, y\}\). Now \(\{x, y, x+1, y+1\}\) produce \(2\) crossing \((n-1)-\)chords.

If \(gcd(x,n)=1\), following the same process we get \(0,n,h_1,h_2,\ldots,h_{n-1}\) where \(h_k\equiv kx\pmod{n}\) for \(1\leq k\leq n-1\). We want to show this sequence fully characterized by \(x\) is beautiful.

Clearly \(n-\)chords are all parallel and do not cross, so we can merge \(n\) and \(0\) such that it is \(n\) when considering \(k-\)chord with \(k\gt n\), and \(0\) if \(k\lt n\). Since \(gcd(x,n)=1\), \(x\) has a unique multiplicative inverse modulo \(n\), i.e. \(x'\in [1,n-1]\) such that \(xx'\equiv 1\pmod{n}\). A \(k-\)chord has endpoints \(ix\pmod{n}\) and \(jx\pmod{n}\) such that

\(\left(ix\pmod{n}\right)+\left(jx\pmod{n}\right)=k\), implying

\((i+j)x\equiv k\pmod{n}\), i.e.

\((i+j)\equiv kx'\pmod{n}\)

A \(k-\)chord then corresponds to a \(\left(kx' \pmod{n}\right)-\)chord in labelling \(0,1,2,\ldots,n-1\), which is beautiful.

Q.E.D.

IMO 2005 Problem 6

In a mathematical competition, in which \(6\) problems were posed to the participants, every two of these problems were solved by more than \(\frac 25\) of the contestants. Moreover, no contestant solved all the \(6\) problems. Show that there are at least \(2\) contestants who solved exactly \(5\) problems each.

Radu Gologan and Dan Schwartz

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

The corner case presented below is the main difficulty of the problem. For that I have a near brute force solution, but I also attached a nice and elegant one from somebody else!

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

Proof:

Let's say each problem pair is solved by at least \(\frac 25n+\delta\) contestants where \(\delta\in\{1/5,2/5,3/5,4/5\}\). The number of contestants that solved \(5\) problems is \(x\). Double counting gives us

\({4\choose 2} n+\left({5\choose 2}-{4\choose 2}\right)x\ge {6\choose 2}(\frac 25n+\delta)\), or

\(6n+4x\ge 6n+15\delta\)

If \(\delta\ge 2/5\) then \(x\ge2\) as described.

If \(\delta=1/5\) and \(x=1\), then \(n=5k+2\) and \(14\) of the \(15\) problem pairs are solved by \(2k+1\) contestants; the remaining problem pair is solved by \(2k+2\) contestants. Moreover, one contestant, called winner, solved \(5\) problems and the rest solved \(4\). Everything adds up now but we will show contradiction.

We focus on what happens before the winner solves the \(5\)-th problem. Let the problems be \(A\), \(B\), \(C\), \(D\), \(E\), and \(F\) up to isomorphism. Everybody solves \(4\) problems, and all problem pairs are solved by \(2k+1\) contestants except for

Case \(1\):
\(AB\), \(AC\), and \(AD\) are solved by \(2k\) contestants.

Case \(2\):
\(AB\), \(AC\), \(AD\), and \(AE\) are solved by \(2k\) contestants, and \(AF\) are solved by \(2k+2\) contestants.

Case \(3\):
\(AB\), \(AC\), \(AD\), and \(AE\) are solved by \(2k\) contestants, and \(EF\) are solved by \(2k+2\) contestants.

Case \(4\):
\(AB\), \(AC\), \(AD\), and \(AE\) are solved by \(2k\) contestants, and \(BC\) are solved by \(2k+2\) contestants.

Then we want to reverse the mapping from \(4\)-problem sets solving stats to \(2\)-problem sets solving stats. Both forward and backward relations are expressed by a \(15\times15\) matrix. The forward matrix has exactly \({4\choose 2}=6\) ones per row and column, and the backward matrix is the inverse of the forward one, which is what we want.

It'd sound brute-force to find the inverse matrix, but it takes less than a minute if you know the trick! Due to symmetry, the inverse has only \(3\) distinct entries.

The second column in the table above is the coefficients for \(CDEF\). The bottom row is the constant term in the number of contestants who solve \(CDEF\), since the term related to \(k\) never changes. For each case, we show two columns. Although they look like two different inputs, they're from different permutations on \(\{A,B,C,D,E,F\}\) and are used to show the number of contestants who solve other \(4\)-problem sets such as \(ACEF\).

Finally, the two sums at the bottom for each case that differ by non-integer number concludes our proof, as they show that the number of contestants that solve \(4\)-problem sets cannot be all integers.

Q.E.D.

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

Below is a very nice and elegant proof that I found here showing that it is impossible to have everybody solve exactly \(4\) problems except a winner that solves \(5\), and every problem pair solved by \(2k+1\) contestants except one by \(2k+2\).

Proof:

Consider a graph \(G\) with vertices \(\{A,B,C,D,E,F\}\). The number of edges between any two vertices is the number of contestants who solve both problems.

On one hand, because contestants who solve \(4\) problems do not change any vertex degree modulo \(3\), the winner alone determines the degree of all vertices. Specifically, the \(5\) problems solved by the winner all have degree \(4-3=1\) modulo \(3\), and the last problem has degree \(0\) modulo \(3\).

On the other hand, all edges have multiplicity \(2k+1\) except for one that have multiplicity \(2k+2\), meaning that the \(2\) problems connected by this last edge have different degree from the rest \(4\), contradiction.

Q.E.D.

Linear algebra riddle

Just saw this puzzle from this source. Rephrased in matrix language: elements in a \(n\times(n+1)\) matrix are either \(0\) or \(1\). Every column has at least a \(1\). Show that there are two disjoint column sets such that a row has at least a \(1\) in the first column set if and only if it has at least a \(1\) in the second column set.

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

Proof:

The matrix has no zero column and its columns are linearly dependent, meaning that we can write

\(a_1v_{i_1}+\ldots+a_nv_{i_n}=b_1v_{j_1}+\ldots+b_mv_{j_m}\)

where \(a_*\) and \(b_*\) are positive, and \(\{v_{i_1},\ldots,v_{i_n}\}\) and \(\{v_{j_1},\ldots,v_{j_m}\}\) are disjoint column sets of the matrix. Since all the numbers involved are non-negative, these two sets satisfy the condition described.

IMO 2001 Problem 3

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.

===========

Proof:

Color each of \(21\times 21\) squares such that no column or row has more than \(6\) colors. We shall prove that there is a color appearing in at least \(3\) rows and \(3\) columns.

For each row, mark the squares whose color appears more than twice in the same row. Each row then has at least \(21-2\times 5=11\) marked squares. By double counting some column has at least \(11\) marked squares. If these \(11\) squares have \(5\) colors or less, then at least one of them appears \(3\) times or more in that column. Otherwise these \(11\) squares have \(6\) colors and there is no other color in the column, i.e. one of these colors appears at least \(4\) times in it.

Q.E.D.

IMO 2014 Problem 2

Let \(n \ge 2\) be an integer. Consider an \(n \times n\) chessboard consisting of \(n^2\) unit squares. A configuration of \(n\) rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer \(k\) such that, for each peaceful configuration of \(n\) rooks, there is a \(k \times k\) square which does not contain a rook on any of its \(k^2\) unit squares.

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

Solution:

\(k=\lfloor\sqrt{n-1}\rfloor\).

We will show that all peaceful configurations of \(n\) rooks permit a \(k\times k\) rook-free square if and only if \(k^2\lt n\).

If \(k^2\lt n\), then find \(k\) consecutive columns that contains a rook at the very bottom. These \(n\) rows are then partitioned into \(k\) consecutive groups with each group containing a rook in the bottom row. By pigeonhole principle there is a group with more than \(k\) rows, which therefore permits a \(k\times k\) rook-free square.

If \(k^2\ge n\), let \(n'=k^2\). There is a \(n'\times n'\) peaceful configuration of \(n'\) rooks without \(k\times k\) rook-free square. Truncate it to \(n\times n\), which may not have \(n\) rooks but already denies the desired rook-free square.

IMO 2010 Problem 5

A problem that I refused to get any hint for in the last 8 years! Of course usually I just gave it some thought for a couple of minutes and then moved on, until now...

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

Each of the six boxes \(B_1\), \(B_2\), \(B_3\), \(B_4\), \(B_5\), \(B_6\) initially contains one coin. The following operations are allowed.

Type 1) Choose a non-empty box \(B_j\), \(1\leq j \leq 5\), remove one coin from \(B_j\) and add two coins to \(B_{j+1}\).

Type 2) Choose a non-empty box \(B_k\), \(1\leq k \leq 4\), remove one coin from \(B_k\) and swap the contents (maybe empty) of the boxes \(B_{k+1}\) and \(B_{k+2}\).

Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes \(B_1\), \(B_2\), \(B_3\), \(B_4\), \(B_5\) become empty, while box \(B_6\) contains exactly \(2010^{2010^{2010}}\) coins.

Proposed by Hans Zantema, Netherlands

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

Comment:

Until the day I solved it, I thought the answer is no -- and until the day before I solved it, I thought it's because \(2010^{2010^{2010}}\) is too large. Then I found it's not, so I turned to number theory and invariant to prove it's not possible, as almost certainly the answer to this kind of problem is no in IMO. But not this time! This is why it's a really hard P2/5 problem and played a crucial role in determining competition result in that year.

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

Solution:

Yes, we can obtain the coins as described.

Define \(N=2010^{2010^{2010}}\) and \((a_1,\ldots,a_k,b\}\) as a partial sequence \(a_1,\ldots,a_k\) followed by \(b\) zeros where the last item, \(a_k\) if \(b=0\) or else \(0\), is the number of coins in \(B_6\).

When determining the maximum coins that \(B_6\) can end up with, it is convienient to consider function \(g_k(n)\) defined such that we can convert \((n,k\}\) to \((0,g_k(n),k-1\}\) without involving numbers preceding the partial sequence. In the language of bin and coin, starting with \(n\) coins followed by \(k\) empty bins, we can end up with \(g_k(n)\) coins followed by \(k-1\) empty bins without touching any prior bin.

If \(n=1\), \(g_k(n)=2\); otherwise \(g_k(n)=g_{k-1}^{(n-1)}(2)\). This is because

\((n,k\}\)
\((n-1,2,k-1\}\)
\((n-1,0,g_{k-1}(2),k-2\}\)
\((n-2,g_{k-1}(2),k-1\}\)
\(\vdots\)

And we get \(g_1(n)=2n\), \(g_2(n)=2^n\), and \(g_3(n)=2^{2^{2^{\cdots}}}\) with exactly \(n\) copies of \(2\). How big is \(N\) written in \(g_3(\bullet)\)? Notice \(\log_2^{(n)}g_3(n)=1\), and

\(\log_2{N}\lt11\times2010^{2010}\)
\(\log_2^{(2)}{N}\lt 4+11\times2010\lt 16\times2010\)
\(\log_2^{(3)}{N}\lt 4+11=15\lt16\)
\(\log_2^{(4)}{N}\lt 4\)
\(\log_2^{(5)}{N}\lt 2\)
\(\log_2^{(6)}{N}\lt 1\)

Thus \(N\lt g_3(6)\), and we can obtain the desired result with the following

\((1,1,1,1,1,1)\)
\((3,1,1,1,1)\)
\((2,3,1,1,1)\)
\((2,2,3,1,1)\)
\((2,2,2,3,1)\)
\((2,2,2,0,7)\)
\((2,2,1,7,0)\)
\((2,2,0,9,0)\)
\((2,1,9,0,0)\)
\((2,0,11,0,0)\)
\((1,11,0,0,0)\)
\(\vdots\)
\((1,0,g_3(11),0,0)\)
\(\vdots\)
\((1,0,\frac{N}{4},0,0)\)
\(\vdots\)
\((1,0,0,0,N)\)
\((0,0,0,0,N)\)

IMO 2012 Problem 3 part 1

The second half of the problem is too hard for me to solve.

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

The liar's guessing game is a game played between two players \(A\) and \(B\) The rules of the game depend on two positive integers \(k\) and \(n\) which are known to both players.

At the start of the game \(A\) chooses integers \(x\) and \(N\) with \(1 \le x \le N\). Player \(A\) keeps \(x\) secret, and truthfully tells \(N\) to player \(B\). Player \(B\) now tries to obtain information about \(x\) by asking player \(A\) questions as follows: each question consists of \(B\) specifying an arbitrary set \(S\) of positive integers (possibly one specified in some previous question), and asking \(A\) whether \(x\) belongs to \(S\). Player \(B\) may ask as many questions as he wishes. After each question, player \(A\) must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any \(k+1\) consecutive answers, at least one answer must be truthful.

After \(B\) has asked as many questions as he wants, he must specify a set \(X\) of at most \(n\) positive integers. If \(x\) belongs to \(X\) then \(B\) wins; otherwise, he loses. Prove that:

1. If \(n \ge 2^k,\) then \(B\) can guarantee a win.
2. For all sufficiently large \(k\) there exists an integer \(n \ge (1.99)^k\) such that \(B\) cannot guarantee a win.

Proposed by David Arthur, Canada

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

Solution to part 1:

Formally, the only possible inference that \(B\) could make is: assume \(k+1\) consecutive answers are all lies, then take the negation of the conclusion. This could be used to solve part 2 as well.

When there are more than \(2^k\) candidates, let \(y\) be a fixed member of it. Now \(B\) could ask if \(y=x\). If the answer is yes, assume it's a lie and focus on the rest \(\ge 2^k\) candidates: in the next \(k\) questions binary partition these numbers. \(B\) can then at least eliminate one of them.

If the answer to whether \(y=x\) is no, \(B\) will keep asking the same question until the answer becomes yes. If it doesn't in \(k+1\) rounds then \(B\) can eliminate \(y\).

Q.E.D.

IMO 2005 Problem 2

Let \(a_1,a_2,\ldots\) be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer \(n\) the numbers \(a_1,a_2,\ldots,a_n\) leave \(n\) different remainders upon division by \(n\).

Prove that every integer occurs exactly once in the sequence \(a_1,a_2,\ldots\).

Proof:

We prove by induction that for each \(n\), \(a_1,\ldots,a_n\) are \(n\) consecutive integers after some permutation. Together with infinitely many positive and negative terms in the sequence the desired result follows.

Suppose it holds for \(n\), i.e. the first \(n\) numbers are \(M+1,M+2,\ldots,M+n\) up to permutation. What could \(a_{n+1}\) be? Clearly \(a_{n+1}\equiv M\mod {(n+1)}\). If \(a_{n+1}\) is below \(M\), then with \(M+n\) it has the same remainder when divided by \(n-a_{n+1}\geq n+1\), contradicting the requirement. Similarly \(a_{n+1}\) cannot be greater than \(M+n+1\), so it is either \(M\) or \(M+n+1\), and the first \(n+1\) terms are \(n+1\) consecutive numbers up to permutation.

Q.E.D.

IMO 2018 P4

I was baffled by this for quite a while, although as P4 it's supposed to be pretty simple! Anyways, just like some combinatoric problems it is very hard until you see the trick, which then becomes easy.

This time I conceived the key trick while having routine dental cleaning.

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

A site is any point \((x, y)\) in the plane such that \(x\) and \(y\) are both positive integers less than or equal to 20.

Initially, each of the \(400\) sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to \(\sqrt{5}\). On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest \(K\) such that Amy can ensure that she places at least \(K\) red stones, no matter how Ben places his blue stones.

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

Solution:

\(K=100\).

Amy can always get \(100\) cells. Embed the cells in a \(20\times 20\) checker board. By taking only black cells, she is guaranteed that no two cells taken by her are \(\sqrt{5}\) units apart. There are \(200\) black cells so Amy can always get at least \(100\) of them.

Ben can always prevent Amy from taking more than \(100\) cells. Partition the cells into disjoint \(4\times 4\) blocks, and further partition each block into \(4\) groups as

ABCD
CDAB
BADC
DCBA

Within each group Amy cannot take more than one cell if Ben plays optimally.