6-я олимпиада им. Шалтая Смагулова, 7 класс, 2 тур
101-бұрыш берілген. Оның төбелері, кез келген қабырғамен қосылмаған екі төбе әртүрлі түсті болатындай, бірнеше түстермен боялған болуы керек. Бұл үшін кем дегенде неше түс керек болады?
посмотреть в олимпиаде
Комментарий/решение:
Представим 101 угольник как связный граф, тогда если раскрасить одну вершину в некий цвет, то она не может не быть связана ребром с вершиной не её цвета потому что иначе их можно будет соединить противоречие, поэтому каждый цвет будет стоять парой в сумме их будет 101/2=50.5 округляем в большую сторону будет 51. Допустим меньше, тогда каких то цвета по принципу Дирихле точно будет 3 и тогда какие 2 из них можно будет соединить противоречие
Отв: 51 цвет
По сути, все что надо заметить, это то что n-угольник надо делить по полам (если будет остаток, то округлить до следуещего целого числа).
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.