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