K1) Anaëlle has $2 n$ pieces, which are labeled $1,2,3, \ldots, 2 n$, as well as a red and a blue box. She now wants to distribute all $2 n$ pieces into the two boxes so that the pieces $k$ and $2 k$ end up in different boxes for each $k=1,2, \ldots, n$. How many ways does Anaëlle have to do this?

Answer: Anaëlle has $2^{n}$ possibilities.
Solution 1 (bijective): For every odd integer $1 \leq t<2 n$, call the set of all bricks whose labeling has the form $t \cdot 2^{k}$ the chain starting at $t$. As soon as we place a brick from a chain into a box, the box of all other bricks in this chain is uniquely determined due to the condition Since $t$ is odd, we also have that pieces in different chains can be placed independently of each other, since the condition only affects pairs of pieces that are in the same chain.

Since each tile is also in exactly one chain, it now follows that each permitted distribution of tiles has a corresponding arbitrary distribution of one representative per chain. (e.g. all tiles with odd labels). Because we have $n$ chains, the total number of possibilities is therefore $2^{n}$.