6-я олимпиада им. Шалтая Смагулова, 7 класс, 2 тур

Вершины 101-угольника нужно покрасить в несколько цветов так, чтобы любые две вершины, не соединенные стороной, были разного цвета. Какое наименьшее количество цветов для этого понадобится?

Комментарий/решение

Представим 101 угольник как связный граф, тогда если раскрасить одну вершину в некий цвет, то она не может не быть связана ребром с вершиной не её цвета потому что иначе их можно будет соединить противоречие, поэтому каждый цвет будет стоять парой в сумме их будет 101/2=50.5 округляем в большую сторону будет 51. Допустим меньше, тогда каких то цвета по принципу Дирихле точно будет 3 и тогда какие 2 из них можно будет соединить противоречие

Отв: 51 цвет

Два одинаковых цвета может быть 2 , и то если они идут подряд, значит всего будет 50 пар + 1 вершина другого цвета от других 50. Значит всего надо 50+1=51 вершин

Пусть есть три вершины одного цвета. Тогда любая пара из этих вершин является концами одной из сторон 101-угольника. Однако это невозможно, так как если, скажем, A и B является стороной 101- угольника и B и C являются другой стороной 101, угольника, то между B и C еще 98 вершин и 99 сторон. Следовательно, количество вершин каждого цвета не более 2, значит цветов не менее чем $\frac{101}{2}$ то есть не менее 51. Окраска в 51 цвет очевидно вытекает из рассуждений: две вершины одного цвета обязательно должны быть соседними, таким образом 100 вершин закрасим в 50 цветов (две вершины одного цвета, две другого и так далее), а оставшуюся вершину закрасим в 51-ый цвет.