asyan.org
добавить свой файл
1
ЗАДАЧІ НА СТРАТЕГІЮ ГРИ


  1. Двоє гравців по черзі кладуть п'ятикопійчані монети на круглий
    стіл. Монети повинні повністю вміщуватися на столі і не торкатися одна
    одної. Той, кому нікуди покласти монету, програє. Хто за умови дотримання правил гри виграє — той, хто ходить першим, чи той, хто ходить другим?

Розв'язання

Виграє перший, якщо своїм першим ходом він покладе монету в центр стола, а потім робитиме ходи симетрично ходам другого відносно центра стола.


  1. Дано шахівницю 8x8 і прямокутне доміно 1x2. За один хід дозво­ляється накрити дві сусідні клітинки шахівниці так, щоб плитки доміно не перекривались. Програє той, хто не зможе зробити наступного ходу. У котрого з двох гравців є виграшна стратегія?

Розв'язання

Виграє другий гравець, якщо щоразу буде ставити плитку доміно си­метрично відносно центра дошки до плитки, поставленої перед першим гравцем.


  1. Двоє гравців по черзі виймають із ящиків кулі. За один хід кожен
    гравець може брати з будь-якого (тільки одного) ящика довільну кількість
    куль. Виграє той, хто візьме останнім. Як повинен грати перший гравець,
    щоб виграти, якщо в першому ящику 73 кулі, а в другому — 118 куль?

Розв'язання

Першим ходом він має взяти 45 куль із другого ящика, тоді куль в ящи­ках стане порівну. А далі відповідати симетрично на ходи другого гравця.


  1. Ромашка має: а) 12 пелюстків; б) 13 пелюстків. Грають двоє грав­ців. За один хід дозволяється відірвати або одну пелюстку, або дві, що рос­туть підряд. Програє той, хто не може зробити хід. У кого з гравців є ви­грашна стратегія?

Розв'язання

В обох випадках виграє другий. Незалежно від ходу першого гравця другий може після першого ходу залишити два однакові за довжиною ланцюжки з пелюсток, а далі — симетрично повторювати ходи першого.


  1. Є три купки камінців: у першій — 10, у другій — 15, у третій — 20. За один хід дозволяється розбити будь-яку купку на дві менші. Програє той, хто не зможе зробити хід. Хто з двох гравців може забезпечити собі виграш?

Розв'язання

Другий гравець виграє без будь-якої стратегії. Після кожного ходу кількість купок збільшується на 1. У кінці гри їх має стати 45, буде зробле­но 42 ходи. Отже, останній хід зробить другий гравець.


  1. Тура стоїть на лівій кутовій клітинці шахівниці (на полі а1). За
    хід дозволяється пересунути її на будь-яке число клітинок вправо чи на
    будь-яке число клітинок угору. Виграє той, хто поставить туру на протилежну праву верхню кутову клітинку (на поле h8). Хто з двох гравців має виграшну стратегію?

Розв'язання

Виграє другий. Кожним своїм ходом він повертає туру на велику діаго­наль a1-h8. Тому перший гравець своїм ходом завжди виводить туру з цієї діагоналі, отже, і не може її туди поставити, а поле h8 знаходиться саме на цій діагоналі.


  1. У коробці знаходиться 60 сірників. За один хід можна взяти від 1
    до 5 сірників. Програє той, хто не може зробити хід. Хто з двох гравців
    може забезпечити собі виграш?

Розв'язання

Проаналізуємо кінцівку такої гри. Якщо кількість сірників менша ніж 5, то той гравець, чия черга ходити, закінчує гру. Якщо кількість сірників більша за 6, то гра закінчується через два або більше ходів. Якщо ж кількість сірників дорівнює 6, то гравець, чий хід передував цій позиції, точно наступним своїм ходом закінчує гру (для цього на хід суперника в к сірників бере 6-k сірників) Тобто, така позиція є виграшною для цього гравця. Очевидно, що позиції 12, 18, 24 тощо сірників для нього також є виграшними. Отже, початкова позиція виграшна для другого гравця, а його виграшною стратегією є доповнення ним ходів першого гравця до 6 сірників.


  1. Двоє грають у подвійні шахи, тобто всі фігури ходять як і в звичай­них шахах, але кожен із шахістів робить по два ходи підряд. Доведіть, що шахіст, який грає білими фігурами, може грати так, щоб не програти (тобто другий не має виграшної стратегії).

Розв'язання

