Игра ним как выиграть
Логические задачи и головоломки
Имеется две кучки спичек. В первой 7 спичек, во второй — 5. За один ход разрешается взять любое количество спичек, но из одной кучки. Проигрывает тот, кому нечего брать. Кто выигрывает при правильной игре — начинающий или его партнер? И как для этого ему надо играть?
Ответ: При правильной игре выигрывает начинающий игрок. Его стратегия: первым ходом он должен сравнять количество спичек в кучках, т.е. взять из первой кучки 2 спички. Каждый следующий его ход должен быть «симметричен» ходу второго игрока, т.е. если «второй» берет n спичек из одной кучки, то «первый» должен взять также n спичек, но из другой кучки. Таким образом, если может сделать ход «второй» игрок, то может сделать ход и «первый». Так как после каждого хода количество спичек уменьшается, то наступит момент, когда «второй» не сможет сделать ход (ни в одной из кучек спичек не останется) и проиграет.
- Математические задачи — Алгоритмы
- Добавить комментарий
Комментарии
Оставлен Гость Сб, 07/10/2010 — 11:46
Ответ неоднозначен. Проигрывает тот, кто начинает игру. Первый берет из одной кучки все, второй — из второй, первый — нечего брать. Он проиграл.
Оставлен Гость Втр, 07/13/2010 — 15:08
Нет тут ты не прав. Написано же при ПРАВИЛЬНОЙ ИГРЕ выигрывает начинающий чтобы не делал его партнер.
Оставлен Гость Втр, 11/23/2010 — 20:22
как ни крути, если первый сравнивает число спичек и зеркалит последующие ходы второго, то у второго на победу шансов просто нет. Поскольку у первого — право первого хода. А если первый ходит не так как нужно, то понятное дело, сам дурак, потерял преимущество
Оставлен Гость Пнд, 10/24/2011 — 16:48
. 1
..11111
1111111
Правы только некоторые из вас. При правильной игре(в 1-ом ряду 3, во 2-ом ряду 5, а в 3-ем 7(чего либо спичек например))Выигрывает тот кто начинает правильно,с ПЕРВОГО ряда берётся одна спичка. а потом главное не ступить. Смотря как походит ваш соперник так и ходите(объяснять не буду как, это опыт)
подскажу вам некоторые комбинации делайте их своим соперникам :
1. 1
. 1 1
. 1 1 1 эту комбинацию делайте своему сопернику главное потом не ступите
2. 1
..1 1 1 1
.1 1 1 1 1 эту комбинацию делайте своему сопернику главное потом не ступите
3. 1 1
. 1 1 эту комбинацию делайте своему сопернику главное потом не ступите(эта комбинация может быть любой главное что цифры были одинаковые )
4. 1
. 1
. 1 эту комбинацию делайте своему сопернику
в этих комбинациях ряды могут быть в разном порядке.
Ну вот и всё весь секрет этой игры
играйте и и усваивайте это, главное первыми походите
Оставлен Гость Чт, 09/26/2013 — 11:18
ребята, все гораздо проще! Если Вы делаете первый ход и берете одну спичку из любого ряда, то после хода соперника, Вы всегда поставите комбинацию 2-4-6 или 1-4-5 или 1-2-3 или 1-1-1 или равное количество при оставшихся двух рядах без третьего. А это Ваш выигрыш! Доводите комбинацию до конца и ВСЁ! Я по началу записывал эти комбинации на спичечный коробок)))) Вы будете непобедимы!
Оставлен Гость Втр, 06/17/2014 — 18:50
А если комбинация из 6 рядов: 5,6,7,8,9,10 спичек — с чего нужно начать?
Оставлен Гость Втр, 11/23/2010 — 20:24
а вы определитесь кто тут первый возьмет спичку, мне кажется что ни один из вас не прав.
Оставлен Слава Пт, 08/27/2010 — 14:41
ололол,при правильной игре,тот второй выигрывает,сейчас объясню:
Первый берет 4 спички из 5(допустим,5 из 5 он не берет,т.к сразу проиграет 7 из 7 также!)
второй: берет 6 из 7,
первый любую одну спичку,
второй-оставшуюся.
Если поменять цифра ответ останется,это просто пример,логичной игры.
Оставлен Гость Вс, 01/09/2011 — 13:35
так первый же возьмёт 2 из 7(это при правильной игре)
Оставлен Слава Пт, 08/27/2010 — 15:19
Вообщем все не правы ,всё зависи от того какое число вначале возьмет 1,при 4,5 из 5 и 7,6 из 7 выигрывает 2
А при 1,2,3 из 5 или 1,2,3,4,5 из 7 выигрывает 1!
от так от
Оставлен Гость Ср, 09/01/2010 — 02:49
Весь прикол правильной игры в том, чтоб в обеих кучках после хода первого игрока оставалось одинаковое количество спичек. Тогда проиграть невозможно
Оставлен Virviil Ср, 11/03/2010 — 16:17
2 кучки — это не итерестно, так как выигрывает второй если сначала не поровну(очевидно)
Другое дело, когда кучек n.
Тогда на компе можно посчитать используя XOR(побитовое ИЛИ)
Оставлен Гость Сб, 03/26/2011 — 21:29
Есть игра называется баше расклад 3,5,7 условия аналогиные, только более интересные, выигрывает тот кто доводит до комбинации, 2 радя при одтн-м кол-ве спичек, по одной в каждом ряду, ну или как у нас вариант
Оставлен Гость Пнд, 03/28/2011 — 15:26
очень простая задача. я сразу же догадалась. )
Оставлен Гость Чт, 12/08/2011 — 13:34
мне нужна эта программа на small basic к завтрашнему дню. помогите, кто может, пожалуйста.
Оставлен Кристина Сб, 12/10/2011 — 02:03
Вот все возможные ситуации:
7-5. 6-5. 5-5. 4-5. 3-5. 2-5. 1-5. 0-5
7-4. 6-4. 5-4. 4-4. 3-4. 2-4. 1-4. 0-4
7-3. 6-3. 5-3. 4-3. 3-3. 2-3. 1-3. 0-3
7-2. 6-2. 5-2. 4-2. 3-2. 2-2. 1-2. 0-2
7-1. 6-1. 5-1. 4-1. 3-1. 2-1. 1-1. 0-1
7-0. 6-0. 5-0. 4-0. 3-0. 2-0. 1-0. 0-0
Правильная стратегия — после своего хода оставлять одну из след. ситуаций: 5-5 или 4-4 или 3-3 или 2-2 или 1-1 или 0-0 (победа). При таком подходе у соперника никогда не будет шанса тоже оставить какую-либо из этих ситуаций, в том числе и 0-0 (победа).
Прим.: Из ЛЮБОЙ другой ситуации всегда можно сделать 5-5 или 4-4 или 3-3 или 2-2 или 1-1 или 0-0 (победа), поэтому никогда не дарите сопернику данную возможность и, соотв-но, шанс на победу! =)
Итак, выиграть может и первый и второй, но если Вы первый и знаете данную стратегию, то победа всегда за Вами! ну Вы, конечно, догадались — сразу делаем 5-5 😉
Оставлен Гость Пнд, 05/20/2013 — 10:54
Ребят,а вот как выиграть в такой ситуации.
|||
|||||
|||||||
Проигрывает тот,кто берет последнюю палочку(спичку и т.д.)правила все те же,брать из любого ряда сколько угодно палочек за раз.
Какой алгоритм решения тут?
Оставлен Гость Пнд, 05/20/2013 — 10:54
Ребят,а вот как выиграть в такой ситуации.
|||
|||||
|||||||
Проигрывает тот,кто берет последнюю палочку(спичку и т.д.)правила все те же,брать из любого ряда сколько угодно палочек за раз.
Какой алгоритм решения тут?
Оставлен ШГ Пт, 06/14/2013 — 16:18
Это «Ним на мизер» (кому палочек не осталось, тот выигрывает). Позиции, которые должны получаться после вашего хода:
3-5-6, 3-4-7,2-5-7 (т.е. в начальной позиции надо ходить первым и брать 1 спичку из любой кучки)
Х-Х — две одинаковых кучки (Х >1). Это значит, что если среди трех вдруг стали 2 одинаковые кучки (и в каждой больше 1 спички), то заберите третью. Поддерживайте равенство, пока в одной не останется 1 спичка, тогда возьмите вторую кучку, а 1 спичку оставьте проигравшему противнику.
Вот еще позиции которые нужно получить своим ходом: 2-4-6, 1-4-5,1-2-3,1-1-1
Если такую позицию оставил вам противник,то попробуйте сделать какой-то ход. Может противник не знает выигрышного алгоритма.
Стратегические игры и решение задач. Игра Ним и ей подобные
(Тут будет о истории Ним и подобных играх, так что если лень, листайте сразу до «Об определении стратегии» (Это под 2 картинкой))
Сосредоточим внимание на так называемых стратегических играх. Их можно разделить на два типа. Те, что описываются простыми правилами, длятся короткое время и количество информации в которых ограничено или относительно невелико, будем называть малыми стратегическими играми.
В других, подобных шахматам или го, полный контроль невозможен ввиду длительности партии, сложности правил и в особенности из-за огромного числа возможных ходов в каждой позиции. На примере малых стратегических игр мы увидим, как математика используется в анализе игр для определения преимущества одного из игроков и для нахождения выигрышной стратегии.
Взаимосвязь между математикой и играми может касаться различных аспектов игр. Применительно к стратегическим играм математика особенно полезна для определения выигрышной стратегии. Стратегическая игра очень похожа на процесс решения математической задачи: речь идет не о том, чтобы выиграть одну партию, совершая более удачные ходы, но о том, чтобы найти способ, как выигрывать всегда. По этой причине при определении выигрышных стратегий используются эвристические методы: способ «от обратного»; предположение, что игра «решена»; применение симметрии; проведение аналогии с другой, уже решенной игрой и прочие. Они аналогичны тем, что используются при решении математических задач. Поэтому когда для некоторой игры известна выигрышная стратегия, игра из развлечения превращается в решенную задачу. Понятно, что это верно только для определенных игр, которые выходят за рамки простых развлечений и описываются в математических теориях. О подобных теориях, порой достаточно сложных, мы, возможно, поговорим позже.
Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр
подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.
Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она будет рассматриваться в следующих постах под названием «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.
Определение общей выигрышной стратегии, применимой к любой игре такого типа, — одно из ярчайших проявлений того, как математика используется для анализа игр, и в особенности того, насколько эффективно представление чисел в двоичной системе.
Об определении стратегии
Сначала мы проанализируем игры с одной группой фишек, в которых на каждом ходу можно брать со стола минимум одну и максимум n фишек. Мы рассмотрим два частных случая, затем приведем обобщение. Самый простой вариант подобной игры таков.
Игра 1: выигрывает первый
На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если вы незнакомы с этой игрой, перед прочтением попробуйте сыграть в нее самому и постараться ответить на заданные выше вопросы.
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну
фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2017), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру
можно обобщить и дальше, изменив число фишек, которые можно брать на каждом
Игра 2: выигрывает второй
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, . 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 — n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.
Игра Ним
Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет.
В классическом варианте игры число кучек равняется трём.
Содержание
История игры
Игра ним попала в Европу в XVI веке из Китая. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Chalres Bouton ), описавшим в 1901 году выигрышную стратегию игры.
Существует несколько вариантов происхождения названия игры:
- от немецкого глагола Nimm или старо-английского глагола Nim, имеющих значение «брать»;
- от английского глагола WIN («побеждать»), переворачиванием слова;
Стратегия игры
В общем случае рассматривается p кучек предметов с предметами. Игроки ходят по очереди. Ход заключается в том, что игрок берёт из кучки
предметов.
Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, то есть сложение двоичных разрядов чисел в поле вычетов по модулю 2:
Выигрышная стратегия состоит в том, чтобы оставлять после своего хода позицию с ним-суммой, равной нулю. Она основана на том, что из любой позиции с ним-суммой, не равной нулю, можно одним ходом получить позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт в позицию с ним-суммой, отличной от нуля.
Варианты игры
Мизер
В этом варианте игрок, взявший последний объект, проигрывает.
Выигрышная стратегия совпадает с выигрышной стратегией обычной игры до того момента, когда в результате хода игрока на столе должно остаться некоторое количество кучек с единственным предметом в каждой из них. В случае мизера игрок должен оставить нечётное количество кучек, тогда как выигрышная стратегия обычной игры требует оставить чётное количество кучек, чтобы ним-сумма равнялась нулю.
Мультиним
Более общий случай игры ним был предложен Муром (Eliakim Moore). В игре Nimi игрокам разрешается брать предметы из максимум i кучек. Легко видеть, что обычная игра ним является Nim1 .
Для выигрышной стратегии игры вводится ним-сумма позиции, определённая как результат сложения размеров всех кучек в системе счисления базы i + 1 без учёта переноса разрядов. В остальном стратегия остаётся прежней.
Ним в массовой культуре
См. также
- Функция Шпрага-Гранди
- Игра Баше
- Крестики-нолики
Литература
- Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М.: Мир, 1986. — С. 474.
- Фомин С. В.Системы счисления. — 5-е изд. — М.: Наука, 1987. — С. 48.
- Гарднер М. Крестики-нолики.
- Jean-Paul DelahayeStratégies magiques au pays de Nim // Pour la science : Журнал. — Paris: Belin, 2009. — Т. 377. — № 3. — С. 88-93.
Wikimedia Foundation . 2010 .
- Игра Джери (мультфильм)
- Игра Жизнь
Полезное
Смотреть что такое «Игра Ним» в других словарях:
Ним (значения) — Ним: Ним город во Франции Ним футбольный клуб из Франции Ним дерево Ним математическая игра НИМ часто используемая аббревиатура для журнала «Навигатор Игрового Мира» 51 Ним астероид главного пояса … Википедия
Ним (игра) — У этого термина существуют и другие значения, см. Ним (значения). Ним математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее… … Википедия
ИГРА НА ГРАФЕ — обобщение позиционной игры на случай, когда граф позиций не древовидный, а произвольный. Частным случаем И. на г. является игра Ним антагонистическая игра с полной информацией, в к рой для каждой окончательной позиции указано, выигрывает или… … Математическая энциклопедия
Игра Баше — Баше математическая игра, в которой два игрока по очереди вынимают из кучки N предметов не менее 1 и не более k. Проигравшим считается тот, кому нечего брать. Названа в честь французского математика Баше де Мезирьяка. Стратегия Выигрышный… … Википедия
Игра (фильм, 1997) — Игра The Game … Википедия
Игра Гранди — это математическая игра на стратегию для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют одну кучу на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух и менее предметов и ни… … Википедия
Игра (телепередача) — Игра Жанр телевизионный квест Ведущий Виктор Вержбицкий, Рома Зверь Страна производства … Википедия
ИГРА — один из важнейших феноменов человеческого существования. Обычно И. противопоставляют труду, в лучшем случае видят в ней тренировку перед серьезным делом или необходимое восполнение монотонной односторонней деятельности. Считается, что только… … Философская энциклопедия
ИГРА — вид непродуктивной деятельности, мотив к рой заключается не в результатах, а в самом процессе. Уже у Платона можно отыскать отдельные суждения об игровом космосе. Эстетич. “состояние И.” отмечено Кантом. Шиллер представил относительно… … Энциклопедия культурологии
ИГРА — ы; мн. игры, игр; ж. 1. к Играть (1, 3 6 зн.). И. детей прекратилась. Вмешаться в детскую игру. И. с ребёнком, собакой. И. на скрипке, на рояле. Виртуозная и. пианистки. Слушать игру духового оркестра. И. актёра в роли Отелло прекрасна. И.… … Энциклопедический словарь