A Game of Cups and Coins
On a disc, there are n (identical) cups forming a regular n-gon with center being the center of the disc. Under each cup, there is a coin. Before the game starts, the coins randomly show either heads or tails. The objective of the game is to have all coins face the same way (all heads or all tails).
For every turn, you are allowed to lift up c cups. Looking at the c revealed coins you may now choose to flip them (you may flip all, none, some, ... your choice). Your turn ends when you place all c cups on top of the coins again. If the game is won at this point, you will know immediately. Otherwise, the disc is spun so fast that you have no idea of the orientation after the disc comes to a halt. You proceed with your next turn.
The game score is computed as follows. Find a deterministic algorithm to win the game. If you can prove that your algorithm wins the game in at most t turns, then your score is To submit an entry to the leader board, email me at tobias.hartung [at] kcl.ac.uk with your algorithm and proof of the upper bound on the number of turns t.
Proofs of necessary conditions are listed below for the leader board.
Leader Board
| Score | Name | n | c | t | Proof |
| Jan Felix | 4m with m≥6 | 2m | 8 | proof | |
| Jan Felix | 4m with m≥4 | 2m | 11 | proof | |
| Asuka Kumon and Tobias Hartung | 2m with m≥18 | n-3 | 6 | proof | |
| Tobias Hartung | 2m with m≥3 | n-2 | 5 | proof | |
| Tobias Hartung | n | n-1 | 2 | trivial | |
| Jan Felix | 8 | 4 | 9 | proof | |
| original puzzle | 4 | 2 | 5 | ;) | |
| Jan Felix | n | n | 1 | trivial |
Necessary conditions
| Description | Statement | Name | Proof |
| symmetric solutions [h...ht...t]^r w/ r>1, k h's, l t's, k≥l | for k>l and c≥1+n/2 for k=l, unless [ht]^r where c≥n/2 | Tobias Hartung | proof |