Припустимо, що твердження задачі неправильне, тобто другий шахіст має виграшну стратегію. Тоді перший гравець теж має виграшну стратегію: перший хід — конем, другий — повернути цього коня назад, а потім першому гравцю треба застосувати виграшну стратегію другого шахіста. Суперечність доводить твердження задачі.


  1. На дошці написано вираз *п8 *п7 *п6 *п5 *n4 *п3 *п2 *. Петрик і Оксана ведуть у таку гру. Вони роблять ходи по черзі, замінюючи одну зірочку «*» на знак «+» або «-». Оксана прагне, щоб здобутий після восьми ходів вираз ділився на 6 для кожного натурального п. Петрик ходить першим. Доведіть, що Оксана може забезпечити собі перемогу незалежно від того, як ходитиме Петрик.

Розв'язання

Зауважимо, що число n5 п = п(п - 1)(п + 1)(п2 + 1) ділиться на 6. Тому Оксані достатньо грати так, щоб числа п8 і n4, п7 і n3, п6 і п2, n5 і n були з різними знаками.


  1. Двоє гравців у запису

a1 sin x + a2 cos 2x + a3 sin 3x + a4 cos 4x +... + a2004 cos 2004x + a2005 sin2005x = 0

по черзі вибирають ще не обрані коефіцієнтна, та замінюють їх будь-якими дійсними числами. Коли всі коефіцієнти замінено, то перший гравець вважатиметься переможцем, якщо здобуте рівняння має корінь на інтервалі . В противному разі переможцем оголошується його суперник. Хто

з двох гравців може забезпечити собі перемогу в цій грі?

Розв'язання

Виграє перший гравець. Першим ходом він довільно замінює коефі­цієнт а1, а потім, користуючись тим, що серед решти коефіцієнтів їх кількість з парними і непарними номерами є число парне, забезпечує собі можливість зробити останнім заміну серед коефіцієнтів а2, a4, ..., а2004. Тому перший гравець може зробити так, щоб f(0) = 0, оскільки f(0) = а2 + а4 + ... + а2004.


  1. Миколка та Сергійко грають у гру, по черзі записуючи цілі числа в клітинки таблиці розмірами 7x9 (7 рядків, 9 стовпчиків). Першим робить хід Миколка. За один хід записується одне число у вільну клітинку. Гра продовжується, поки вони не заповнять числами всю таблицю. Потім підраховуються значення S1, S2, ..., S7, — суми чисел у рядках таблиці. Якщо серед чисел S1, S2, ..., S7 парних більше, ніж непарних, виграє Ми­колка. В противному разі — Сергійко. Хто з двох гравців може забезпечити собі виграш?

Розв'язання

Виграє Миколка. Першим своїм ходом Миколка записує число 1 у центральну клітинку таблиці. Якщо Сергійко запише в певну клітинку число а, то Миколка має записати число а+1 у клітинку, яка є централь­но-симетричною до клітинки, що містить число а. Кожній клітинці пер­шого рядка можна поставити у відповідність клітинку сьомого рядка, що буде центрально-симетричною до неї, і навпаки. Тому перший і сьомий рядки таблиці будемо називати центрально-симетричними. Клітинки цих рядків можна розбити на дев'ять центральносиметричних пар. Сума чисел у кожній парі таких клітинок буде непарною, оскільки a+(a+1) = 2a+l. Тоді числом, S1+S2 – непарне. Отже, одна із сум S1 або S2 є парною. Аналогічно числа S2+S6, S3+S5 також будуть непарними, і в кожній з цих пар одна сума буде парною. Якщо Сергійко виконує хід у певну клітинку четвертого рядка, то Миколка у відповідь записує до­вільне число в будь-яку вільну клітинку цього ж четвертого рядка. Кліти­нок у рядку непарна кількість, тому останню вільну клітинку четвертого рядка буде заповнювати Миколка, тобто він у змозі забезпечити парність суми S4. Отже, чотири із семи чисел S1, S2, ..., S7 будуть парними.


  1. Двоє по черзі знімають зі столу фішки. За один раз дозволяється зняти зі столу 1, 10 або 11 фішок. Виграє той, хто зніме останню фішку. Перед початком гри на столі було 40 фішок. Хто виграє за умови дотри­мання правил гри — той, хто починає гру, чи його суперник?

Розв'язання

