Game theory problem

Question

Two players $A$ and  $B$ are playing a game. $B$ has $k$ sheets of paper lying next to each other on a table. On each of the sheets, he writes some of the numbers from $1$ to $n$ (he can write no number, or all the numbers). On the back of each sheet, he writes all those integers from $1$ to $n$ that he did not write in the front. Now player $A$ is allowed to flip any number of sheets. If he succeeds in making all the numbers from $1$ to $n$ visible at least once, he wins. Determine the smallest value of $k$ so that $A$ can always win, irrespective of $B$'s actions.

How shall I even begin solving this? I am not getting any idea to do this game theory problem.

I got the question from a friend and he says it's from Netherlands Olympiad, though I didn't get after Googling a bit.. And suppose, $A$ decides opened-eyes, then $n=1$ is the minimum value, right? I am not fully sure though. Can it be proved? And what if he cannot do opened-eye?

I can't form a rigorous solution to the whole problem.

Answer 1

If we let $m$ be the positive integer such that $2^m \leq n < 2^{m+1}$, then $k=m+1.

The proof consists of two steps. Showing that $k>m$ by constructing a set of $m$ sheets that cannot reveal all the numbers $1,\dots,n$ at the same time, and after that by induction that there is a strategy for $A$ such that with $k+1$ sheet this can always be done.

For constructing the $m$ sheets we take the binary representation of the numbers $1,\dots,2^m \leq n$ (with leading zero's if required). On the front side of the $l$th sheet we write all the numbers with a "1" at the $l$th significant digit in its binary representation and the numbers with a "0" will be on the back. The numbers $>2^m$ can be distributed using the same pattern or arbitrarily.

In this way sheet 1 contains $1,3,5,7,\dots,2^m-1$ on the front and $2,4,6,8,\dots,2^m$ on the back. Sheet 2 will have $1,4,5,8,\dots,2^m$ on the front and $2,3,6,7,\dots,2^m-1$ on the back, etc.

If player $A$ has some of the $m$ sheet turned face upwards and some other face downwards, we can write this order as the binary representation $b_mb_{m-1}\dots b_2b_1$ where $b_i$ is 1 it the $i$th sheet is front up and 0 if it is downwards. The number with binary representation $a_ma_{m-1}\dots a_2a_1$ with $a_i = 1 - b_i$, will never be visible (here only zero's will correspond with $2^m$). Note that the numbers $>2^m$ do not play any role and hence the same construction applies to larger values of $n$. It follows that for $n \geq 2^m$ we find a lower limit of cards $m<k$ for a guaranteed winning of $A$.

For the second part of the proof we use the following statement:

• For all $2^m \leq n < 2^{m+1}$ it will be possible for $A$ to win with $k=m+1$ sheets.

I the case $m=0$ this is trivially true, because for $n=1$ one card is all it takes. So suppose it is true for all $m < l$. Consider a game with $2^l \leq n < 2^{l+1}$. A(ny) sheet will contain at least $\lceil\frac{n}{2}\rceil$ of numbers on one side (possibly more). By turning that side up the game changes to a smaller game with $n - \lceil\frac{n}{2}\rceil < 2^{l}$ different numbers for which we know that at most $l$ sheets would be required, and hence we find that the statement is also true for $m=l$ and hence by induction for all $m$.

Answer 2

This answer is partial: I assume $n=2^m$, so that the set of $n$ elements is even, and describe an optimal play from B. For simplicity, denote by $<a,s>$ the set of numbers written on side $s=1,2$ of sheet $a=1, \ldots, k$.

0) By symmetry, we can assume that B writes exactly the same quantity of numbers on either side of each sheet; otherwise, A may pick the most populated side and uncover more numbers. So $|<1,1>| = |<1,2>| = 2^{m-1}$.

1) Given the set $<1,1>$, B splits it into two equally sized subsets with $2^{m-2}$ elements and writes the first subset in $<2,1>$ and the second subset in $<2,2>$. She does the same for $<1,2>$ so that each side of $<2,*>$ contains $2 \cdot 2^{m-2}= 2^{m-1}$ numbers, half of which come from $<1,1>$ and half from $<1,2>$.

2) Moving to the second sheet, she intersects each side of $<1,*>$ with each side of $<2,*>$ and obtains four subsets of size $2^{m-2}$. She splits each of them into two equally sized subsets with $2^{m-3}$ elements and writes one in $<3,1>$ and one in $<3,2>$. Each side of $<3,*>$ contains $2^2 \cdot 2^{m-3}= 2^{m-1}$ numbers, half of which come from each side of $<c,s>$ for $c=1,2$ and $s=1,2$.

$t$) Iterate this reasoning. Moving to sheet $t$, B goes over all the intersections of exactly one side for each $<c,*>$ (where $c=1, \ldots, t-1$) and obtains $2^t$ subsets of size $2^{m-t}$. She splits each of them into two equally sized subsets with $2^{m-t-1}$ elements and writes one in $<t,1>$ and one in $<t,2>$. Each side of $<t,*>$ contains $2^t \cdot 2^{m-t-1}= 2^{m-1}$ numbers, with $2^{m-t}$ coming from each side of $<c,s>$ for $c=1,2, \ldots, t-1$ and $s=1,2$.

This process ensures that B wins, provided that she can find (non-empty) even-sized intersections at stage $t$. Since there are $2^m$ numbers and that the size of the intersection at stage $t$ is $2^{m-t}$, this is possible until $t=m-1$.

Hence, the minimum $k$ required to ensure A's win when $n=2^m$ is $k=m$.