IMO 2019 Problem 3

A social network has $2019$ users, some pairs of whom are friends. Whenever user $a$ is friends with user $b$, user $b$ is also friends with user $a$. Events of the following kind may happen repeatedly, one at a time:

Three users $a$, $b$, and $c$ such that $a$ is friends with both $b$ and $c$, but $b$ and $c$ are not friends, change their friendship statuses such that $b$ and $c$ are now friends, but $a$ is no longer friends with $b$, and no longer friends with $c$. All other friendship statuses are unchanged.

Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Proposed by Adrian Beker, Croatia

The official solutions are much more elegant.

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

Proof:

Consider the graph of friendship $G$. Each operation reduces the number of edge by $1$, so it suffices to show that we can go on till the end condition is met without ever creating any isolated clique with more than $2$ vertices. Note that no vertex's degree will ever change parity.

Terminology

Let $C$ and $D$ be the induced subgraphs of $G$ with vertex sets being those with odd and even degrees in $G$, respectively.

An almost-clique is obtained by removing an edge from a clique. By induction it could be proved that within it the end condition is achievable.

We define three types of operation: intra operation applies within $C$ or $D$; cross operation removes an edge from $C$ or $D$, removes one and adds another to between $C$ and $D$; scissor operation removes $2$ edges between $C$ and $D$. Each operation belongs to one of them.

When $G$ has an isolated clique with more than $2$ vertices, it is in dead state because we could not touch that clique anymore.

Remark An isolated clique is either within $C$ or $D$ because of parity of vertex degree.

Algorithm

Initially, $G$ is not in dead state.

While end condition is not met

  If intra operation can be applied

    Do so

  Else if cross operation can be applied

    Do so

  Else

    Apply scissor operation

Scissor operation is never applied, because cross operation is always possible in that situation. Cross operation doesn't cause $G$ to be in dead state, and it creates an almost-clique $X$ in $C$ or $D$. We can then apply intra operation on $X$ until the end condition holds within $X$. Then, we are forced to apply cross operation again, and so on. So we have the following.

Lemma Once a cross operation has been performed, the end goal is achievable.

It remains to show that we can keep $G$ away from dead state before the first cross operation, i.e. there exists a sequence of first consecutive intra operations that do not lead to dead state. Note that each vertex in $D$ initially has degree $1010>1008=|D|-1$, so is connected to $C$. In other words, we only have to make sure no isolated clique with more than $2$ vertices shows up when applying first intra operations to $C$.

We only discuss one case out of three, and the other two are similar. Suppose an intra operation connects vertices $b$ and $c$ and disconnects them from $a$, and we end up with isolated cliques $E$ and $F$, both of even size since they are in $C$. Then we could have produce almost-cliques $E'$ and $F'$, where $a$ and $d$ in $E'$ are disconnected, $b$ and $c$ in $F'$ are disconnected, $a$ connects with $c$, and $b$ connects with $d$. Then by operations inside $E'$ and $F'$ the end goal is achieved for all vertices within.

Q.E.D.

IMO 2018 Problem 3

An anti-Pascal triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it.

Does there exist an anti-Pascal triangle with $k=2018$ rows which contains every integer from $1$ to $N=1 + 2 + 3 + \dots + 2018$?

Proposed by Morteza Saghafian, Iran

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

By the way, this turned out to be a known result. See another solution and a sharper result from Taiwan more than 40 years ago!

Solution:

We show that anti-Pascal triangle with $k\geq 25$ rows doesn't exist.

Proof:

We prove by contradiction. Consider an anti-Pascal triangle $T$.

Terminology

-We number the rows of $T$ such that row $i$ has exactly $i$ numbers.

-A number is small if it is less than or equal to $k$.

-A number is big if it is greater than or equal to $N-k$.

-Numbers $a$ and $b$ are the parent and delta of number $c$, respectively, if $a$ and $b$ are immediately below $c$ and $a=b+c$.

Remark A big number's delta must be small.

Intuition: Smaller numbers spread evenly across the rows of $T$.

Lemma Each row $i$ has exactly one small number $m_i$.

Consider the number in the top row and the chain of deltas as we traverse $T$ from it to parent at each step until arriving at the bottom row. We got $k$ distinct numbers that sum up to no more than $N=1+\ldots+k$, so these deltas must all be small.

Lemma In each row $i$, $m_i$ is right next to $M_i$, the largest number in row $i$. $M_{i-1}+m_i=M_i$. All numbers in $(M_{i-1},M_i)$ are in row $i$ or below.

