Interesting number theoretical game

Question

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$?

Answer 1

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.