Будемо розв'язувати задачу з кінця. Якщо припустити, що на столі залишилася одна фішка, то ситуація є виграшною для того гравця, чия черга ходити. Він бере цю фішку й виграє. Якщо залишилось дві фішки – ситуація програшна для того, чия черга ходити. Будемо записувати числа 1, 2, 3, ... зі знаками «+» або «-» залежно від того, виграшною чи про­грашною є дана ситуація для гравця, який робить хід. Тоді якщо гравець певним ходом (знявши 1, 10 або 11 фішок) може створити програшну си­туацію для свого суперника (бо його черга ходити), то для нього початко­ва ситуація є виграшною. Тепер можна з'ясувати по черзі для всіх чисел 1, 2, 3, ... виграшною чи програшною є ситуація для даної кількості фішок на столі. Для чисел від 1 до 9 знаки «+» або «-» розставляються по черзі. Числа 10, 11, 12, 13. ..., 19 є виграшними, 20 - програшним (будь-яким ходом можна досягнути лише чисел 9, 10 і 19, які є виграш­ними для суперника). Помітивши закономірність (знаки через 20 чисел повторюються), можемо легко продовжити розставляння знаків. Неваж­ко переконатися, що число 40 має знак «-», тобто за правильної гри дру­гий гравець виграє.


  1. Дано дерев'яну дошку в клітину розміром пп. Двоє гравців по черзі роблять пилкою розпили довжиною 1, що йдуть по лініях сітки.
    Кожний розпил має починатися з вузла сітки, на краю дошки або на вже
    зробленому розпилі. Програє той гравець, після ходу якого дошка розпа­дається на дві частини. Хто виграє за правильної гри: той, хто починає, чи його суперник?

Розв'язання

Нехай гравці роблять розпили, після яких дошка не розпадається. Кожний новий розпил, очевидно, повинен досягати ще одного з (n – 1)2 внутрішніх «вузлів» дошки (вершини квадратиків). З іншого боку, якщо до якогось з таких вузлів розпили не дійшли, то можна зробити ще один розпил так, щоб дошка не розпалася: провести від такого вільного вузла лінію до якогось розпилу по сторонах квадратиків і продовжити згаданий розпил на одиницю по цій лінії. З цих міркувань випливає, що за пра­вильної гри всього до розпадання дошки можна зробити рівно (n – 1)2 роз­пилів незалежно від того, в якому порядку вони виконувались. Тому ((n – 1)2 + 1) хід буде програшний. Отже, при парному п виграє перший гра­вець, а при непарному— другий.


  1. Двоє гравців по черзі ставлять на клітинки шахової дошки 2525 фішки, один — білого, а другий — чорного кольорів. Кожна нова фішка ставиться на вільну клітинку, забороняється лише ставити фішку на таку клітинку, де на всіх сусідніх із нею клітинках уже стоять фішки цього кольору (сусідніми вважають клітинки, які мають спільну сторону). Про­ грає той, хто не може зробити свій черговий хід. Хто виграє за умови правильної гри — перший чи другий?

Розв'язання

Виграє перший гравець. Справді, виділи­мо одну із клітинок, а решту розіб'ємо на частини 12. Розглядаємо такий випадок: правий верхній кут дошки покрито квадра­том розмірами 1x1, а решту дошки — прямо­кутниками розмірами 12. Перший гравець першу фішку ставить у виділену клітинку, а кожну наступну — у вільну клітинку тієї частини розміром 12, в яку попереднім хо­дом поставив свою фішку другий гравець. Очевидно, що все це завжди можна зробити.


  1. На столі стоять п'ять коробок, позначених номерами 0, 1, 2, 3, 4.
    У коробках з номерами 1, 2, 3, 4 знаходяться відповідно p1, р2, р3, р4 сірни­ків. По черзі кожний із двох гравців бере кілька сірників з якоїсь коробки з додатним номером та перекладає їх у коробку, номер якої на одиницю менший. Виграє той гравець, після ходу якого всі сірники будуть у нульовій коробці. Хто виграє за умови правильної гри — той, хто починає гру, чи його суперник?

Розв'язання

Доведемо, що у випадку р1 = р2 Другий гравець завжди може виграти. Його відповідь на можливі ходи першого гравця видно з наступної схеми:

0 + k, p1k, p2, p4) → (p0 + k, р1 - k, р2 + k, р3 - k, р4)

(р0, p1 + k, р2 k, р4) → (р0 + k, р1, р2 k, р3, р4)

(р0, p1, р2 + k, р3 k, р4) → (р0 + k, р1k, р2 + k, р3k, р4)

