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$. Once Daniel is done, Merlijn may flip some of the sheets to show the back (he can 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 will show that Merlijn can win if and only if $2^{k}>n$. The smallest $k$ for which Merlijn wins is thus the smallest $k$ with $2^{k}>n$.
Suppose that $2^{k}>n$. Merlijn chooses one by one for each sheet whether to flip it or not. For the first sheet, he places the side with the most numbers on top (so at least half of the numbers from 1 to $n$). For each subsequent sheet, he places the side with as many numbers as possible that he has not yet made visible on earlier sheets. Let $b_{j}$ be the number of numbers that are still not visible on sheets 1 to $j$ after Merlijn has made his choices for these sheets. Then $b_{1} \leq \frac{1}{2} n$ and $b_{j} \leq \frac{1}{2} b_{j-1}$ for $j \geq 2$. Thus, $b_{j} \leq \left(\frac{1}{2}\right)^{j} n$ and in particular $b_{k} \leq \left(\frac{1}{2}\right)^{k} n$. Since $2^{k}>n$, it follows that $\left(\frac{1}{2}\right)^{k} n<1$, so $b_{k}<1$. Since $b_{k}$ must be an integer, $b_{k}=0$. Therefore, after Merlijn's choice for all $k$ sheets, there are no numbers left that are not visible.
Now we prove that for $2^{k} \leq n$ Daniël can ensure that Merlijn cannot win. We do this by induction on $k$. For $k=1$, we have $n \geq 2$. Daniël writes the number 1 on one side of the sheet and all other numbers (there is at least one) on the other side. Merlijn cannot now turn this sheet in such a way that he can win. This is the base case of the induction. Now let $k \geq 1$ and assume that Daniël can describe $k$ sheets with $n \geq 2^{k}$ numbers such that Merlijn cannot win. We now consider $k+1$ sheets. Describe the first $k$ sheets in such a way with the numbers 1 to $2^{k}$ that Merlijn cannot win with only these numbers; this is possible according to the induction hypothesis. Then write the same numbers on each sheet again, but increased by $2^{k}$, so that these numbers run from $2^{k}+1$ to $2^{k+1}$. Finally, write all numbers $m$ with $2^{k+1}<m \leq n$ on the back of each sheet. Now each of these $k$ sheets contains the numbers 1 to $n$. On sheet number $k+1$, write the numbers 1 to $2^{k}$ on the front and the numbers $2^{k}+1$ to $n$ on the back. Suppose Merlijn leaves the last sheet with the front side up. Then he must at least make the numbers $2^{k}+1$ to $2^{k+1}$ visible on the first $k$ sheets, but this is not possible according to the induction hypothesis. Suppose Merlijn lays the last sheet with the back side up. Then he must make the numbers 1 to $2^{k}$ visible on the first $k$ sheets, but this is also not possible according to the induction hypothesis. Merlijn can therefore not win with these sheets. This completes the proof.