Разделы 
Дополнительно
Задача по математике - 3767
2019-06-16 
Дан квадратный лист клетчатой бумаги $100 \times 100$ клеток. Проведено несколько несамопересекающихся ломаных, идущих по сторонам клеток и не имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами выходят на его границу. Докажите, что кроме вершин квадрата найдется узел (внутри или на границе), не принадлежащий ни одной ломаной.
Решение:
Раскрасим все узлы в шахматном порядке в черный и белый цвет. На границе лежат $4 \cdot 99$ узлов (не считая вершин) - поровну черных и белых. Пусть все они служат концами ломаных, Тогда имеется одинаковое количество ломаных с двумя белыми и двумя черными концами. Поэтому общее количество белых и черных узлов, лежащих на ломаных внутри доски, также одинаково. (На ломаных с белыми концами на один черный узел больше, на ломаных с черными - на один белый.) Но всего внутри доски 99 - нечетное число - узлов, так что по крайней мере один из них не лежит на ломаной.
Дан квадратный лист клетчатой бумаги $100 \times 100$ клеток. Проведено несколько несамопересекающихся ломаных, идущих по сторонам клеток и не имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами выходят на его границу. Докажите, что кроме вершин квадрата найдется узел (внутри или на границе), не принадлежащий ни одной ломаной.
Решение:
Раскрасим все узлы в шахматном порядке в черный и белый цвет. На границе лежат $4 \cdot 99$ узлов (не считая вершин) - поровну черных и белых. Пусть все они служат концами ломаных, Тогда имеется одинаковое количество ломаных с двумя белыми и двумя черными концами. Поэтому общее количество белых и черных узлов, лежащих на ломаных внутри доски, также одинаково. (На ломаных с белыми концами на один черный узел больше, на ломаных с черными - на один белый.) Но всего внутри доски 99 - нечетное число - узлов, так что по крайней мере один из них не лежит на ломаной.
