Найпростіше рішення задачі 26 або за старим С3
з інформатики та ІКТ наочним методом "Горбів і ям"
Приклад рішення задачі в разі збільшення каменів в купі двома способами "+1" і "* 2"
Два гравці, Петя і Ваня, грають в наступну гру. Перед гравцями лежить купа каміння. Гравці ходять по черзі, перший хід робить Петя. За один хід гравець може додати в купу один камінь або збільшити кількість каменів в купі в два рази. Наприклад, маючи купу з 15 каменів, за один хід можна отримати купу з 16 або 30 каменів. У кожного гравця, щоб робити ходи, є необмежена кількість каменів. Гра завершується в той момент, коли кількість каменів в купі стає не менш 22. Переможцем вважається гравець, який зробив останній хід, тобто першим отримав купу, в якій буде 22 або більше каменів.
У початковий момент в купі було S каменів, 1 <= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Виконайте наступні завдання. У всіх випадках обгрунтовуйте свою відповідь.
1. а) Вкажіть всі такі значення числа S, при яких Петя може виграти в один хід. Обгрунтуйте, що знайдені всі потрібні значення S, і вкажіть виграє хід для кожного зазначеного значення S.
б) Вкажіть таке значення S, при якому Петя не може виграти за один хід, але при будь-якому ході Петі Ваня може виграти своїм першим ходом. Опишіть виграшну стратегію Вані.
2. Вкажіть два таких значення S, при яких у Петі є виграшна стратегія, причому
- Петя не може виграти за один хід, і
- Петя може виграти своїм другим ходом, незалежно від того, як буде ходити Ваня.
Для кожного зазначеного значення S опишіть виграшну стратегію Петі.
3. Вкажіть значення S, при якому:
- у Вані є виграшна стратегія, що дозволяє йому виграти першим або другим ходом при будь-якій грі Петі, і
- у Вані немає стратегії, яка дозволить йому гарантовано виграти першим ходом.
Для зазначеного значення S опишіть виграшну стратегію Вані.
Побудуйте дерево всіх партій, можливих при цій виграшної стратегії Вані (у вигляді малюнка або таблиці). На ребрах дерева вказуйте, хто робить хід, в вузлах - кількість каменів в купі.
Питання 1а.
Зворотним ходом від "перемоги" визначаємо межі початкової виграшній позиції: 22 - 1 = 21 і 22/2 = 11
Для будь-якого числа, що лежить в межах даного діапазону справедлива наступна запис max0 * 2> = 22 або max0 * 2> 21 (обводимо даний діапазон зверху і позначаємо його какmax0, що буде означати початкову виграшну позицію або виграш за один хід)
1а) Петя виграє першим ходом при 11 <= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.
Питання 1б. Для відповіді на це питання потрібно знайти позиції, умовно назвемо їх min0. з яких всі можливі ходи ведуть в початкову виграшну позицію, зазначену нами як max0. Зворотним ходом визначаємо «підозрювані» позиції на min0:
11/2 =? остачі не ділиться, отже, таку позицію немає. Залишається тільки S = 11-1 = 10
(Але поки це тільки предполагаемийmin0, тому малюємо «яму» двома рисами, що буде означати - не забути про існування 2х можливих ходів, які потрібно буде обов'язково перевірити!)
Перевіряємо припущення для S = 10 на min0. Ця перевірка і послужить відповіддю на питання 1б
При S = 10 у Петі є 2 ходу, якими він не може виграти за один хід, але при будь-якому ході Петі Ваня може виграти своїм першим ходом:
Будь-хід Петі «10 + 1 = 11» або 10 * 2 = 20 ведуть в початкову виграшну позицію Ваню, який, подвоївши кількість каменів в купі, отримує 22 або 40, що більше 21 і перемога дістанеться Вані
П оетому позицію S = 10 обводимо знизу суцільний рисою (малюємо яму) - min0 (початковий програш або програш за 1-й хід):
Відповідь на питання 1б. може бути таким: При S = 10 у Петі є 2 ходу, якими він не може виграти, але при будь-якому ході Петі Ваня може виграти своїм першим ходом. Будь-хід Петі «10 + 1 = 11» або «10 * 2 = 20» веде в початкову виграшну позицію Ваню, який, подвоївши кількість каменів в купі, отримує 22 або 40, що більше 21 і Ваня виграє
Питання 2. Для того щоб Петя гарантовано виграв другим ходом, тобто виявився в позиції max0. після ходу Вані, йому необхідно своїм першим ходом «посадити Ваню в яму». Зрозуміло, що таких позицій може бути дві. значення яких знаходимо зворотним ходом і обов'язково перевіряємо ...
Перша підозріла позиція «10-1 = 9»
S = 9. Перевіримо дану позицію на гарантованість перемоги!
Якби Петя грав в піддавки, він би зробив хід «9 * 2 = 18», але йому потрібно виграти, тому даний хід відкидаємо. Залишається тільки «9 + 1 = 10», і Ваня виявляється в «ямі» - що призводить Петю до виграшу другим ходом незалежно від того, як сходить Ваня!
Друга "підозріла позиція" 10/2 = 5
S = 5. Перевіримо дану позицію на гарантованість перемоги! Хід «5 + 1 = 6», затягує гру, тому його не розглядаємо (відкидаємо)
Залишається тільки «5 * 2 = 10», і Ваня виявляється в «ямі» - що призводить Петю до виграшу другим ходом незалежно від того, як сходить Ваня!
При S = 5 і 9 Петя не може виграти першим ходом, але він може виграти другим ходом і для цього йому досить з позиції S = 5 зробити хід «5 * 2 = 10», тим самим відправити Ваню в початкову програшну позицію або з позиції S = 9 відправити його в ту ж позицію ходом «9 + 1 = 10»
Питання 3. Ваня повинен виграти, отже, він повинен опинитися на вершині max0, це означає, що Петя неодмінно повинен виявитися в min0, куди його «посадить» Ваня з max1, а нам залишається знайти такі позиції, з яких би Петя однозначно потрапляв в max1
Знаходимо «підозрілі» позиції, які можуть привести Петю в max1 за допомогою того ж самого зворотного ходу:
9-1 = 8
9/2 =? 9 на 2 не ділиться - відпадає
5-1 = 4
5/2 =? 5 на 2 не ділиться - відпадає
Знаходимо, що таких «підозрілих» позицій всього дві, але їх ще потрібно перевірити!
S = 8. Перевіримо дану позицію на гарантованість програшу Петі!
Хід Петі 8 + 1 = 9 і Ваня виграє другим ходом
Хід Петі 8 * 2 = 16 і Ваня виграє першим ходом
S = 4. Перевіримо дану позицію на гарантованість програшу Петі!
Хід Петі 4 + 1 = 5 і він би програв, але з цієї позиції Петі вигідний хід 4 * 2 = 8, тим самим Ваня потрапляє в «яму» і програє. Але нам потрібно знайти виграшну стратегію Вані, тому позицію S = 4 виключаємо з претендентів і отримуємо остаточну «картину»:
3. У позиції S = 8 - у Вані немає стратегії, яка дозволить йому гарантовано виграти першим ходом, оскільки його перемога залежить від ходу Петі, тому у Вані є стратегія виграти або першим, або другим ходом: Якщо Петя вибирає хід «+1» , в купі стає 9 каменів і Ваня виграє на 2-му ході (див. відповідь на питання 2). Якщо Петя вибирає хід «* 2», Ваня виграє першим ходом, подвоївши число каменів в купі.
Отриманий нами вище малюнок можна легко перемалювати в дерево гри, попередньо позначаючи червоними лініями програшні ходи (товста лінія - «короткий хід» або «+1», а тонка - «довгий» або «* 2») і зеленими - виграшні. (Червоні товсті лінії можна намалювати горбами вгору, що буде співпадати з напрямом «коротких» гілок дерева гри)
Остаточно стратегічна картинка виграшу Петі може виглядати так:
З іншими методами вирішення завдань даного типу можна познайомитися тут - показати