We attempt to place numbers from bottom to top rows. Suppose $m_i$ and $M_i$ have been placed in row $i$ . Where can $M_i-1$ be if it's not $M_{i-1}$? It has to be right above something larger, which are all in row $i$ or below by induction. If it's in row $i-1$ it must be right above $M_i$, though row $i$ has only one small number so $M_i-1=M_{i-1}$, contradiction. Similarly, all else in $(M_{i-1},M_i)$ couldn't be in row $i-1$ or above.

Intuition: Too many big numbers have to go to bottom rows, leading to contradiction.

Lemma Suppose $N-k$ is in row $k-n$, then $k+1\leq 2n+\lceil\frac{k+1}{2}\rceil$, or $\frac{1}{2}\left(k+1-\lceil\frac{k+1}{2}\rceil\right)\leq n$

The left hand side is the number of big numbers and they all have to be in row $k-n$ or below. The bottom row can have at most $\lceil\frac{k+1}{2}\rceil$ big numbers while each of the $n$ rows right above can have no more than two, because all these big numbers must have a small number as delta right below.

Note that $\frac{1}{2}n(n+1)\leq m_k+m_{k-1}+\ldots+m_{k-n+1}=M_k-M_{k-n}\leq N-(N-k)=k$, which is impossible for $k\geq 25$.

Q.E.D.

IMO 2020 Problem 3

This is the worst combinatorial problem I've seen in IMO. Well, yes I'm biased by my failure to make progress until getting hint, something too advanced and specialized but also makes the problem very simple once you get it. There doesn't seem to be any other approach to it. Moreover rumor has it that some students were able to draw inspiration from here.

Problem:

There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n.$ Each pebble is colored in one of $n$ colors and there are four pebbles of each color. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied:

-The total weights of both piles are the same.

-Each pile contains two pebbles of each color. 

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

Proof:

The strategy is to pair $k$ with $4n+1-k$. In a graph $G$ with $n$ vertices each representing a color, two colors $a$ and $b$ have a connecting edge for every pair of pebbles of colors $a$ and $b$ that sum up to $4n+1$. Note that multiple edges can exist between a pair of colors or even a self loop. So $G$ is $4$-regular and therefore has a $2$-factorization, and the partitioning follows immediately which clearly satisfies all conditions.

Q.E.D.

IMO 2020 Problem 4

There is an integer $n > 1$. There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies.  

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

Solution:

Represent a cable car by a tuple $(a, b)$ where $0\leq a\lt b\leq n^2-1$.

First, we show that with $k=n^2-n+1$, companies $A$ and $B$ will both link a common pair of stations. Consider only company $A$'s cable cars. There will be at least $2(n^2-n+1)-n^2=n^2-2n+2$ stations that is both a starting point and an end point, because no two cable cars could start or end at the same station. Thus there are at most $2n-2$ stations that are only a starting or end point but not both, which we call singleton station. We group cable cars into chains. A chain is a sequence of connecting cable cars, i.e. $(a_1,b_1), (a_2,b_2),\ldots$ where $b_i=a_{i+1}$ for all $i$. Each chain has exactly $2$ singleton stations, so there are at most $n-1$ chains, and thus the longest chain must have at least $n+1$ cable cars. However every cable car connects two stations no more than $n-1$ intervals apart, as otherwise the company will have at most $n^2-(n+1)+1=n^2-n\lt k$ cable cars. So the longest chain has only one possibility: sequence $(m(n-1), (m+1)(n-1))$ for $0\leq m\leq n$. Since it applies to any company, the statement holds.

Then, we show that for $k=n^2-n$ companies $A$ and $B$ could have no common pair of linked stations. Let $A$ be $(i, i+n)$ for $0\leq i\leq n^2-n-1$, i.e. all stations $n$ intervals apart. Let $B$ be $(i,i+n-1)$ for $0\leq i\leq n^2-2n$ and $(j,j+1)$ for $n^2-n\leq j\leq n^2-2$. We could verify that the pairs of stations linked by companies $A$ and $B$ are indeed disjoint.

USOMO 2020 Problem 2

An empty $2020 \times 2020 \times 2020$ cube is given, and a $2020 \times 2020$ grid of square unit cells is drawn  on each of its six faces. A beam is a $1 \times 1 \times 2020$ rectangular prism. Several beams are placed inside the cube subject to the following conditions:

