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

$

КВАНT 2000/?4

> N N - 1 8 . Так как общее число партий равно N N - 1 2 , то доля правильных партий больше 1/4. б) Пусть сначала в турнире участвовал 2k + 1 игрок, причем каждый участник с номером i k проиграл участникам с номерами i + 1, ..., i + k и выиграл у остальных, а каждый участник с номером i > k выиграл у участников с номерами i k,..., i 1 и проиграл остальным. Очевидно, что все игроки набрали по k очков, причем в таблице турнира выше главk k +1 клетках из ной диагонали единицы стоят лишь в 2 2k 2k + 1 . Теперь 'размножим' каждого игрока, заменив его 2 блоком из k новых, и пусть игроки из разных блоков играют друг с другом так же, как соответствующие прежние игроки, а игроки из одного блока играют друг с другом вничью. Получим новую таблицу, в которой по-прежнему у всех игроков поровну очков. Изменим эту таблицу так, чтобы суммы очков игроков перестали быть равными. Для этого будем менять результаты игроков из блока k + 1: в их встречах с игроками из блока k + 1 i заменим ik выигрышей ничьими так, что сумма очков каждого игрока из блока k + 1 уменьшится, а кажi дого игрока из блока k + 1 i увеличится на . 2 (Это можно сделать. Действительно, пусть А и В k-элементные множества, i k . Легко построить i (взаимно однозначных) отображений А на В так, что, какой элемент х множества А ни возьми, образы х при любых двух из этих отображений различны.) Напротив, в партиях с игроками из блока k + 1 + i заменим ничьими ik проигрышей. Число s неправильных партий станет равно k k +1 2 2k 2k + 1 2 k k +1 k -k - 2k . 2 2 2 При этом общее число партий S равно

b

g

b

g

Избранные задачи отбора на Российскую олимпиаду
1. Нет. Если три такие хорды нашлись, то они делят площадь круга в одинаковом отношении 3:4 и потому равны. Секторы между их концами равновелики, поэтому между хордами одинаковые углы по 60њ. Но тогда можно показать, что эти секторы меньше по площади, чем соседние усеченные секторы. 2. Среди цифр числа n не более двух единиц, а остальные нули. Всегда S ab S a S b , причем равенство означает, что при умножении 'в столбик' нет переносов из одного разряда в другой. Если при возведении n в четвертую степень нет переносов, то четвертая степень каждой цифры однозначное число. Если в записи n хотя бы три единицы, то при возведе2 нии n в квадрат появляется перенос. Если единиц не более двух, то переноса не возникает. 3. Так как вписанные углы KBD и KCA равны, то точки X, Y, B, C лежат на одной окружности. Тогда углы CBY и CXY равны как вписанные. Далее используем равенство вписанных углов CBD и CAD. 4. (Решение основано на работе ученицы 10 класса лицея 'Вторая школа' Е.Муравьевой.) Треугольники, в которые вписаны равные окружности, будем называть отмеченными. Если отмечены какие-либо два треугольника, 'симметричных относительно биссектрисы AD', то АВ = АС. Действительно, если отмечены АОЕ и АОF, то АЕВ = = AFC, откуда АВЕ = АСF. Пусть отмечены ОВF и ОСЕ. Тогда в этих треугольниках равны углы при вершине О, опущенные из О на BF и CE высоты и радиусы вписанных окружностей. Отсюда легко вывести, что равны и сами треугольники. Так как OBF OEC, то OBF = = OCЕ. Равенство OBD = OCD следует и из отмеченности треугольников OBD и OCD; доказав это, мы завершили бы решение задачи. (В самом деле, какую биссектрису l ни возьми, найдется хотя бы одна пара 'симметричных относительно l' отмеченных треугольников.) Однако мы не умеем доказывать это равенство без вычислений; не прибегая к ним, мы окончим решение несколько по-другому. Очевидно, у треугольника АВС есть вершина, к которой примыкают отмеченные треугольники, например, А. Значит, АВ = АС. Опираясь на это, докажем, что из отмеченности OFB и OFA следует АС = ВС. Обозначим через O1 , O2 , O3 центры окружностей, вписанных в треугольники АОЕ, АОF, BOF соответственно. Легко видеть, что OO2 || BC , O2 O3 || AB , O3 O1 || BE , откуда O2 O3 = 1 = OO2 . Значит, окружности с центрами O2 и O3 имеют об1 щую точку касания с CF, CF O2 O3 , откуда АС = ВС. 5. Зафиксировав k, проведем индукцию по числу ребер n. Начало очевидно. Для индуктивного перехода от n 1 к n сотрем ребро, соединяющее какие-то вершины А и В. Теперь количество правильных раскрасок есть многочлен P k . Из него нужно вычесть количество правильных раскрасок графа, получаемого при отождествлении А и В. Но по индуктивному предположению это также некоторый многочлен Q k . 6. Если x 0 , то x = - y 2 для некоторого у, и f x =

b

g

b

g

b g bgbg

b

g

b

g

b

g

k 2k + 1 k 2k + 1 - 1 2
При k = 20 неправильные партии от общего числа партий. Заметим s lim = k S

b

gd b

gi

.

235 600 составляют > 0,7 335 790 также, что 3 . 4

15. Будем помещать между плоскостями правильные тетраэдры, расстояние между противоположными ребрами которых равно расстоянию между плоскостями. Пусть одно из ребер каждого тетраэдра лежит в одной из граничных плоскостей, а противоположное ему в другой. Два тетраэдра можно расположить так, чтобы конец 'верхнего' ребра первого совпадал с серединой 'верхнего' ребра второго, а середина 'нижнего' ребра первого с концом 'нижнего' ребра второго, и при этом как 'верхние', так и 'нижние' ребра обоих тетраэдров были перпендикулярны. Распространив этот процесс на весь слой, получим, что каждый тетраэдр окружен четырьмя другими (рис.11). Эти 'соРис. 11 седи' не позволяют сдвинуть тетраэдр во внешнюю (по отношению к нему) сторону от любой его грани.

bg

=f f f y = - f y 0 . В области x > 0 функция f x взаимно однозначна, и из непрерывности следует ее строгая монотонность. Если f a > 0 для некоторого а > 0, то 2 f f x возрастает при х = а, тогда как - x убывает. 7. n + 1. Для n = 0 и n = 1 результат очевиден. Пусть он верен для какого-то n > 1. В кубе с ребром 2 и плотной расстаn новкой ладей 'раздуем' единичные кубики в 2 раз. На место ладей поставим кубы с плотной расстановкой и n + 1 'угловиком'. Получим куб с ребром 2 n +1 и не менее чем n + 2 'угловиками'. Больше их быть и не может: если 'угловик' с ребром l содержится в 'угловике' с ребром m, то m 2l . Последнее следует из того, что в их 'разности' можно рас2 ставить не более 3 m - l ладей так, чтобы они не били друг

e d b g ij

d b gi

2

bg bg

d b gi

bg

bg

b

g