МАЛЫЙ МЕХМАТ МГУ

Кружок 10 класса

Индукция (19.09.2009)

1.

Докажите, что если в числе 12008 между нулями вставить любое количество троек, то получится число, делящееся на 19.

2.

Найдите x₁₀₀₀, если x₁=4, x₂=6, и при любом натуральном n ≥ 3 x_n — наименьшее составное число, большее 2x_{n − 1} − x_{n − 2}.

3.

Докажите, что из произвольного включающего не менее четырёх чисел множества трёхзначных чисел, взаимно простых в совокупности, можно выбрать четыре числа, взаимно простых в совокупности.

4.

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

5.

В строку записаны в некотором порядке натуральные числа от 1 до 2009. Над строкой производится следующая операция: если на первом месте стоит число k, то первые k чисел строки переставляются в обратном порядке. Докажите, что через несколько таких операций 1 окажется на первом месте.

6.

Лабиринт представляет собой квадрат 8×8, в каждой клетке которого поставлена одна из четырёх стрелок: вверх, вниз, вправо, влево. Верхняя сторона правой верхней клетки — выход из лабиринта. В левой нижней клетке находится фишка, которая каждым своим ходом перемещается на одну клетку в направлении, указанном стрелкой. После каждого хода стрелка в клетке, в которой только что была фишка, поворачивается на 90° по часовой стрелке. Если фишка должна сделать ход, выводящий её за пределы квадрата, то она остаётся на месте, а стрелка поворачивается на 90° по часовой стрелке. Докажите, что рано или поздно фишка выйдет из лабиринта.

7.

Набор чисел a₀, a₁, …, a_n удовлетворяет условиям: a₀=0, 0 ≤ a_{k + 1} − a_k ≤ 1 при k=0,1,…, n − 1. Докажите неравенство a₁³ + … a_n³ ≤ (a₁ + … a_n)².