Трудный вопрос на собеседовании #2

Продолжаем серию переводов цикла «Трудные вопросы на собеседовании».

Задача #2

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

Ждите ответ через неделю!

UPDATE: решение

👍НравитсяПонравилось0
В избранноеВ избранном0
Подписаться на автора
LinkedIn



Підписуйтесь: Soundcloud | Google Podcast | YouTube

18 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

да, она реально выигрышная

2Sanya: прочитай внимательней комментарий под номером 17. Есть понятие того, что означает «диаметрально противоложно»?

А вариант, когда монеты выкладываются на столе неплотно не рассматривается? Как известно, вокругодной монеты впритык укладывается шесть таких же монет. Допустим, после первого хода первого игрока в центр, начинается «обкладывание» центральнаой монеты. Но если второй игрок третьим ходом (т.е. когда остается место для двух монет рядом) положит свою монету вплотную к центральной, но на определенном расстоянии от соседних, то первый игрок не может сделать симметричный ход, не расширив диаметр занятого монетами круга.

Итак, оригинальный ответ:

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

А если размер монеты больше диаметра стола, то выиграет второй игрок, поскольку первый не сможет положить свою монету.

Если диаметр стола «неопределенный», и монеты — тоже, то возможна ситуация, когда диаметр монеты будет больше или равен диаметру стола. В таком случае первый игрок побеждает всегда:)

У второго игрока может быть стратегия гарантирующая победу в том случае, если первый игрок первым ходом не поставит монетку в центр — поставить монетку близко к центру настолько, чтобы в центре «слота» для монетки не осталось и далее играть симметрично ходам первого игрока...:)

Центральная симметрия необязательна, достаточно и осевой.

Задача имеет одинаковое решение для стола в виде любой центральносимметричной фигуры.решение предложено в первоых трех коментарияхСледующий.

А для эллиптического стола с полуосями a и b и радиусом монетки c?

классическая игровая задача. действительно нужно первым положить монету в центр и копировать ходы противника. причем монеты могли бы иметь разное достоинство. тогда ходить нужно монетой того же достоинства что и противник.

Хотів би поділитись своїми роздумами. Висловлена умова про те, що «для правильных многоугольников точно ничего не меняется =) » не є достатньою та і необхідною також. Скажімо для трикутників висловлена раніше стратегія не підійде. Але вона чудово працює у випадку такого неправильного многокутника, як прямокутник.Ця задача вирішується виказаною стратегією у випадку будь-яких фігур симетричних відносно свого геометричного центра. Для прикладу стіл може бути прямокутником, а фігура правильним шестикутником. Для правильних многокутників можна зробити поправку на те, що вони повинні мати парну кількість вершин...Ну, а у випадку фігур несиметричних відносно свого геометричного центру... То тут треба враховувати розмір фігури у стола (=

Вспомнился анекдот про козірній пипец:)

Можно уточнение? Игроки ходят пошагово, как в шахматах? Или же на время кто быстрее?:)

для правильных многоугольников точно ничего не меняется =)

Интересно, что меняется, если стон не круглый, а квадратный? И монетки квадратные:)

достаточно положить первым монету по центру. Потом, учитывая что стол круглый, в любом случае найдется ход у первого.

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

Подписаться на комментарии