Олимпиадные задачи по теме «Индукция» для 6 класса - сложность 3 с решениями

В поселке 100 домов. Какое наибольшее число замкнутых не пересекающихся заборов можно построить, чтобы каждый забор огораживал хотя бы один дом и никакие два забора не огораживали бы одну и ту же совокупность домов?

Доказать, что  2^{2<i>n</i>–1} + 3<i>n</i> + 4  делится на 9 при любом <i>n</i>.

а) В графе есть эйлеров путь. Доказать, что граф связен и вершин с нечётной степенью в нём не больше двух.

б) Доказать обратное: если в связном графе вершин с нечётной степенью не больше двух, то в нём есть эйлеров путь.

В стране каждые два города соединены дорогой с односторонним движением. Доказать, что можно проехать по всем городам, побывав в каждом по одному разу (то есть что в полном ориентированном графе есть <i>гамильтонов путь</i>).

Сумма положительных чисел <i>x</i>₁, <i>x</i>₂, ..., <i>x_n</i> равна ½. Докажите, что   <img align="MIDDLE" src="/storage/problem-media/30908/problem_30908_img_2.gif">

20 команд сыграли круговой турнир по волейболу.

Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, ..., 19-я – у 20-й.