Let $n$ be a positive integer. Daniel and Merlijn are playing a game. Daniel has $k$ sheets of paper lying next to each other on the table, where $k$ is a positive integer. He writes a number from 1 to $n$ on each sheet (no number is allowed, all numbers are allowed too). On the back of each sheet, he writes exactly the remaining numbers from 1 to $n$. When Daniel is done, Merlijn may flip some of the sheets to show the back (he may also choose not to flip any or to flip all of them). If he can make all the numbers from 1 to $n$ visible at the same time (where duplicates are allowed), he wins.
Determine the smallest $k$ for which Merlijn can always win, regardless of what Daniel does.
We give all of Daniel's sheets of paper a different color. Furthermore, we have $n$ boxes with the numbers 1 to $n$ on them. We also provide enough tokens in exactly the colors of Daniel's sheets of paper. For each sheet, he looks at the numbers on the front of the sheet and puts a token of the color of this sheet in each of those boxes. Each box then contains the tokens in the colors of the sheets of paper on which that number is on the front, and precisely not the tokens in the colors of the sheets of paper on which that number is on the back.
If Merlin has laid the sheets of paper he desires with the back side up, he picks from the supply exactly the tokens in the colors of those sheets. A number is not visible on the table precisely if the sheets on which this number is on the front are the sheets that Merlin has turned over, or in other words, precisely if the set of tokens in his hand is equal to the set of tokens in the box of this number. Merlin wins then and only then if the set of tokens in his hand does not occur in any of the boxes, because then all numbers are visible. We claim now that Merlin can win if and only if $2^{k}>n$. The smallest $k$ for which Merlin wins is thus the smallest $k$ with $2^{k}>n$.
Assume that $2^{k}>n$. The number of possible sets of colors is $2^{k}$ and therefore greater than $n$. There are $n$ boxes, so not all sets of colors can be exactly the colors of tokens in a box. Merlin can thus choose a set of colors that does not occur in a box and lay the sheets of those colors with the back side up. Then he wins. Now assume that $2^{k} \leq n$. Daniel first fills the boxes with sets of tokens so that every possible set occurs in a box. This is possible because the number of possible sets is $2^{k}$ and we have at least $2^{k}$ boxes. Now Daniel writes on each colored sheet of paper on the front exactly the numbers of the boxes that contain a token of the correct color, and on the back the rest. In this way, the tokens in the boxes again correspond exactly to the numbers on the front of the sheets. No matter which set of colors Merlin chooses, there is always a box with exactly that set of colors. Merlin can therefore not win.