Given a positive integer n and a game board consisting of n+1 square fields arranged next to each other, numbered from left to right from 0 to n. At the beginning of the game there are n game pieces on field no. 0 and the other fields are empty.
A patient player now chooses, for each move, a field with k=0 pieces and moves one of them at most k fields to the right. In doing so, the piece must remain on the game board. His goal is to bring all n pieces to field no. n by means of a sequence of such moves.
Prove that the player cannot achieve this goal with fewer than ⌈1n⌉+⌈2n⌉+⌈3n⌉+…+⌈nn⌉ moves. (Here ⌈x⌉ denotes the smallest integer not smaller than x.)
Solution
Solution:
The game pieces are indistinguishable and all have the same starting field and the same target field. Therefore, the patient player can devise a rule that tells him which of the pieces on the field he has selected he should move.
One possible rule is obtained by numbering the pieces fixedly from 1 to n and, in each move, after selecting the field, moving the piece with the highest number located there.
Suppose that in this way he moves the piece with number k (1≤k≤n) to the right. Then the field selected for this cannot have had more than k pieces on it, because their numbers are at most equal to k. Hence piece k is moved at most k fields to the right in each such move. But since it is moved a total of exactly n fields, at least ⌈kn⌉ moves are required for this. This holds for all k with 1≤k≤n. Summing over k yields the minimum number of moves required as stated in the problem. □
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: MathNet,
licensed CC-BY-4.0.
Statement translated into English from de; metadata (topic, difficulty) added by this project.