Ссылки по теме:
Подборка статей в журнале "Квант"
Подтемы:
Подборка статей в журнале "Квант"
Подтемы:
-
Теория игр
(278 задач)
Взвешивания
(154 задачи)
Теория алгоритмов (прочее)
(268 задач)
Кооперативные алгоритмы
(29 задач)
Переправы
(1 задача)
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
Игра ``Ним''. Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней m1, m2, ..., ml поставим в соответствие его ним сумму (5.1 ).
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n
0.
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?
Решение
Убрать все задачи
Игра ``Ним''. Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней m1, m2, ..., ml поставим в соответствие его ним сумму (5.1 ).
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?
Решение
Задачи
Страница: << 126 127 128 129 130 131 132 >> [Всего задач: 737]
Игра ``Ним''. Имеется несколько кучек камней. Двое по очереди берут из
них камни. За один ход разрешается взять любое (ненулевое)
количество камней, но только из одной кучки. Выигрывает тот, кто
взял последний камень.
Для анализа игры каждому набору кучек камней m1, m2, ...,
ml поставим в соответствие его ним сумму (5.1
).
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n 0.
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?
У Васи есть 100 банковских карточек. Вася знает, что на
одной из карточек лежит 1 рубль, на другой – 2 рубля, и так
далее, на последней – 100 рублей, но не знает, на какой из
карточек сколько денег. Вася может вставить карточку в банкомат и
запросить некоторую сумму. Банкомат выдает требуемую сумму, если
она на карточке есть, не выдает ничего, если таких денег на
карточке нет, а карточку съедает в любом случае. При этом банкомат
не показывает, сколько денег было на карточке. Какую наибольшую
сумму Вася может гарантированно получить?
Какое наименьшее число гирь необходимо для того,
чтобы иметь возможность взвесить любое число граммов от 1 до 100
на чашечных весах, если гири можно класть на обе
чашки весов?
На выборах в городскую Думу каждый избиратель, если он приходит
на выборы, отдает голос за себя (если он является кандидатом) и
за тех кандидатов, которые являются его друзьями.
Прогноз социологической службы мэрии считается хорошим, если
в нем правильно предсказано количество голосов, поданных хотя бы
за одного из кандидатов, и нехорошим в противном случае.
Докажите, что при любом прогнозе избиратели могут так явиться на
выборы, что этот прогноз окажется нехорошим.
Страница: << 126 127 128 129 130 131 132 >> [Всего задач: 737]
Задача 60915[Игра "Ним"] |
|
|
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?
|
|
|
Решение |
Задача 111337 |
|
|
|
|
Решение |
Задача 30840 |
|
|
|
|
|
Решение |
Задача 109965 |
|
|
|
|
|
Решение |
Задача 64784 |
|
|
Двое игроков играют в карточную игру. У них есть колода из n попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если A бьёт B, а B бьёт C, то может оказаться, что C бьёт A). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.
|
|
|
Решение |
Страница: << 126 127 128 129 130 131 132 >> [Всего задач: 737]
