Нестандартные задачи на олимпиадах по математике Учебно (стр. 3 из 5)

n –m =10. С другой стороны, оба числа n и m делятся на 3. Получено противоречие.

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

Решение: Пусть Q – квадратный лист бумаги, L(Q) – сумма длин тех сторон клеток, которые лежат внутри его. Тогда L(Q) делится на 4, так как все рассматриваемые стороны разбиваются на четверки сторон, получающихся друг из друга поворотами на 90⁰ и 180⁰относительно центра квадрата.

Если квадрат Q разделен на квадраты Q₁, …, Q_n, то сумма длин отрезков деления равна

L (Q) - L (Q₁) - … - L (Q_n). Ясно, что это число делится на 4, так как числа L(Q), L(Q₁), …, L(Q_n) делится на 4.

4. Инварианты

11. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна черная клетка?

Решение: При перекрашивании горизонтали или вертикали, содержащей k черных и 8-k белых клеток, получится 8-k черных и k белых клеток. Поэтому число черных клеток изменится на (8-k)-k=8-2k, т.е. на четное число. Так как четность числа черных клеток сохраняется, из исходных 32 черных клеток мы не сможем получить одну черную клетку.

12. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки, расположенные внутри квадрата размером 2^х2. может ли при этом на доске остаться ровно одна черная клетка?

Решение: При перекрашивании квадрата 2^х2, содержащего k черных и 4-k белых клеток, получится 4-k черных и k белых клеток. Поэтому число черных клеток изменится на (4-k)-k=4-2k, т.е. на четное число. Так как четность числа черных клеток сохраняется, из исходных 32 черных клеток мы не сможем получить одну черную клетку.

13. Докажите, что выпуклый многоугольник нельзя разрезать на конечное число невыпуклых четырехугольников.

Решение: Предположим, что выпуклый многоугольник M разрезан на невыпуклые четырехугольники M₁,…, M_n. Каждому многоугольнику N поставим в соответствие число f(N), равное разности между суммой его внутренних углов, меньших 180, и суммой углов, дополняющих до 360 его углы, больше 180. Сравним числа А= f(М) и В=f(М₁)+…+ f(М_n). Рассмотрим для этого все точки, являющиеся вершинами четырехугольников М₁…, М_n. Их можно разбить на четыре типа.

1. Вершины многоугольника М. Эти точки дают одинаковые вклады в А и В.

2. Точки на сторонах многоугольника М или М₁.Вклад каждой такой точки в В на

180 больше, чем в А.

3. Внутренние точки многоугольника, в которых сходятся углы четырехугольника,

меньшие 180. Вклад каждой такой точки в В на 360 больше, чем в А.

4. Внутренние точки многоугольника М, в которых сходятся углы четырехугольников, причем один из них больше 180. Такие точки дают нулевые вклады в А и В.

В итоге получаем А<В. С другой стороны, А>0, а В=0. Неравенство А >0 очевидно, а для доказательства равенства В=0 достаточно проверить, что если N-невыпуклый четырехугольник, то f(N)=0. Пусть углы N равны а>b>с>d. У любого невыпуклого четырехугольника ровно один угол больше 180, поэтому f(N)=b+c+d-(360-a)=a+b+c+d-360=0.

Получено противоречие, поэтому выпуклый многоугольник нельзя разрезать на конечное число невыпуклых четырехугольников.

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

Решение: Если хотя бы одно из расстояний между фишками увеличилось бы, то увеличилась бы и сумма всех попарных расстояний между фишками, но сумма всех попарных расстояний между фишками не изменяется при любой перестановке.

15. Квадратное поле разбито на 100 одинаковых квадратных участков, 9 из которых поросли бурьяном. Известно, что бурьян за год распространяется на те и только те участки, у которых не менее двух соседних (т.е. имеющих общую сторону) участков уже поросли бурьяном. Докажите, что поле никогда не зарастет бурьяном полностью.

