Question

Два игрока играют в следующую игру. Перед ними лежит кучка из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Решить надо спомощью ТАБЛИЦЫ​

Answer 1

Ответ:

Первый выигрывает при правильной игре

Объяснение:

Состояние "начинающий проигрывает" (НП): выражается формулой: 1 + 4 * n, где n - натуральное число >= 0

или 1, 5, 9 ...

Первому игроку нужно перевести игру в состояние "НП", для этого нужно взять один камень.

Answer 2

Для решения этой задачи с помощью таблицы можно использовать метод динамического программирования. Создадим таблицу размером 7x2, где каждая строка представляет количество камней в кучке (от 0 до 6), а столбцы соответствуют игроку, делающему ход (1 - первый игрок, 2 - второй игрок). Значение в ячейке [i][j] будет равно 1, если игрок j имеет выигрышную стратегию при i камнях в кучке, и 0 в противном случае.

Используя базовые случаи, заполним таблицу:

Количество камней (кучка)	Игрок 1	Игрок 2
0	0	1
1	1	0
2	1	0
3	1	0
4	0	1
5	1	0
6	1	0

Заполнение таблицы происходит следующим образом: для каждого количества камней в кучке проверяем, возможно ли взять 1, 2 или 3 камня и оставить сопернику состояние, в котором он не может выиграть. Если хотя бы один ход приводит к такой ситуации, то игрок, делающий ход, имеет выигрышную стратегию.

Из таблицы видно, что при 6 камнях в кучке первый игрок имеет выигрышную стратегию, так как он может взять 1 камень и оставить второму игроку 5 камней, при которых второй игрок не сможет выиграть. Следовательно, выигрывающий игрок должен начать с хода, взяв 1 камень изначально.

Таким образом, игрок, делающий первый ход, выигрывает при безошибочной игре обоих игроков. Его первый ход должен состоять в том, чтобы взять 1 камень изначально.