Трудный вопрос на собеседовании #2
Александр СкакуновОпубликовано 9.06.2008 в Статьи
Продолжаем серию переводов цикла “Трудные вопросы на собеседовании“.
Задача #2
Рассмотрим игру, в которую играют двое на круглом столе неопределенного диаметра. Каждый игрок имеет безграничное количество одинаковых монет (четвертаков) и ходит, располагая монету на столе так, что она целиком находится на столе и не накрывает другие монеты, расположенные на игровом поле. Побеждает тот игрок, который делает последний допустимый ход. У кого из игроков (если таковой будет) может быть стратегия, гарантирующая победу, и какова эта стратегия?
Ждите ответ через неделю!
UPDATE: решение
(15 голосов, средний: 3.33 из 5)
Загрузка ...Понравилась статья? Подпишись на обновления по RSS/E-mail
первый игрок
первый ход – кладем монету по центру
остальные хода – симметрично монете противника относительно центра
Насколько я понимаю, в этой игре выиграет тот, кто ходит первым.
Стратегия простая: первым ходом положить монету по центру, каждый следующий ход — клсть монету симметрично предыдушей монете противника.
достаточно положить первым монету по центру. Потом, учитывая что стол круглый, в любом случае найдется ход у первого.
Интересно, что меняется, если стон не круглый, а квадратный? И монетки квадратные
для правильных многоугольников точно ничего не меняется =)
Можно уточнение? Игроки ходят пошагово, как в шахматах? Или же на время кто быстрее?
Вспомнился анекдот про козірній пипец
Хотів би поділитись своїми роздумами.
Висловлена умова про те, що “для правильных многоугольников точно ничего не меняется =)” не є достатньою та і необхідною також. Скажімо для трикутників висловлена раніше стратегія не підійде. Але вона чудово працює у випадку такого неправильного многокутника, як прямокутник.
Ця задача вирішується виказаною стратегією у випадку будь-яких фігур симетричних відносно свого геометричного центра. Для прикладу стіл може бути прямокутником, а фігура правильним шестикутником. Для правильних многокутників можна зробити поправку на те, що вони повинні мати парну кількість вершин…
Ну а у випадку фігур несиметричних відносно свого геометричного центру… То тут треба враховувати розмір фігури у стола (=
классическая игровая задача. действительно нужно первым положить монету в центр и копировать ходы противника. причем монеты могли бы иметь разное достоинство. тогда ходить нужно монетой того же достоинства что и противник.
А для эллиптического стола с полуосями a и b и радиусом монетки c?
Задача имеет одинаковое решение для стола в виде любой центральносимметричной фигуры.
решение предложено в первоых трех коментариях
Следующий.
Центральная симметрия необязательна, достаточно и осевой.
У второго игрока может быть стратегия гарантирующая победу в том случае, если первый игрок первым ходом не поставит монетку в центр – поставить монетку близко к центру настолько, чтобы в центре “слота” для монетки не осталось и далее играть симметрично ходам первого игрока…
Если диаметр стола “неопределенный”, и монеты – тоже, то возможна ситуация, когда диаметр монеты будет больше или равен диаметру стола. В таком случае первый игрок побеждает всегда
ну да, или диаметр монеты будет бесконечно мал по сравнению с диаметром стола, и в таком случае игра вообще не закончится…
А если размер монеты больше диаметра стола, то выиграет второй игрок, поскольку первый не сможет положить свою монету.
Итак, оригинальный ответ:
А вариант, когда монеты выкладываются на столе неплотно не рассматривается?
Как известно, вокруг одной монеты впритык укладывается шесть таких же монет. Допустим, после первого хода первого игрока в центр, начинается “обкладывание” центральнаой монеты. Но если второй игрок третьим ходом (т.е. когда остается место для двух монет рядом) положит свою монету вплотную к центральной, но на определенном расстоянии от соседних, то первый игрок не может сделать симметричный ход, не расширив диаметр занятого монетами круга.
2Sanya: прочитай внимательней комментарий под номером 17. Есть понятие того, что означает “диаметрально противоложно” ?
да, она реально выигрышная