М741 - М760 (20)

16.

M756*

В стране, кроме столицы, больше 100 городов. Столица страны соединена авиалиниями со 100 городами; каждый из остальных городов соединен авиалиниями ровно с 10 городами. Известно, что из любого города можно (быть может, с пересадками) перелететь в любой другой. Докажите, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из любого города в любой сохранится.

17.

M757

Из последовательности 1, 1/2, 1/3, 1/4,... нетрудно выделить арифметическую прогрессию длиной 3: 1/2, 1/3, 1/6. Можно ли из этой последовательности выбрать арифметическую прогрессию а) длиной 4? б) длиной 5? в) длиной k, где k — любое натуральное число?

18.

M758*

Какое наименьшее количество чисел можно вычеркнуть из последовательности 1, 2, 3,... 1982, чтобы ни одно из оставшихся чисел не равнялось произведению двух других оставшихся чисел?

19.

M759

Внутри выпуклого четырехугольника, у которого сумма шести попарных расстояний между вершинами (т.е. сумма длин всех сторон и диагоналей) равна S₁, расположен другой, для которого эта сумма равна S₂.

a) Может ли величина S₂ быть больше S₁?

б) Докажите, что S₂ < 4S₁/3.

в) Докажите, что если внутри правильного тетраэдра с суммой длин ребер S₁ расположен другой, для которого эта сумма равна S₂, то S₂ < 4S₁/3.

20.

M760

С замкнутой ломаной A₁A₂...A_m, где m нечетно, проделывается такая операция: середины ее звеньев соединяются m отрезками через одну (середина A₁A₂ — с серединой A₃A₄, A₂A₃ — с A₄A₅, ..., A_m-1A_m — с A₁A₂, A_mA₁ — с A₂A₃). С полученной ломаной вновь проделывается эта же операция и т.д. Докажите, что из любой m-звенной ломаной

a) при m = 5 — через 2 шага (показано на рисунке),

б) при m = 7 — через 3 шага,

в) при любом нечетном m — через некоторое (зависящее от m) число шагов получится ломаная, подобная (даже гомотетичная) первоначальной.