-- The two $1 \times 1$ faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence, there are $3 \cdot {2020}^2$ possible positions for a beam.)
-- No two beams have intersecting interiors.
-- The interiors of each of the four $1 \times 2020$ faces of each beam touch either a face of the cube or the interior of the face of another beam.

What is the smallest positive number of beams that can be placed to satisfy these conditions?

This one is easy!

Solution:

We prove it's $3n/2$ for every even $n$, i.e. $3030$ for $n=2020$, followed by construction.

Let $S$ be the set of minimum number of beams. Define a layer as a set of horizontally or vertically adjacent $n^2$ unit cubes. There are $3n$ layers. Consider the $n$ horizontal layers. Either each of them contains a beam in $S$, or none of them does and $S$ consists of $n^2$ vertical beams.

If nothing like the latter case happens in any direction, then each of the $3n$ layers contains a beam in $S$. Every beam is contained in exactly $2$ layers, so $S$ has at least $3n/2$ beams. It could be easily constructed. If the latter case happens in some direction, then $S$ has $n^2$ beams, more than $3n/2$ and so not the minimum.

APMO 2020 Problem 3

Determine all positive integers $k$ for which there exist a positive integer $m$ and a set $S$ of positive integers such that any integer $n > m$ can be written as a sum of distinct elements of $S$ in exactly $k$ ways.

I was totally screwed by a mistake and thought $k=1$. My excuse is that I didn't have a chance to sit down and think about it seriously. So below are just my proof after knowing that $k$ can only be power of two.



We say a number is good if it could be written as the sum of distinct elements of $S$ in exactly $k$ ways.

Let $s_1 \lt s_2 \lt \ldots \lt \ldots$ denote the good numbers in $S$. Let $S_1 \lt S_2 \lt \ldots \lt \ldots$ constitute $S$.

Lemma 1
There does not exist number $x+S_j=S_i+S_k\gt m$ where $x\lt S_j$, $x\notin\{S_i,S_k\}$, and $x$ is good.
Proof
If it does, then $x+S_j$ has at least $k+1$ representations, a contradiction.
$\square$

Lemma 2
For sufficiently large $i$, $2s_i\leq s_{i+1}$.
Proof
If not, let $x=s_{i+1}-s_i \lt s_i$. If $x \gt m$ then $x$ is good and $s_{i+1}$ has at least $k+1$ representations, a contradiction. If $x\leq m$, then given $s_i$ is sufficiently large we can find $S_a \lt y \lt s_i \lt s_{i+1}$ such that $y$ is good and $y+s_i=S_a+s_{i+1}$ which contradicts Lemma 1.
$\square$

With this, let $a=s_i\gt m$ where $2s_j\leq s_{j+1}$ for any $j\ge i$. Let $S'=\{x: x\lt a, x\in S\}$ and $t$ be the sum of elements in $S'$.

Lemma 3 
$t\leq a+m$
Proof
Note that $a+m$ is less than the next element in $S$ after $a$. If $a+m\lt t$, then $t$ has at least $k+1$ representations where $k$ of them come from representations of $t-a$ and an extra from $S'$, a contradiction.
$\square$

Lemma 4
$k$ is a power of two.
Proof
Double count representations using only $S'$. Define $f(n)$ as the number of representations using $S$. For $x\in[0, a-1]$, $f(x)$ completely comes from $S'$. For $x\in[a, a+m]$, $f(x)-f(x-a)$ counts representations using only $S'$. So the quantity

$$
f(0)+f(1)+\ldots+f(a-1)+\left(f(a)-f(0)\right)+\left(f(a+1)-f(1)\right)+\ldots+\left(f(a+m)-f(m)\right),
$$

reduced to $f(m+1)+\ldots+f(a+m)=ak$, is equal to $2^{|S'|}$, therefore $k$ must be a power of two.

$\square$

Finally, for any $k=2^{k'}$, the desired $S$ could be $S=\{3^0,3^1,\ldots,3^{k'}\}\cup\{2^0,2^1,\ldots\}$.

Task scheduler

Source

You have a bunch of tasks to be executed on a single thread. Each is of a certain type in $\{1,2,\ldots,n\}$ and each takes exactly one second to finish. Tasks of the same type must be executed at least $k$ seconds apart. How long does it take to finish them all?

