Выбрано 2 задачи 
Убрать все задачи
Игра в "супершахматы" ведётся на доске размером 30×30, и в ней участвуют 20 разных фигур, каждая из которых ходит по своим правилам. Известно, однако, что
1) любая фигура с любого поля бьёт не более 20 полей и
2) если фигуру сдвинуть на несколько полей, то битые поля соответственно сдвигаются (может быть, исчезают за пределы поля).
Докажите, что
а) любая фигура F бьёт данное поле Х не более, чем с 20 полей;
б) можно расставить на доске все 20 фигур так, чтобы ни одна из них не била другую.
В стране 1988 городов и 4000 дорог.
Докажите, что можно указать кольцевой маршрут, проходящий не более, чем через 20 городов (каждая дорога соединяет два города).
|
|
 |
Условие
В стране 1988 городов и 4000 дорог.
Докажите, что можно указать кольцевой маршрут, проходящий не более, чем через 20 городов (каждая дорога соединяет два города).
Решение
Назовём город "захолустным", если из него идёт не более двух дорог. Сотрём с карты страны любой захолустный город, если таковой имеется,
вместе с выходящими из него дорогами. Подчистим таким же образом новую карту
и будем продолжать стирание захолустных городов, пока они не исчезнут.
Число дорог, которые мы при этом можем стереть, не превосходит 2·1988 < 4000; поэтому хотя бы один город останется.
Выберем любой из оставшихся городов. Из него, как и из других оставшихся городов, выходят по меньшей мере три дороги. Пойдём по одной из них и каждый раз, приходя в новый город, будем двигаться дальше по одной из дорог, отличных от дороги, по которой мы пришли. Если какие-нибудь два маршрута, состоящие не более чем из 10 дорог, закончатся в одном городе, то мы получим искомый кольцевой маршрут не более чем из 20 дорог. В противном случае число всех таких маршрутов не меньше чем 3(1 + 2 + 2² + ... + 29) = 3(210 – 1) = 3069, а число городов, то есть возможных концов этих маршрутов – не больше 1988. Противоречие.
Замечания
6 баллов
