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

Проект МЦНМО
при участии
школы 57
Задача 111846
Темы:    [ Процессы и операции ]
[ Разбиения на пары и группы; биекции ]
[ Вспомогательная раскраска (прочее) ]
[ Четность и нечетность ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Петров Ф.

В каждой вершине выпуклого 100-угольника написано по два различных числа. Докажите, что можно вычеркнуть по одному числу в каждой вершине так, чтобы оставшиеся числа в каждых двух соседних вершинах были различными.


Решение

  Пусть в каждой вершине стоят одни и те же числа a и b; тогда достаточно оставить в вершинах с чётными номерами число a, а в вершинах с нечётными – число b.
  Пусть это не так. Пронумеруем вершины по порядку от 1 до 100 так, чтобы в вершинах 1 и 100 стояли разные пары чисел. Покрасим все поставленные числа в красный и синий цвета следующим образом. Числа в первой вершине окрасим в разные цвета. Пусть в k-й вершине числа a и b окрашены в красный и синий цвета соответственно. Тогда в (k+1)-й вершине можно покрасить числа так, чтобы одноцветные числа в k-й и (k+1)-й вершинах различались. Таким образом мы покрасим все числа; при этом в каждой паре соседних вершин, кроме  (1, 100),  одноцветные числа будут различны.
  Рассмотрим вершины 1 и 100. Если в них равны красные числа и равны синие числа, то в этих вершинах стоит одна и та же пара чисел, что не так.
  Пусть синие числа в этих вершинах различны. Тогда, стерев во всех вершинах красные числа, мы получим требуемое.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 5
Класс
Класс 11
задача
Номер 07.5.11.5
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 5
Класс
Класс 9
задача
Номер 07.5.9.5

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

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