№ 15.29 Алгебра = № 31.29 Математика
Два гравці по черзі беруть з купки камінці. За правилами гри дозволяється за один хід брати 1, 2, 4, 8, … (будь-який степінь двійки) камінців. Виграє той, хто візьме останній камінець. Хто переможе в цій грі за правильної стратегії, якщо початкова кількість камінців у купці дорівнюватиме: 1) 2016; 2) 2017?
Розв'язок:
Проаналізуємо виграшні позиції, починаючи з кінця гри. Нехай N – кількість камінців у купці. Перебираючи варіанти для малих N, нескладно побачити, що програшними для першого гравця є числа 3,6,9,12.... а останні числа є виграшними. При цьому стратегія гри другого гравця полягає в тому, щоб весь час залишати своєму супернику число камінців, кратні 3. Після цього, при будь–якому ході суперника, число камінів в купці не може залишатися кратним 3, а, отже, не може залишитися і 0 камінців.
1. N = 2016. Оскільки 2016 – число кратне 3, то при правильній стратегії виграє другий гравець.
2. N = 2017. Якщо перший гравець візьме один камінець, то в купці залишиться 2016 камінців.
Оскільки 2016 – число, кратне 3, то для другого гравця – це програшна ситуація при правильній стратегії першого гравця.
Відповідь:
1. переможе другий гравець;
2. переможе перший гравець (за умови правильної стратегії).