Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/02/15.pdf Дата изменения: Fri Dec 23 19:25:44 2005 Дата индексирования: Tue Oct 2 00:21:34 2012 Кодировка: Windows-1251

ЗАДАЧНИК

'КВАНТА'

15
m

М1702*. В некоторой группе из 12 человек среди

каждых 9 найдутся 5 попарно знакомых. Докажите, что в этой группе найдутся 6 попарно знакомых.

Но 0 < t < 1, поэтому t

>t,
m

n

1+ t

>1+t ,
n m

n

Возьмем граф на 12 вершинах, которые соответствуют людям; две его вершины соединены, если люди незнакомы. Если в этом графе нет циклов нечетной длины, то его можно разбить на две части, в каждой из которых вершины не будут соединены, и поэтому найдутся 6 попарно знакомых. Предположим теперь, что в графе есть циклы нечетной длины. Рассмотрим нечетный цикл минимальной длины. Пусть его длина равна: а) 2. Тогда если среди 9 человек, не входящих в этот цикл, есть два незнакомых, то среди оставшихся 7 человек из каждых 4 найдутся три знакомых. Таким образом, в подграфе на 7 вершинах каждые два ребра имеют общую вершину. Третье ребро обязано проходить через эту вершину. Иначе среди 4 человек не найдется трех знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем 6 попарно знакомых. б) 5. Тогда, как и выше, среди оставшихся 7 из каждых 4 найдутся 3 знакомых и среди этих 7 найдутся 6 знакомых. в) 7. Тогда среди 5 человек, не входящих в этот цикл, все попарно знакомы. Если есть человек из цикла, знакомый со всеми этими 5, то все ) доказано. В противном случае, каждый из цикла не знаком с кем-то из оставшихся. Так как 7 > 5, то найдется человек А из оставших, ся, не знакомый с дву* + мя из цикла В и С (см. рисунок). Из того, что мы взяли цикл минимальной длины, следует, что эти два незнакомых из цикла должны быть знакомы через одного D. Но тогда D знаком со всеми из пяти оставшихся, потому что, удаляя из цикла D и заменяя на А, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы. г) 9. Цикла длины 9 не может быть по условию задачи. д) 11. Тогда, как и выше при рассмотрении циклов длины 7, мы видим, что оставшийся человек может быть незнаком максимум с двумя из цикла. Но тогда в цикле легко найти 5 человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и не знакомых с оставшимся.) В.Дольников

Полученное противоречие доказывает равенство abc = 0. Замечание. Используя свойства функции у = x , где > 1, нетрудно доказать более сильное, чем утверждение задачи, Предложение. Пусть

e1

+t

m

j > e1 + t j
n

.

a +b +c +d
n n n

m

m

m

m

= 0,

a + b + c + d = 0,
где m n . Тогда числа a, b, c, d можно разбить на пары вида k,-k , l,-l . В.Произволов, В.Сендеров

n

b gb g

М1704*. В квадрате n Ч n клеток бесконечной шах2 матной доски расположены n фишек, по одной фишке в каждой клетке. Ходом называется перепрыгивание любой фишкой через соседнюю по стороне фишку, непосредственно за которой следует свободная клетка. При этом фишка, через которую перепрыгнули, с доски снимается. Докажите, что позиция, в которой дальнейшие ходы невозможны, возникнет не ранее чем через 2 n ходов. 3
Будем различать два типа ходов внутренние и внешние, в зависимости от того, куда ставится фишка, делающая ход: внутрь исходного квадрата n Ч n клеток или вне его. Пусть получена позиция, где дальнейшие ходы невозможны, причем сделано k внутренних ходов и l внешних. Ясно, что никакие две фишки не находятся в соседних 2 n клетках, а в исходном квадрате n Ч n не менее чем 2 клеток пусты. Так как каждый внутренний ход увеличивал количество пустых клеток не более чем на 1, а каждый внешний не более чем на 2, то имеем неравенство

LM MN

OP PQ

LM MN

OP PQ

k + 2l

М1703. Для чисел а, b и с нашлись два неравных m m m натуральных числа m и n такие, что a + b + c = 0 n n n и a + b + c = 0. Докажите, что abc = 0.
Пусть числа m и n нечетны и abc 0 . Тогда условия можно переписать в виде
n n n x +y =z ,

Предположив теперь, что n четно, разобьем исходный 2 n четырехклеточных квадратиков и замеквадрат на 4 тим, что на каждый квадратик пришлось не менее двух ходов, в которых участвовали (делали ход или снимались с доски) фишки, стоявшие в клетках этого квадратика. Поскольку в каждом внутреннем ходе участвовали фишки не более чем двух квадратиков, а в каждом внешнем не более чем одного, то
2k + l 2 n
2

LM MN

n

2

2

OP PQ

.

(1)

4

.

x +y

m

m

m =z ,

где х, у, z > 0. n m Если х = у, то 2 = 2 . y Пусть x > y, n > m. Положим = t < 1. Тогда x m n n m 1+t = 1+ t .

Из неравенств (1) и (2) получаем k + l

n

2

e

je

j

утверждение задачи в этом случае верно. Легко видеть, что оно верно также при n = 1 и при n = =3. В случае n = 2m + 1, где m > 1, в 'кресте', образованном третьей сверху горизонталью и третьей слева верти-

3



LM MN

n

2

3

OP PQ

(2) , т.е.

4*