This puzzle was suggested by Sanandan Swaminathan - thanks!
A game show is arranged as follows: The main attraction is a wheel that has NN buttons equidistant from one another, such that the wheel looks perfectly symmetric.
Each button has two possible states: "on" and "off". There's no indicator to the status of a button, and each press toggles between those two states ("on" -> "off" -> "on" and so forth). At the beginning of the game, the buttons have random states with the one condition that not all buttons are "on".
On each turn, the wheel spins randomly without the contestant looking; the buttons are marked with 1,2,…1,2,\ldots beginning at the top-left button and going clockwise. The contestant picks a subset of the buttons and pushes them. After the contestant is done, two things can happen:
The contestant's goal is to find a strategy that guarantees winning in the least number of rounds, even if the game cheats and the spins of the wheel are not random.
The choices of the contestant can be described by a sequence of natural numbers. Rounds are separated by 0, and each round contains the numbers of the buttons pressed by the contestant.
For example, the following is an optimal solution for the case N=2N=2:
If both buttons were "off" at the beginning, the game is won after the first round. Otherwise, after the second round both buttons have the same state, so after the third round, the contestant has certainly won the game.
Summing up the numbers in the solution, we arrive at the value 77. If, in the middle round, we would have used 2 instead of 1, we'd reach the value 88. We are interested in the minimum value that can be obtained from an optimal solution: We call this the "optimal solution sum" for NN.
Your goal: Find the optimal solution sum for N=8N=8.
A bonus "*" will be given for finding the optimal solution sum for N=64N=64.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。