MathDB
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 k>1k>1 blue cells, and a pack of 2n2n cards, enumerated by the numbers from 11 to 2n2n. 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 11, or onto an empty cell. Given kk, what is the maximal nn for which it is always possible to move all the cards onto a blue cell?