Track / Stage 7 / 15 of 300 #1415 of 1964

Problem 1415

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it

Given is a positive integer $n$ and a game board consisting of $n+1$ square fields arranged side by side, numbered from 0 to $n$ from left to right. At the beginning of the game, $n$ game pieces are located on field No. 0, and the other fields are empty.
A patient player now chooses for each move a field with $k \neq 0$ pieces and moves one of them at most $k$ fields to the right. The piece must remain on the board. His goal is to move all $n$ pieces to field No. $n$ with a sequence of such moves.
Prove that the player cannot achieve this goal in fewer than $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$ moves. (Here, $\lceil x\rceil$ denotes the smallest integer not less than $x$ .)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

The game pieces are indistinguishable and all have the same starting and target field. Therefore, a patient player can invent a rule that tells him which of the pieces on the selected field he should move.
A possible rule is obtained by firmly numbering the pieces from 1 to $n$ and in each move, after selecting the field, moving the piece with the highest number there.
Assume he moves the piece with the number $k(1 \leq k \leq n)$ to the right in this way. Then there cannot have been more than $k$ pieces on the selected field, because their numbers are at most equal to $k$ . Thus, piece $k$ is moved at most $k$ fields to the right each time. Since it is moved a total of exactly $n$ fields, at least $\left\lceil\frac{n}{k}\right\rceil$ moves are required. This holds for all $k$ with $1 \leq k \leq n$ . Summing over $k$ yields the minimum number of required game moves according to the problem statement. $\square$

Hint: A proof by complete induction is just as doomed to fail as considerations of seemingly "optimal" strategies whose optimality can only be locally convincingly justified.
It can be shown that the exact value of the given term can only be achieved for $n=1,2,3,4,5,7$ .

## Solutions to the 2nd Selection Test 2018/2019

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.