3. Let $N=400$. What is the maximum number of balls that the magician can guarantee are not in their correct vessels?

#
# Solution:

Answer: 533.

Let's imagine that inside the vessels, the balls are divided into cells, and each cell contains one ball. Then we can imagine that (regardless of whether they are in the same vessel or different ones) balls $i$ and $j$ simply swap cells upon the command ( $i j$ ). Thus, any sequence of commands simply performs a fixed permutation of the balls in the cells. (Note that transpositions allow us to perform any permutation). We will make a permutation of the type "a pile of cycles of 3 and one of 5", then in each cycle of 3, at least two will change ownership, and in the cycle of length 5, at least three. In total, 533. We cannot guarantee more than this— in a cycle of length $k$, we can guarantee a maximum of $(k+1) / 2 \leqslant \frac{2}{3} k$ changes in ownership (the cycle can consist of pairs of neighboring balls (standing next to each other on the cycle) + possibly one unpaired ball), and two-thirds of 800 is less than 534.