На клетчатой бумаге изобразите шестиугольник, который можно одним прямолинейным разрезом разделить на четыре равных треугольника. Покажите, как это можно сделать. (Вершины многоугольника должны располагаться в узлах сетки, но стороны и разрез не обязательно проводить по линиям сетки.)

   Решение

Тема:    [ Теория игр (прочее) ]

Сложность: 4 Классы: 8,9,10,11

Прислать комментарий

Условие

В куче $n$ камней, играют двое. За ход можно взять из кучи количество камней, либо равное простому делителю текущего числа камней в куче, либо равное 1. Выигрывает взявший последний камень. При каких $n$ начинающий может играть так, чтобы всегда выигрывать, как бы ни играл его соперник?

Решение

Стратегия: каждый раз оставлять в куче кратное 4 число камней: при $n = 4k + 1$ надо взять один камень, при $n = 4k + 2$ — два камня; при $n = 4k + 3$ надо взять $p$ камней, где $p$ — простой делитель числа $n$ вида $4q + 3$ (такой есть, иначе все простые делители $n$ имеют вид $4m+1$, а произведение чисел такого вида тоже имеет такой вид и не равно $4k+3$).

Противник из кучи с кратным 4 числом камней не может взять число камней, кратное 4 (это будет не простое число), поэтому начинающий и дальше может играть по стратегии.

Ответ

при $n$, не кратном 4.

Источники и прецеденты использования