Соглашение. В этом листочке буквами $m$, $n$ и $k$ обозначены натуральные числа.

Аксиома. Каждое непустое подмножество множества натуральных чисел имеет наименьший элемент, т. е. элемент, который меньше любого другого элемента этого подмножества.

Задача 1. а) Останется ли предыдущее утверждение верным, если "множество натуральных чисел" заменить на "множество целых чисел"? б) Останется ли предыдущее утверждение верным, если "наименьший элемент" заменить на "наибольший элемент"? Отправить решение

Задача 2. На острове Буяне все страны треугольной формы. Если две страны граничат, то по целой стороне. Докажите, что страны можно раскрасить в 3 цвета так, что соседние по стороне страны будут окрашены в разные цвета. Отправить решение

Принцип математической индукции. Пусть задана последовательность утверждений $A_1, A_2, \dots, A_k, \ldots$, в которой: 1) (база индукции) первое утверждение истинно, 2) (шаг индукции) из истинности утверждения $A_n$ следует истинность утверждения $A_{n+1}$. Тогда все утверждения $A_n$ истинны. (Данным утверждением разрешается пользоваться без доказательства. Иногда это утверждение принимают за аксиому.)

Задача 3. * Докажите принцип математической индукции. Отправить решение

Задача 4. На острове Буяне каждые два города соединены напрямую автомобильной либо железной дорогой. Докажите, что или из любого города в любой другой можно добраться на автомобиле, или из любого города в любой другой можно добраться на поезде. Отправить решение

Задача 5. Докажите, что части, на которые $n$ прямых делят плоскость, всегда можно раскрасить в два цвета так, чтобы соседние части (то есть части, имеющие общий отрезок или луч) были окрашены в разные цвета. Отправить решение

Задача 6. Докажите по индукции, что: а) $1+\ldots+n=\frac{n(n+1)}2$; б) $1+\ldots+n^2=\frac{n(n+1)(2n+1)}6$; в) $1+\ldots+n^3=\frac{n^2(n+1)^2}4$. Отправить решение

Задача 7. Найдите ошибку в следующих доказательствах. а) Докажем, что $n>n+1$. Действительно, пусть это утверждение верно для $n$, то есть $n>n+1$. Прибавив к обеим частям равенства единицу, мы получаем, что $(n+1)>(n+1)+1$, то есть верно утверждение для $n+1$. б) Докажем, что в произвольном стаде из $N$ коров все коровы одного цвета. База индукции. В любом стаде из одной коровы все коровы, очевидно, одного цвета. Шаг индукции. Предположим, что в любом стаде из $N$ коров все коровы одного цвета. Докажем, что в любом стаде из $N+1$ коровы все коровы одного цвета. Рассмотрим произвольное стадо из $N+1$ коровы. Возьмем в нем произвольную корову А. Оставшиеся $N$ коров одного цвета. Теперь возьмем другую корову B. Оставшиеся $N$ коров также одного цвета. В частности, А одного цвета со всеми коровами, кроме А и В, и В одного (того же!) цвета со всеми коровами, кроме А и В (см. рисунок). Значит, А, В, и вообще все коровы в стаде одного цвета. в) В стране несколько городов, некоторые пары которых соединены дорогами, причем каждый город соединен хотя бы с одним другим. Докажем, что из любого города можно проехать в любой другой по дорогам. Будем доказывать индукцией по числу городов. База индукции для стран, состоящих из одного города, очевидна. Докажем шаг индукции. Возьмем какую-нибудь страну из $n$ городов и добавим к ней еще один город. Между старыми городами можно проехать по старым дорогам, так что достаточно доказать, что из нового города можно проехать в любой из старых. По условию задачи из этого города ведет дорога в один из старых городов. Следовательно, из него можно доехать в один из старых городов, а оттуда уже добраться до любого другого. Итак, в новой стране тоже можно из любого города доехать до любого другого, и шаг индукции доказан. Отправить решение

Задача 8. На сколько частей делят плоскость $n$ прямых в общем положении? (Говорят, что прямые находятся в общем положении, если никакие две из них не параллельны и никакие три не пересекаются в одной точке.) Отправить решение

Задача 9. Докажите, что: а) $2^{5n+3}+5^n\cdot 3^{n+2}$ делится на 17; б) $n^{2m-1}+1$ делится на $n+1$; в*) $2^{3^n}+1$ делится на $3^{n+1}$. Отправить решение

Задача 10. (неравенство Бернулли) Докажите, что если $a>-1$, то $$(1+a)^n\ge 1+na\text{.}$$ Отправить решение

Задача 11. Докажите, что: а) $2^n>n$;  б) $2^n>n^2$ при $n>4$;  в) $n!>2^n$ при $n>3$; г) существует такое $k$, что $2^n>n^{2004}$ при всех $n>k$. Отправить решение

Задача 12. Вершины выпуклого многоугольника раскрашены ровно в три цвета так, что никакие две соседние вершины не окрашены в один цвет. Докажите, что многоугольник можно разбить диагоналями на треугольники так, чтобы у каждого треугольника вершины были трех разных цветов. Отправить решение

Обобщенный принцип математической индукции. Пусть задана последовательность утверждений $A_1, A_2, \ldots, A_k, \ldots$ Известно, что: 1) (база индукции) первое утверждение истинно, 2) (шаг индукции) из истинности утверждений $A_1, A_2, \ldots, A_n$ следует истинность утверждения $A_{n+1}$. Тогда все утверждения истинны.

Задача 13. *Докажите обобщенный принцип математической индукции. Отправить решение

Задача 14. Докажите, что если $a+\smash{\frac{1}{a}}$ целое, то $a^k+\smash{\frac{1}{a^k}}$ целое при любом $k$. Отправить решение

Задача 15. * В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей-молчунов. Докажите, что учитель может выгнать из класса не более половины учеников так, чтобы все болтуны молчали. Отправить решение

Задача 16. * (задача Сильвестра) На плоскости взяты несколько точек так, что на каждой прямой, соединяющей любые две из них, лежит по крайней мере еще одна точка. Докажите, что все точки лежат на одной прямой. Отправить решение

Задача 17. * Докажите, что $n^{n+1}>(n+1)^n$ при $n>2$. Отправить решение