The greedy algorithm works naturally: at each second run the type with most remaining tasks that are allowed to be executed. However you don't necessarily need to produce execution order if only the total run time is asked. Can we find out the total idle seconds? It turns out to be simple.

Order the types by task count $a_1\leq a_2\leq \ldots \leq a_n$. There are at least $a_n-1$ chunks of $k-1$ or more seconds between execution of task $n$. Consider
$$
S=\sum_{i < n}\min\left(a_n-1, a_i\right).
$$

These are the tasks that we hope to squeeze in those $(a_n-1)(k-1)$ seconds. Apparently if
$$
S<(a_n-1)(k-1)
$$
then there will be at least $(a_n-1)(k-1)-S$ idle seconds, and not hard to see how to achieve exactly that.

Interestingly, TONCAS -- The Necessary Condition is Also Sufficient! If $S\geq (a_n-1)(k-1)$ then there will be no idle seconds. It could be proved by induction.

Sum of squares <= Sum of cubes

Source: http://ruffnsluff.blogspot.com/2020/04/sum-of-squares-sum-of-cubes.html

Suppose $x, y, z>0$ and $xyz=1$. Show that $x^3+y^3+z^3\ge x^2+y^2+z^2$.

My solution is far from elegant.

Proof:

We try to show $f\left(x,y,z\right)=x^3+y^3+z^3-x^2-y^2-z^2\geq 0$. By fixing one variable and taking partial derivative to zero, a necessary condition for such $\left(x,y,z\right)$ is that

$$
3x^3-2x^2=3y^3-2y^2=3z^3-2z^2.
$$

There are three cases.

(i) $x,y,z$ are distinct. Then they are roots of polynomial $3p^3-2p^2-3=0$. It is not hard to find out the corresponding $f\left(x,y,z\right)$, which is positive so not the minimum $0$ we want to show.

(ii) $x=y=z=1$. Trivial.

(iii) $x=y\neq z$. Setting partial derivative to zero gives us

$$
3x^9-2x^8+2x^2-3=0,
$$

which has only one real root $x=1$, i.e. $x=y=z=1$.

Q. E. D.

USAMO 2012 Problem 2

A circle is divided into $432$ congruent arcs by $432$ points.  The points are colored in four colors such that some $108$ points are colored Red, some $108$ points are colored Green, some $108$ points are colored Blue, and the remaining $108$ points are colored Yellow.  Prove that one can choose three points of each color in such a way that the four triangles formed by the chosen points of the same color are congruent.

Hints I got (select the whole line to see): rotation, pigeonhole principle, quadruple

Proof:

Consider quadruples ordered clockwise in RGBY, there are $431\times 430\times 429$ possible shapes. There are also a total of $108^4$ ordered RGBY quadruples. If any shape has at least $3$ instances then we are done. However, $\frac{108^4}{431\times 430\times 429}$ is between $1$ and $2$, so the argument doesn't seem to work. Now what?

Interestingly, it does if we are greedier.

First, consider ordered RG arcs. There are $108^2$ of them and $431$ possible lengths, so at least $\lceil \frac{108^2}{431}\rceil=28$ ordered RG arcs have the same length.

Next, consider ordered RGB triangles extended from these $28$ or more ordered RG arcs, there are $28\times 108$ with at most $430$ shapes, so we get at least $\lceil \frac{28\times 108}{430}\rceil=8$ ordered RGB triangles of the same shape.

Finally, we have at least $8\times 108$ ordered RGBY quadruples extended from these $8$ or more ordered RGB triangles falling into at most $429$ shapes, so some shape would have at least $\lceil \frac{8\times 108}{429} \rceil=3$ instances.

Q.E.D.

Note that ceiling operation in each step is essential. Moreover, it proves a stronger result, that the congruent triangles have the same orientation.

Cauchy-Davenport Theorem

Cauchy-Davenport Theorem says that given a prime $p$ and non-empty subsets $A$ and $B$ of $\mathbb{Z}_p$, the minimum possible size of $A+B\equiv\{c|a+b=c,a\in A, b\in B\}\subset\mathbb{Z}_p$ is $\min\{p, |A|+|B|-1\}$.

I learned a few interesting things.

1. For $|A|+|B|>p$, this implies every number in $\mathbb{Z}_p$ is in $A+B$, which does not rely on $p$ being a prime. This is because every number $c$ can be written as $c=a+b$ in exactly $p$ ways, so at least one $\left(a,b\right)$ is covered, i.e., $a\in A$ and $b\in B$. Hence the theorem is only non-trivial when $|A|+|B|\leq p$.