(р0, p1, р2, р3 + k, р4k) → (р0, р1, р2 + k, р3, р4k)

Таким чином, перший гравець своїм ходом обов'язково порушує рівність сірників у першій та третій коробках, а другий завжди має мож­ливість своїм наступним ходом цю рівність відновити. Оскільки в за­ключній позиції кількість сірників у першій і третій коробках однакова (дорівнює 0), то другий гравець за такої стратегії завжди виграє. Якщо р1 ≠ р2, то перший гравець своїм першим ходом завжди може вирівняти кількість сірників у першій та третій коробках, і ми отримаємо про­аналізовану вище ситуацію зі зміною номерів гравців. Отже, у випадку р1 = р3 виграє другий гравець, в усіх інших випадках – перший.


  1. Двоє гравців по черзі вписують у клітинки дошки розмірами пп по одному натуральному числу згідно з такими правилами: перший гра­вець має право записати в клітинку найбільший спільний дільник номера рядка та стовпчика, на перетині яких знаходиться дана клітинка, а другий має право записати в клітинку найбільше спільне кратне номера рядка та номера стовпчика, на перетині яких знаходиться клітинка. Після запов­нення дошки кожне число ділиться на номер стовпчика, в якому воно розташоване, а потім підраховується добуток усіх здобутих чисел. Якщо цей добуток є меншим за 1, то переможцем вважається перший гравець, в іншому випадку — другий. Хто з гравців може забезпечити собі перемо­гу — той, хто починає гру, чи його суперник?

Розв'язання

Доведемо, що другий гравець може забезпечити собі перемогу. Якщо число я парне, то він має на кожний хід першого гравця відповідати ходом у симетричну відносно головної діагоналі клітинку (на хід у клітинку, яка розташована на головній діагоналі, потрібно відповідати довільним ходом також на цю діагональ). Якщо число я є непарним, то другий гравець у ви­падку, коли можна зробити відповідні ходи, має діяти так само, як описано вище, а коли потрібний хід не виявляється можливим, потрібно просто зро­бити будь-який хід. Оскільки, як відомо, для будь-яких натуральних чисел а і b має місце рівність HCД(a;b)∙НCK(a;b)=ab, то добуток всіх чисел у таб­лиці дорівнюватиме (п!)n. Очевидно, що після ділення дістанемо в добутку число 1, що й означає перемогу другого гравця.

