[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 369

Помню в армии один товарищ любил людей разводить этой игрой, так он говорил основную заповедь -оставил противнику два ряда значит проиграл! Т.е. надо подвести противника к тому что бы он оставил два ряда по фигу сколько спичек в каждом ряду!

Да-да, два ряда тут ключевой момент. Но не просто два ряда, а с уточнениями:

- если ты оставил ему 1,1, то проиграл ты

- если ты оставил ему равные n,n (n>1), то проиграл он

- если ты оставил ему любые два неравных числа, то выиграл он.

Проблема в том, как сделать оптимальные ходы до этих двух рядов.

Да! Как дойти до двух рядов да еще что бы попасть под нужные условия - вариантов множество! И после каждого хода противника просчитывать варианты исходя из указанных Mathematом ограничений! Ну хотя бы известен промежуточный вариант к которому надо стремиться!

Бородатая игра. Называется "Ним". Стратегия заключается в том, что количество спичек на каждом "этаже" преобразуется в двоичное число, а потом считается четность-нечетность для отдельных колонок нулей и единиц.

Сомневаюсь, что этот мужик в подпитии преобразовывал числа в двоичные... Ну для маленьких чисел это легко. А если уже пива на грудь литра три принял?

Решение есть?

На википедии https://ru.wikipedia.org/wiki/Ним_(игра) есть описание выигрышной стратегии. Честоно говоря, я так и не понял, в чём суть. Как-то мутно написано.

Все там предельно ясно написано. Преобразуем количество спичек в двоичные числа, потом проводим побитовые операции над числами через логическое сложение по модулю 2 - что является полным аналогом вычисления четности-нечетности. Получаем стратегию, т.е. число которое нужно обнулить. Берем "этаж" в которой число спичек больше или равно числу стратегии. Если равно, то забираем все спички с этажа.

Если не равно, тогда число спичек на этаже складываем с числом-стратегией с помощью двоичного сложения по модулю 2. Получаем результат, т.е. сколько спичек должно остаться на "этаже", чтобы ход следующего игрока стал заведомо проигрышным. Забираем с "этажа" лишние спички.

Все гораздо проще. Для такого количества спичек все выигрышные комбинации можно запросто запомнить и вспомнить даже в подпитии. Будучи студентом я именно так и делал и обыгрывал своих сокурсников. Поэтому и говорю, что игра бородатая.

Попробуем разобрать пример, который приведён на википедии.

Пример: предположим, в игре три кучки, в них соответственно 2 (0010 в бинарном представлении), 8 (1000) и 13 (1101) предметов. Ним-сумма этой позиции — 7 (0111).
Следовательно, выигрышная стратегия состоит в том, чтобы взять 3 предмета из третьей кучки — там останется 10 (1010) предметов, и ним-сумма позиции станет 0 (0000).
Предположим, после вашего хода противник забирает все предметы из первой кучки — выигрышная стратегия будет заключаться в том, чтобы забрать 2 предмета из третьей
кучки. В таком случае после вашего хода в кучках будет соответственно 0 (0000), 8 (1000) и 8 (1000) предметов, ним-сумма по прежнему будет равняться 0.

 Складываем числа:

0010+1000+1101 = 0111 если не учитывать перенос единиц в старший разряд. Согласен. Как только ним-сумма была вичислена, автор утверждает, что нужно взять три предмета из третьей кучки. Вот этого-то я и не понял. С чего он взял что брать нужно только три предмета и почему именно из третьей кучки? Ведь для того, чтоб ним-сумма стала равна 0 нужно из числа 0111 вычесть 0111, то есть, вычесть семь. 

0010

1000

1101

-----

0111 - результат, т.е. в первой колонке четное количество спичек, в остальных нечетное.

Третий этаж 1101 = 13

Складываем количество кучек третьего этажа с результатом:

1101

0111

----

1010 = 10

13 - 10 = 3, т.е. с третьего этажа нужно забрать 3 спички, тогда там останется 10 спичек, что в двоичной системе = 1010

Проверяем, то что осталось:

0010

1000

1010

-----

0000 - выигрышная стратегия