The carromboard puzzle
You get inside a room with a square table and a lamp. On each side of the table there's a toggle switch, which can be pressed to toggle it (the four switches have two states each). The lamp turns on if all switches are in the same state (either on or off). When you enter a room, the lamp is not on, so you know that the switches are not all the same state - but that's all you know about their states.
Your goal is to turn the lamp on in as few rounds as possible. The complication is that after each round of pressing (you can press either one switch or two at a time), you must close your eyes, and a goblin turns the table by some unknown amount (wlog it is either 0, 90, 180 or 270 degrees).
Can you turn the lamp on at all? How many rounds does it take you? Is the optimal solution (essentially) unique?
Generalizations
The puzzle can be generalized as follows. There are $n$ switches and $m$ states for each. Each round, you're allowed to press any number of switches (i.e. you have as many hands as you want), and moreover, you can press any given switch more than once. In other words, you're adding an arbitrary vector to the state vector of the switches. The goblin still turns the $n$-sided table each round.
For which $n,m$ can you turn the lamp? What is the minimal rounds needed? How do all the optimal solutions look like?
(If you don't like switches with $m$ states, you can stick to the case $m=2$, which is also simpler.)
Answers
Well, not quite. There is a simple condition on $n,m$ that tells you whether there is a solution. When a solution does exist, the size of the minimal solution has a simple formula. When $m$ is prime (e.g. $m=2$), all minimal solutions have a nice description. For the rest of the solvable cases (other than the trivial ones), there's apparently no nice description (this is an open question, for your more ambitious students).
It turns out that it's better to change the turn-on criterion from all-switches-equal to all-switches-on; there's a simple reduction between the two (when $m$ is prime), and the latter criterion is somewhat more natural.
Prison
The wardens in a state penitentiary are playing a game with the prisoners. All the prisoners are gathered, and told the following: "There is a special cell in the prison, within it a switch with N states (we do not tell you its initial state). From time to time, we will take a prisoner into the special cell. We promise to take each prisoner indefinitely many times into the cell, but we take the prisoners in any order. At any given time, a prisoner can shout "Liberty!" At that point, if all prisoners have been to the cell, we set you free; otherwise, we double your sentences."
For which N do the prisoners have a winning strategy? (I think they win even for $N=2$ but I don't remember; larger N are easier anyhow.)
Hats
A 100 students are standing in a row, so that each one can see the color of everyone in front of her. They know that the color of their hats is either red or blue. The teacher asks them one by one, from back to front, as to the color of their hat. Anyone who answers correctly gets a trip to Disneyworld.
What should the students do to maximize the number of those students who go to Disneyworld?
For the ambitious: What happens if there are countably many students?