Game of writing numbers from 1 to n on k pages
Source: Dutch BxMO/EGMO Team Selection Test 2014 P5
July 17, 2014
ceiling functionlogarithmscombinatorics proposedcombinatoricsgreedy algorithm
Problem Statement
Let be a positive integer. Daniel and Merlijn are playing a game. Daniel
has sheets of paper lying next to each other on a table, where is a
positive integer. On each of the sheets, he writes some of the numbers
from up to (he is allowed to write no number at all, or all numbers).
On the back of each of the sheets, he writes down the remaining numbers.
Once Daniel is finished, Merlijn can flip some of the sheets of paper (he is
allowed to flip no sheet at all, or all sheets). If Merlijn succeeds in making
all of the numbers from up to n visible at least once, then he wins.
Determine the smallest for which Merlijn can always win, regardless of
Daniel’s actions.