Doing a magic trick with limited memory (from a problem solving course)
I got the following question in a problem solving course:
There are four different objects lying on places 1, 2, 3, 4. A magician closes his eyes and someone from the audience comes. He switches pairs of objects 10 times, and each time shouts the places he switched. Then he does a secret switch and doesn't tell the magician the places. Then he switches another 10 times and shouts the places as before. The magician open his eyes, look at the objects and point on one of the objects that participated in the secret switch.
The magician has a bad memory, thus he can only remember one number between 1 to 10. How does he do it?
My direction is not to find the secret switch itself, but 2-3 options with a mutual object and choose that object, but I can't figure out how.
Actually, there's a reasonably simple way to do it, remembering an integer between $-4$ and $4$ . It's really a modulus between $1$ and $4$, and a sign, that must be tracked independently; it’s actually easier than remembering a number between $1$ and $10$ (though if the magician just can’t remember negative numbers, he can substitute $5,6,7,8$ for $-1,-2,-3,-4$).
The modulus is the position where object $1$ should be, disregarding the secret switch. So whenever the magician hears a pair of numbers and one of them is the modulus he has in mind, he switches his modulus to the other number. He has $2$ in mind and hears $2,4$? He concentrates on $4$. He has $3$ in mind and hears $1,3$? He concentrates on $1$. He has $4$ in mind and hears $1,3$? He keeps concentrating on $4$.
The sign is switched whenever the magician hears and odd-even pair, otherwise it is left unswitched. He has $-1$ in mind and hears $2,3$? He concentrates on $1$. He has $-4$ in mind and hears $2,4$? He concentrates on $-2$. (He does not switch sign, but he does switch modulus!)
The magician starts with the number $1$ in mind and follows the two rules above, tracking the (alleged) position of object $1$ in the modulus, and flipping the sign when hearing odd-even switches. At the end of the game:
- He checks the position he has in mind. If he does not see object $1$, he points to object $1$.
- Otherwise, he asks himself whether neither or both of objects $1$ and $3$ are in an odd position. If the answer and the sign agree, i.e. they are both positive or both negative, he points to object $2$.
- Othewise, he points to object $3$.
Let's prove it works. First of all, it's pretty obvious that object $1$ is where the magician looks for it if and only if it was left alone during the secret switch. If it is not, the magician can point to object $1$.
Otherwise, consider the parity of the number of odd-even switches necessary to bring every object to the starting position: it is $0$ if and only if both or neither $1$ and $3$ are in an odd position (including at the beginning of the game), and obviously changes if and only if there’s an odd-even switch. So both the answer to the question “are both or neither ...”, and the sign of the number the magician remembers, are positive or negative depending on whether there were an even or an odd number of parity switches respectively in the room and in the “called out” switches; the secret switch was an odd-even switch if and only if they disagree. If they agree, the switch must have been between between $2$ and $4$, since it did not involve $1$, so the magician can point to $2$. If they agree, the switch must have involved $3$ since, again, it did not involve $1$ - so the magician can point to $3$.