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

ЗАДАЧНИК

'КВАНТА'

'

Поэтому для доказательства неравенства (1) достаточно показать, что
xy + xz + yz + 2 Ч 27 Ч 9 ? xyz .

(2)

8 8 8 Положим 3 = A , 3 = B , 3 = C , тогда (2) примет a b c вид

1 + A 1 + B + 1 + A 1 + C +
+ 1 + B 1 + C + 486 ? 1 + A 1 + B 1 + C Ы


М1806. Таблица чисел размером n Ч n такова, что любые n чисел, указанные по одному в каждой строке и в каждом столбце, дают всегда одинаковую сумму. В каждой строке таблицы определяется минимальное число, среди этих n чисел выделяется максимальное число М. В каждом столбце таблицы определяется максимальное число, среди них выделяется минимальное число m. Докажите, что М = m.
Обозначим таблицу, оговоренную условием задачи, через А. Составим таблицу В, у которой все n строк будут одинаковыми и такими, какая первая строка у таблицы А. Затем, вычтя из таблицы А таблицу В, получим новую таблицу С, у которой в каждой строке будут стоять одинаковые числа (например, в первой только нули), т.е. у таблицы С одинаковыми будут все столбцы. Таким образом, таблица А представлена как сумма двух специальных таблиц: А = В + С (чуть подробнее об этом рассказано в решении задачи М1760 в 'Кванте' ?4 за 2001 г.). К примеру,

A + B + C + 488 ? A BC .

Но

A Ч BЧC =
отсюда и, значит,

8

3 3

abc

= 83 ,

A + B + C ? 3 3 A B C = 24 ,

A + B + C + 488 ? 512 = 8 3 = A Ч B Ч C .
Утверждение доказано.
*

М.Гарбер

М1805 .В математической олимпиаде приняли участие двадцать один мальчик и двадцать одна девочка. Известно, что ћ каждый из них решил не более шести задач; ћ для каждого мальчика и каждой девочки найдется по крайней мере одна задача, которая была решена ими обоими. Докажите, что найдется задача, которую решили хотя бы три мальчика и три девочки.
Исключим из рассмотрения задачи, которые никто не решил. Обозначим через А множество задач, каждую из которых решили не более двух мальчиков, а через A остальные задачи олимпиады, т.е. решенные не менее чем тремя мальчиками. Аналогично для девочек определим множества В и B . Если бы некоторый мальчик решил задачи только из В, то не более 12 девочек решили бы общие с ним задачи (хотя бы по одной), что противоречит условиям задачи. Значит, каждый мальчик решил хотя бы одну задачу из B и, тем самым, не более пяти задач из В. Поэтому у каждого мальчика не более чем с 10 девочками общие задачи из В и, следовательно, не менее чем с 11 девочками общие задачи только из B (если у некоторой девочки общие с ним задачи как из В, так и из B , то она в число этих 11 девочек не входит). Для всех мальчиков мы получили множество М из не менее 21 Ч 11 пар 'мальчикдевочка' с общими задачами только из B . Точно так же рассматривая девочек, получаем множество N из не менее 21 Ч 11 пар 'девочкамальчик' с общими задачами только из A . Всего пар 'мальчикдевочка' 21 Ч 21 , следовательно, какаято пара 'мальчикдевочка' входит как в М, так и в N, т.е. у них есть общая решенная задача, входящая в множества B и A . Это означает, что найденную задачу решили по крайней мере 3 девочки и по крайней мере 3 мальчика. Утверждение доказано. С.Спиридонов
5*

ж1, 2, 3ц ж1, 2, 3ц ж0, 0, 0ц чз чз ч з ч з чз ч з4, 5, 6ч = з1, 2, 3ч + з 3, 3, 3ч . чз чз ч з чз чз ч з чз чз ч з чз чз з7, 8, 9ч з1, 2, 3ч и6, 6, 6ч ч и ши ш ш
Теперь легко сообразить, что М равно сумме минимального числа из таблицы В и максимального числа из таблицы С. Точно так же число m, в силу его определения, равно сумме максимального числа из таблицы С и минимального числа из таблицы В, т.е. M = m. Сформулируем дополнительное утверждение. В каждой строке таблицы А выберем максимальное число, среди этих n чисел выберем минимальное число m . Можно доказать (по той же схеме), что M +m равно сумме максимального и минимального чисел из таблицы А. В.Произволов

М1807.При каких n можно разрезать треугольник на n выпуклых многоугольников с различным числом сторон?
Основой решения является следующее утверждение: нельзя разрезать плоскость на 5 областей, из которых любые две имели бы общую границу (не точечную). Для его доказательства достаточно заметить, что если 4 области попарно граничат, то одна из них лежит в 'кольце', образованном тремя остальными, как на рисунке 1, и, следовательно, пятая область не может граничить со всеми четырьмя. Пусть k наибольшее из чисел сторон многоугольников разбиения. Так как соответствующий многоугольник выпуклый, к границе треугольника примыкает не бо лее трех его сторон. В силу выпуклости остальных n 1 " многоугольников каждый из них граничит не более чем с одной стороной k-угольника. Следовательно, k ? n + ! + 2 , и, значит, есть единственная возможность: тре- Рис.1