2
$\begingroup$

You have been captured by the devil, but he proposes a game, in which if you win, you may go free. The game is as follows.

• The devil chooses a natural number k and gives you k sheets of paper.

• On every sheet, you are required to write the natural numbers from 1 to $2^k$ inclusive,

and you may write on both sides of the sheet.

• The Devil now arranges the papers side by side, choosing a side for each of them, as they like.

• The Devil wins if he can arrange them in such a way that each of the numbers from 1 to $2^k$ is on the top side of at least one of the sheets, after he has laid them down.

Who has a winning strategy?

If $k=2$, then on page 1 side 1 let us put $(2, 3)$ and on side 2 $(1,4)$. On page 2, side 1 put $(1,3)$ and side 2 $(2,4)$.
I think this works. But can I do this for any $k$?

$\endgroup$
  • $\begingroup$ Anyone any hint? $\endgroup$ – ami_ba Jan 13 '18 at 8:59
  • $\begingroup$ Please reload....I have edited $\endgroup$ – ami_ba Jan 13 '18 at 9:05
2
$\begingroup$

This game becomes much easier if you write numbers in binary form: 1 = 000...0001, 2 = 000...00010, 3 = 000...00011, ..., $2^k$ = 1000...000 (with exactly k zeroes after the 1).

For each sheet of paper, we'll number the sides '0' and '1', for consistency with that binary representation.

For n between 1 and k:

On the n'th sheet of paper, Side Zero gets all the numbers whose binary representation has '0' in the n'th-last place, and Side One gets all the numbers which have '1' in the n'th-last place.

For example, on the first sheet of paper, we write all the even numbers on Side 0, and all the odd numbers on Side 1. On the second, Side 0 has 1, 2, 5, 6, 9, 10, ... and Side 1 has 3, 4, 7, 8, 11, 12, ...

Note that the number $2^k$ has zeroes in all of the last k places, so it will always be on Side Zero.

From there, no matter which way up the Devil puts these sheets, you can always find one of these numbers that's not visible. If the Devil puts page n with Side 0 upwards, then our invisible number has '1' in the n'th-last place; if Side 1 upwards, it has '0' in that place.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.