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

ОЛИМПИАДЫ

"%
am + a - 1 a n + a2 - 1

Огромная благодарность работавшим с командой тренерам А.Белову, С.Берлову, А.Глазырину, В.Дольникову, Д.Карпову, П.Кожевникову, А.Пояркову, М.Пратусевичу, А.Храброву, Г.Челнокову. Всего на олимпиаде золотыми медалями были награждены 39 участников, и их вручала победителям британская принцесса Анна. В неофициальном командном зачете значительных изменений по сравнению с прошлыми годами не произошло, и лучшие 20 команд расположились в следующем порядке: Китай Россия США Болгария Вьетнам Ю.Корея Тайвань Румыния Индия Германия Иран Канада Венгрия Белоруссия Турция Япония Казахстан Израиль Франция Украина Очки 212 204 171 167 166 163 161 157 156 144 143 142 142 135 135 133 133 130 127 124 Золото 6 6 4 3 3 1 1 2 1 2 0 1 1 1 1 1 0 0 0 1 Серебро 0 0 1 2 1 5 4 3 3 1 4 3 2 2 1 4 3 3 2 3 Бронза 0 0 0 1 2 0 1 1 2 2 2 1 3 3 4 1 3 3 3 0

таких, что число целое.

(Румыния)

4. Дано натуральное число n, большее 1. Обозначим через d1, d2, K , dk все его делители так, что
1 = d1 < d2 < K < d = n .

Пусть D = d1d2 + d2d3 + K dk -1dk . а) Докажите, что D < n 2 . б) Найдите все n, для которых D делитель числа n 2 . (Румыния) 5. Найдите все функции f: 4 R 4 такие, что

(f ( x )

+ f (z

) ) (f ( y )

+ f (t

))

= f ( xy - zt ) + f ( xt + yz

)

для всех действительных x, y, z, t.

(Индия)

6. На плоскости расположены окружности 1, 2, K , n , радиуса 1 каждая, с центрами O1, O2, K , On соответственно; n ? 3 . Известно, что любая прямая плоскости имеет общие точки не более чем с двумя из этих окружностей. Докажите, что
1? i < j ? n

е

1 (n - 1) ? . OOj 4 i
(Украина)

Решения задач
1 (О.Стырт). Занумеруем точки множества T: (i; j) , где i номер столбца, j номер строки, i ? 0 , j ? 0 , i + j < n, т.е. i + j ? n - 1 . Будем также считать точки (i; 1) и (1; j) красными. Пусть mi число синих точек в i-м столбце. Тогда количество X-множеств равно произведению P =

В заключение хотелось бы выразить благодарность всем организациям и лицам, оказавшим поддержку в успешном выступлении команды России на XLIII ММО: Министерству образования РФ, Стипендиальному фонду Владимира Потанина, компании 'Apple', Исполкому Союза правых сил, а также Ю.В.Прохорову. Ниже приведены задачи олимпиады и их решения, предложенные нашими участниками.

Х
i =0

n -1

mi .

Задачи олимпиады
1. Дано натуральное число n. Обозначим через T множество точек (x; y) координатной плоскости, где x и y неотрицательные целые числа такие, что x + y < n. Каждая точка из T окрашена в красный или синий цвет. Если точка (x; y) красная, то все точки (x?; y ?) из T, для которых x? ? x и y ? ? y , также красные. Назовем X-множеством множество из n синих точек, имеющих различные координаты x, а Y-множеством множество из n синих точек, имеющих различные координаты y. Докажите, что количество Xмножеств равно количеству Y-множеств. (Колумбия) 2. Дана окружность с центром O и диаметром BC. Пусть A точка на такая, что 0o < РAOB < 120o , а D середина дуги AB, не содержащей C. Прямая, проходящая через точку O параллельно DA, пересекает прямую AC в точке J. Серединный перпендикуляр к отрезку OA пересекает в точках E и F. Докажите, что точка J центр вписанной окружности треугольника CEF. (Ю.Корея) 3. Найдите все пары натуральных чисел m, n ? 3 , для которых существует бесконечно много натуральных чисел a

Выберем некоторое i0 О {0,K n - 1} . Если mi0 = 0 , то все точки i0 -го столбца красные. Пусть mi0 > 0 . Рассмотрим наименьшее j0 такое, что (i0 ; j0 ) синяя точка. Тогда, из определения, точка (i0; j ) синяя, т.е. j ? j0 . Также i0 + j ? n - 1 , т.е. mi0 = n - i0 - j0 . Посмотрим, сколько раз число k, 1 ? k ? n , встречается среди чисел mi в произведении P. Это количество равно числу пар {i; j} таких, что i ? 0 , j ? 0 , i + j = n k, и при этом точка (i; j) синяя, а точка (i; j 1) красная. С другой стороны, из определения множества T точки (i; j) и (i; j 1) либо одноцветны, либо (i; j) синяя, а (i; j 1) красная. Значит, разность между числом синих точек (i0; j ) и числом синих точек (i0 ; j - 1) как раз равна числу пар (i0 ; j) таких, что (i0 ; j) синяя, а (i0; j - 1) красная точка. Итак, любое ненулевое число k встречается в произведении P ровно столько раз, какова разность между числом синих точек (i; j), для которых i + j = n k, и числом синих точек, для которых i + j = n k 1. Из симметрии этого выражения относительно i и j следует, что ненулевое k входит в произведение P ровно столько раз, сколько раз оно входит в произведение Q =

Х
j =0

n -1

lj , где l j количество синих

точек в j-й строке, задающее Если же в P входит хотя бы если mi0 = 0 для некоторого числе и (i0 ; j0 ) , где i0 + j0 =

количество Y-множеств. один нулевой множитель, т.е. i0 , то все точки (i0; j ) , в том n - 1 , красные. Это означает,