3. Применение мми в задачах на делимость

Пример 1. Докажите, что .

Решение.

1. При имеем: . Но , а это означает истинность нашего утверждения при .

2. Предположим, что это утверждение истинно при , т.е. что .

3. Докажем, что тогда оно будет истинно и при , т.е. что , или .

4. Действительно, .Полученная сумма делится на 133, т.е. утверждение истинно и при .

По принципу математической индукции наше утверждение доказано для всех .

Пример 2. Докажите, что .

Решение.

1. При имеем: , . Значит, наше утверждение истинно при .

2. Предположим, что это утверждение истинно при , т.е. что .

3. Докажем, что тогда оно будет истинно и при , т.е. что , или .

4. Действительно,-------------------------------------------------------------

По принципу математической индукции наше утверждение доказано для всех .

4. Применение мми в геометрических задачах

П ример 1. Пусть на плоскости даны точек: A, B, C, D … . Соединим некоторые пары этих точек линиями так, что никакие линии не имеют общих точек, отличных от A, B, C, D … . Эти линии задают разбиение плоскости на несколько областей. Назовем точки A, B, C, D … вершинами получившейся сети, линии – ее ребрами. Число ребер обозначим через , число областей (включая бесконечную область) – через , а число вершин – через (например, для сети, изображенной на рисунке 1, , , ). Сеть называют связной, если из каждой ее точки можно перейти в любую другую, двигаясь лишь по ребрам сети (например, сеть на рисунке 1 связна, а на рисунке 2 несвязна). Найдем зависимость между в случае связной цепи.

Решение.

Я сно, что при из любой вершины связной сети выходит хотя бы одно ребро. Вершины, из которых выходит только одно ребро, назовем концевыми (вершина E на рисунке 1). Если сеть состоит из сторон n-угольника, то , а (контур многоугольника делит плоскость на две области). Поэтому выполняется равенство . Это равенство сохранится, если внутри многоугольника взять точку и соединить ее со всеми вершинами (рисунок 3) – получится областей, вершин и ребер, а . Сохранится равенство и в случае, когда из некоторых вершин выходят «висячие» ребра (например, ребро DE на рисунке 1) – каждое такое ребро добавляет 1 и в число ребер, и в число вершин, не меняя числа областей, а потому не меняя и значения выражения .

Сделанные наблюдения приводят к гипотезе, что верно следующее утверждение: для любой связной сети на плоскости имеет место равенство . Это утверждение называется теоремой Эйлера.

Пример 2. Докажем, что различных точек, лежащих на прямой, делят ее на интервалов (из которых два интервала бесконечны).

Решение.

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

Итак, наше утверждение истинно при , а из его истинности при вытекает, что оно истинно и при . Тем самым доказано, что оно истинно при всех .