Probl2

AlgKons

The following rules applies to both parts of this problem:

You are sitting blind-folded in front of a table which is partitioned into 4 equal squares. In each square there is a cup, and each of the squares has a letter attached to it (A,B,C and D). These letters are never moved. When this game starts, each of the four cups are placed either the correct way or upside down (randomly).

After each round of the game, your assistant rotates the cups. Note that only the cups are rotated, the squares stay as they were, and you are not capable of seeing how the cups are rotated.

Part 1

In each round, you may touch exactly two cups. You may then place them back either the same way or turned upside-down. If all cups are either placed the right way or upside-down, you will be notified that you have won. Otherwise, you will have to play another round.

What is the smallest number of rounds you will have to play to guarantee that you have won? What is your strategy?

Part 2

You, as a player, may ask your assistant to turn any number of cups (you may for example say: "Turn the cups in A,B and D"). Your assistant will do as you tell him. If all cups are rotated the correct way, you have won. Otherwise, the cups are rotated randomly as in part one, and you will have to play another round.

What is the smallest number of rounds you will have to play to guarantee that you have won? What is your strategy?

A clarification of how your helper rotates the cups follows:

If the cups are numbered, and are placed as below:

A:1 B:2 C:3 D:4

The cups may have each of the following placements after the helper has rotated them:

A:1 B:2 C:3 D:4

A:2 B:3 C:4 D:1

A:3 B:4 C:1 D:2

A:4 B:1 C:2 D:3