Учащиеся 57-й школы решили провести чемпионат по мини-футболу. Так как ворота на школьном дворе разного размера, то игроки хотят составить расписание игр так, чтобы:
  1) Каждая команда сыграла с каждой ровно по одному разу.
  2) Каждая команда чередовала свои игры – то на плохой стороне, то на хорошей стороне двора.
    а) Удастся ли это сделать, если в турнире принимают участие 10 команд?
    б) Можно ли при этом составить расписание так, чтобы каждый день каждая команда играла ровно одну игру?

   Решение

Тема:    [ Шахматная раскраска ]

Сложность: 5 Классы: 8,9

Прислать комментарий

Условие

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

Решение

Раскрасим узлы клетчатой бумаги в шахматном порядке (рис.). Так как концы любого единичного отрезка разноцветны, то ломаная с одноцветными концами содержит нечетное число узлов, а с разноцветными — четное. Предположим, что из всех узлов границы (кроме вершин квадрата) выходят ломаные. Докажем, что тогда все ломаные вместе содержат четное число узлов. Для этого достаточно доказать, что число ломаных с одноцветными концами четно. Пусть на границе квадрата расположено 4m белых и 4n черных узлов (вершины квадрата не учитываются). Обозначим число ломаных, у которых оба конца белые, через k. Тогда имеется 4m - 2k ломаных с разноцветными концами и  [4n - (4m - 2k)]/2 = 2(n - m) + k ломаных с черными концами. Поэтому ломаных с одноцветными концами будет k + 2(n - m) + k = 2(n - m + k) — четное число. Остается заметить, что квадратный лист бумаги размером 100×100 клеток содержит нечетное число узлов. Поэтому ломаные, содержащие четное число узлов, не могут проходить через все узлы.

Источники и прецеденты использования