Олимпиадная задача по математике: закрашивание камней в круге, 8–11 класс, теория чисел
Задача
По кругу лежат 100 белых камней. Дано целое число k в пределах от 1 до 50. За ход разрешается выбрать любые k подряд идущих камней, первый и последний из которых белые, и покрасить первый и последний камни в чёрный цвет. При каких k можно за несколько таких ходов покрасить все 100 камней в чёрный цвет?
Решение
При k = 1 покрасить все камни, очевидно, можно.
Пусть k > 1. Пометим произвольный камень. Затем пометим камень, (k–1)-й по часовой стрелке после помеченного и будем повторять эту процедуру, пока не вернёмся к исходному камню. Каждые два последовательно помеченных камня будут концами ряда из k подряд идущих камней. Поэтому помеченные камни можно перекрашивать только в паре с помеченными. Стало быть, их удастся перекрасить тогда и только тогда, когда их чётное число, и это число, как нетрудно проверить, равно 
. Осталось заметить, что все 100 камней разбиваются на НОД(100, k–1) наборов помеченных.
Итак, нас "не устраивают" те и только те k, при которых k – 1 кратно 4.
Ответ
При всех k от 1 до 50, кроме k = 4m + 1 (m = 1, 2, ..., 12).
Чтобы оставлять комментарии, войдите или зарегистрируйтесь