Решение: Легко проверить, что длина границы всего заросшего бурьяном участка (или нескольких участков) не возрастет. В начальный момент она не превосходит 4*9=36, поэтому в конечный момент она не может быть равной 40.

Следовательно, поле никогда не зарастет бурьяном полностью.

16. Дан выпуклый 2m-угольник А₁…А_2m. Внутри его взята точка Р, не лежащая ни на одной из диагоналей. Докажите, что точка Р принадлежит четному числу треугольников с вершинами в точках А₁,…, А_2m.

Решение: Диагонали разбивают многоугольник на несколько частей. Будем называть соседними те из них, у которых есть общая сторона. Ясно, что из любой внутренней точки многоугольника можно попасть в любую другую, переходя каждый раз только из соседней части в соседнюю. Часть плоскости, лежащую вне многоугольника, также можно считать одной из этих частей. Число рассматриваемых треугольников для точек этой части равно нулю, поэтому достаточно доказать, что при переходе из соседней части в соседнюю четность числа треугольников сохраняется.

Пусть общая сторона двух соседних частей лежит на диагонали (или стороне) PQ. Тогда всем рассматриваемых треугольникам, кроме треугольников со стороной PQ, обе эти части одновременно либо принадлежат, либо не принадлежат. Поэтому при переходе из одной части в другую число треугольников изменяется на k₁-k₂, где k₁-число вершин многоугольника, лежащих по одну сторону от PQ. Так как k₁+k₂=2m-2, то число k₁-k₂ четно.

4. Вспомогательные раскраски в шахматном порядке

17. В каждой клетке доски 5^х5 клеток сидит жук. В некоторый момент все жуки переползают на соседние (по горизонтали или вертикали) клетки. Обязательно ли при этом остается пустая клетка?

Решение: Так как общее число клеток шахматной доски 5^х5 клеток нечетно, то черных и белых клеток не может быть поровну. Пусть для определенности черных клеток будет больше. Тогда жуков, сидящих на белых клетках, меньше, чем черных клеток. Поэтому хотя бы одна из черных клеток остается пустой, так как на черные клетки переползают только жуки, сидящие на белых клетках.

18. Можно ли замостить костями домино размером 1^х2 шахматную доску размером 8^х8, из которой вырезаны два противоположных угловых поля?

Решение: вырезаны поля одного цвета, пусть для определенности черного. Поэтому остается 32 белых и 30 черных клеток. Так как кость домино всегда накрывает одну белую и одну черную клетку, то костями домино нельзя замостить шахматную доску 8^х8 клеток, из которой вырезаны два противоположных угловых поля.

19. Докажите, что доску размером 10^х10 клеток нельзя разрезать на фигурки в форме буквы Т, состоящие из четырех клеток.

Решение: Предположим, что доска 10^х10 клеток разбита на такие фигурки. Каждая фигурка содержит либо 1, либо 3 черные клетки, т.е. всегда нечетное число. Самих фигурок должно быть 100/4=25 штук. Поэтому они содержат нечетное число черных клеток, а всего черных клеток 100/2=50 штук. Получено противоречие.

5. Задачи о раскрасках

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

Решение: Рассмотрим правильный треугольник со стороной 1.

се три его вершины не могут быть разного цвета, поэтому две вершины

имеют один цвет; расстояние между ними ровно 1.

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

Решение: Предположим, что любые две точки, лежащие на расстоянии 1, окрашены в разные цвета. Рассмотрим правильный треугольник АВС со

стороной 1; все его вершины разного цвета. Пусть точка А₁ симметрична А

относительно прямой ВС. Так, как А₁В = А₁С=1, то цвет точки А отличен от

цветов точек В и С, т.е. она окрашена в тот же цвет, что и точка А. Эти рассуждения показывают, что если АА₁= 2, то точки А и А₁ одного цвета. Поэтому все точки окружности радиуса 2 с центром А одного цвета. Ясно, что на этой окружности найдутся две точки, расстояние между которыми ровно 1. Получено противоречие.

С₁ А₁

В

1

А С