Maths Olympiad Prep

Library / /22 of 22

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

You are blindfolded and have a spinning table with four switches on it in front of you. The switches are always either up or down, and you don't know what configuration they start in. On each move, you can spin the table some unknown amount, then reach out and choose two switches (either next to each other or diagonally opposite each other), feel whether they are up or down, and then choose to flip one, both, or neither of them. You win if you turn the switches either all up or all down. Determine whether it is always possible to win the game.

Solution

Solution:

It is indeed possible. One strategy is as follows:

a) Choose two switches that are next to each other. Turn them so they are both up.

b) Choose two switches that are diagonally opposite each other (so exactly one is a switch you picked last time). Turn them so they are both up. Now at least three switches are up, so if the fourth is also up, you win. Thus, assume the fourth switch is down.

c) Choose two switches that are diagonally opposite each other. If one is down, turn it up, and you win since all four are up. Otherwise, both are up, so turn one of them down. There are now two adjacent down switches and two adjacent up switches.

d) Choose two adjacent switches. If both are up, turn them both down, and you win. If both are down, turn them both up, and you win. Otherwise, one is up and the other down, so turn the up one down and the down one up. Now there are two diagonally opposite up switches and two diagonally opposite down switches.

e) Choose two diagonally opposite switches. If they are up, turn them down, and if they are down, turn them up. Either way, you win!

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.