ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116270
Темы:    [ НОД и НОК. Взаимная простота ]
[ Четность и нечетность ]
[ Раскраски ]
[ Процессы и операции ]
Сложность: 3+
Классы: 8,9,10,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).

Замечания

4 балла

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

олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
Задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .