Олимпиадные задачи по теме «Комбинаторика» для 6-10 класса - сложность 3 с решениями

В каждой вершине выпуклого многогранника сходятся три грани. Каждая грань покрашена в красный, жёлтый или синий цвет.

Докажите, что число вершин, в которых сходятся грани трёх разных цветов, чётно.

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

В стране 100 городов, между каждыми двумя городами осуществляется беспосадочный перелёт. Все рейсы платные и стоят положительное (возможно, нецелое) число тугриков. Для любой пары городов А и Б перелёт из А в Б стоит столько же, сколько перелёт из Б в А. Средняя стоимость перелёта равна 1 тугрику. Путешественник хочет облететь какие-нибудь <i>m</i> разных городов за <i>m</i> перелётов, начав и закончив в своём родном городе. Всегда ли ему удастся совершить такое путешествие, потратив на билеты не более <i>m</i> тугриков, если

  а)  <i>m</i> = 99;

  б)  <i>m</i> = 100?

На кольцевой дороге через равные промежутки расположены 25 постов, на каждом стоит полицейский. Полицейские пронумерованы в каком-то порядке числами от 1 до 25. Требуется, чтобы они перешли по дороге так, чтобы снова на каждом посту был полицейский, но по часовой стрелке за номером 1 стоял номер 2, за номером 2 стоял номер 3, ..., за номером 25 стоял номер 1. Докажите, что если организовать переход так, чтобы суммарное пройденное расстояние было наименьшим, то кто-то из полицейских останется на своём посту.