Задачі для самостійного розв'язування

  1. Двоє по черзі розламують шоколадну плитку 68. За один хід доз­воляється зробити прямолінійний розлом будь-якого зі шматків вздовж заглиблення. Програє той, хто не зможе зробити наступного ходу. У кого з гравців є виграшна стратегія?




  1. Є дві купки камінців: в одній — 30, у другій — 20. Двоє по черзі бе­руть будь-яку довільну кількість камінців, але тільки із однієї купки. Про­грає той, кому немає чого брати. У кого з гравців є виграшна стратегія?




  1. У коробці лежить 300 сірників. За один хід дозволяється взяти з коробки не більше ніж половину сірників, які там знаходяться. Виграє той, хто бере останній сірник. Хто з двох гравців може забезпечити собі виграш?




  1. Гра починається з числа 2004. За хід дозволяється змінити число на один з його дільників. Програє той, хто дістав нуль. У кого з двох гравців
    є виграшна стратегія?




  1. Є дошка розміром: а) 1991; б) 1992. За один хід дозволяється зафарбувати одну або декілька клітинок, що утворюють квадрат. Зафарбову­вати клітинки двічі не можна. Виграє той, хто зафарбує останню клітинку.
    Хто з двох гравців має виграшну стратегію?




  1. Двоє по черзі викреслюють числа від 1 до 27, поки не залишаться два числа. Якщо їх сума ділиться на 5, то виграє перший, а якщо ні — то другий. Хто виграє за умови правильної гри?




  1. На дошці записано рівність *х2 + *х + * = 0. Перший називає три довільних числа, а другий розставляє їх на свій вибір замість зірочок. Чи може перший гравець домогтися, щоб здобуте рівняння мало обидва раціональні корені? Які числа йому слід назвати?




  1. Є т та п сірників у двох купках. Можна брати по одному сірникові з кожної купки або скільки завгодно з однієї з них. Виграє той, хто візьме останній сірник. Як закінчиться гра двох осіб, які роблять ходи по черзі, не допускаючи при цьому помилок, залежно від т та n?




  1. У 50-ти коробках є 100 цукерок. Дівчинка і хлопчик по черзі беруть
    по одній цукерці. Чи може хлопчик домогтися того, щоб дві останніх цу­керки лежали в одній коробці?




  1. У ряд виписані послідовні натуральні числа від 1 до 2000. Двоє по черзі вписують між цими числами знак додавання «+» або множення «» (усього вписано 1999 знаків). Якщо кінцеве значення цього виразу ділить­ся на 3, то виграє той, хто ходив першим. У противному разі виграє його суперник. Хто з гравців може забезпечити собі виграш? Знайдіть для нього виграшну стратегію.




  1. З паперу в клітинку вирізано квадрат розмірами 20042004, з якого потім вирізано одну кутову клітинку. Два гравці по черзі відрізають від цієї фігури квадрати довільних розмірів, які відкидаються. Програє той гра­вець, після ходу якого фігура, що залишилася, є прямокутником довільно­го розміру або ця фігура розпалася на частини (якщо частини мають хоча б одну спільну вершину, вони не розпадаються). Хто з гравців може забез­печити собі виграш?




  1. Член журі та учасник олімпіади грають у таку гру: кожен з них бере по черзі сірники з купки, в якій перед початком було 1995 сірників. За своїм ходом гравець може взяти 1 або 2 сірники (але не більше, ніж за своїм попереднім ходом). Виграє той, хто бере сірники останнім. Почесне право першого ходу надається учаснику олімпіади. Хто виграє, якщо обидва гравці гратимуть найкращим чином?




  1. На столі лежать п цукерок. Петрик та Миколка по черзі беруть зі
    столу кілька цукерок за таким правилом: той з хлопців, хто підходить до
    столу першим, бере одну цукерку, а той, хто підходить до столу другим, —
    і цукерок, де число і є дільником двійки; той хто підходить до столу третім,
    може взяти Ii цукерок, де і є дільником трійки, і т. д. Переможцем вважається той з хлопців, кому дістанеться остання цукерка. Хто з них може забезпечити собі перемогу, якщо Петрик бере цукерки першим?




  1. Двоє гравців по черзі записують по од­ному натуральному числу від 1 до 7 у кружеч­ки (рис), причому кожне з чисел повинно бути записано тільки один раз. Після запов­нення всіх кружечків обчислюються суми чи­сел уздовж кожної з прямих, що зображено на рисунку. Якщо серед здобутих сум є при­наймні три однакові, то переможцем виз­нається перший гравець. У противному разі — другий. Хто з гравців може забезпечити собі перемогу?




  1. На дошці розміром пп (п > 2) у лівій нижній кутовій клітинці стоїть фішка. За один хід гравець може перемістити її на одну клітинку праворуч, або на одну клітинку вгору, або на одну клітинку по діагоналі праворуч вгору. Двоє гравців по черзі роблять такі ходи, а переможцем вважається той, хто поставив фішку в правий верхній кут дошки. Хто з двох гравців може забезпечити собі перемогу?




  1. Двоє гравців по черзі записують у рядок цілі числа таким чином:
    перший записує довільне число а1, другий довільне число а2, і далі кожен
    по черзі записує число, що дорівнює сумі попередніх. Гра закінчується
    тоді, коли в здобутій послідовності а1, а2, а3, ... вперше зустрінуться такі
    значення індексів і, j (ij), що числа ai aj та аi+1 – аj+1, ділитимуться на
    1999. Переможцем вважається той, хто зробить останній хід. Хто з гравців
    може забезпечити собі виграш?




  1. Троє грають у таку гру. Кожний по черзі кладе на круглий стіл п'ятикопійчані монети, монети можуть торкатися, але не повинні накла­датися одна на одну. Програє той, чия монета не вміститься на столі. До­ведіть, що перший і третій (за порядком ходів) гравці можуть змовитися так, що другий гравець завжди програватиме.




  1. Є дві купки сірників: а) 101 сірник і 201 сірник; б) 100 сірників і 201
    сірник. За хід дозволяється зменшити кількість сірників в одній з купок на число, що є дільником кількості сірників у другій купці. Виграє той, після чийого ходу сирників не залишиться. Хто з двох гравців може виграти?




  1. Король за хід може поставити по хрестику в будь-які дві вільні
    клітинки нескінченного аркуша паперу. Міністр за хід може поставити нулик у довільну вільну клітинку. Чи може король поставити 100 хрестиків у ряд?