Re:Трудные вопросы на собеседовании, четные задачи Опции

[compiler]

Итак сдесь четные задачи, не четные и вступление сдесь:

Задача #2

Рассмотрим игру, в которую играют двое на круглом столе неопределенного диаметра. Каждый игрок имеет безграничное количество одинаковых монет (четвертаков) и ходит, располагая монету на столе так, что она целиком находится на столе и не накрывает другие монеты, расположенные на игровом поле. Побеждает тот игрок, который делает последний допустимый ход. У кого из игроков (если таковой будет) может быть стратегия, гарантирующая победу, и какова эта стратегия?

В атаче задание на ангельском. Решение через неделю.

[andriano]

Итак сдесь четные задачи, не четные и вступление сдесь:
В атаче задание на ангельском. Решение через неделю.

Спойлер (Показать/Скрыть)

Очевидно, у первого есть выигрышная стратегия: первую монету поставить в центр, а каждую последующую - симметрично последней монете противника относительно центра.

[compiler]

решение:

Спойлер (Показать/Скрыть)

У игрока 1 есть выигрышная стратегия. Его первым ходом должно быть расположение монеты в точном центре стола. Если это уже достаточно вам сказало, то, думаю, дальше вам лучше не читать. Если же вы до смерти хотите узнать все остальное, читаем дальше.

Затем игрок 2 располагает монету где-либо на столе (но не в центре, разумеется). Теперь убедимся, что игрок 1 всегда имеет допустимый ход: располагая монету диаметрально противоложно только что поставленной монете игрока 2 (т.е. самый первый ход игрока 1 будет средней точкой на линии между последним ходом игроков 1 и 2). Продолжаем, пока стол не заполнится, но т.к. игрок 1 всегда имеет допустимый ход, игрок 2 столкнется с тем, что у него-то допустимого хода нет. И игрок 1 побеждает.

Обратите внимание, что эта стратегия работает даже в вырожденном случае, когда стол имеет размеры четвертака.

оригинал:

Спойлер (Показать/Скрыть)

Player 1 has a strategy to win. His first move is to put a quarter in the exact center of the table. If this is enough of a hint for you, I suggest you stop reading now. If you're just dying to know the rest, read on:

Player 2 then places a quarter anywhere on the table (but not in the center, of course). Now convince yourself that Player 1 always has a legal move: by playing a quarter diametrically opposite from the quarter Player 2 just put down (i.e., Player 1's first quarter is the midpoint of the line between Player 2's last quarter and Player 1's last quarter). We continue until we fill up the table, but since Player 1 always has a legal move, it is only Player 2 that will be faced with no legal move. Then Player 1 wins.

Note that this strategy works even in the degenerate case when the table is the size of a quarter.