2. A quick proof uses Combinatorial Nullstellensatz. Consider  a polynomial $f(x,y)=\prod_{i=1}^{|A|+|B|-2}(x+y-c_i)\in\mathbb{Z}_p(x,y)$ where all $c_i$ are distinct. It has a highest-degree term $x^{|A|-1}y^{|B|-1}$, so there is $(x,y)\in A\times B$ such that $f(x,y)\ne 0$.

3. It leads to another result: given $t$ elements in $\mathbb{Z}_p$ which are not necessarily distinct, they have at least $\min\{p, t+1\}$ distinct partial sums: grab $t_1$ elements that produce at least $t_1+1$ partial sums including $0$, which is always possible when $t_1=1$. Similarly grab another $t_2$ elements. Applying the theorem on them yields a set of $t_1+t_2$ elements with at least $t_1+t_2+1$ partial sums. Keep doing it until all $t$ elements have been enumerated or bound $p$ has been hit.

4. Finally, here is the ingenious proof of Cauchy-Davenport Theorem with minimum algebra found here.

Proof:
Consider the following two operations that do not change $|A|+|B|$ and do not increase $|A+B|$.

(i) rotate $A$ and $B$ by replacing each element $a\in A$ and $b\in B$ with $a+r_A$ and $b+r_B$, respectively.

(ii) whenever $A$ and $B$ overlap, replace them with $A\cup B$ and $A\cap B$.

When $A$ and $B$ are disjoint, do (i) until they overlap.

When $|A\cap B|>1$, do (ii) to get $A'\subset B'$ and then rotate $A'$ so that it has fewer but non-zero overlap with $B'$. If it is impossible, then every rotation of $A'$ either has $0$ or $|A'|$ overlap with $|B'|$, and eventually $|B'|=p$ is implied because $p$ is prime and $|A'|>1$.

After finite operations we have $|A\cap B|=1$. We rotate both so that they overlap at $0$ only and we are done.

$\diamond$

Combinatorial Nullstellensatz

A powerful algebraic tool in combinatorics. Proof below could be found elsewhere.

We say a polynomial $f$ in $n$ variables $x_1,\dots,x_n$ over field $F$ has a leading term $x_1^{d_1}\dots x_n^{d_n}$ if $[x_1^{d_1}\dots x_n^{d_n}]f\ne0$ and $\deg f=d_1+\dots+d_n$.

Combinatorial Nullstellensatz

If $f$ has a leading term $x_1^{d_1}\dots x_n^{d_n}$ and

for every $i\in[n]$, $S_i\subseteq F$ has size $d_i+1$, then there exists $$t=(t_1,\ldots,t_n)\in S\equiv\prod_{i\in[n]}S_i$$ s.t. $f(t)\ne0$.

Proof:

Suppose that $f(t)=0,\forall t\in S$. We prove by induction on $n$ that $x_1^{d_1}\dots x_n^{d_n}$ is not a leading term of $f$. 

For $n=1$ this is trivial. For $n>1$, we write $$f(x_1,\ldots,x_n)=g_1(x_1,\ldots,x_n)\prod_{s_{1,i}\in S_1}(x_1-s_{1,i})+p_{d_1}(x_2,\ldots,x_n)x_1^{d_1}+\ldots+p_1(x_2,\ldots,x_n)x_1+p_0(x_2,\ldots,x_n).$$

The second part of $f$ vanishes for $d_1+1$ distinct values of $x_1$ while $x_2,\dots,x_n$ are fixed, so $p_{d_1}$, and others that are not importnat, are $0$ for every $$(x_2,\dots,x_n)\in\prod_{2\le i\le n}S_i.$$

By inductive hypothesis, $x_2^{d_2}\dots x_n^{d_n}$ is not a leading term of $p_{d_1}$ and:

(i) If $\deg p_{d_1}>d_2+\dots+d_n$, then $\deg f>d_1+\dots+d_n.$

(ii) If $[x_2^{d_2}\dots x_n^{d_n}]p_{d_1}=0$, then $x_1^{d_1}\dots x_n^{d_n}$ can only come from the first part of $f$, which meanwhile also provides a nonzero term $x_1^{d_1+1}x_2^{d_2}\dots x_n^{d_n}$ not to be eliminated anywhere in $f$.

In any case, $f$ does not have a leading term $x_1^{d_1}\dots x_n^{d_n}$.