Competition problem — Combinatorics

Library / /416 of 520

Combinatorics Difficulty 7.0 National olympiad, round 2 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$ .)

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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