One red cell, k blue cells, and a pack of 2n cards
Source: 2002 All-Russian MO, Grade 9, Problem 6; Grade 10, Problem 6
January 2, 2012
inductionpigeonhole principlecombinatorics unsolvedcombinatorics
Problem Statement
We are given one red and blue cells, and a pack of cards, enumerated by the numbers from to . Initially, the pack is situated on the red cell and arranged in an arbitrary order. In each move, we are allowed to take the top card from one of the cells and place it either onto the top of another cell on which the number on the top card is greater by , or onto an empty cell. Given , what is the maximal for which it is always possible to move all the cards onto a blue cell?