IMO 2017 Problem 5

I didn't solve this one. It's very easy to get wrong with this problem: I did it once in 2017 and thought I solved it, then read the solution to find out I didn't. Now that I already forget the solution, same thing happens again!

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

For any positive integer $N$, you are given $N(N+1)$ distinct numbers in a row. Prove that we can always remove $N(N-1)$ of them so that among the remaining $2N$ numbers, the largest and the second largest are adjacent, the third largest and the fourth largest are adjacent, and so on.

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

Proof:

Divide the numbers into $N$ blocks of $N+1$ numbers. In round $i=0,1,\ldots,N-1$ the following happens.

Initially we have $N-i$ blocks of $N+1-i$ numbers. We then sequentially pick out the largest among them until two numbers from the same block is picked. This is guaranteed to happen before we pick the $(N+2-i)$-th number because there are only $N-i$ blocks.

The two picked numbers from the same block go into a pool $P$ that will eventually consist of the $2N$ numbers asked for. The rest of that block is discarded, so are all other picked numbers. Finally, for any block that hasn't been touched in this round, discard a random number. This concludes round $i$.

Clearly before round $i+1$, we have $N-i-1$ blocks of $N-i$ numbers. Moreover by the end of round $N-1$, pool $P$ has the $2N$ numbers satisfying the desired properties.

Q.E.D.

Geometry puzzle with differential equation

A geometry puzzle goes like this: at time $t=0$ point $A$ is at the origin $(0,0)$ and point $B$ is at $(0,1)$. At time $t=1$, $A$ starts to move to the right with velocity $1$, and $B$ starts to move toward $A$ with the same velocity. What will be the distance between them when $t$ goes to infinity?

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

Perhaps it is solvable by differential equation, but that's not the point. There are at least two interesting solutions that doesn't involve differential equation, although they're arguably the same solution.

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

My solution:

We describe everything from $A$'s perspective.

A stays at $(0,0)$ forever, while $B$ starts from $(0,1)$ and has velocity vector $(-1,0)+\alpha(-x,-y)$ when it is at $(x,y)$. $\alpha$ is a positive number such that the second terms has length $1$, i.e. $B$'s velocity vector bisects vectors $(-1,0)$ and $(-x,-y)$.

Recall parabola can be defined as a curve consisting of points with equal distance to a fixed point, focus, and a line, directrix. Moreover the tangent line of any point on parabola bisects the rays from the point to the focus and directrix.

So, taking initial condition into account, $B$ is on the parabola with focus $(0,0)$ and directrix $x+1=0$. It moves downward and leftward and approaches $(-0.5,0)$ as time goes to infinity.

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

An even more interesting solution, not by me, requires no knowledge of parabola:

By analyzing $B$'s velocity vector also from $A$'s perspective, the amount that $B$ has moved to the left equals what it has moved toward $A$. So at $t=\infty$, suppose it's at $(-k,0)$ with $k>0$. Then $k=1-k$, i.e. $k=0.5$.

Two combinatorial identities about non-empty partition

Let \(P_n\) be the set of all integer partitions of \(n\), i.e. each \(p\in P_n\) is represented by a non-increasing integer sequence that sums up to \(n\). For example, \(P_4=\{(4), (3,1), (2,2), (2,1,1), (1,1,1,1)\}\). For simplicity to represent \(p\) we use an alternative sequence \(\{d^p_i\}\) where \(d^p_i\) is the number of times \(i\) appears in \(p\), i.e. \(\sum_{i>0} id^p_i=n\). Define \(l_p=\sum_{i>0}d^p_i\) to be the length of sequence \(p\).

The first identity is easy:
$$
\sum_{p\in P_n}\binom{l_p}{d^p_1,d^p_2,\ldots}=2^{n-1}
$$
The left hand side is the number of ordered partitioning of sequence \((1,2,\ldots,n)\). Since there are \(n-1\) boundaries it evaluates to the right hand side.

The second identity is
$$
\sum_{p\in P_n}\frac{n}{l_p}\binom{l_p}{d^p_1,d^p_2,\ldots}=2^n-1
$$

How do we interpret the left hand side and prove the identity combinatorially? It took me some time to come up with the idea.

Proof:

For each permutation \(p'\) of some \(p\in P_n\) consider both \(l_p\) blocks in \(p'\) and sequence \((1,2,\ldots,n)\), both in its own cycle. We count the ways of aligning these two cycles. We compute the required scaling factor for term \(\binom{l_p}{d^p_1,d^p_2,\ldots}\).

Let \(p'\) consist of \(k>0\) identical segments, e.g. \(k=2\) for \(p'=(4,3,2,4,4,3,2,4)\). Before applying scaling factor we count it \(\frac{l_p}{k}\) times,  and there are \(\frac{n}{k}\) ways to align it with \((1,2,\ldots,n)\), so the scaling factor is \(\frac{\frac{n}{k}}{\frac{l_p}{k}}=\frac{n}{l_p}\).

What do all these sum up to? Almost same as the ordered partitioning of \((1,2,\ldots,n)\) in the first identity, except the boundary between \(1\) and \(n\) may or may not align with a block boundary in \(p'\). So there are \(2^n\) possibilities with one of them invalid: when there is only \(1\) block, i.e. \(p=p'=(n)\), it can't be that none of the \(n\) boundaries in \((1,2,\ldots,n)\) aligns with any block boundary. Therefore the left hand side equals \(2^n-1\).

Q.E.D.