Олимпиадные задачи из источника «глава 23. Делимость, инварианты, раскраски» - сложность 4 с решениями

Плоскость раскрашена в семь цветов. Обязательно ли найдутся две точки одного цвета, расстояние между которыми равно 1?

Дан квадратный лист клетчатой бумаги размером100×100 клеток. Проведено несколько несамопересекающихся ломаных, идущих по сторонам клеток и не имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами обязательно выходят на границу. Докажите, что кроме вершин квадрата найдется еще узел (внутри квадрата или на границе), не принадлежащий ни одной ломаной.

Выпуклый многоугольник разрезан на<i>p</i>треугольников так, что на их сторонах нет вершин других треугольников. Пусть<i>n</i>и<i>m</i>— количества вершин этих треугольников, лежащих на границе исходного многоугольника и внутри его. а) Докажите, что<i>p</i>=<i>n</i>+ 2<i>m</i>- 2. б) Докажите, что количество отрезков, являющихся сторонами полученных треугольников, равно 2<i>n</i>+ 3<i>m</i>- 3.

Многоугольник разрезан на несколько многоугольников. Пусть <i>p</i> — количество полученных многоугольников,<i>q</i> — количество отрезков, являющихся их сторонами,<i>r</i> — количество точек, являющихся их вершинами. Докажите, что<i>p</i>-<i>q</i>+<i>r</i>= 1.

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