Гра "11 сірників"
Двоє гравців беруть по черзі сірники (всього 11 сірників) брати можна не більше 3-х сірників за один ряд; програє той, хто бере останній сірник.
Ясно, що для перемоги 1-го гравцеві необхідно залишити 2-му 5 або 4 сірники. Тоді в будь-якому розкладі 1-ий переміг.
У разі для 11 сірників, треба намагатися витримати суму сірників після ходів = 6, так як 11-6 = 5. Соответсвенно для 11 їх легко можна все записати, безвиграшну тільки (3, 3).
Питання - а як перекласти алгоритм на більше число сірників. Взагалі потрібно написати безпрограшну програму. Може вже хтось робив таку прогу? Для будь-якого чи числа сірників можна зробити алгоритм?
Гра Баше начебто називається. Ідея - доповнювати до 4х
Ідея - доповнювати до 4х ну це я так розумію тільки одна тсратегія. Наприклад, для 11 сірників імем
(2,31, х)
(2,22, х)
(2,13, х)
Тут дійсно спрацьовує доповнення до чотирьох, після ходу 2.
Але є й інша стратегія
(1,23, х)
(1,32, х)
(1,11,3)
(1,11,21, х)
(1,11,12, х)
Тут як раз спрацьовує, щоб сума була 6, щоб звести до залишку 5. Просто для більшої кількості сірників складно програмно реалізувати алгоритм.
а при чому тут "проги" і "алгоритми"? Це цілком конкретна шкільна задача на подільність, вирішити яку для довільних N - загального числа і n - максімальнго числа забору за один підхід до фуршетного столу (N> n я сподіваюся, Ви в змозі.
Гра Баше начебто називається Дійсно, гра так і називається. Спасибі, що сказав назва - в неті купа документів, зараз шукати буду
а при чому тут "проги" і "алгоритми"? при тому, що треба написати програму, котораяреалізует ВСЕ виграшні алгоритми
ніяких "всіх" виграшних алгоритмів не існує: якщо він існує для одного з гравців - то один невірний хід веде до того, що існує виграшна стратегія у суперника
виграшний алгоритм для першого гравця, ситуація, що гравець тупанул НЕ рассамтрівается
це при 11-3 виграшний алгоритм (причому, єдиний, а не два) для першого.
не гони! алгоритм для першого: витягнути спочатку 2 сірники а далі доповнювати до 4, щоб остання залишилася після ходу першого гравця повинно завжди залишаюсь ся 4 * k + 1 сірник
але можна виграти 1-им гравцем, якщо взяти спочатку і 1 сірник.
ні звичайно
якщо є алгоритм забезпечує виграш витягуванням 2 сірників, то не можна виграти витягнувши 1.
(1,11,3) ось ця частина мені не зрозуміла, що першому далі робити?
це програшна стратегія.
Нехай все N сірників. Ясно, що для перемоги 1-го гравцеві необхідно залишити 2-му 5 або 4 сірники. Тоді в будь-якому розкладі 1-ий переміг. не зрозумів, як залишити 4 сірники 2-му. він береn 3, і перший програв .. Номери програшних позицій при розподілі на 4 дають залишок 1. Тобто програшні позиції 4n + 1 = 1,5,9. інші виграшні. Оскільки береш стільки сірників, щоб весь час противник потрапляв на позицію 4n + 1. З кожним повним ходом (спочатку! Противника, а потім своїм) n зменшується на 1, а число сірників в купі на 4.
Нехай перший може виграти, взявши першим ходом n сірників.
маємо
1) Якщо до ходу гравця залишається N-n, то при будь-яких його діях він програє.
Нехай перший може виграти, взявши першим ходом m
2) Якщо до ходу гравця залишається N-m, то при будь-яких його діях він програє
Але, якщо з N-m другий візьме n-m (0
З 11 сірників до цього веде перший хід "забрати 2".
Залишилося 9 = 4 * 2 + 1 Противник забрав скільки то - ти забираєш так, щоб потрапити на
5. Потім на 1. І все - він програв.
PS Більш серйозна задача в хобі в завданнях на подумати моє завдання про N куп. запостив (а спасибі.Схожі статті