Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/05/63.pdf Дата изменения: Fri Dec 23 19:26:35 2005 Дата индексирования: Tue Oct 2 00:16:53 2012 Кодировка: Windows-1251 Поисковые слова: m 16

ОТВЕТЫ,

УКАЗАНИЯ,

РЕШЕНИЯ

63

EMK = MKB + KBM = MKB + MKE = BKE = 120њ .
Так как ENK = 60њ , отсюда следует, что четырехугольник EMKN вписанный. Значит, AMN = EKN = 60њ . 16. Условие задачи не нарушится, если мы будем считать, что каждый депутат знаком с самим собой. Для каждого депутата рассмотрим множество знакомых с ним депутатов. Из условия следует, что никакие два множества знакомых не совпадают (для любых двух депутатов тот третий, который знаком ровно с одним из них, принадлежит множеству знакомых одного и не принадлежит множеству знакомых другого). Лемма. Пусть A один из депутатов. Предположим, что президент приказал поменять партию всем депутатам, не знакомым с A. Тогда в результате этого все депутаты, имеющие не меньше знакомых, чем A (кроме самого A), поменяли партию. Доказательство, Пусть некоторый депутат B, отличный от A, не поменял партию. Это означает, что B не знаком ни с одним депутатом из числа незнакомых с A. Другими словами, множество знакомых B содержится в множестве знакомых A. Так как эти множества не могут совпадать, количество знакомых B строго меньше, чем количество знакомых A. Построим депутатов в порядке невозрастания числа знакомых. Докажем, что для любого натурального n президент может добиться того, чтобы первые n депутатов в этом ряду состояли в одной партии. Воспользуемся индукцией. При n = 1 утверждение тривиально. Для индукционного перехода предположим, что первые n 1 депутатов уже состоят в одной партии, а n-й депутат (назовем его A) в другой. Пусть президент прикажет поменять партию всем депутатам, не знакомым с A. Тогда по лемме все, у кого число знакомых не меньше, чем у A (в том числе все те, кто стоят перед A), поменяют партию. Значит, все, кто стоят перед A, окажутся во второй партии. В той же партии по-прежнему будет и сам A, значит, n первых депутатов в ряду будут состоять в одной партии (а именно, во второй). Утверждение доказано. Следовательно, президент может добиться того, чтобы все депутаты состояли в одной партии. Если это еще не та партия, которую поддерживает он сам, то он прикажет поменять партию всем депутатам сразу, и его цель достигнута. 17. Поскольку для любых натуральных чисел m, n m, n = mn , где m, n = НОД m, n , неравенство можно переписать в виде mn m +1 n +1 2mn + . m, n m + 1, n + 1 m-n Применив к сумме, стоящей в левой части, неравенство о средних, получим, что

Докажем, что функция f(x) линейная. Для этого проверим, что при всех y 0 отношение g(y)/y постоянно. Действительно, применяя формулу ( ) для y = y1 и k = g y2 , получаем, что

di

f x + g y1 g y f x + g y1 g y
1 2 2

e e

d i d ij = f b x g
2 2

+ 2 g y2 y1 .
1

откуда f(y) = y при y 0 . Заметим, что 0 , в противном случае, например, при x 0 и x - f 1 - 1 должно выполняться равенство

d i d ij = f b x g + 2 g Стало быть, g d y i y = gd y i y , т.е. g d y i / y Обозначим это отношение через + 1 . Тогда y + f(y) = b + 1g y,
1 1 1

По той же самой формуле для y = y2 и k

di = gd y i d y iy .
2 1

имеем

=gy

di
2

/ y2 .

bg

0 = f(x + 1 + f(1)) = f(x) + 2 = 2. Покажем далее, что f(0) = 0. Для этого подставим в условие на функцию число x, отличное от 0 и f(0), и y = 0. Получим ( x + f (0)) = f ( x + f (0)) = f ( x) = x , откуда f(0) = 0. Таким образом, f(x) = x при всех целых x. Установим, при каких функция f(x) = x удовлетворяет условию. Для этого подставим x = 0 и y = 1, получим квад2 ратное уравнение на : + - 2 = 0 , откуда = 1 или = -2 . 19. Прямоугольники, вырезанные из таблицы, будем называть полосками. Предположим, что полоска 1 Ч 20 расположена вертикально. Отрежем от квадрата 20 Ч 20 слева и справа по прямоугольнику 1 Ч 20 . Каждый из них разрежем на 10 прямоугольников 1 Ч 2 , а оставшуюся часть доски на 90 квадратов 2 Ч 2 . Квадраты 2 Ч 2 или пару прямоугольников 1 Ч 2 , расположенных на одной горизонтали по разные стороны квадрата 20 Ч 20 , назовем обобщенными квадратами. Если одна из клеток обобщенного квадрата была вырезана при вырезании полоски 1 Ч k , то мы будем говорить, что полоска задевает квадрат. Заметим, что если из какого-то обобщенного квадрата 2 Ч 2 нельзя вырезать ни одной доминошки (прямоугольника 1 Ч 2 ), то этот квадрат задевают по крайней мере две полоски. Если из обобщенного квадрата нельзя вырезать две доминошки, то его задевает как минимум одна полоска. Таким образом, если из обобщенного квадрата нельзя вырезать больше чем k доминошек, то его задевает как минимум 2k полоски. Поскольку всего в разбиении ровно 100 обобщенных квадратов, то количество доминошек, которое можно будет заведомо вырезать из квадрата 20 Ч 20 , будет не меньше чем 200 минус общее число задеваний обобщенных квадратов всеми полосками. Рассмотрим теперь разрезание на обобщенные квадраты, полученное из первоначального поворотом на 90њ. Для этого разрезания также верно, что если из обобщенного квадрата нельзя вырезать больше чем k доминошек, то его задевает как минимум 2 k полоски. Единственное исключение представляет собой пара прямоугольников 1 Ч 2 , которую задевает полоска 1 Ч 20 . Из такого обобщенного квадрата нельзя вырезать ни одной доминошки. Для удобства будем считать, что вертикальная полоска 1 Ч 20 дважды задевает такой обобщенный квадрат. Подсчитаем, какое количество обобщенных квадратов задевает полоска 1 Ч k . Для определенности будем считать, что полоска расположена вертикально. Если k = 2m 1, то полоска 1 Ч k задевает по m обобщенных квадратов первого и второго разрезаний, в сумме 2m = k + 1. Если k = 2m, то полоска 1 Ч k на одном разрезании задевает m обобщенных квадратов,

bg

bg bg b gb g bgb g
2

bm + 1gbn + 1g bm, ng bm + 1, n + 1g
mn +

b gb g bm, ngbm + 1, n + 1g
m m +1 n n +1 >

>

Так как m - n M m, n и m - n M m + 1, n + (m + 1, n + 1) взаимно просты, то m - Значит, m - n (m, n) (m + 1, n + 1) , но тогда правая часть неравенства ( ) не меньше чем 2 mn m - n . 18. f(x) = x и f(x) = 2x.

bg

b

bm, ngbm + 1, n + 1g 1g , а числа (m, n) и n M b m, n gb m + 1, n + 1g .

2mn

. ( )

Пусть g(y) = y + f(y). По индукции легко показать, что при любом натуральном k f(x + kg(y)) = f(x) + 2ky. ( ) Если мы подставим вместо x число x + kg(y), то получим, что равенство ( ) верно при всех целых k.