Vizzini's Cups

You're facing a square table, in which each corner has a cup, either face up, or face down (four cups). Vizzini challenges you to a game.

Basic rules: For you to win, you need to get all the cups towards the same direction (either all face up, or all face down). You are blind-folded, and you cannot see the cups. However, by feeling a cup you can tell whether it's face up or face down, and when all the cups face the same direction, a bell rings and you know you have won.

Turns: in each turn, Vizzini rotates the table as much as he wants, and then lets you choose. You can choose up to two cups, feel them up, and turn over any of them (or both, or none).

You must come up with an deterministic algorithm, that wins in all cases. Smart adversary that he is, Vizzini will know your algorithm, so your algorithm must be resilient to that fact.

Solution

Password:
Back to Index