А. В. Летчиков
ПРИНЦИП ДИРИХЛЕ
Задачи с указаниями и решениями
УЧЕБНОЕ ПОСОБИЕ
Ижевск 1992
Министерство науки, высшей школы и технической политики Российской Федерации
Удмуртский государственный университет
А.В.Летчиков
ПРИНЦИП ДИРИХЛЕ
Задачи с указаниями и решениями
Учебное пособие
Ижевск Издательство Удмуртского университета 1992
УДК 517.11(075)
ББК 22.12Я73 Л52
Настоящее издание предназначено для студентов старших курсов математического факультета в качестве сборника задач по курсам "Решение задач повышенной трудности" и "Математические факультативы и кружки в школе". В нем собраны задачи различной тематики и сложности, объединенные общим логическим методом решения, известным в математике как принцип Дирихле, а также их подробные решения. Настоящий сборник задач рассчитан на широкий круг читателя : от школьников младших классов до учителей и руководителей математических кружков.
Л52 Летчиков А.В. Принцип Дирихле. Задачи с указаниями и решениями : Учебное пособие. Ижевск : Изд-во Удм.ун-та, 1992Л08 с.
© Изд-во Удмуртского университета, 1992
ПРЕДИСЛОВИЕ
Настоящее пособие является сборником задач математичес— ких олимпиад различного уровня, объединенных под обобщенным названием ”На принцип Дирихле". С одной стороны, предлагав— мый сборник задач может служить учебным пособием для учителей, ведущих факультативы по математике в различных классах, руководителей математических кружков, а также готовящих школьников I олимпиадам по математике. С другой стороны, каждый желающий ученик может самостоятельно заниматься по этому сборнику, так как все задачи содержат достаточно пол— ные решения, в которых есть ссылки на популярную литературу.
Задачник состоит из введения,, шести параграфов, каждый из которых содержит цикл задач определенной тематики, и части, включающей в себя решения задач. В начале каждого параграфа приводятся краткие сведения о логике рассуждений, необходимой при решении цикла задач дачного параграфа, и приводятся характерные примеры. Некоторые теоретические выкладки (особенно в последних параграфах) могут быть достаточно сложными для учеников младших классов, пытающихся самостоятельно работать со сборником. В этом случае мы советуем их опустить из рассмотрения и перейти сразу к примерам. Для удобства читателя после номера задачи стоит ссылка на литературу, откуда взята эта задача, и номер этой задачи в том издании. Некоторые задачи заимствованы из задачника "Кванта", в таких случаях при ссылке на номер журнала стоит номер задачи, как она числится в задачнике "Кванта". Список литературы, на которую ссылается автор, приводится b конце книги.
3
Естественно, задачи различаются по уровню сложности : есть задачи достаточно трудные - они выделены звездочкой, есть совсем простые, их мы пытались поставить в начало па— раграфа. Поэтому те, кто уже имеет опыт решения подобных за— дач, может обрапггься сразу в задачам со звездочкой. Задачи не разделены по классам, так как автор полагает, что чита— тель может сам выбрать себе задачи, соответствующие его уровню. Понятно, что было бы глупо ученику младших классов браться, скажем, за задачу по стереометрии. Некоторые задачи публикуются впервые, поэтому могут быть использованы в качестве задач школьных или районных олимпиад, а также на матбоях.
Первые три параграфа посвящены так называемому дискрет— ному принципу Дирихле : в первом - задачи общего типа, во втором - задачи по теории чисел, в третьем - геометрические задачи, решаемые с помощью дискретного принципа Дирихле. В четвертом параграфе собраны задачи на принцип Дирихле, кото— рые удобно решать с помощью теории графов. Последние два па— раграфа объединяют задачи, при решении которых используются теоремы, подобные принципу Дирихле.
Часть задач была собрана студенткой 5 курсо математи— ческого факультета 3. Ширяевой. Некоторые задачи были предложены А.Б.Воронецким. Кроме того, рукопись просмотрел Л.Э.Медников, сделав ряд замечаний. Автор выражает всем искреннюю признательность за ту большую помощь, оказанную при создании настоящего пособия.
ВВЕДЕНИЕ
Так уж получилось, что попытки академика А.Н.Колмогорова ввести в 70-х годах в школьный курс математики элементы математической логики потерпели неудачу. В нынешних курсах алгебры и геометрии математической логике отводится одно из последних мест, хотя любая математическая теория ( да и не только математическая ) основана на стропа логических рассуждениях. Как показывает практика, пробелы в логаческой грамоте характерны не только ученикам, но и многим студентам естественных факультетов университета. Между тем умешю строго логически рассуждать обязательно уже для учеников младших классов. Наиболее удобным инструментом в исправлении ошибок в этом разделе математики являются задачи олимпи ад— кого типа, которые обычно имеют название "На принцип Дирихле". Задачи на принцип Дирихле хороши тем, что порою не тре— буют для своего решения каких-нибудь дополнительных математических знание, поэтому они часто встречаются на олимпиадах различного уровня как для младших классов, так и для студентов-математиков;- Чаще всего для их решения-достаточно умения четко логически строить свои рассуждения. В иных задачах даже трудно понять, что это логическая задача на принцип Ди— рхоле, а не какая-нибудь геометрическая ш, к примеру, задача по теории чисел. Решая задачи из настоящего сборника, читатель научится отличать задачи такого рода.
Задачи на принцип Дирихле относятся к логическим задачам, которые решаются методом от противного. Это задачи, в которых требуется доказать, что если выполнено некоторое условие то обязательно будет иметь место утверждение В. Для доказательства предполагаем противное : условие А выполнено, а утверждение В нет. Если путем логических рассуждений мы приходим к противоречию, то, значит, из А следует В..В задачах на принцип Дирихле это противоречие имеет kojhi— чественный характер переполнения или недополнения.
5
В качестве примера докажем утверждение, сформулированное немецким математиком П. Дирихле (1805-1859) и названное впоследствии его именем : как бы мы не рассаживали шесть зайцев в пять клеток, обязательно найдется клетка, в которой будут, по крайней мере, два зайца, Итак, мы имеем 6 зай— цев и 5 клеток. Предположим противное : мы их рассадили так, что нет клетки, в которой будут, по крайней мере, два зайца. Это означает, что во всех клетках не более одного зайца. Так как клеток пять, отсюда следует, что зайцев должно быть не более пяти. Но у нас их шесть. Получили противоречие. Смысл его в том, что, рассаживая зайцев по одному в каждую клетку, мы получим одного лишнего зайца, так как их больше, чем клеток. Это аналогично тому, как если бы мы наливали в стакан воды, по объему большей, чем в него войдет , - как бы мы это ни делали, часть воды обязательно выльется из стакана (произойдет переполнение). Вышесказанное показывает, что ре— шающий задачи на принцип Дирихле овладевает основными навыками математической логики : умением правильно строить отри— цание логического высказывания, понятиями общности ("для всех”, ’•найдется”). Как показывает практика, отсутствие именно этих навыков является характерным пробелом в школьном математическом образовании сегодня.
Сегодня на практике математику приходится встречаться с задачами, когда про какую-то систему объектов ничего неизвестно, кроме определенного количественного свойства. Но по такой, казалось бы, недостаточной информации математик' может логически вывести, что характерно для этой системы. Именно к таким задачам и относятся задачи на принцип Дирихле. Например, в задаче Дирихле известно, что мы имеем шесть зайцев и пять клеток, но неизвестно, каким образом и в какую клетку рассажены зайцы, то есть мы имеем неполную информаш.-? об этой системе. Однако нам этого достаточно, чтобы утверждать, что найдется клетка, содержащая по крайней мере хвул зайцев. Таким образом, решая эти задачи, школьники приобщаются к современным методам математики, что мажет быть развито в дальнейлюй научной работе.
6
§ 1.	Дискретный принцип Дирихле
Этот принцип наиболее известен в популярной математической литературе 1см. 1-4]. Сформулируем его в виде теоремы.
ТЕОРЕМА 1. Если в п клетках сидит (nk+1) зайцев, то хотя бы в одной клетке зайцев не меньше (к+1).
ДОКАЗАТЕЛЬСТВО. Предположим противное : пусть в каждой клетке находятся не более к зайцев. Так как клеток п, из этого следует, что всего зайцев «не более nk, а их (nk+1). Получили противоречие.
Приведем примеры применения этой теоремы.
ПРИМЕР 1. (5. 106]. В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом янцпсе лежали яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?
РЕШЕНИЕ. Предположим, что 9 ящиков яблок одного сорта нет. Тогда ящиков каждого сорта не более 8. Так как сортов 3, находим, что тогда всего ящиков не более 2*1, а их 25. Противоречие. Значит, всегда можно найти 9 ящиков с яблоками одного сорта.
В данном случае условие задачи похоже на условие теоремы 1. Понятно, что "зайцами" здесь будут ящики, а "клетками" -сорта яблок. Тогда n=3, a (nk + 1) = 25. Следовательно, к=8. В силу теоремы 1 (или, как обычно говорят, по принципу Дирихле) найдется сорт яблок ("клетка"), которому соответствует по крайней мере (к+1) = 9 ящиков ("зайцев").
ПРИМЕР 2. [1]. В классе 30. человек. В диктанте Саша сделал 13 ошибок, а остальные - меньше. Доказать, что по край— ней мере 3 ученика сделали ошибок поровну.
РЕШЕНИЕ. Кроме Саши, в классе учеников 29, и все они сделали ошибок от О до 12 включительно. Будем считать учеников "зайцами" (думаем, они нас простят), а количество сделанных ошибок в диктанте - "клетками". Тогда "клеток" - 13 штук, а "зайцев" - 29. По принципу Дирихле всегда найдется "клетка" (а значит, и число ошибок), в которой будет (которому будет соответствовать) по крайней мере 3 "зайца" (ученика). Действительно, если это не так, то "зайцев" не более
7
26,	а их - 29. Следовательно, найдутся три ученика, получив— шне на диктанте одинаковое количество ошибок.
Для тех, кому не по душе "зайцы" и "гтетки", сформули— руем принцип Дирихле в строгих терминах теории множеств и отображений. Пусть заданы конечные множества А и В, причем элементов в множестве А - (nk+1), а в множестве В - п. Пред— положим, что задана функция f, действующая из А в В. Тогда найдется элемент b из В такой, что существуют по крайней мере (п+1) элементов а ,а  а из А таких, что f(a) =
1 2	п+1	1
= Ъ для всех i = 1, 2....... п+1. В данном случае элементы
множества А - "зайцы", а элементы множества В - "клетки".
Иногда при решении задач используется бесконечный аналог принципа Дирихле : если бесконечное множество разбито на конечное число подмножеств, то найдется подмножество, содержащее бесконечное число элементов. Доказательство его повторяет доказательство теоремы 1. Предположим, что нет подмножества, содержащего бесконечное число элементов исходного множества. Тогда из того, что подмножеств конечное число, и каждое из них содержит конечное число элементов, следует, что всего элементов в множестве конечное число, что противоречит бесконечности самого множества.
1.	[1]. В классе 41 человек. В диктанте Саша сделал 13 ошибок, а остальные - меньше. Доказать, что по крайней мере 4 ученика сделали ошибок поровну.
2.	Группа из 25 студентов сдавала экзамен. Каждый из. студентов получил на нем одну из четырех возможных оценок : "отлично", "хорошо", "удовлетворительно" или "неудовлетворительно". Доказать, что найдутся семь студентов, получивших одинаковую оценку на экзамене.
3.	Мальчик купил 49 апельсинов и раздал их среди 8 друзей. Доказать, что кому-то из друзей досталось по крайней мере 7 апельсинов.
4.	Миша в течение трех дней купил 100 марок. Доказать, что в один из этих трех дней он купил не менее 34 марок.
5.	Машинистка, перепечатывая текст в 25 страниц, сделала 101 ошибку. Доказать, что найдется страница, на которой она сделала более четырех ошибок.
8
6.	На выставке собак была зарегистрирована 51 собака. Конкурс устраивался по шести различным породам. Доказать, что в конкурсе по одной из пород участвовало по крайней мере И собак.
7.	У мальчика 25 медных монет. Доказать, что у него найдется 7 монет одного достоинства.
8.	[5, 107]. В ящике лежат цветные карандаши : 10 красных, 8 синих, 8 зеленых и 4 желтых. В темноте берем из ящика карандаши. Какое наименьшее число карандашей надо взять, чтобы среди ши заведомо а) было- не меньше 4 карандашей одного цвета? б) был хотя бы один карандаш каждого цвета? в) было бы не меньше 6 синих карандашей? (Приведите примеры, показывающие, что меньше взять нельзя.)
9.	В ящике лежит 100 флажков : красных, зеленых, желтых, сшпи. Какое наименьшее число флажков надо взять не глядя, чтобы среди ши нашлось не менее 10 одноцветных? (Приведите пример, показывающий, что меньше взять нельзя.)
10.	В компьютерном классе может находится не менее 3 и не более 12 компьютеров. В городе 91 школа, в каждой из которых имеется компьютерный класс. Доказать, что найдется по крайней мере 10 школ, в компьютерных классах которых стоит одинаковое число компьютеров.
11.	В ящике лежат 10 пар перчаток черных и 10 пар перчаток красных. Сколько перчаток надо вытащить из ящика наугад, чтобы наверняка среди них были : а) две перчатки одного цвета, б) одна пара перчаток одного цвета, в) одна пара перчаток (возможно разного цвета)? (Приведите примеры, показывающие, что меньше взять нельзя.)
12.	(5, 114]. В классе 40 учеников. Найдется ли такой месяц в году, в котором отмечают свой день рождения не меньше, чем 4 ученика этого класса?
13.	В пяти классах школы 160 учеников. Доказать, что среди них найдется не менее 4 человек, у которых день рождения в этом году в одну и ту же неделю.
14.	15, 115]. В школе 30 классов и 1000 учащихся. Доказать, что есть класс, в которм не менее 34 учеников.
15.	В школе более 1100 учеников. Доказать, что среди них найдутся четыре, имеющие один и тот же день рождения в году
9
16.	(1). в Москве около 7.1 млн. жителей, на голове у ждого меньше 100 тыс. волос. Доказать, что в Москве есть >тя бы 70 человек с одинаковым числом волос на голове.
17.	[2]. У человека на голове не более 300 тыс. волос, доказать, что в Москве найдутся 25 человек, у которых число юлос на голове одинаковое (население Москвы - более 8 млн. человек).
18.	В некотором лесу имеется 600 001 елка. На каждой елке менее 100 тыс. иголок. Доказать, что в лесу по крайней мере 7 елок с одинаковым числом иголок (или. быть может, совсем без иголок).
19.	На Земле живет* более 3,6 млрд, человек. Известно, что среди них найдется не более одного процента людей старше 100 лет. Доказать, что на Земле найдется по крайней мере два человека, родившиеся в одну и ту же секунду.
20.	[4, 22]. Доказать, что среди 82 кубиков, каждый из которых выкрашен в определенный цвет, всегда можно выбрать 10 кубиков так, что либо все они выкрашены в разные цвета, либо все они одного цвета.
21.	[4, 25). По краю круглого стола равномерно расставлены таблички с фамилиями дипломатов, участвующих в переговорах. После начала переговоров оказалось, что ни один из дипломатов не сидит против своей таблички. Можно ли повернуть стол так, чтобы по крайней мере два дипломата сидели протиг своих табличек?
22.	(Квант. 1976. N 3. С. 68). В олимпиаде участвовало 55 школьников. Все они сдали свои работы. При проверке каждой задачи ставилась одна из трех оценок : "+" - задача решена, - задача решалась, но не решена, "0" - задача не решалась. После проверки всех работ оказалось, что ни в каких двух работах не совпало одновременно количество оценок
и оценок Какое наименьшее число задач могло быть предложено на олимпиаде?
23.	(5, 123). Шестеро друзей решили в воскресенье побы- • вать в семи кинотеатрах, сеансы которых начинаются в 9, 10, И....... 19 часов. На каждый сеанс двое из них шли в один ки-
нотеатр, остальные - в другой. Вечером выяснилось, что каждый из них побывал в этот день во всех семи кинотеатрах. До
10
казать, что в каждом из семи кинотеатров хотя бы на одн< сеансе в этот день не был никто из друзей.
24.	(Квант. 1990. 9. С. 70.) На отборочный тур олимпиах были приглашены победители из 8-го, 9-го, 10-го и ll-i классов - всего И человек. Можно ли их рассадить за круглы столом так, чтобы среди любых пяти сидящих подряд школьнике нашлись представители всех четырех классов?
25.	(Обл. тур Всес. олимп., 1991.) В квадрате размеров пхп каждая клетка закрашена в один, из (п-1) цветов. Разрешается любую строку или любой столбец перекрасить в один цвет, если в ней или в нем были две клетки этого цвета. Доказать, что за несколько таких перекрашиваний можно добиться того, что весь квадрат будет одного цвета.
26.	Бесконечный лист бумаги разлинован в клетку. Каждая клетка окрашена в один из данных п цветов (п & 2). Доказать, что найдутся 4 клетки одного цвета, центры которых являются вершинами прямоугольника, стороны которого параллельны прямым линиям на бумаге.
27.	(Квант. 1990. N 2. М1183.) Каждый из семи мальчиков в воскресенье 3 раза подходил к киоску мороженого. Известно, что каждые два из них встречались около киоска. Докажите, что в некоторый момент там встречались одновременно трое мальчиков.
В предыдущих задачах мы использовали идею переполнения. В настоящей теореме и следующем за ней цикле задач применяется принцип недополнения.	п•(n-1)
ТЕОРЕМА Если в п клетках сидит менее-------------зайцев,
2 то найдутся две клетки, в которых одинаковое количество зайцев (может быть, ни одного).
ДСКАЗАТЕЛЬСТВО. Предположим, что во всех клетках разное количество зайцев. Выпишем число зайцев возрастания :	< а2 <...< а^. Тогда в
не меньше О зайцев ; а а О, во второй
а2 * 1, в третьей - не менее двух зайцев/ ад а 2, и т.д.
в клетках в порядке первой клетке будет
- не менее одного :
Всего зайцев, посаженных в клетки, будет не менее а + а + n-(n-l)	1	2
+...+ a а О + 1 + 2 +...+ (п-1) =----------. А их по условию
п	2
n-(n-l)
менее ---------. Получили противоречие. Значит, найдутся две
2
клетки с одинаковым количеством зайцев. Смысл теоремы в том, п- (п-1) что нам как бы не хватает зайцев. Если бы было ровно-------
2 зайцев, то, посадив в клетки зайцев так : в первую - ни одного, во вторую - одного, в третью - двоих и т.д., мы бы имели клетки с различным числом зайцев в них.
28.	В районе 14 школ. На район выделили 90 компьютеров. Доказать, что как бы мы их ни распределяли между школами, найдутся две школы, получившие одинаковое число компьютеров (может быть, ни одного).
29.	[1]. Двадцати одному мальчику дали 200 орехов. Доказать, что как бы они их не разделили, найдутся два мальчика, которым досталось поровну орехов (может быть, ни одного).
30.	К празднику 10 мальчиков надули 44 шарика, среди них 11 красных, а остальные - других цветов. Доказать, что а) найдется мальчик, надувавший по крайней мере два красных шарика, б) найдется мальчик, надувавший по крайней мере 5 шариков, в) найдутся два мальчика, надувавшие одинаковое количество шариков (может быть, ни одного).
31.	Из леса возвращались 25 грибников. При подсчете грибов оказалось, что всего они собрали 275 грибов, причем среди собранных грибы только шести сортов : белые, грузди, волнушки, рыжики, подосиновики и подберезовики. Докажите, что а) среди грибников есть два, набравшие одинаковое количество грибов (может быть, ни одного), б) если среди грибников есть набравшие разное количество грибов, то найдется грибник, собравший по крайней мере 12 грибов, в) среди всех собранных грибов найдутся 46 одного сорта.
32.	[6. 424]. Десять студентов-математиков составили 35 задач для математической олимпиады. Известно, что среди них
12
были студенты, составившие по одной, две или три задачи. Доказать, что среди них были студенты,* составившие не менее пяти задач.
33.	В кружке "Умелые руки" занимаются 13 девочек. Они сшили 70 платьев куклам. Причем известно, что среди них есть те, кто сшил одно или два платья. Доказать, что в кружке можно найти девочку, сшившую по крайней мере семь платьев.
34.	(Квант. 1990. N 9. С. 70.) Докажите,что из 53 различных натуральных чисел, не превосходящих в сумме 1990, всегда можно выбрать 2 числа, составляющие в сумме 53.
§ 2.	Теория чисел
Приведем примеры, когда при решении задач на делимость чисел используют принцип Дирихле.
ПРИМЕР 3. [5, 108]. Доказать, что среди шести любых целых чисел найдутся два, разность которых делится на 5.
РЕШЕНИЕ. Эта задача сводится к принципу Дирихле простым утверждением, что разность двух целых чисел делится на 5, если они имеют одинаковые остатки при делении на 5. Значит, нам достаточно доказать, что среди шести чисел всегда найдутся два, имеющие одинаковые остатки при делении на 5. Так как возможных остатков при делении на 5 только пять : 0, 1, 2, 3, 4, а чисел шесть, то по принципу Дирихле это всегда будет выполнено.
Чтобы понять связь с зайцами и клетками, представим себе, что у нас шесть бирок с написанными на них шестью данными числами. Возьмем шесть зайцев и повесим на шею каждого из них пр бирке с заданным числом. На каждую из пяти клеток повесим табличку с одним из возможных остатков при делении на S. Рассадим зайцев в клетки по следующему правилу : заяц сиди? в Клетке. если число, записанное на его бирке, при делении йа 5 даег остаток, совпадающий с остатком на табличке Клетки. По принципу Дирихле : как бы мы не рассаживали шесть зайцев в пять клеток, обязательно найдется клетка, в которой сидит по крайней мере два зайца. Рассмотрим этих двух зайцев. Числа, написанные на их бирках, имеют одинаковые остатки при делении на 5. Разность этих чисел и делится на 5.
13
Этот пример можно обобщить в виде следующей теоремы.
ТЕОРЕМА 3. Пусть нам дан набор целых чисел а^ а2„... а^. Среди этих чисел всегда найдутся два, имеющие одинаковые остатки при делении на п.
ДОКАЗАТЕЛЬСТВО. Действительно, всего при делении на п целого числа мы можем получить п различных остатков : 0, 1, ..., п-1. А чисел на одно больше. Следовательно, по принципу Дирихле найдется остаток, которому соответствуют по крайней мере два числа из данного набора. Они будут иметь одинаковый остаток при делении на п.
ПРИМЕР 4. [5, 126]. Если целые числа шип взаимно прос-ты, то найдется такое натуральное число к, что m -1 делится на п.	-
РЕШЕНИЕ. Пусть a^m, a2=mZ,...,a^i=mn+1. По теореме 3 найдутся два числа, имеющие одинаковые остатки при делении на п. Пусть это а^т1 и a=mJ (i>j). Тогда их разность m'-n? = mJ(m1”J-l) делится на п. Но ш и п взаимно просты. Поэтому существует k = i-j такое, что mk-l делится на п.
Приведем пример более тонкого применения принципа Дирихле в задачах на делимость чисел.
ТРИМЕР 5. [2]. Числа а и m взаимно просты. Доказать, что найдется натуральное к, для которого число ка при делении на m дает остаток 1.
РЕШЕНИЕ. Рассмотрим (т-1) число вига ка, где 0<к<т. Каждое из этих чисел не делится на т, так как а и т взаимно просты, а к<т. Покажем, что среди этих чисел есть то, которое при делении на m дает остаток 1. Предположим, что это не так. Тогда при делении на m эти числа могут давать всевозможные остатки, кроме 0 и 1. Таких остатков будет (т-2), а чисел - (т-1). По принципу Дирихле найдутся два различных числа ак и ак (к > к ), имеющие одинаковые остатки при 12	2	1
делении на m и разность которых a(k-kJ делится на ш. Так как а и т взаимно просты, то к -к делится на т. Но это 2 1
14
невозможно, поскольку О < k^ - k^ < m. Полученное противор чие показывает, что найдется такое к, что ка дает остаток при делении на т.
Тем самым мы доказали следующее утверждение : для любы взаимно простых целых чисел а и m всегда найдутся натураль ные к и 1 такие, что ka = Im + 1 или ка - Im - 1.
Заметим, что при доказательстве утверждения этого примера фактически мы доказали, что если числа а и m взаимно просты, то числа вида ka (1 s k s m-1) дают различные остатки при делении на m : 1, 2.... m-1.
ПРИМЕР 6. [21. Пусть а, Ь , х - некоторые натуральные числа. Доказать, что в последовательности х , х = ах +Ъ, 0	1 о
х = ах +Ь...... х = ах +Ь,... имеется бесконечно много
2	I	n	п-1
чисел, которые не являются простыми.
РЕШЕНИЕ. Если числа а и b имеют общий делитель d, больший единицы, то и все числа последовательности делятся на d, а следовательно, они составные. Пусть а и Ъ взаимно просты. Тогда для любого кХ) хк будет взаимно просто с а. Предполо жим, что в построенной последовательности составных чисел конечное число. Выберем из них член последовательности с максимальным номером N. Тогда для любого k>N х^ - простое число. Обозначим М = х . Рассмотрим (М+1) натуральных чисел N
х , х ,..., х . По теореме 3 или по принципу Дирихле N+1	М*2	N+M+1
среди этих члсел найдутся два, имеющие одинаковые остатки при делении на М. Пусть это х их (р > q). Тогда их раз-Р я
кость х - х делится на М. Но х - х = (ах	+ Ь) -
р	q	р	q	р-1
- (ах	+ Ъ) = а(х - х ). Поскольку а и М взаимно
q-l	р-1	q-l
просты, х - х делится на М. Аналогично х - х _ р-1 q-l	р-2	q-2
делится на М и т.д. Так мы дойдем до числа х -хи / N+p-q N
покажем, что оно делится на М = х^. Отсюда вытекает, что
15
х также делится на М. Так как х > М, то х N+p-q	N+p-q	N+p-q
составное число. Это противоречит предположению, что N -максимальный номер составного члена данной последовательности. Из этого противоречия вытекает, что в. последовательности составных чисел бесконечное число, что и требовалось доказать.
35.	[5, 117]. Доказать, что из любых трех целых чисел можно найти два , сумма которых делится на 2.
36.	[7, 1-296]. Верно ли, что из 5 чисел всегда можно выбрать два таких, у которых разность квадратов делится на 7?
37.	(5, 121]. Можно ли найти такие две (разные) степени числа 4, у которых а) последняя цифра одинаковая? б) две последние цифры одинаковые? в) три последние цифры одинаковые?
38.	[5, 122]. Можно ли найти такую натуральную степень числа 3, которая оканчивается на 0001?
33.	[5,	110]. Доказать, что найдется число вида
19711971...197100...0, которое делится на 1972.
40.	[5, 120]. Доказать, что существует натуральное число, последние четыре цифры которого 1972 и которое делится на 1971.
41.	[5, 111]. Доказать, что для каждого натурального числа п найдется натуральное число, все цифры которого пятерки и нули, которое делится на п.
2.	[1]. Докажите, что для любого натурального m существует число, записываемое (в десятичной системе) единицам# й нулями, делящееся на т.
43.	[2]. Существует ли такое натуральное п, Что п-ойНЧ-ное число, записываемое (в десятичной системе) одкйм* езШНЙ-цами, делится на 1977?
44.	(Квант. 1974. N 2. М206.) Дана бесконечная тюследо-вательность цифр. Докажите, что для любого натурального числа п, взаимно простого с числом 10, в последовательности можно указать такую группу стоящих подряд цифр, что записывав--, мое этими цифрами число делится на п.
45.	[7; 1-12]. Верно ли, что из 100 произвольных целых чисел всегда можно выбрать : а) 15, б) 16 таких, у £$й0рых разность любых двух делится на 7?
16
46.	(Всеросс. Олимп., i960.) Доказать, что среди чисел 2*-1, 22-!,..., 2п"1-1, где п - нечетное число, хотя бы одно делится на п.
47.	[1]. В строку выписано 5 натуральных чисел. Докажите, что либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.
48.	(5, 109]. Имеются п целых чисел. Доказать, что среди них найдутся несколько ( иди, быть может, одно ), сумма которых делится на п.
49.	По окружности расставлены п чисел. Докажите, что всегда можно выбрать несколько из них, стоящих подряд (или одно), сумма которых делится на п.
50.	Доказать, что среди 65 целых чисел всегда найдутся 9 чисел, сумма которых делится на 9.
» ____________
51.	(Квант. 1975. N 4. М284.) Сумма 100 натуральных чисел, каждое из которых не больше 100, равна 200. Докажите, что из та можно выбрать несколько чисел, сумма которых равна 100.
52.	(5, 118]. Доказать, что из совокупности любых 2n -1 целых чисел можно найти 2П чисел, сумма которых делится на
2n. w
53. (8, 3]. Доказать, что среди любых 39 последовательных натуральных чисел обязательно найдется такое, у которого сумма цифр делится на И.
54. [1].Даны 12 различных двузнач: ых чисел. Докажите, что из mix можно выбрать два числа, разность которых - двузначное число, записываемое двумя одинаковыми цифрами.
*
55. [6, 770]. Некоторое натуральное число удвоили, затем прибавили к нему единицу. Вновь полученное число удвоили и прибавили единицу. Описанную операцию повторили сто раз. Может ли полученное в итоге число делиться на 1981?
56. [6, 493]. Рассмотрим последовательность 1, 1, 2, 3, 5, 8, 13,..., каждый член которой, начиная с третьего, равен сумме двух предыдущих (последовательность Фибоначчи). Напишем под каждым членом этой последовательности три последние его цифры (если этих цифр меньше трех, число дополняется
17
слева нулями) : 001, 001, 002, 003, 005, 008, 013,... . Доказать, что полученная последовательность - периодическая.
Применение принципа Дирихле к задачам по теории чисел разнообразно. Это показывает следующий цикл задач.
ПРИМЕР 7. [2]. Доказать,что для любого числа а и любого натурального числа N найдутся такие целые числа m & 0, 1 , к > 0, что | ка - m | s —.
N
1	2	N-1
РЕШЕНИЕ. Точки	~,	-.....—-	разбивают отрезок [0,1] на
N	N	N
N отрезков, мы их будем считать "клетками". Числа 1, 2......
N+1 будем считать "зайцами". Рассадим "зайцев" по "клеткам" следующим образом. Возьмем к. Представим число ка в виде ка = m + х, где m - целая часть ка (наибольшее целое число, не превосходящее ка), а х - его дробная часть. Тогда х попадет в один из отрезков, на которые разбит отрезок [0,1]. В эту "клетку" мы и посадим "зайца" к. Так как "зайцев” на одного больше, чем "клеток", то по принципу Дирихле найдется "клетка", содержащая по крайней мере двух "зайцев". Это означает, что существуют два различных числа и к2 (к1<к2>
1 такие, что ка = ш.+ х, к а  т + х , |х - х I л ”.
1	1	1	2	2	2	* 1	2’,.,
N
1
Таким образом, I (к-к )а - (т -т ) I * ”. Следовательно, 1	2 1	2	1	1
N
числа k=k2~kj и т=т2~т1 удовлетворяют условиям задачи.
ПРИМЕР 8. [2]. Пусть р и q - натуральные числа, и рацио-Р
нальное число — записывается в виде бесконечной десятичной Ч
дроби. Доказать, что тогда эта дробь будет периодической.
РЕШЕНИЕ. При выполнении деления числа р на число q "столбиком" мы все время будем получать ненулевые остатки
18
р
(иначе дробь — будет конечной десятичной дробью). Таким образом. при нахождении очередной цифры частного в остатке будет получаться одно из чисел : 1, 2..... q-1.	При выполнении
первых q делений мы получим q остатков. По принципу Дирихле найдутся по крайней мере два равных. Пусть это i-й и j-й по счету остатки (i<j). Если на i-м шаге мы получили остаток г, то для некоторого п справедлива формула :
р = q(a + а Ю”1 + а 10”* +...+ а 10 п) + r*10'n, г 4 о 1	2	п
где а , а .... а - первые п значащих цифр после запятой в
12 п
Р
разложении числа —. Чтобы получить следующие значащие цифры, необходимо делить "столбиком" число г на q. Поэтому следующие цифры однозначно определяются остатком г. Это означает, что поскольку i-й и j-й остатки совпадают, процесс деления, начиная с j-ro остатка, в* точности повторяет процесс деления после i-ro остатка. Пусть между появлением этих остатков мы получили к значащих цифр : а , а ............. а . Тогда
гн1 п+2	п+к
р = q(a т а 10”1 + а 10‘2 +...+ а 1О‘п + а’ 1О‘п"1 +...+ 0	1	2 .	п	п+1
+ а 1О‘п*к) + г’10*п"к. Следующие значащие цифры получают-п+к
ся делением г на q. Поэтому это снова а , а .......... а . и
п+1	п+2 п>к
т.д. Получаем периодическую последовательность с периодом к.
57. [9, 39]. Пусть а , а ..... а - некая перестановка
12	п
чисел 1,	2,..., п. Доказать,	что произведение
(а-1)(а -2)...(а -п) равно четному числу, если п нечетно. 12	п
58.	В соревнованиях по бегу участвуют 100 спортсменов. Известно, что среди любых 12 человек найдутся двое знакомых. Докажите, что как бы ни раздали спортсменам стартовые номера (не обязательно от 1 до 100) найдутся два знакомых спортсмена, номера которых начинаются с одинаковой цифры.
19
каким-то способом выбрано выбранных чисел делится на
45-уголышк. Можно ли рас
1... 9	так, чтобы для лк>
59.	(2). Даны 8 целых чисел а , ал. а . О < а < а <
2	2	8	12
<.,.< а < 16. Докажите, что для некоторого к и данных вось-8
ми чисел можно выбрать не менее трех пар (а{,ар, связанны? соотношением а - а = к.
i J
60.	12]. В вершинах выпуклого 65-уголькика написаны различные натуральные числа, каждое из которых не превосходит 1977. Доказать, что найдутся две диагонали, для которых разности чисел, написанных у их концов, одинаковы.
61.	(1). Из ряда 1,2.200
101 число. Доказать, что одно из другое.
62.	[8, 37). Дан правильный ставить в его вершинах цифры 0,
бой пары различных цифр нашлась сторона, концы которой занумерованы этими цифрами?
63.	(1). Дано 20 целых положительных не равных между собой чисел, меньших 70. Доказать, что среди их разностей найдутся 4 одинаковые.
64.	(5, 112). Сколько можно взять разных натуральных чисел, не больших 10, чтобы среди них не нашлось двух, одно из которых точно вдвое больше другого? (Приведите гфимер, что больше взять нельзя.)
65.	(5, 113). Верно ли, что среди любых 30 разных натуральных чисел, не превосходящих 50, всегда можно выбрать два, одно из которых вдвое больше другого?
66.	Известно, что из любых к натуральных чисел, не превосходящих п, можно выбрать два, одно из которых вдвое больше другого.
67.	[8, вычеркнуть нм одно из
других оставшихся чисел? Каким образом это можно сделать?
68.	[2]. Доказать, что из 9S0 различных натуральных чисел, не превосходящих 19Т7, можно выбрать три числа, сумма двух из которых равна третьему. Можно ж здесь уменьшись число 990?
При каких значениях к это возможно?
342). Какое наименьшее количество чисел нужно из совокупности чисел 1, 2,..., 1S32 так, чтобы оставшихся чисел не равнялось произведению двух
20
69.	15, 119). Даны п+1 различных натуральных чисел, меньших 2п. Доказать, что среди них найдутся три таких числа, что одно из них равно сумме двух других.
70.	(1). В городе Лиссе 10000 телефонов, номера которых задаются четырехзначными числами. В центральном районе установлено более половины всех телефонов. Доказать, что хотя бы один из номеров центральных телефонов равен сумме двух номеров других центральных телефонов (или удвоенному номеру такого телефона).
71.	(6, 458]. Карточки пронумерованы последовательными целыми числами от 1 до 2п+1. Какое наибольшее число карточек можно выбрать так, чтобы ни один из номеров не был равен сумме каких-нибудь двух других номеров карточек?
72.	[10, 4.7]. Множество чисел 1, 2. 100	разбито на
7 подмножеств. Доказать, что хотя бы в одном из этих подмножеств найдутся или 4 числа a, b, с, d, для которых а + b » » с + d, или 3 числа е, f, g, для которых е + f = 2g.
73.	[1]. Школьник в течение года решает задачи, каждый день - хотя бы по одной задаче. Каждую неделю, чтобы не переутомляться, он решает не больше 12 задач. Доказать, что найдется несколько последовательных дней, в которые он решит ровно 20 зад^ч.
74.	(Квант. 1989. N 6. М1143.) Масса каждой из 101 гирьки, расположенных по окружности, - натуральное число, а их сбщая масса равна 300 г. Доказать, что из этого набора можно выбрать одну или несколько гирек, расг воженных подряд, с общей массой 200 г.
 •
75.	[7, 367]. Доказать, что среди любых 2т+1 различных целых чисел, не превосходящих по модулю 2т-1, можно найти три числа, сумма которых равна 0.
76.	[5, 125]. Дано 51 различное Однозначное или двузначное число. Доказать, что из них можно выбрать шесть таких чисел, что никакие два из выбранных не имеют одинаковых цифр ни в одном разряде.
. 77. (Квант. 1974. N 8. М2366.) Даны натуральные числа к и п, 1<к<п. Для какого наименьшего m верно следующее утверждение: при любой расстановке ш ладей на доске размером n х п
21
можно выбрать к ладей из этих m так, чтобы никакие две из выбранных ладей не били друг друга?
*
78.	[11]. Последовательность чисел строится следующим образом. Первое число в ней равно двум. Каждое следующее число равно сумме десятых степеней цифр предыдущего числа. Докажите, что в этой последовательности встретятся два одинаковых числа.
*	п
79.	[6, 613]. 2 простых чисел выписаны в строчку. Известно, что среди них менее п различных. Доказать, что можно выбрать группу из рядом стоящих чисел, произведение которых является полным квадратом.
§ 3. Геометрия
В этом параграфе собраны геометрические задачи, которые в своем решении опираются на дискретный принцип Дирихле.
ПРИМЕР 9. [2]. Доказать, что если прямая не проходит ни чер» з одну вершину треугольника, то она не может пересечь все 3 стороны треугольника.
РЕШЕНИЕ. Прямая делит плоскость на две полуплоскости. Поэтому найдется полуплоскость, содержащая две вершины, а вместе с ними и отрезок, их соединяющий, который и не пересечет данная прямая. Допустим, что это не так. Тогда в каждой полуплоскости должно быть только по одной вершине. А вершин три. Получили противоречие. В данном случае вершины являются аналогами "зайцев", а полуплоскости - "клеток".
80.	Каждая грань куба выкрашена в белый или черный цвет. Доказать, что найдутся две грани с общим ребром, которые одинаково окрашены.
81.	(Квант. 1989. N 9. С. 73.) Часть клеток бесконечной клетчатой бумаги покрашена в красный цвет, остальные - в белый (не обязательно в шахматном порядке). По красным клеткам прыгает кузнечик, по белым - блоха, причем каждый прыжок может быть сделан на любое расстояние по вертикали или гори
22
зонтали. Докажите, что кузнечик и блоха могут оказаться рядом, сделав в общей сложности (в сумме) не более трех прыжков.
82.	[4, 23]. Плоскость произвольным образом раскрашена в два цвета. Доказать, что найдутся две точки одного цвета на расстоянии 1 м друг от друга.
83.	(Квант. 1976. N 6. М344.) На шахматной доске отмечены центры всех 64 полей. Можно ли провести на доске 13 прямых так, чтобы на каждой из частей, на которые эти прямые делят доску, оказалось не более одной отмеченной точки? (Прямые не должны роходить через центры полей.)
84.	[5, 127]. В единичный квадрат бросили 51 точку. Доказать, что некоторые три из них обязательно лежат внутри круга радиусом 1/7.
85.	Внутри равностороннего треугольника со стороной 1 расположено 5 точек Доказать, что можно выбрать две из них, расстояние между которыми.не более 0,5.
86.	В равнобедренный прямоугольный треугольник с катетом 1 брошены 1000 точек. Доказать, что найдется 32 точки, лежащие в полукруге радиусом 1/8.
87.	(5, 128]. Сосновый лес растет на участке, имеющем форму квадрата со стороной 1 км. Зная, что весь этот лес состоит из 4500 деревьев диаметром 50см, доказать .что в лесу можно выбрать прямоугольную площадку Юм х 20м, на которой не растет ни одно дерево.
88.	(1]. В квадрате, сторона которс о длиной 1, взята произвольно 101 точка (не обязательно внутри квадрата), причем никакие три из них не лежат на одной прямой. Докажите, что существует треугольник с вершинами в этих точках, площадь которого не более 0,01.
89.	(-]. В куб со стороной 1 помещена 2001 муха. Доказать, что хотя бы трех из них можно поймать сферой радиусом 1/11.
90.	[И]. Какое наибольшее количество точек можно расположить в квадрате со стороной 1 так, чтобы все расстояния между этими точками были меньше 0,5? ("В квадрате” означает "внутри квадрата или на его границе".)
91.	(Всеросс. Олимп., 1980.) Каждая вершина выпуклого
23
(2п+1)-угольника окрашена в один из трех цветов так, что любые две соседние вершины окрашены в разные цвета. Доказать, что (2п+1)-угольник можно разрезать непересекающимися диагоналями на треугольники так, чтобы вершины каждого треугольника были окрашены в различные цвета.
92.	(Квант. 1978. N 2. М441.) Внутри выпуклого 2п-уголь-ника взята точка Р. Через каждую вершину и точку Р проведена прямая. Доказать, что найдется сторона многоугольника, с которой ни одна из проведенных прямых не имеет общих точек (кроме, быть может, концов стороны).
93.	[10, 26.2]. На клетчатой бумаге отмечены произвольные п клеток. Доказать, что из них всегда можно выбрать не менее, чем п/4 клеток, попарно не соприкасающихся друг с другом (соприкасающимися считаются клетки, имеющие хотя бы одну общую вершину).
94.	(Квант. 1978. N 12. С. 56.) На плоскости дано 1978 точек. Запишем все попарные расстояния между ними. Доказать, что среди этих чисел не меньше тридцати различных.
•
95.	(Квант. 1991. N 7. М1226.) Внутри круга радиусом 1990 с центром в начале координат отмечено 555 точек с целыми координатами, никакие три из которых не лежат на одной прямой. Докажите, что найдутся два треугольника равной площади с вершинами в этих точках.
•
96.	[8, 166]. Каждая из девяти прямых разбивает квадрат на два четырехугольника, площади которых относятся как 2:3. Докажите, что по крайней мере три из этих девяти прямых проходят через одну точку.
97.	[8, 444]. Игра "Морской бой" происходит в квадрате 7x7 клеток. Какое наименьшее число выстрелов необходимо сделать, чтобы наверняка ранить четырехпалубный корабль { I I I |
98.	[8, 446]. Какое наименьшее число уголков П | нужно разместить в квадрате 8x8 клеток, чтобы в него нельзя было больше поместить без наложения ни одной такой фигуры?
99.	[6, 693]. В правильном 9-угольнике одни вершины
24
покрашены белым, а другие - черным цветом. Доказать, что существуют два различных конгруэнтных треугольника, вершины каждого из которых закрашены в один цвет.
100.	(Всеросс. Олимп., 1990.) В квадрате со стороной 12 расположены 1990 точек. Докажите, что существует равносторонний треугольник со стороной И, в котором расположены по крайней мере 498 из этих точек.
«
101.	(Квант. 1978. N 2. С. 55..) Каждая точка числовой оси, координата которой - целое число, покрашена либо в красный, либо в синий цвет. Доказать, что найдется цвет со следующим свойством : для каждого натурального к имеется бесконечно много точек этого цвета, координаты которых делятся на к.
102.	(Квант. 1990. N 3. М1188.) а) Дан 101 прямоугольник с целыми сторонами, не превосходящими 100. Доказать, что среди них найдутся три прямоугольника А, В, С, которые можно поместить друг в друга : A s В s С.
б) Доказать, что среди 1989 прямоугольников с целыми сторонами, не превосходящими 100, найдутся 40 прямоугольников таких, что первый можно поместить во второй, второй - в третий, .... 39-й - в 40-й.
103.	18, 4]. Дана таблица 4x4 клетки, в некоторых клетках которой расставляются звездочки. Докажите, что можно так расставить семь звездочек, что при вычеркивании любых двух строк и любых двух столбцов этой таблицы в оставшихся клетках всегда будет хотя бы одна звездочка. Докажите, что если звездочек ме.шпе, чем семь, то всегда можно так вычеркнуть две строки и два столбца, что все оставшиеся клетки будут пустыми.
104.	(Квант. 1990. N 3. М1190.) а) Доказать, что если в таблице 2п х 2п клеток стоят Зп звездочек, то можно вычеркнуть п строк и п столбцов так, что все звездочки будут вычеркнуты.
б) Доказать, что в таблице 2п х 2п клеток можно расставить Зп+1 звездочку так, что после вычеркивания любых п строк и п столбцов останется по крайней мере одна звездочка.
25
§ 4.	Теория графов
В некоторых задачах, связанных с принципом Дирихле, удобно применять теорию графов [см. 4, 12-15]. Изображая элементы некоторого множества точками и соединяя некоторые пары точек отрезками, мы получаем наглядное геометрическое представление данного множества и отношения между его элементами. Такое представление называется графом. Точки (элементы множества) называются вершинами, отрезки (или дуги) - ребрами графа. Количество ребер, выходящих из вершины, называется степенью вершины. Если на ребрах расставить стрелки, то получится ориентированный граф.
Если соединены все вершины, то такой граф называется полным. Часто используют при решении задач полные графы, у которых ребра раскрашены в разные цвета. Докажем следующее утверждение, аналог которого известен как задача Рамсея (см. задачу 105).
ТЕОРЕМА 4. В полном графе из 6 вершин с ребрами двух цветов найдутся три вершины, образующие треугольник с ребрами одного цвета.
ДОКАЗАТЕЛЬСТВО. Выберем произвольную вершину А графа.Тогда из нее выходит 5 цветных отрезков, соединяющих с оставшимися пятью вершинами. Так как цветов только два, то по принципу Дирихле из этой точки выходит по крайней мере три ребра одного цвета. В силу того, что красный цвет и синий цвет равноценны (мы всегда можем перекрасить красные ребра в синие, а синие - в красные), будем предполагать, что из вершины А выходит 3 красных ребра. Рассмотрим треугольник, состоящий из вершин, в которые эти три ребра ведут. Если одно из них красное, то его концы вместе с точкой А образуют красный треугольник. Если красных ребер в этом треугольнике нет, то значит, этот треугольник синий.
В качестве примера решим такую геометрическую задачу.
ПРИМЕР 10. На плоскости отмечено 6 точек, никакие три из которых не .лежат на одной прямой. Каждую пару этих точек соединили отрезком либо красного, либо синего цвета. Доказать, что найдутся три точки, образующие треугольник одного цвета.
26
РЕШЕНИЕ. Каждую точку плоскости можно считать вершин' графа, отрезки, их соединяющие, - ребрами графа. Тогда л теореме 4 найдется треугольник либо синего, либо красног цвета.
105.	[9, 1431. Задача Рамсея. Доказать, что в любой компании из шести человек всегда найдутся либо трое знакомых друг с другом, либо трое не знакомых друг с другом. (Считается, что если А знаком с В, то и В .знаком с А.)
106.	(15]. Шесть школьников участвуют в шахматном турнире, который проводится в один круг. Докажите, что всегда среди них найдутся три участника турнира, которые провели уже все встречи между собой, либо еще не сыграли друг с другом ни одной партии.
107.	(16(прил.), 4]. Даны 6 прямых в пространстве, из которых никакие 3 не параллельны, никакие 3 не проходят через одну и ту же точку и никакие 3 не лежат в одной плоскости. Доказать, что из этих 6 прямых всегда можно выбрать 3 прямые, из которых любые 2 скрещивающиеся.
108.	(15]. Каждый из 17 ученых переписывается с остальными. В их переписке речь идет о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Доказать, что не менее трех ученых переписываются друг с другом по одной и той же теме.
109.	(15]. Назовем группу людей "однородной", если любые два человека из этой группы знакомы, или, напротив, не знакомы. Докажите,что среди восьми случайно встретившихся людей всегда найдутся две однородные группы, состоящие из трех человек каждая, причем никто из первой группы не входит во вторую.
110.	(15]. В трехмерном пространстве 9 точек размещены так, что никакие три не лежат на одной прямой. Каждая точка соединена отрезками прямых в точности с четырьмя другими. Доказать, что всегда найдется хотя бы один треугольник с вершинами в этих точках.
Ш. (Квант. 1982. N 2. М687а.) В двятиугольной пирамиде все 9 боковых ребер и все 27 диагоналей основания окрашены : некоторые - в красный цвет, остальные - в синий. Докажите,
27
что существют три вершины пирамиды, служащие верпцшами треугольника, все стороны которого окрашены в одинаковый цвет.
112.	(Квант. 1990. N 9., С. 70.) В компании из семи мальчиков каждый имеет среди остальных не менее трех братьев. Доказать, что все семеро - братья.
113.	(Турнир городов, 1989.) 10 друзей послали друг другу праздничные открытки, так что каждый послал 5 открыток. Докажите, что найдутся двое, которые послали открытки друг другу.
114.	В компании 16 человек. Каждому из них нравится 8 человек из компании. Доказать, что есть двое, которые нравятся друг другу.
115.	(Квант. 1990. N И. С. 70.) В стране Далекой 101 город; города соединены дорогами с односторонним движением так, что любые два города соединены не более чем одной дорогой. Известно также, что из любого города выходит ровно 40 дорог и в любой город входит ровно 40 дорог. Докажите, что из каждого города в любой другой можно попасть, проехав не более чем по трем дорогам.
116.	(Квант. 1989. N И. М1168.) В стране 1989 городов и 4000 дорог (каждая дорога соединяет два города). Доказать, что можно выбрать кольцевой маршрут, проходящий не более, чем через 20 городов.
” некоторых задачах удобно сначала выделить крайний элемент, а после этого применить принцип Дирихле. В следующих задачах крайним элементом является вершина графа с максимальной степенью.
ПРИМЕР И. На плоскости отмечено п точек (п&2). Иеьвторые из них соединены дугами, но каждая пара не более, чем одной. Доказать, что найдутся две точки, из которых выходит одинаковое количество дуг.
РЕШЕНИЕ. Фактически точки с дугами, их соединяющими, образуют граф. Отметим точку Л на плоскости, из которой выхо-, дит максимальное число дуг - т. Если таких точек несколько,' то задача решена. Пусть такая точка единственна. Рассмотрим множество концов дуг, выходящих из А. Из каждого из них выходит хотя бы одна дуга, и число выходящих не превосходит
28
(m-i). Таким образом, количество возможных значений стелен вершин меньше числа вершин. По принципу Дирихле найдутся д вершины с одинаковой степенью. Это означает, что найдутс две точки, из которых выходит одинаковое количество дуг.
Задачу можно решить методом от противного. Предположим что все вершины графа имеют различные степени. Так как вершит может быть соединена с другой не более, чем одной дугой, тс степени вершин не превышают п-1. Поэтому количество значений, которые могут принимать степени, - п ( 0, 1,.... п-1 ). В силу того, что вершин -пи все они имеют разные степени, найдутся две вершины, одна из которых имеют степень С, а другая - (п-1). Такого быть не может, потому что тогда одна вершина не имеет выходящих ребер, а другая соединена со всеми остальными.
117.	(1]. Выберем произвольным способом пять человек. Доказать, что по крайней мере двое из них имеют одинаковое число знакомых среди выбранных.
118.	(1]. Доказать, что 23 октября 1965 года в кинотеатре "Мир” на первом сеансе присутствовало минимум двое зрителей, имеющих среди сидящих в зале одинаковое число знакомых (известно, чю в первом ряду сидело пять человек).
119,	(6, 461]. В комнате находится 50 человек. Некоторые из них знакомы между собой, другие - нет. Считается, что если А знаком с В, то В знаком с А. Доказать, что в комнате найдутся 2 человека, имеющие одинаковое число знакомых среди присутствующих.
120.	[5, 124]. В розыгрыше кубка по футболу (в один зфуг) участвует 30 команд. Доказать, что в любой момент найдутся две команды, сыгравшие одинаковое количество игр.
121.	(6, 475]. В первенстве по футболу принимают участие п команд. Каждые две команды должны сыграть между собой один матч. Доказать, что на любом этапе соревнования найдутся две команды, сыгравшие одинаковое число матчей.
Ш.	(17, 13.9]. Доказать, что у любого выпуклого многогранника найдутся две грани с равным числом сторон.
1S3.	(5, 380]. На конгрессе собрались ученые, среди которых есть друзья. Оказалось, что никакие двое ученых,
29
имеющих равное число друзей, не имеют общих друзей. Доказать, что найдется ученый, который имеет ровно одного друга.
§ 5. Принцип усреднения
Следующие утверждения не принято называть принципом Дирихле, но их доказательство также основано на логическом противоречии переполнения или недополнения. А связаны они с понятием усреднения.
ТЕ	ОРЕМА 5. а) Если сумма чисел а + а +...+ а ь S 12	П
(соответственно s S), то найдется элемент а( такой, что S S
а а ~ (a s — 1 п 1 п
б)	Если сумма чисел а + а +...+ а = S, то либо все 12	п
S
они равны -, либо найдутся два числа а( и а^ такие, что S S
В формулировке пункта а теоремы 5 все пестроте перавен-ва можно заменить на строгие. Другими словами это утверждение еоремы звучит так: среди нескольких чисел всегда найдутся два, одно из которых не больше среднего арифметическо
го этих чисел, а второе - не меньше его.
ДОКАЗАТЕЛЬСТВО, а) Предположим противное : пусть не найдется числа а^ г: s/n. Это означает, что для всех j а^ < S/n. Суммируя все элементы, находим, что а + а +...+ a <n-S/n = 12	п
= S, что противоречит условию теоремы. Аналогична и в других случаях.
б)	Если все данные числа равны между собой, то все они равны S/n. Предположим, что среди них есть неравные. Выберем из них* наибольшее (пусть - это а() и наименьшее (а^). В силу того, что среди них есть разные, имеем : а(>а^. Докажем
30
теперь, что эти числа удовлетворяют условию теоремы. Предположим противное. Пусть, например, S/n. Так как - наи-
меньшее число из всех заданных, каждое из них не меньше S/n, а а( строго больше S/n. Следовательно .сумма чисел +а строго больше S, но это противоречит условию теоремы. Л
Следовательно, a^S/n. Аналогично показывается, что a^S/n.
Следующая теорема есть обобщение уже доказанной теоремы,
но при доказательстве выступает как ее следствие. ТЕОРЕМА 6. а) Если сумма чисел а + а +...+ a t S 12	п
(соответственно s S), то для любого натурального k a п найдутся к чисел а ,а ...a (lai <i <...<! an) , сумма
11	1	12k
12 к
s	s
которых at + at +...+ a a k— (a + a +...+ a a k—). i 2	к n 1	*2	*k n
б) Если сумма чисел a + a +...+ a = S, то либо все 12	П
s они равны ~, либо для любого натурального к a п найдутся два набора индексов i Л....i (lai <i <...<! ап) и j ,j
12k	12k	12
S
1 <j <...<j an) такие, что a + a +...+ a > k-~ и k 1 2 k	II	1	П
12	k
S a + + a +...+ a < k*—.
J1 J2 Jk П ДОКАЗАТЕЛЬСТВО. Воспользуемся теоремой 5. Для этого построим вспомогательные суммы из к членов. Пусть b  а + а +...+ а , 112	к
о = а + а +...+ а', п-к*1	л-к+1	п-к+2 г п
/
>	« а + а +...♦ а + а г
n-k+2	n-k+2	n-k+3	n 1
31
b « a + a + a +...♦ a, . n n 1	2	K-l
Легко заметить, что каждое число присутствует в заданных суммах ровно к раз. Поэтому сумма построенных чисел равна Ь +Ь +...+Ь = к*(а +а +...+а ). По условию пункта а а+а + 1 2 n	1 2 п	12
+...+а aS. Отсюда следует, что b +b +...+b tkS. По теореме 5 n	1 2 п	•
найдется число b(tkS/n. Но bj и есть сумма к исходных чисел. Таким образом, пункт а теоремы доказан.
Прежде чем доказать пункт б теоремы, предположим, что заданные числа а1>а2........ап занумерованы в порядке
возрастания (asas...sa). По условию пункта б а+а„ + +...+an=S. Поэтому bj+b^.-.+b^kS. Рассмотрим случай, ког-
да среди исходных чисел есть разные. Тогда а < а . Следова-1 п
только, b < b . Последнее означает, что среди чисел b , 1	n-k+1	1
Ь.... b есть различные. В силу пункта б теоремы 5 среди
2 п
этих чисел найдутся два и такие, что b^kS/n, b<kS/n.
Отсюда сразу вытекает утверждение пункта б теоремы С.
ПРИМЕР 12. По окружности расставлено 1991 число, сумма которых неотрицательна. Доказать, что найдется 100 стоящих
подрал чисел, сумма которых также неотрицательна.
РЕШЕНИЕ. Обозначим эти числа по порядку по часовой стрелке а^а2......а1991- Как и ПРИ Доказательстве теоремы 6»
введем дополнительные суммы :
b 1
= а + 1
а +...+ а ,
2 юо'
+...+
b 2
= а +
а
з
2
а , 101
b = а * а +...+ а , 1892	1892	1893	1991
Ь « а ♦ а +...+ а ♦ а, 1893	1893	1894	1991	1
Ь 1991
а + а ♦ а +...+ а 1	2	<
32
Сумма всех этих чисел неотрицательна, так как Ь +Ь2 + +...+Ъ	= 100*(а +а +...+а	) а 0. По теореме 5 найдется
1991	1	2	1991
по крайней мере одно из них, которое также неотрицательно. Но каждое из чисел Ь{ является суммой 100 стоящих подряд исходных чисел. Из этого и следует утверждение задачи.
ПРИМЕР 13. Покупатель приобрел на рынке 13 помидоров общим весом 1,5 кг. Доказать, что среди купленных помидоров можно найти а) помидор, весящий более 115 г, б) 5 помидоров, суммарный вес которых меньше 580 г.
РЕШЕНИЕ. Обозначим вес 1-го по счету помидора а( г. Тогда а +а +...+а = 1500 г. По теореме 5 найдется а такое, 1 2	13	1
что а^а 1500/13 > 115 г. Значит, вес какого-то помидора больше 115 г. Таким образом, пункт а задачи решен. С другой стороны, по теореме 6 найдутся пять помидоров, суммарный вес которых не более 5*1500/13 < 580 г. Из этого следует пункт б данного примера.
ПРИМЕР 14. На плоскости проведены 9 прямых, про которые известно, что никакие две из них не параллельны и никакой угол между ними не исчисляется целым числом градусов. Доказать, что найдутся две прямые, один из углов между которыми больше 160°.
РЕШЕНИЕ. Через произвольную точку плоскости проведем прямые, параллельные заданным. 9 прямых, проведенные через одну точку, делят плоскость на 18 углов. Обозначим величину каждого из них через а, а,..., а. Тогда а +а +...+а = 12	18	1	2	18
= 360°. По теореме 5 либо все а{ равны между собой, либо есть среди этих чисел одно, которое меньше 360°/18 = 20°. Первый случай не может быть, потому что если все равны между собой, то они равны 20°, что противоречит условию задачи, что никакой угол между прямыми не исчисляется целым числом градусов. Поэтому найдется пара прямых, угол между которыми меньше 20°. Тогда дополнительный к нему угол больше 160°, что и требовалось доказать.
33
124.	[1]. Б доме 123 жильца, им вместе 3813 лет. Можно ли выбрать 100 из них, которым вместе не меньше ,3100 лет ?
125.	В составе поезда 52 вагона. Вес груза всего состава 261 тонна. Верно ли, что найдутся 40 вагонов, груз которых составляет в сумме более 200 т ?
126.	В соревнованиях по спортивной гимнастике участвовала команда девушек, состоящая из 6 человек. В командном результате девушки набрали 217 баллов. Докажите что из команды можно убрать одну гимнастку так, чтобы сумма оставшихся была более 180 баллов ?
127.	Букет цветов состоит из 9 роз. Число лепестков всего букета равна 190. Доказать, что найдутся 4 розы, лепестков у которых более 84.
128.	(Турнир городов, 1989.) Дано 1989 чисел. Известно, что сумма любых 10 из них положительна. Докажите, что сумма всех чисел положительна.
129.	[7, 4-22а]. Дано 1981 число. Сумма любых двух из них больше 1. Докажите, что сумма всех 1981 чисел больше 990,5.
130.	На нижнем круге, разделенном на 21 сектор, написано 21 число. На верхнем круге проделаны 5 окошек, в которые видны 5 чисел из нижнего круга. При любом положении верхнего круга сумма видимых чисел равна 0. Доказать, что сумма всех чисел равна нулю.
131.	(Квант. 1976. N 8. С. 58.) На полях бесконечной шахматной доски написаны натуральные числа так, что каждое число равно среднему арифметическому четырех соседних чисел -верхнего, нижнего, правого и левого. Докажите, что все числа на доске равны между собой.
132.	[6, 685]. Даны 1976 различных чисел. Известно, что произведение любых 7 из этих чисел больше 1. Доказать, что произведение всех 1976 чисел тоже больше 1.
133.	(6, 662]. Выпуклый n-угольник разместили в квадрате со стороной 1. Доказать, что найдутся три вершины А, В, С этого многоугольника такие, что площадь треугольника АВС не превышает 8/п .
*
134.	[7, 4-45]. В различных точках кольцевой дороги стоят несколько одинаковых автомобилей. Общее количество на^<-того в них бензина достаточно для того, чтобы один из них
34
объехал всю кольцевую дорогу. Докажите, что можно выбрать автомобиль, который, поехав по дороге и забирая бензин у всех стоящих на дороге автомобилей, сможет объехать всю кольцевую дорогу.
*
135.	(6, 583]. На каждой стороне картонного листа единичной площадью нарисованы карты, изображающие по 10 стран. Страны на одной стороне закрашены десятью разными красками. Доказать, что теми же красками страны на другой стороне листа можно закрасить так, чтобы они были разного цвета, а общая площадь участков картона, закрашенных с двух сторон в один цвет, была не меньше 0,1.
136.	[6, 432]. Внутри квадрата со стороной 1 лежат 102 точки, причем никакие три из них не лежат на одной прямой. Докажите,.что среди этих точек найдутся три такие, что площадь треугольника с вершинами в этих точках меньше 0,01.
137.	(6, 794]. Доказать,что в каждом девятиугольнике существует пара диагоналей, угол между которыми меньше 7 градусов.
138.	11]. На плоскости даны 7 прямых, никакие две из которых не параллельны. Докажите, что найдутся две из них, угол между которыми меньше 26 градусов. Верно ли аналогичное утверждение, если 26 градусов заменить на 25?
139.	(Квант. 1981. N 12. С. 37.) Докажите, что в любом выпуклом семиугольнике есть две диагонали, угол между которыми меньше 13°.
140.	(9, 172]. На плоскости задано г сть точек, из которых никакие три не лежат на одной прямой. Докажите, что из шести заданных точек три можно выбрать так, чтобы один из углов треугольника с вершинами в выбранных точках был не менее 120 градусов.
141.	(9, 194]. В круге выбрали 8 точек (точки граничной окружности считаются принадлежащими кругу). Докажите, что среди Я выбранных точек найдутся две такие, расстояние между которыми меньше радиуса круга.
35
§ 6.	Геометрический принцип Дирихле
В этом параграфе мы рассмотрим геометрические задачи, решения которых основаны на логическом противоречии геометрического недополнения или переполнения. В общем виде для плоского случая утверждения такого типа мы сформулируем в виде следующих теорем.
ТЕОРЕМА 7. Если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площадью S.
Другими словами это утверждение можно сформулировать так: если сумма площадей фигур, покрывающих фигуру Ф, меньше площади фигуры Ф, то в фигуре Ф можно найти точку, которая не покрыта ни одной из заданных фигур.
ДОКАЗАТЕЛЬСТВО. Пусть дана фигура Ф и несколько фигур Ф1,Ф2...Ф^,	покрывающих Ф. Рассмотрим вначале случай, ког-
да фигуры Ф) попарно не пересекаются. Тогда площадь объединения этих фигур равна сумме их площадей. Она меньше площади фигуры Ф. Если бы объединение фигур Ф( покрывало полностью фигуру Ф (то есть все точки из Ф принадлежали бы объединению), то площадь фигуры Ф была бы не больше площади объединения, а она больше по условию теоремы. Следовательно, найдется точка из Ф, не покрытая ни одной из фигур Ф.
Теперь пусть некоторые из фигур Ф( пересекаются. Построим новый набор фигур Ф ,Ф из данных по следующим правилам. Пусть Ф^^ Если Фх и Ф2 не пересекаются, то положим Ф2=Ф2- В обратном случае в качестве Ф2 выберем множество тех точек, которые принадлежат Ф , но не принадлежат 2
Ф . Тогда объединение Ф и Ф совпадает с объединением Ф и I	,	,	1	2	1
Ф2, но Ф1 и Ф2 не пересекаются. Сумма площадей Ф^ и Ф2 не
36
меньше суммы площадей фигур Ф1 и Ф2> За фигуру причем множество тех точек, которые не принадлежат объединению » » » »
фигур Ф1 и Ф2, но принадлежат фигуре Фз> Тогда фигуры Ф^ Ф, и Ф попарно не пересекаются, в сумме совпадают с объедине-3
нием фигур Ф , Ф и Ф , и сумма их площадей не больше суммы площадей фигур Ф^ Ф? й Фз- Эту процедуру продолжаем до тех пор, пока не построим весь набор Ф , Ф2..... Ф^. Построенные
фигуры попарно не пересекаются, их объединение совпадает с объединением фигур Ф , Ф2>..., Ф » и сумма их площадей не превосходит суммы площадей исходных фигур, откуда следует, что сумма их площадей меньше площади фигуры Ф По уже доказанному найдется точка из Ф, не покрытая фигурами Ф{, а значит, и фигурами Ф$. Таким образом, теорема доказана.
Здесь мы использовали принцип недополнения. Следующая теорема основана на обратном - принципе переполнения.
TEOPENL. 8. Если сумма площадей нескольких фигур, брошенных в фигуру Ф, больше площади фигуры Ф, то найдется точка из Ф, принадлежащая по крайней мере двум фигурам, брошенным в Ф.
ДОКАЗАТЕЛЬСТВО. Если все фигуры, брошенные в фигуру Ф попарно не пересекаются, то сумма их площадей равна площади их объединения и не превосходит площади фигуры Ф. Но это противоречит условию теоремы. Поэтому найдутся две фигуры, которые имеют общую точку. Эта точка и есть искомая, так как она принадлежит фигуре Ф и по крайней мере двум фигурам, брошенным в Ф.
Приведем утверждения двух теорем (без доказательства), которые обобщают теоремы 7 и 8.
ТЕОРЕМА 9. Если сумма площадей нескольких фигур меньше kS, то ими нельзя покрыть фигуру площадью S так, чтобы на ней не нашлась точка, покрытая не более (к-1) фигурами из данных.
37
Утверждение этой теоремы можно сформулировать так : если сумма площадей фигур, покрывающих фигуру Ф площадью S, меньше (k+l)S, то в фигуре Ф можно найти точку, которая покрыта не более к фигурами из заданных.
ТЕОРЕМА 10. Если сумма площадей нескольких фигур, брошенных в фигуру Ф площадью S, больше kS, то найдется точка из Ф, принадлежащая по крайней мере (к+1) фигурам, брошенным в Ф.
Как видно, эти теоремы ограничиваются двумерным случаем. Чтобы свести эти теоремы к подобным в других размерностях, необходимо заменить слова площадь и фигура на соотвествую-щие. В одномерном случае площадь естественно заменяется на длину, а фигуры - на отрезки, интервалы, дуги и т.п. В трехмерном случае площадь - это объем, а фигура - это тело.
ПРИМЕР 15. В квадрате со стороной 15 расположено 50 попарно непересекающихся квадратиков со стороной 1. Доказать, что в большом квадрате можно разместить круг радиусом 1 так, чтобы он не пересекался ни с одним из квадратиков.
РЕШЕНИЕ. Центр круга диаметром 1, целиком помещающегося внутри квадрата, должен быть расположен на расстоянии, большем 1/2, от любой из сторон
Рис. 1.
квадрата, то есть внутри квадрата 14x14, площадь которого равна 14-14 = 196. Кроме того, центр круга должен быть расположен на расстоянии, большем 1/2, от контура любого из квадратиков, то есть вне фигуры, получаемой из квадрата, четы— рех прямоугольников размером 1x0,5 и четырех четвертинок круга радиусом 1/2 (см. рис. 1). Площадь этой фигуры равна 1 + 4-1-0,5 + я(1/2)2 = = 3 + я/4. Суммарная площадь 50 таких фигурок равна 50(3 +
+ я/4) = 150 + 50я/4, что
38
меньше, чем 150 + 50-3,2/4 = 150 + 40 = 190. Таким образом, по теореме 7 покрыть квадрат площадью 196 такими фигурами нельзя - найдется точка внутри этого квадрата, не принадлежащая ни одной из 45 построенных фигурок. Круг радиуса 1/2 с центром в этой точке не пересекает брошенных квадратов и сторон исходного квадрата со стороной 15.
142.	Дсразать, что в круге радиусом 9,5 нельзя разместить 401 точку так, чтобы расстояние между любыми двумя было бы больше 1.
143.	(8, 12]. В прямоугольник со сторонами 20 и 25 бросают 120 квадратов со стороной 1. Докажите, что в прямоугольник можно поместить круг диаметром 1, не пересекающийся ни с одним из квадратов.
144.	(Квант. 1991. N И. С. 38.) В квадрате 70x70 размещены без налегания пять фигур : квадрат 30x30, прямоугольники 25x15 и 20x10 и два круга радиусами 5. Докажите, чго найдется место, чтобы, не сдвигая имеющиеся фигуры, разместить еще один круг радиусом 5.
145.	Парк имеет форму квадрата со стороной 1 км. На территории парка имеются озеро формой круга радиусом 200 м и лес, состояний из 1500 одинаковых деревьев радиусом 80 см. Докажите, что в парке можно найти лужайку формой прямоугольника 20м х Юм, на которой нет деревьев.
146.	(Квант. 1973. N 10. С. 45.) В квадрат со стороной 38 см бросили 100 выпуклых многоугольников, площадь каждого из которых не превосходит я см2, а перим гр - 2л см. Докажите, что в хвадрат можно поместить круг радиусом 1 см, не пересекающийся ни с одним из многоугольников.
147.	(Квант. 1973. N 10. С. 45.) В квадрате со стороной 1 находится 9 отрезков длиной 1/2. Доказать, что на некоторых двух отрезках найдутся точки М и N,< расстояние между которыми меньше 1/4.
148.	(Квант. 1973. N 10. С. 45.) В параллелепипеде 5x10x25 произвольным образом расположено 120 единичных кубов. Докажите, что в параллепипед можно поместить шар радиусом 1/2, не имеющий общих точек ни с одним из кубов.
39
149.	[8, 78]. Докажите, что в выпуклый четырехугольник площадью S и периметром Р можно поместить круг радиусом S/P.
150.	[6 , 507]. Докажите, что в выпуклый многоугольник площадью S и периметром Р можно поместить круг радиусом S/P.
151.	(Квант. 1981. N 8. М656.) В пространстве имеются 30 ненулевых векторов. Докажите, что среди них найдутся два, угол между которыми меньше 45°.
152.	(Квант. 1978. N 12. С. 56.) На белой сфере 12) площади поверхности закрашено в черный цвет. Доказать, что существует вписанный в сферу прямоугольный параллелепипед, все вершины которого находятся в белых точках.
153.	(Квант. 1982. N 9. М735). а) Докажите, что круг диаметром 1 нельзя покрыть несколькими бумажными полосками, суммарная ширина которых меньше 1.
б)	Назовем слоем толщины h часть пространства, заключенную между параллельными плоскостями, находящимися на расстоянии h друг от друга. Докажите,что шар диаметра 1 нельзя покрыть несколькими слоями .суммарная толщина которых меньше 1.
*
154.	[4, 28]. Внутри круга радиусом 16 расположено 650 точек. Докажите, что найдется кольцо шириной 1 и внутренним радиусом 2, содержащее не менее 10 из этих точек.
155.	(6, 598]. Внутри квадрата со стороной 1 расположено несколько кругов, сумма радиусов которых равна 0,51. Докажите, что найдется прямая, которая параллельна одной из сторон квадрата и пересекает по крайней мере два круга.
156.	[6, 608]. Внутри квадрата со стороной 1 расположены несколько окружностей, сумма длин которых равна 10. Докажите, что существует прямая, пересекающая хотя бы четыре из этих окружностей.
157.	[1]. Несколько дуг окружности покрашены в черный цвет. Сумма длин окрашенных дуг меньше половины длины окружности. Докажите, что существует диаметр, оба конца которого не окрашены.
158.	(4 , 27]. В окружности радиусом 1 проведено несколько хорд, суммарная длина которых больше, чем 1п. Локажжп, что найдется диаметр, пересекающий не менее восьми хорд.
40
159.	В окружности радиусом 1 проведено несколько хорд. Доказать, что если каждый диаметр пересекает не более к хорд, то сумма длин хорд меньше як.
160.	Внутри окружности радиусом п расположено 4п отрезков длиной 1. Докажите, что можно провести прямую, параллельную или перепендикулярную данной прямой а и пересекающую по крайней мере два данных отрезка.
161.	(17, 13.10]. Внутри шара радиусом 3 расположено несколько шаров, сумма радиусов которых равна 25 (эти шары могут пересекаться). Докажите, что для любой плоскости найдется плоскость, параллельная ей и пересекающая по крайней мере 9 внутренних шаров.	у
162.	Даны две окружности, длина каждой из которых равна 100 см. На одной из них отмечено 100 точек, а на другой -несколько дуг, сумма длин которых меньше 1 см. Доказать, что эти окружности можно совместить так, чтобы ни одна отмеченная точка не попала на отмеченную дугу.
163.	(7, 4-43]. На одной из двух одинаковых окружностей отмечены 50 красных точек, на другой - несколько синих дуг, сумма длин которых меньше, чем 1/50 длины окружности. Докажите, что можно так наложить первую окружность на вторую, что ни одна из красных точек не окажется ни на одной из синих дуг.
РЕШЕНИЯ ЗАДАЧ ’
1.	Аналогично разобранному примеру 3 положим "зайцами" всех учеников, кроме Саши. Их будет 40. "Клетками" предста--вим возможное число ошибок, их будет 13 : 0, 1........12. Сле-
довательно, n=13, а (nk+l)=40. Отсюда к=3. в силу теоремы 1 найдется число ошибок ("клетка"), которое совершили (в которой сидят) по крайней мере 4 ученика ("зайца").
2.	В данном случае студенты -это ’‘зайцы", оценки - это "клетки". Тогда зайцев 25, а клеток - 4 : п = 4, пк + 1 = = 25. Отсюда .вытекает, что к = 6. По теореме 1 найдется клетка, в котрой сидит по крайней мере к + 1 = 7 зайцев. Значит, найдутся семь студентов, получивших одинаковые оценки.
Можно было рассуждать другим образом. Предположим, что нет семи студентов, получивших одинаковые оценю!. Тогда каждую из возможных четырех оценок полу’пгли не более шести студентов. Из этого следует,' что студентов не более 24’, а их 25. Получили противоречие.
3.	Будем считать апельсины "зайцами", а каждого друга -"клеткой". Тогда в терминах теоремы 1 п = 8, a (nk + 1) = = 49. По принципу Дирихле кому-то из друзей (в какую-то "клетку") досталось (попало) по крайней мере 7 апельсинов (к+1 "зайцев").
4.	Как и в предыдущих решениях эту задачу легко свести к теореме 1. Но можно рассуждать непосредственно методом от противного. Допустим, что нет того дня, когда Миша купил 34 марки. Значит, в каждый из этих трех дней он покупал ле более 33 марок, а всего вместе тогда он купил не более 99. Однако по условию задачи он купил 100 марок. Получили противоречие.
5.	Пусть страницы - "клетки", а опечатки - "зайцы*. По принципу Дирихле следует, что как бы мы не сажали 101 "зайца" в 25 "клеток" обязательно найдется "клетка", в которой
42
будут по крайней мере;4 ’.’зайца". По этим же соображениям найдется страница, нй!	йгенёеопечаток.
6.	Если бы в конкурсеiib кфЙюй Из пяти1 пород участвовало не более 10 собак,"'76.. всЬго собак было бы не более! 50, а их по условию задачи: !5L/^чит/^сШйЙЙ:‘,1Й,;'к(ип^р(й® участвовало по крайней‘i^e^ff сЬбПк.1-' J i •>
7.	Всего медных МрйеТ разного достоинства МожеТ'бЫть четыре - 1 коп., 2 коп.,'3 коп. и 5 коп. Если бы'у ’Хмальчика было бы не более шести монет каждог6!ьд6стойнства, то всего у
него было бы не более 6-4 = 24 монет, а их п’о условию задачи 25. Следовательно, у него найдутся по крайней мере 7 монет одного достоинства.
8.а) 13. Всего различных цветов 4. Если мы взяли 13 ка-
рандашей, то по принципу Дирихле найдется цвет, которому соответствуют по крайней мере 4 карандаша .'' Здесь цвета -"клетки", а карандаши - "зайцы". С Другой стороны, если мы возьмем по 3 карандаша’каждого цвета, то всего' карандашей будет 12, и при этом ни одной четверки одного цвета. Этот пример показывает, что меньше тринадцати карандашей выбрать нельзя.
б)	27. Пусть мы выбрали 27 карандашей. Всего карандашей было 30. Поэтому остались невыбранными 3 карандаша. Но минимальное число карандашей одного цвета - 4 (желтого). Значит, по принципу Дирихле для каждого цвета найдется карандаш, не вошедший в число невыбранных, откуда следует, что среди выбранных всегда найдутся карандаши всех цветов. 27 есть наименьшее в этом случае число, так как 26 карандашей можно выбрать без карандашей желтого цвета.
в)	28. Аналогично предыдущему : если выбрано 28, то осталось - 2. Значит, максимальное число невыбранных синих карандашей тоже 2. Так как синих карандашей 8, среди выбранных этого цвета будет по крайней мере 6 карандашей.
9.	37. У нас флажки четырех разных цветов. Как бы мы ни выбирали 37 флажков, по теореме 1 найдутся 10 флажков одного цвета (здесь "клетки" - цвета, а "зайцы" - флажки). С другой стороны, 36 флажков для выполнения условия задачи недостаточно, так как мы можем достать по 9 флажков каждого цвета.
43
10.	Число компьютеров в любой школе может принимать 13 значений : О, 1,..., 12. А школ 92. По принципу Дирихле найдется школа, в которой будет по крайней мере 8 компьютеров. Здесь в терминах теоремы 1 п = 13, к = 7,
11.	а) Не менее трех. Так как цветов два: черный и красный, то из трех перчаток всегда найдется две одного цвета.
б)	Не менее 21. Всего пар перчаток 20. Если мы выбрали 21 перчатку, то по принципу Дирихле найдутся две, принадлежащие одной паре (одинакового цвета). Число 20 недостаточно, так как мы можем достать, например, 20 правых перчаток, не образующих между собой пар.
в)	Не менее 21. Рассуждения аналогичны предыдущему пункту.
12.	Допустим, что это не так. Это означает, что в каждом месяце отмечают не более трех учеников класса. Так как в году месяцев 12, то и учеников не более 36, а их по условию задачи 40. Получили противоречие. Здесь "клетки" - месяц, а ученики - "зайцы".
13.	Всего недель в году 53. Пусть недели - его "клетки", а ученики - "зайцы”. В терминах теоремы 1 п = 53, a n(k+l) = 160. Отсюда находим, что к = 3. По теореме 1 найдется неделя ("клетка”), в которой отпразднуют свой день рождения (находятся) по крайней мере 4 ученика ("зайца"), что и требовалось доказать.
14.	Если бы в каждом классе было бы не более 33 учеников, .о в 30 классах школы было бы не более 990 учеников, а их 1000. Получили противоречие.
15.	Пусть в году нет дня, в котором отмечали бы свой день рождения более трех учеников школь. Тогда из того, что в году не более 366 дней, в школе должно быть не более 1068 человек, а по условию их более 1100.
16.	По условию на голове у человека возможно от 0 (когда он совсем лысый) до 100 000 волос - всего 100 001 различных значений. Если бы каждому такому числу соответствовало не более 69 москвичей, имеющих это число волос на голове, то в Москве было бы не более 100001*69 = 6 900 069, что менее семи миллионов жителей. Однако по условию задачи в Москве более 7 миллионов жителей, что приводит к противоречию.
44
17.	Эта задача аналогична предыдущей. Ее формулировка несколько отличается, но это объясняется тем, что задачи придуманы в разное время. Ее можно решить, например, так. Распределим всех москвичей на группы по количеству волос на голове. Таких групп получим не более 300 001. Если в каждой группе будет не более 24 человек, то всего жителей Москвы не более 7,5 млн. А их более 8 млн. Противоречие. Значит, можно найти 25 человек с одинаковым числом волос на голове.
18.	Распределим елки на группы по количеству иголок на них. Получим не более 100 000 групп. Если бы в каждой такой группе было бы не более 6 елок, то всего в лесу было бы не более 600 000 елок, а их 600 001. Следовательно, найдется 7 елок с одинаковым количеством иголок.
Эта задача предлагалась на районной олимпиаде по математике в 1991 году.
19.	Если среди 3,6 миллиарда людей на Земле не более 1 процента тех, кто старше 100 лет, то тех, чей возраст не превышает 100 лет, не менее, чем 3,6-109(1-0,01) = =3,6-109-0,99 = 3,564"Ю9. Подсчитаем, сколько секунд входит в 100 лет: 100 лет < 36600 суток = 36600*24 часа = = 36600-24-60 Mini. = 36600-24-60-60 сек. < 3,66-104-25-3600 сек. = 3,66-104-9-104 < 3,3-109 сек. Таким образом, за последите 100 лет родилось не менее чем 3,5 млрд, людей, а различных секунд было менее 3,3-109. По принципу Дирихле найдется секунда, в которую родилось по крайней мере два человека, живущих на земле, что и требовалось доказать.
20.	Пусть 10 кубиков разного цвета выбрать нельзя. Это означает, что у нас кубики не более 9 цветов. Распределим кубики по группам в зависимости от цвета. Если в этом случае в каждой группе будет не более 9 кубиков, то всего кубиков будет не более 81, а их по условию 82. Следовательно, по принципу Дирихле найдется цвет, в который окрашено по крайней мере 10 кубиков.
21.	Можно считать, что таблички стоят в вершинах правильного n-угольника. Всего мы можем сделать п-1 различный поворот, переводящий п-угольник сам в себя, после чего снова
45
получим начальное положение. Следовательно, вместе с начальным мы получим п различных сочетаний табличек и неподвижно сидящих дипломатов. Так как мы будем двигать таблички по кругу, каждый дипломат на каком-нибудь шаге будет .дядеть против своей таблички. Такую ситуацию будем называть правильной. Заметим, что в начальном положении все они сидели против чужих табличек. Поэтому на оставшиеся п-1 сочетание приходится п правильных положений (так как дипломатов всего п). По принципу Дирихле найдется поворот, при котором произойдут по крайней мере два правильных положения, что и означает, что можно повернуть стол так, чтобы не менее двух дипломатов сидело бы против своих табличек.
22.	Предположим, что всего было дано на олимпиаде к задач.Каждая работа оценивается р плюсами и q минусами, р & О, q а 0, р + q s к. Зафиксируем сумму р + q = г. Изменяя р от О до г, получаем набор различных оценок этих работ. Всего их г+1. Изменяя г от 0 до к, получим всевозможные варианты оце-
(к+1)(к+2)
нивания. Всего их 1 + 2 +...+ (к+1) = -----------. Для того,
2
чтобы ни одна пара работ не совпала по плюсам и минусам, необходимо, чтобы количество работ было не больше полученного
(к+1)(к+2)
числа. Решаем неравенство : ------------s 55. Преобразуем :
2	2
к + Lx - 108 * 0 или (к + 12)(к - 9) * 0. Так как к - натуральное число, к+12 положительно. В итоге получаем к ь 9. Минимальное из таких к равно 9. Это и есть ответ задачи.
23.	Так как друзья смотрели кино в течение 11 часов (по часу на сеанс), и каждый час двое шли в один кинотеатр, остальные - в другой, то всего они посетили 22 киносеанса. Допустим, что есть кинотеатр, в котором они были на всех 11 киносенсах. Тогда оставшиеся 11 киносеансов, которые они посетили, приходятся на оставшиеся 6 кинотеатров. Следовательно, по принципу Дирихле из этих шести можно выбрать какой-то кинотеатр, где они посетили не более одного сеанса. На этом сеансе кто-то из них был, а кто-то нет, что противоречит условию, что каждый из них побывал в каждом кинотеатре. Сле
46
довательно, предположение неверно и во всех кинотеатрах хотя бы на одном седнсе в этот день не был никто из друзей.
24.	Нельзя?' Всего человек 11, а классов 4. Поэтому по принципу Дирихле найдется класс, представленный не более чем двумя участниками олимпиады. Рассмотрим положение этих двух участников за столом. Так как остальных человек 9, то найдется по крайней мере пять, сидящих между ними. В этой пятерке и не будет представителей данного класса.
25.	Выберем произвольную строку - в ней п клеток, закрашенных в (п-1) цветов. По принципу Дирихле найдутся две клетки одного цвета. Поэтому каждую строку можно перекрасить так, чтобы она была одного цвета. Тогда у нас получится квадрат, у которого все столбцы одинаковые. В каждом из них найдутся, две клетки одного цвета. В этот цвет мы можем перекрасить каждый столбец. Получим квадрат одного цвета.
26.	При решении этой задачи используется утверждение, сформулированное в начале § 1 : если бесконечное множество разбито на конечное число подмножеств, то найдется подмножество, содержащее бесконечное число элементов.
Предположим, что утверждение задачи не выполнено. Рассмотрим бесконечный столбец к^ клеток на листе, раскрашенных в конечное число цветов - п. По предыдущим рассуждениям найдется цвет (назовем его первым), которому соответствует бесконечное число клеток в столбце. Выкинем теперь все строки, кроме тех, в которых стоят клетки первого цвета столбца А^. Возьмем следующий столбец к^. В нем опять бесконечное число клеток. Поэтому найдется цвет, которому соответствует бесконечное число клеток в столбце. Если это первый цвет, то выберем две клетки этого цвета из первого столбца и стоящие с ними в одних строках две клетки из второго столбца. Эти четыре клетки одного цвета (первого) и образуют прямоугольник, стороны которого параллельны линиям на бумаге, что противоречит принятому предположению. Если это цвет, отличный от первого, то назовем его вторым. После этого выкинем все строки, кроме тех, в которых стоят клетки второго цвета столбца А .Аналогичную операцию произведем с клетками столб
47
ца Аз : выделим бесконечное число клеток с третьим цветом (первого и второго цвета быть не может), строки с этими клетками оставим, а остальные - выкинем. Этот процесс будем производить, пока не получим п бесконечных столбцов, в каждом из которых стоят клетки одного из п цветов. Возьмем теперь (п+1)-й столбец. В нем бесконечное число клеток. Поэтому найдутся две клетки одного цвета (пусть i-ro). Эти клетки вместе с клетками, стоящими в тех же строках и в столбце А(, образуют прямоугольник, стороны которого параллельны прямым линиям на бумаге и угловые клетки которого одного цвета. Но это противоречит принятому предположению. Следовательно, оно неверно, что и требовалось доказать.
27.	Пусть утверждение задачи неверно и пусть
- непересекающиеся промежутки времени, в течение которых около киоска находились двое мальчиков. В начальный момент каждого из промежутков Л2» d3,..., 4п к киоску подходил по крайней мере один мальчик, в начальный момент промежутка 4^ - либо один (если около киоска уже был мальчик), либо два (если около киоска никого из мальчиков не было). Следовательно, общее число s приходов к киоску всех семи мальчиков не меньше п+1. Так как всего из 7 мальчиков можно образовать 7-6/2 = 21 различную пару, а по условию каждые двое мальчиков встречались у киоска, п ь 21. Следовательно, s t 22. С другой стороны, s = 7-3 = 21. Противоречие.
28.	Предположим, что все школы получили разное количество компьютеров. Выпишем эти числа в порядке возрастания :
< а2 <...< а^. Первое из них не меньше 0, второе - не меньше 1, третье - 2 и т.д. Последнее не меньше 13. Их сумма, таким образом, не меньше 0+1+...+13=91 в этом случае. Но компьютеров на район выделено 90. Получили противоречие, из которого следует, что найдутся две школы, получившие одина- > ковое количество компьютеров.
Можно было рассуждать, применяя непосредственно теорему ’ 2. Пусть компьютеры будут "зайцами", а школы - "клетками". !
48
n(n-l) 14-U4-1) Тогда в терминах теоремы 2 п=14, а 90<--------=--------------
2	2
= 743 « 91. Отсюда из теоремы 2 вытекает, что найдутся две школы ("клетки"), в которых одинаковое количество компьютеров ("зайцев”).
29.	Аналогично предыдущей задаче, если все мальчики получили разное количество орехов, то в сумме они должны получить орехов не менее чем 0 + 1 +...+ 20 = 210, а их всего лишь 200. Значит, найдутся двое-, получившие поровну.
30.	а) Если бы среди мальчиков не нашлось ни одного, который надул по крайней мере два красных шара, то десять мальчиков надули бы не более десяти шаров, а их И. Значит, кто-то надул не менее двух красных шаров.
б) Аналогично : так как 10-4=40<44, то найдется мальчик, надувший более четырех шаров, то есть по крайней мере пять.
в) Если бы мальчики надули разное количество шариков, то шариков было бы не менее 0 + 1 +...+ 9 = 50, а их 44.
31.а) Пусть грибы будут "зайцами", а корзины грибников -п(п-1) "клетками". Тогда в терминах теоремы 2 п = 25, а ---------- =
25-(25-1)
= ---------- = 25*12 = 300 > 275. Значит, в силу теоремы 2
2
найдутся два грибника с одинаковым числом набранных грибов.
б)	Предположим, что среди грибник в нет такого, кто собрал по крайней мере 12 грибов. Тогда каждый собрал не более И грибов. Причем в силу того, что есть собравшие разное количество грибов, найдется грибник, собравший не более 10 грибов (иначе получится, что все собрали одинаковое количество грибов - по 11). Итак, имеем : од:;н собрал не более 10, остальные (а их 24) - не более 11. Тогда всего грибов собрано не более 10 + 24*11 = 274, что противоречит условию задачи, так как их собрано 275. Отсюда следует, что найдется грибник, нашедший по крайней мере 12 грибов.
в)	Если грибов каждого из шести сортов не более 45, то всего грибов не более 45-6 = 270, а их 275. Из этого противоречия следует, что найдется сорт, грибов которого собрано
49
по крайней мере 46.
32.	Если среди студентов не было составивших 5 и более задач, то каждый составил не более 4. Замен i, что по крайней мере было по одному студенту, составивших по одной, две и три задачи. Значит, всего задач должно было быть не более, чем 1 + 2 + 317-4 = 34, а их было 35. Противоречие.
33.	Предположим, что девочки сшили платьев не более шести каждая. По условию из 13 девочек есть две, одна из которых сшила одно платье, а другая - два. Тогда всего платьев они должны сшить не более чем 1 + 2 + 11-6 = 69, но на самом деле платьев было 70. Из этого противоречия следует, что есть девочка, сшившая по крайней мере 7 платьев.
34.	Предположим, что из данных 53 различных чисел, нельзя выбрать два числа, составляющих в сумме 53. Тогда среди них нет ни одной пары (k,53-k), где k = 1, 2,..., 2S. Выпишем данные числа в порядке возрастания а, < а„ <...< ag3. Тогда а не может быть меньше 53, иначе на 26 выписанных 27
пар будет приходиться 27 чисел, и по принципу Дирихле найдутся два числа из одной пары. Поэтому а* £ 1,	£ 2,
.... а £ 26, а £ 5-3, а £ 54,..., а £ 79. Тогда общая 26	27	2S	53
сумма этих чисел не меньше чем (1 + 2 +...+ 26) + 26- (26+1).	27-(53+79)
+ (53 + 54 +...+ 79) ~ -------— + + —-------------- s 2133, то
2	2
есть больше 1990, что противоречит условию задачи. Следовательно, сделанное предположение неверно.
35.	Любое целое число либо четно, либо нечетно. По принципу Дирихле из трех чисел всегда найдутся два числа, имеющие одинаковую четность. Их сумма и делится ка 2.
38. Заметим, что при делении на 7 квадрат целого числа может дать один из четырех возможных остатков s 0, 1, 2, 5. Представим целое число в виде m » 7q t г, С + г 2 £. Тогда
~ 49q2 14qr + г' « 7’(7q* + 2qr) + г2. Отсюдл следует, что числа т2 к г2 имеют одинаковые остатки при делении на 7. Поэтому достаточно проверить утверждение задачи для первых
50
семи натуральных чисел.
Так как возможных остатков четыре, а всего квадратов чи сел пять, по принципу Дирихле найдутся два квадрата, имеющих одинаковые остатки при делении на 7 и разность которых делится на 7.
Приведем другое решение. Заметим, что разность квадратов 2	2
двух чисел представима в виде а - b = (а - Ъ)(а + Ь). Поэтому для того, чтобы разность квадратов делилась на 7, достаточно, чтобы либо разность этих чисел делилась на 7, либо их сумма. Отсюда вытекает, что если среди выбранных чисел есть два, имеющие одинаковые остатки при делении на 7, то разность их квадратов делится на 7. Предположим, что все пять чисел имеют различные остатки при делении на 7. Возможные остатки при делении на 7 разобьем на 4 множества : {0}, (1,6), <2,5}, <3,4}. Рассмотрим 5 различных остатков, полученных при делении выбранных чисел на 7. По принцип:* Дирихле найдутся два, принадлежащих одному из построенных множеств. Сумма этих двух остатков равна 7. Поэтому сумма чисел, им соответствующих, делится на 7. Следовательно, и разность квадратов тоже делится на 7.
37.	Можно. Покажем это сразу для пункта-в}, из него будут следовать и первые два пункта. Для этого воспользуемся теоремой 3. Заметим, что совпадение трех последних цифр у двух чисел означает, что эти числа имеют одинаковые остатки при делении на 1000. Выберем первые 1001 натуральные степени числа 4. По теореме 3 среди них найдутс** две, имеющие одинаковые остатки при делен..и на 1000, а значит, и три последние цифры (тем более две и одну*).
Первые два пункта можно было решать, не пользуясь принципом Дирихле. Путем перебора можно было найти периодичность последних цифр степеней числа 4. Однако для трех и более последних цифр перебор становится физически неосуществимым (если нет компьютера под рукой).
4	0	1
38.	Рассмотрим 10 +1 первых степеней тройки : 3 , 3 З2,..., З10000. Согласно лемме среди них найдутся две различные степени, которые при делении на 104 дают одинаковые
51
остатки. Поэтому их разность будет делиться нацело на 104. Пусть это степени 3* и 3J (i > j). Тогда З1 - 3J = 104m для некоторого натурального т. Или (3I~J - 1)-3J = 104т. Так как 3J и 104 взаимно просты, a (3*"J - D'3J делится на 104, то и 3IJ - 1 делится на 104. Отсюда вытекает, что 3*"J - 1 = « 104k или 3м = = 104k + 1.Следовательно, найдется степень числа 3, оканчивающаяся на цифры 0001.
39.	Выпишем набор из 1973 чисел : 1971, 19711971, 197119711971... 19711971... 1971 (в последнем числе 1971
повторяется 1973 раза). По лемме найдутся два числа, имеющие одинаковые остатки при делении на 19?2. Следовательно, их разность делится на 1972. Но если из большего числа такого набора вычесть меньшее, то получится число вида 19711971...197100...0.
40.	Аналогично предыдущей задаче построим набор из 1972 чисел таким образом : 1972, 19721972  19721972... 1972 (в последнем числе четверка 1972 повторяется 1972 раза). Среди этих чисел, найдутся два, имеющие одинаковые остатки при делении на 1971, а значит, их разность делится на 1971. Эта разность имеет вид : 19721972... 1972-10* = 1971k. Так как 10* и 1971 взаимно простые числа, то существует число вида 19721972... 1972, которое делится на 1971, что и требовалось доказать в условии задачи.
41.	Аналогично предыдущим задачам строим набор чисел : 5, 55, 555  55...5 (в последнем числе 5 повторяется п+1 раз). Так как чисел п+1, найдется пара чисел, разность которых делится на п. Эта разность состоит из пятерок и нулей (она вида 55...500...0). Поэтому удовлетворяет условиям задачи.
42.	См. решение предыдущей задачи.
43.	См. решение задачи 34. Строим набор из 1978 чисел : 1, И, 111, 11...1 (в последнем числе единица повторяется 1978 раз). Как и раньше, по принципу Дирихле найдется пара,
52
разность которых делится на 1977. Вид этой разности таков И...Г10*. Так как 10* и 1977 взаимно просты, то найдется число, состоящее из одних единиц и которое делится на 1977.
44.	Будем считать, что нам задана бесконечная последовательность цифр а(, а2..... а(,..., записанная слева направо.
Рассмотрим такие числа	= а а ...а , Ь2 =
= а а ...а ..... Ь = а (черта здесь означает деся-тачную запись числа). По теореме 3 найдутся два числа b и bj (i<j), дающие одинаковые остатки при делении на л. Их
разность b -Ь = а а ...а	- а а ...а	=
1 J	1 1*1 пЯ	j j*i п*1
= а а ...а 00...0 = а а ...а •10п+2 '’ делится на п. 1 г*1 j-i	i i*i j-i
Так как по условию задачи п и 10 взаимно просты, отсюда
вытекает, что а|аН1...а,_,‘ делится на п, что и требовалось
Н
доказать.
45.	Сначала заметим, что в множестве целых чисел разность любы* двух делится на 7 тогда и только тогда, когда все числа этого множества имеют одинаковый остаток при делении па 7. Поэтому разделим 100 заданных чисел на 7 групп по остаткам при делении на 7. Так как групп 7, а чисел - 100, по принципу Дирихле найдутся 15 чисел, попавших в одну группу и, следовательно, удовлетворяющих условию задачи. Значит, для пункта а) ответ : верно.
Покажем, что в пункте б) ответ отрицательный. Выберем для простоты первые 105 натуральных чисел : 1, 2....... 105.
Разс<ьем их на 7 групп по остаткам при делении на 7. Тогда в каждой группе будет по 15 чисел. Выбирая 16 чисел, мы не можем всех их взять из одной группы. По принципу Дирихле найдутся два числа из разных групп. Разность этих чисел не будет делиться на 7.
46.	Покажем, что среди чисел 2-1, 2-1.... 2n -1 нет
такого, которое при делении на п дает остаток п-1. Допустим, что это не так. Пусть для какого-то j 2J-1 = nq + п-1. Тогда
53
2J = n(q + 1),что может быть только при одном нечетном n = 1 (в этом случае утверждение задачи тривиально), так как 2} и п взаимно просты. Предположим, что среди чисел 2*-1, 22-1... 2п1-1 нет такого, которое делится на п. Тогда в
силу предыдущего эти числа могут давать только п-2 различных остатка при делении на n : 1, 2.... п-2.	Но чисел п-1. По-
этому по принципу Дирихле мы должны найти два числа, имеющих одинаковые остатки при делении на п. Их разность (2*-1) -- (2J-1) » 2J-(2,-J-l) будет делиться на п. Так как 2J и п взаимно просты, то 2*'J-1 должно делиться на п. Но это противоречит начальному предположению. Из этого следует, что хотя бы одно из этих чисел делится на п.
47-49. Мы дадим общее решение этих трех задач. Пусть выписаны следующие числа : а, а....... а . Построим набор
12 п
чисел: b =а, b = а + а,..., b = а + а +...+а . Если 112	1	2 п 1	2 п
одно из них делится на п, то задача решена. Если среди них таких нет, то при делении на п они дают в остатке одно из п-1 возможных чисел : 1, 2...... п-1. Так как остатков на
единицу меньше, то по принципу Дирихле найдутся два числа, имеющие одинаковые остатки при делении на п и разность которых, следовательно, делится на п. Но разность = aJ+j + + а^2 +...+ а( и есть сумма подряд стоящих выписанных чисел. Решение задачи 47 получается, если положить п = 5.
50.	Рассмотрим остатки данных 65 чисел при делении на 9. Если среди них есть девять различных : 0, 1,..., 8, то сумма чисел, дающих остатки, делится на 9, так как сумма остатков 0 + 1 +...+ 8 = 36 делится на 9. Предположим, что среди полученных остатков нет одного из возможных. Тогда возможных значений остатков только 8, а всего остатков 65. По принципу Дирихле найдутся 9 одинаковых остатков (см. теорему 1 : возможные значения - "клетки", п = 8, остатки - "зайцы", (nk+1) = 65, следовательно, к+1 = 9). Сумма девяти чисел, имеющих одинаковые остатки при делении на 9, делится на 9.
54
51.	Пусть среди заданных чисел а, а а какие 12	100
нибудь /ва. например числа а} и а2> различны (если все числа одинаковы, то они все равны двум и 50 из них дадут в сумме 100). Составим новые ,100 чисел: b = а,Ь = а,Ь = а +
О 1*1	2	2	1
+ а...... b = а + а +...+а . Каждое из этих чисел
2	99	1	2	99
меньше 200, но больше 0. Среди остатков при делении на п найдутся либо 0, либо два одинаковых остатка. В первом случае bk> соответствующее нулевому остатку, равно 100 (делится на 100, больше 0 и меньше 200). Во втором найдутся два числа bj и Ь^ (i>j), разность которых равна 100. При этом i не может равняться 0 или 1, так как по условию задачи числа bQ и
Ь} не превосходят 100. Так как построенные числа Ь^ таковы.
что для любых i и j разность
(ь.
-ь?
есть сумма нескольких
данных чисел, то найдется сумма, равная 100.
52.	Докажем методом матиндукции (об этом методе решения задач можно посмотреть, например, в (18-211). При n = 1 эта задача поверяет задачу 35. Потому считаем, что базис доказан. Преположим, что при каком-то п утверждение задачи выполнено: из совокупности любых 2Р-1 целых чисел, можно вы-
брать Р таких, что их сумма делится на Р (здесь Р = 2П). Докажем, что из этого вытекает, что и при n + 1 оно верно. Пусть нам дано 4Р-1 каких-то целых чисел. Одно число уберем и оставшиеся разделим на две группы по 2Р-1 числу в каждой. По предположению индукции в каждой из групп найдется по Р чисел, сумма которых делится на Р. Всего 2Р чисел. Из оставшихся чисел опять же по предположению индукции можно выбрать Р чисел так, чтобы их сумма делилась на Р. В итоге имеем три группы по Р чисел, каждая из которых в сумме делится на Р. Пусть суммы в этих группах равны = Pq^ S2= Pq2, S3 = = Pq . Из трех чисел q , q , q всегда можно найти два, з	1	2 з
сумма которых четна (см. задачу 35). Пусть это qt и q2. Тог
55
да сумма 2Р чисел + S2 = = P(qi + q2) делится на 2Р, что и требовалось доказать.
53.	Среди первых двадцати из данных чисел найдутся два. у которых последняя цифра десятичной записи равна нулю (в каждой десятке последовательных натуральных чисел одно оканчивается на 0). Хотя бы у одного из этих двух чисел предпоследняя цифра не 9. Пусть это число - N, а сумма его цифр - S. Тогда числа N, N+1.... N+9,	N+19 содержатся среди
данных 39 и имеют суммы цифр S, S+l,..., S+10. Среди одиннадцати последовательных натуральных чисел одно делится на 11. что и требовалось доказать.
54.	Из 12 чисел согласно лемме найдутся два, имеющих одинаковые остатки при делении на И. и разность которых делится на И. Это будет двузначное число, так как единственное однозначное число, делящееся на И, - это 0, чего не может быть в разности. Все двузначные числа, делящиеся на И, записываются двумя одинаковыми числами.
55.	Может. Пусть мы выбрали число т. Тогда после первого выполнения операции получим число 2т + 1 = 2!(т + 1) -- 1. Проведем второй раз операцию : а2= 2а + 1 = 2(а}+ 1)-1= в 2г(т + 1) - 1. Замечаем закономерность afe = 2k(m + 1) - 1.
Докажем это методом матиндукции (см. (19-21JL Для первых членов последовательности это уже проверено. Пусть это выполнено для к : а = 2k(m + 1) - 1. Докажем, что из этого * км вытекает, что и а -2 (m + 1) - 1. Действительно а = к*1	к*»
в 2(а + 1) - 1 = 2(2 (га + !))-!« 2**,(m + 1) - 1.
к
Следовательно, а „ = 2100(т + 1) - 1 « 2l00n - 1. Как видно 100
из этой формулы, полученное в результате выполнения 100 раз операции число а{^ зависит от п.
Докажем теперь, что существуют такое целое n > 8 и натуральное к, что 2100п - 1 = 1Ш1*к. №няя п от 2 до 1992, поручим набор из 1981 числа :  2адо2 - fi, 2t003 - 1»...,
56
2 1982 - 1. Если среди них нет числа, которое делится » 1981. то при делении на 1981 они дают остатки от 1 до 198' Возможных остатков на единицу меньше, чем всего чисел. По этому по принципу Дирихле найдутся два числа, имеющие едина ковые остатки при делении на 1981 .Тогда их разность (2100i -- 1) - (2100j - 1) = 2100(i - j) делится на 1981, но таког< быть не может, так как 2100 и 1981 взаимно просты, а 0 < i -- j < 1981. Следовательно, среди выбранных чисел есть хотя бы одно 2|00п - 1, которое делится на 1981. Выберем теперь m = п - 1. Тогда а делится на 1981.
100
'56. Пусть а, а...... а,... - последовательность чисел
.	12	п
Фибоначчи, а г, г........ г,... - последовательность их по-
12 п
следних трех цифр. По условию числа Фибоначчи удовлетворяют уравнениям ; а = а^ + а для п > 1. Поэтому и в последовательности остатков каждый последующий член однозначно задается двумя предыдущими. Если + г .< 1000, то г ;
г + г . если же г + г а 1000, то г = г + г П п+1	п п+1	п+2 п п+1
- 1000. Таким образом, если две пары последовательных остатков совпали, то совпадут и члены последовательности, идущие за этими парами, что и означает ее периодичность.
Подсчитаем количество возможных различных пар в последовательности остатков. Каждый остаток принимает значение от 0 до 999, то есть возможных значений 1000. Тогда пара принимает 10002 = 106 различных вариантов. Возьмем из последовательности первые (10*+1) пар остатков. По принципу Дирихле найдутся по крайней мере две совпадающие пары, что и требовалось доказать.
57.	Если n = 2k - 1, то среди первых п натуральных чисел к этечепшх и к-1 четных, то есть нечетных на одно больше. Дяя того, чтобы произведение было нечетным, необходимо, что-бм ж® множители были нечетными. Действительно, если хотя бы отда ш множителей делится на 2, то и все произведение де-
57
i на 2. Чтобы разность вида а( - i была нечетной, необ-мо,чтобы числа а( и i были разной четности (то есть одно пюе, а другое - нечетное). Однако, как было уже замече-нечетных чисел больше, чем четных. По принципу Дирихле лется хотя бы одна разность, где из нечетного числа читается нечетное. Следовательно, произведите
- 1)(а - 2)...(а - п) четное. I	2	П
58.	Заметим, что стартовые номера могут начинаться толь-> с девяти различных цифр (с нуля они не могут начинаться). ,>еди 100 участников по принципу Дирихле найдутся 12 чело-к, имеющие номера, начинающиеся с одинаковой цифры. В про-инном случае на каждую цифру приходилось бы не более И частников, а значит, всего их было бы не более 99, а их -100. По условию задачи среди этих 12 всегда найдутся два •иакомых. Следовательно, найдутся два знакомых спортсмена, номера которых начинаются с одинаковой цифры.
59.	Рассмотрим всевозможные разности а -а, a8-d2.......
а -а , а -а..... а -а...... а -а . Всего т будет 7 + 6 +
8	7	7	1	7	6	2	1
...+ 1 = 8-7/2 = 28. По условию задачи наибольшая из них ag-aj не превосходит 14, так как а8 * 15, at а 1. Наименьшая из построенных разностей не меньше 1. Поэтому 28 разностей могут зринимать только 14 значений от 1 до 14. Заметим, что максимальное значение - 14 - может принимать только максимальная разность Таким образом, на оставшиеся 13 значений приходится не менее 27 разностей. По принципу Дирихле найдется значение к, которому равны по крайней мере три разности. Это и тебовалось доказать.
60.	Вначале посчитаем, сколько различных диагоналей внутри выпуклого 65-угольника. Возьмем первую вершину. Из нее проведем 64 отрезка к остальным вершинам. Из второй вершины проведем 63 отрезка (один, соединяющий с первой вершиной, мы уже провели). Из третьей - 62 и т.д. В итоге число отрезков равно 64 + 63 +...+ 1 + 0 = 65-32 = 2080. теперь вычтем чис
58
ло сторон. Получаем количество диагоналей : 2080 - 65 = > 1977. Так как максимальное выписанное число не превосх 1977, то и их разности также не превосходят 1977. Ч диагоналей больше, поэтому найдутся две диагонали, в коь которых стоят числа, отличающиеся друг от друга на один, вое число.
61.	Разобьем числа 1, 2. 200 на 100 групп следуют:
образом. Обозначим через Ап множество чисел вида (2п-1) . где п меняется от 1 до 100, а рьО таково, что (2п-1)-2р s 200. Тогда все числа внутри множества обладают т<
свойством, что одно делится на другое. Всего таких множис; 100. По условию задачи выбрано 101 число. Следовательно. н< принципу Дирихле найдется пара выбранных чисел, принадлежа тих одному множеству Ап- Это и означает, что одно из выбранных чисел делится на другое.
62.	Нельзя. Чтобы любая такая пара встретилась на какой-то стороне многоугольника, необходимо поставить каждую цифру по крайней мере 5 раз. Действительно, если цифра встретилась только 4 раза, то соседями у нее могут быть 8 цифр, а нужно, чтобы все оставшиеся девять. Так как цифр 10, для их размещения необходимо 50 мест, а их только 45. Поэтому требуемое в условии размещение цифр невозможно.
63.	Выпишем все числа в порядке возрастания : а^ < а2 < <...< а < 70. Вычтем из каждого предыдущее : b = а - а .
20	12	1
b « аз -аг..... Ь = а2о - а^. Предположим, что среди них
нет четырех одинаковых. Выпишем полученные разности в порядке возрастания. Первые три разности не меньше 1, следующие по порядку три - не меньше 2 (иначе четыре первых числа будут равны 1), следующие три - не меньше 3 и т.д. Шестая тройка чисел не меньше 6, а девятнадцатое число не меньше 7. Просуммируем эти неравенства. Получим, что их сумма, равная разности а2о - а^ не меньше ЗЧ1 + 2 +...+ 6) + 7 = 70. Но разность а20 - а^ < 70. Из полученного противоречия следует, что найдутся четыре одинаковые разности.
59
64.	Разобьем десять чисел от 1 до 10 на группы {1,2}, 3,6>, <4,8>, <5,10>, <7>, <9}. Всего получим 6 групп. Заме-.им, что если мы выберем числа так, что среди них есть пара 1з одной группы, то это и будет пара чисел, одно из которых твое больше другого. Если мы возьмем 7 чисел, или больше, то iio принципу Дирихле всегда найдется пара чисел из одной группы, одно из которой будет вдвое больше другого. С другой стороны, если взять 6 чисел по одному из каждой группы, например : 1, 3, 4, 5, 7, 9, то среди них не будет пары чисел, одно из которых вдвое больше другого. Таким образом, ответ в задаче : не больше шести.
65-66. Напишем общую формулу для числа k(n), при котором для любых к натуральных чисел, не превосходящих п, найдутся два, одно из которых вдвое больше другого. Разобьем первые п натуральных чисел на группы следующим образом. Каждая группа будет состоять либо из пары <р,2р>, либо из числа р (это в случае, если 2р превосходит п), где число р имеет вид р = 4ч*(2г - 1), q = 0, 1,... , г - натуральное. Тогда если мы возьмем два числа из разных групп, то они не будут обладать свойством, что одно больше другого вдвое. Два числа из одной группы, наоборот, удовлетворяют этому условию.
Посчитаем, сколько групп получилось. Это число совпадает с количеством чисел вида 4ч*(2г - 1), не превосходящих п. Начнем с нечетных (то есть q = 0). Количество нечетных чисел f равно п/2, если п четно, и - (n + DZ2, если п нечетно.
Пользуясь понятием целой части (напомним, что целая часть (х] - это наибольшее целое число, не превосходящее х), получаем f = 1(п + 1)/2]. Теперь зафиксируем произвольное q. Найдем число f натуральных чисел, делящихся на 4Ч , но не ч
делящихся на 2*4 и не превосходящих п. Это числа вида 4ч*(2г - 1), где г - натуральное. Найдем наибольшее г, для которого число вида 4ч*(2г - 1) не превосходит п. Для этого 1 п
решаем неравенство 4ч*(2г - 1) s о или г s —( — + 1 ).
2 4Ч
60
pin 1
Значит, f = I —( — + 1 ) I. Найдем максимальное q, д;:  4 L 2 44 J
которого f > 0. Это выполнено, когда 4Ч s п или q s log n. я	4
Пусть s = (log п]. Тогда всего построенных групп равно 4
f = f + f + ... + f » О 1	s
pl	q	p 1	П	-|	• pin	q
=• —(n +1)	+	—(- + 1)	+ ... +	—(- + 1) .
L 2	J	L 2	4	J L 2 4s	J
Если мы выберем k > f, то по принципу Дирихле найдутся два числа из одной группы (так как групп f меньше, чем число взятых-чисел к), одно из которых вдвое больше другого. Если же k s f, то выбирая числа по одному из каждой группы, получим набор чисел, не удовлетворяющих условию задачи. В частности, при п = 50 выберем числа таким образом. Возьмем 25 нечетных чисел. К ним добавим 4, 12, 20, 28 и 36 и получим 30 чисел таких, что никакие два не обладают тем свойством, что одно в два раза больше другого. Таким образом, ответ задачи 65 : неверно.
67. 43 числа : 2, 3.... 44.	Покажем, что из оставшихся
чисел нельзя выбрать три, одно из которых есть произведение двух других. Понятно, что 1 не может образовать такой тройки. Выберем какие-то два числа, отличные от 1. Каждое из них не меньше 45, следовательно, и произведение этих чисел не меньше 452 = 2025 > 1982. Значит, произведение любой пары оставшихся чисел не принадлежит данным числам.
Рассмотрим тройки чисел вида ( к, 89-к, к(89-к) }, где 2зк*44. Так как 44*45 = 1980 < 1982, то эти тройки составлены из чисел, входящих в ряд 1, 2.... 1982. Поэтому если мы
выкинем из этого ряда чисел менее, чем 43, то по принципу Дирихле найдется тройка, полностью принадлежащая оставшимся числам.
68-69. Решим сначала задачу 69. Пусть а < а <...< а
1	2	п+1
- данные числа. Вычтем из каждого наименьшее: Ь = а -а < /	1	2	1
61
< Ъ = а -а <...< b = а -а . Получим еще п положительных 2	3	1	n n+1	1
различных чисел, каждое из которых меньше 2п. Таким образом, мы имеем (2п+1) натуральных чисел, не превосходящих 2п. Среди этих чисел есть два равных. Но так как различны исходные числа и их разности, то совпадают какое-то число а& и какая-то разность b} t = а( - а^. Следовательно, а* = а( - или а& = а^ + а^, что и требовалось доказать.
При решении задачи 68 полагаем 2п = 1978, откуда получаем, что п = 989. В силу предыдущих рассуждений средн п+1 = = 990 чисел найдутся три, одно из которых равно сумме двух других. Покажем, что уменьшить 990 нельзя. Для этого возьмем 989 нечетных чисел : 1, 3,..., 1977. Сумма любых двух таких чисел равна четному числу и естественно не принадлежит исходному множеству.
70.	В центральном районе не менее 5001 телефона. Как и к предыдущей задаче выпишем все номера в порядке возрастания : а < а <...< а . Вычтем из каждого номера наименьший 1	2	5001
(может быть, 0000) : b =а -а < Ь =а -а <...< Ь ® 12 1	2 3 1	sooo
= a5001-aj- Получим 1001 число, каждое из которых может принимать 1000 значений - от 0000 до 9999. Найдется пара равных чисел : одно из них из первой группы, второе - из второй. Следовательно, найдутся i и к такие, что а^ = а^ + а&е что н требовалось доказать.
71.	п+1. Выберем нечетные : 1,2.. 2п+1. Покажем, что
п+2 числа выбрать таким образом нельзя. Гак и в предыдущих задачах, пусть а < а <...< а - данные числа. Вычтем из 12	п+2
каждого наименьшее: b = а -а < Ь = а -а <...< Ь « 12 12	3 1	п+1
= an+2~aj’ Получим еще п+1 положительных различных чисел, каждое из которых меньше 2п+1. Таким образом, мы имеем 2п+3 натуральных чисел, не превосходящих 2п+1. Среди этах чисел есть два равных. Но так как различны исходные числа я '£ разности, то совпадают какое-то число а и какая-то разноса к
62
V = а- а. Следовательно, a= а- а или a= a + а, что M !	1	к 1	1	Ilk
и требовалось доказать.
72.	По принципу Дирихле в одном из подмножеств будет по крайней мере 15 чисел (иначе в каждом из семи подмножеств было бы не более 14 чисел, а всего чисел было бы не более 7’14 — 98» а их - 100). Рассмотрим всевозможные разности (а-Ъ) пар чисел из этого подмножества, где а > Ь. Таких разностей будет не менее 15-14/2 = .105. Так как величина разности может принимать только значения от 1 до 100 - всего не более 100, по принципу Дирихле найдутся две пары чисел а > Ь И с > d таких, что а - b = с - d (а * с, b * d). Тогда а + d -tic. Если же при этом а = d (или b = с, других совпадений быть не может), то b + с = 2а (или а + d = 2b). Утверждение'задачи доказано.
72.	Предположим, что за первый день ученик решил а< задач, за два первых дня - а2...... за первые 77 дней - а^.
Рассмотрим числа а, а,..., а , а+20, а +20,..., а +20. Всего 154 числа. По условию задачи школьник в течение недели решает не более 12 задач, поэтому за первые 77 дней (за 11 недель) он решил не более 12’11 = 132 задач. Последнее означает, что максимальное из выписанных чисел а +20 s 152.
77
В итоге имеем, что 154 числа могут иметь 152 значения от 1 до 152. По принципу Дирихле найдется пара равных. Но среди чисел а, а ,..., а нет равных (иначе нашелся бы день, 12	77
когда он из решал задачи). Поэтому существуют i и j (i>j) такие» что а = а + 20 или а - а = 20. Отсюда следует, 1 J	1	1
те? начиная с (j+D-го дня по i-й день мальчик решил 20 задач.
.7,	5.Медниковым автору было сообщено другое решите этой згдачн. Выберем произвольные три педели, за которые он решал задачи. Пусть в первый день он решил х задач, во второй -
х Б 21-й день - х . Все это натуральные числа. Из ре-’зе:«ия зздач 47-49 следует, что найдутся несколько стоящим а-.гдряд чисел» сумма'которых делится на 20. Но так гак такая
63
сумма не больше 36 (каждую неделю он решал не больше 12 задач), она равна 20.
74.	Выберем новую окружность и отметим на ней 300 точек, разбивающих ее на 300 равных дуг. Снимая по одной со старой окружности, по этим точкам будем расставлять гирьки в следующем порядке. Выберем произвольную гирьку массой и поставим ее на произвольную точку новой окружности. Следующую по часовой стрелке гирьку массой тг поставим на новую окружность через дуг, на которые мы разделили окружность, по часовой стрелке от первой гирьки. Следующую гирьку поставим от второй через ш2 дуг и т.д. Так как сумма масс гирек равна 300, то все гирьки будут расставлены таким образом, что число дуг от некоторой гирьки до следующей по часовой стрелке равно ее массе.
Рассмотрим равносторонние треугольники с вершинами в заданных точках. Таких различных треугольников будет 100. Каждая точка нашей окружности будет принадлежать только одному такому треугольнику .Так как гирек 101, то по принципу Дирихле найдется треугольник, содержащий две вершины с гирьками на них. Это означает, что между некоторыми двумя гирьками ровно 100 дуг. Если двигаться по часовой стрелке от конца первой из этих дуг, то мы получим несколько гирек, стоящих подряд, сумма масс которых равна 100 г.
75.	Докажем методом матиндукции по ш (об этом методе см. [18-21]). При m = 1 утверждение выполнено. Действительно, три различных целых числа, по модулю не превышающих единицы, - это -1, 0 и 1. Их сумма равна 0. Пусть оно верно при ш = = к-1 (к ь 2). Рассмотрим произвольное множество А, состоящее из 2к+1 целых чисел, по модулю не превосходящих 2к-1. Если среди них найдутся 2к-1 чисел, которые не больше 2к-3 по модулю, то по предположению индукции найдутся три числа, сумма которых равна нулю. Пусть это не так. Тогда среди 2к+1 чисел есть три из множества : 2к-2, 2к-1, 2-2к, 1-2к.
Возможны два случая : либо среди этих чисел есть пара (2к-1,1-2к), либо среди них нет одного из пары (2к-1,1-2к). В первом случае рассмотрим пары (1,2к-2), (2,2к-3)............
64
(к-1,к). Их всего к-1, и сумма в каждой из них равна 2к-1 Возьмем также к пар (0,1-2к), (-1,2-2к),..., (-к+1,-к), сум ма элементов в каждой из них равна 1-2к. Всего пар мы полу чили 2к-1, да плюс число 2к-1, не вошедшее ни в одну из пар Но чисел в множестве А - 2к+1. По принципу Дирихле найдете пара, принадлежащая множеству А. Если это пара из перво группы пар, то вместе с числом 1-2к она образует тройку сумма в которой равна 0. Если же это пара из второй группы то она вместе с числом 2к-1 дает нам тройку, сумма элементе которых равна 0.
Рассмотрим второй случай, когда множество А не содержи одно число из пары (2k-l,l-2k) (для определенности пусть 1-2к, другой случай аналогичен в силу симметрии чисе относительно 0). Разобьем заданные числа на две группы пар (0,2к-2),’ (1,2к-3)... (к-2,к) и (-1,2-2к),	(-2,3-2к),..
(-к+1,-к). Всего таких пар получим 2к-2. Вместе с числам к-1 и 2к-1, не вошедшими в пары, мы образовали 2к подмно жеств возможных значений заданных чисел, а по условию т 2к+1. По принципу Дирихле найдется пара, принадлежащая мне жеству А. Если она из первой группы пар, то вместе с число 2-2к (а оно обязательно принадлежит А) эта пара образуй искомую тройку. Если - из второй, то к ней следует присоеди нить 2к-1, чтобы получить три числа, дающие в сумме 0. Таки образом, шаг индукции также доказан : утверждение верно при m = к.
76.	Разобьем заданные числа на груг ты, в каждой из коте рых находятся числа с одинаковой первой цифрой (если чист однозначное, то будем считать, что первая цифра - 0). Мака, мальное число возможных групп - 10, а чисел - 51. По принци пу Дирихле найдется группа, в которой по крайней мере 6 чм сел. Пусть это А&. Оставшихся чисел минимальное число - 4: По принципу Дирихле есть группа А&, в которой по крайней ме ре 5 чисел и т.д. Таким образом, выделим шесть групп чисе А , А2,..., А6 таких, что в А^ по крайней мере 1 число, в / - 2 числа..... в А6 - шесть чисел. Заметим, что числа »
разных групп обязательно отличаются первой цифрой. Выберс
65
из одно число Так как в А2 по крайней мере два числа, то мы всегда можем выбрать число а^, отличающееся от а^ второй цифрой. В Аз по крайней мере три числа, поэтому из них можно выбрать одно, отличное от а и а2 в разряде цифр. Рассуждая аналогично, мы можем выбрать из полученных групп шесть чисел, каждое из которых отличается от другого в разряде цифр. Так как каждое из них взято из своей группы, то любые два из них отличаются и в разряде десятков. Значит, никакие два из этих шести чисел не имеют одинаковых цифр ни в одном разряде.
77.	Докажем, что если m - n(k - 1) + 1, то всегда можно выбрать к ладей так, чтобы никакие две не били друг друга. Рассмотрим строки, в которых стоят ладьи, всего их п. По принципу Дирихле найдется строка Afc, в которой стоят по крайней мере к ладей. Рассмотрим оставшиеся строки - их будет (п-1). Так как в строку входит максимум п ладей, то оставшихся ладей не менее п(к - 2) + 1. Аналогично по принципу Дирихле найдется строка А^ , содержащая по крайней мере (к - 1) ладью, и т.д. (См. решение предыдущей задачи.) В итоге получим набор строк А , А2>..., Ак> обладающих тем свойством, что в первой находится по крайней мере одна ладья, во второй - две.... в k-й - по крайней мере к ладей.
Выберем к ладей следующим образом. Первую возьмем из строки А . Так как в строке А2 есть две ладьи, то из них выберем ту, которая стоит с первой ладьей в разных столбцах. Аналогично, поскольку в строке Ад стоит по крайней мере три ладьи, из них можно выбрать ту, которая стоит с первыми двумя в разных столбцах. Этот выбор мы можем продолжить, пока не получим набор из к ладей. Из построения этого набора следует, что никакие две ладьи из выбранных не стоят ни в одной строке и ни в одном столбце, а значит, и не бьют друг друга.
Покажем, что при m = n(k - 1) существует расстановка ладей, из которой выбрать к нужным образом нельзя. Для этого расставим все ладьи в первые (к - 1) строк. Если теперь
66
взять любые к ладей из этой расстановки, то по принципу Дирихле найдутся две, стоящие в одной строке и бьющие друг друга.
78.	Нетрудно убедиться, что первые члены последовательности содержат не более 12 цифр. Пусть у какого-то члена последовательности не более 12 цифр и пусть это цифры а , а2, .... a (п*12). Тогда последующий член последовательности п а а	а
равен 10 1 + 10 2 +..,+ 10 “ и.меньше 12-Ю10 (так как а^ < < 10). Последнее число имеет не более 12 цифр. Значит, и последующий член последовательности имеет не более 12 цифр. Следовательно, все члены последовательности имеют не более 12 цифр. Различных натуральных чисел, имеющих не более 12 *	12
цифр, всего - М = 10 -1. Рассмотрим первые (М+1) членов последовательности, каждое из которых принимает не более М различных значений. По принципу Дирихле найдутся по крайней мере два члена последовательности, принимающие одинаковые значения. Отсюда следует : в этой последовательности встретятся два одинаковых.
79.	Дли решения задачи достаточно показать, что в некоторой группе рядом стоящих чисел каждое простое число встречается четное число раз. Пусть в данной последовательности (а , а ,..., а } встречается m различных простых чисел р , 2
р .... р . По условию задачи m < п. Обозначим с степень
2	m	1J
числа Р[ (intern), в которой" это число входит в произведение а а •...•а первых j чисел данной последовательности, 1 £ js 12 J
з	2П. Пусть d^ - остаток от деления числа с на 2. Каждый набор D = = (d , d ,..., d ) состоит из ш нулей и
J	1J 2J mJ
единиц, всего таких наборов 2П. Но различных наборов вида (d, d ,..., d ) имеется 2m, где d - 0 или 1 (См. (201) 12m	k
Так как 2m < 2П, то найдутся два набора D( и Dfc, равны»
67
между
собой. Следовательно, d
d для всех 1 s i s ш. !к
Отсюда следует, что для всех
возможных
i с 1к
делится
на 2. Но по определению
с число pt встречается в
произведении aj+jaj+2 * • • • ’ ак =
- с^ раз. Поэтому любое число а а •...•а в четной степени,
J+l J+2 к
---------------- ровно с -а а • . . . • а
1 2	j
входит в произведение
то есть а а •...•а J+l J+2 к
точный квадрат.
80.	Выберем произвольную ьершину куба. К ней примыкает три грани, две из которых одного цвета. Они и имеют общее ребро, выходящее из данной вершины.
81.	Выберем горизонталь, на которой находится кузнечик, и вертикаль, на которой находится блоха. Эти горизонталь и вертикаль имеют общую клетку. Она либо красного цвета, либо белого. Если она белая, то в эту клетку прыгает блоха, если - красная, то - кузнечик. Так за один ход они окажутся на одной линии клеток. Между кузнечиком и блохой найдутся две соседние клетки разного цвета. За два оставшихся прыжка кузнечик и блоха окажутся в этих клетках.
82.	Выберем произвольный равносторонний треугольник со стороной 1м. По принципу Дирихле среди вершин (их три) найдутся две одинакового цвета. Они и удовлетворяют требованиям
задачи.
83.	Нельзя. Рассмотрим граничные клетки шахматной доски. Они представляют квадратное кольцо и их 28. Соединив центры угловых клеток отрезками, параллельными сторонам доски, получим контур квадрата, на котором лежат центры граничных клеток. Так как каждая прямая может пересечь контур не более чем в двух точках, то 13 прямых дают нам максимум 28 точек пересечения с контуром. Следовательно, 13 прямых делят контур не более чем на 26 частей. А отмечено точек на границе 28. Поэтому найдутся две точки, принадлежащие одной части.
84.	Разобьем квадрат на 25 квадратиков со стороной 1/5. Из 51 точки по принципу Дирихле найдутся три, лежащие в од-
68
ном квадратике. Круг, описанный около этого квадратика, /2	Г~\	/ 1	1
имеет радиус г =-------= v ------ < v ------ = Поэтому эти
10	50	49	7
три точки лежат и в круге радиусом 1/7.
85.	Проведем средние линии в равностороннем треугольнике. Они разбивают наш треугольник на 4 равносторонних треугольника со стороной 0,5. Так как точек 5, по принципу Дирихле найдется треугольник, содержащий пару данных точек. Покажем, что расстояние между любыми двумя точками, принадлежащими равностороннему треугольнику, не превосходит дли-. --------------------- - ны СТОроны этого треугольника.
*	Пусть нам дан треугольник АВС
j*	и две точки К и М в нем (см.
/\	- рис. 2). Проведем прямую КМ до
/ \	пересечения со сторонами тре-
/	\	угольника. Обозначим точки пе-
р /	\	ресечения Р и Е (пусть для
\	определенности Р лежит на АВ,
/	\ с а Е - на АС). Тогда РЕ КМ.
/	Рассмотрим треугольник АРЕ.
/	К \ Так как zPAE = 60°, сумма
f-------------------Р оставшихся углов АРЕ и АЕР
°	L равна .' 20°. Следовательно,
один из этих углов не меньше
Рис. 2.	’	60°. Допустим, что это угол
АРЕ. Мы получили, что zPAE s, zAPE. Но во всяком треугольнике против большего угла лежит большая сторона. Поэтому РЕ АЕ s АС, что и требовалось доказать.
86.	Разрезая равнобедренный прямоугольный треугольник пополам по биссектрисе прямого угла, каждый раз мы получаем два равнобедренных прямоугольных треугольника, у которых гипотенузы в 7~2. раз меньше гипотенузы исходного треугольника. Разрежем заданный треугольник таким образом на два, вновь полученные треугольники снова разрежем так, и эту операцию
69
проведем 5 раз, чтобы получить 32 одинаковых треугольника, подобных данному. Гипотенузы полученных треугольников в ('/~2Т> раз меньше, чем гипотенуза исходного треугольника. Так как она равна Уг, то гипотенуза каждого полученного треугольника равна 1/4. Такой треугольник помещается в полукруг с радиусом 1/8. Так как треугольников 32, а точек 1000, и 32-31 = 992 < 1000, то по принципу Дирихле найдется по крайней мере 32 точки, лежащие в каком-то из полученных треугольников, а значит, и в полукруге радиусом 1/8.
87.	Разделим квадратный участок на прямоугольные следующим образом. Возьмем произвольную сторону квадрата и разобьем ее на 48 равных отрезков. Через концы полученных отрезков проведем перпендикуляры к взятой стороне. На прилегающей стороне квадрата построим 95 равных отрезков, из концов которых восстановим перпендикуляры. Полученные прямые разобьют квадрат на 95-48=4560 прямоугольников размером 1/48x1/95 км. Если теперь в квадрат произвольно бросить «<>00 точек (центров деревьев), то по принципу Дирихле найдется прямоугольник, в котором не будет ни одной точки.
Внутри этого прямоугольника построим прямоугольник 10x20м, граница которого располагается на расстоянии, большем чем 25 см, от границы большого прямоугольника. Для этого построим отрезок длиной 20м в центре стороны прямоугольника размером 1/48 км. В его концах восстановим перпендикуляры. Они будут отстоять от сторон на расстоянии (1000/48 - 20)/2 > (20,5 -- 20)/2 = 1/4 м. Аналогично на другой стороне размером 1/95 км на расстоянии 5 м от ее центра построим перпендикуляры. Они будут отстоять от сторон прямоугольника на расстоянии 1000/190 - 5 >5,3-5>0,25м. Построенные перпендикуляры отсекают прямоугольник со сторонами 10м и 20м, граница которого расположена далее, чем 25 см, от границы большого прямоугольника. Мы показали, что в лесу нет дерева, центр которого находится в большом прямоугольнике. Следовательно, любой центр дерева расположен на расстоянии, большем чем 25 см, от маленького прямоугольника. А значит, это и есть прямоугольная площадка, на которой не растет ни одно дерево.
70
88.	Разобьем квадрат на 50 прямоугольников размером 0,1x0,2. По принципу Дирихле найдется прямоугольник, содержащий по крайней мере 3 из взятых точек. Покажем,что треугольник, образованный этими точками имеет площадь не более 0,01.
Зафиксируем треугольник АВС внутри прямоугольника. Возьмем вершину А. Через нее проведем прямую а, параллельную стороне ВС. Если по ней теперь двигать вершину А, то площадь 'Треугольника АВС не будет меняться. Если же выбрать любую точку At в полуплоскости, не содержащей отрезка ВС, то площадь треугольника А^ВС будет больше площади треугольника АВС, так как высота а Е боль-1 1
ше высоты АЕ, а основания ВС одинаковы (см. рис. 3). Если прямая а проходит через вер
шину прямоугольника, то возьмем за At эту вершину. Если это не так, то возьмем за точку А} ту вершину прямоугольника, которая лежит в другую сторону от отрезка ВС по отношению к прямой а. Это всегда можно сделать, иначе все вершины прямоугольника лежат по одну сторону гт прямой а, чего быть не может (а обязательно пересекает прямоугольник). Таким образом, всегда можно выбрать треугольник А^С такой, что Aj - вершина прямоугольника и его площадь не меньше, чем площадь исходного. Аналогично через вершину В проведем прямую р, параллельную АС, и выберем вершин., прямоугольника, лежащую с отрезком AjC в разных полуплоскостях, образованных прямой р. Обозачим ее В . Площадь полученного треугольника не меньше, чем площадь треугольника А^ВС, а значит, и исходного треугольника. Аналогично поступаем с вершиной С тре
71
угольника АДС. Получим треугольник АДСр вершины которого совпадают с вершинами прямоугольника. Его площадь равна половине площади прямоугольника и не меньше . лошади исходного треугольника. Следовательно, площадь любого треугольника, лежащего внутри прямоугольника, не превосходит половины площади этого прямоугольника, что и требовалось доказать.
89.	Разрежем куб со стороной 1 на 1000 кубиков со стороной 0,1. Большая диагональ такого куба равна i/з-ОД. Поэтому он входит в шар радиусом г^З-0,05. Так как /^3-0,05 < < 1,8-0,05 = 0,09 < 1/11, то этот куб вмещается и в шар радиусом 1/11. Поскольку мух 20G1, а кубиков 1000, по принципу Дирихле найдется куб, содержащий трех мух. Их и можно поймать сферой радиусом 1/11.
90.	Девять. Поставим точки таким образом : одну точку -в центр квадрата, четыре - в вершинах и еще четыре - в серединах сторон квадрата (см. рис. 4). При таком расположении точек любые две находятся на расстоянии не менее 0,5 друг от друга. Покажем, что больше девяти точек расположить в квадрате гребуемым образом нельзя. Разобьем квадрат на 9 маленьких квадратов со сторонами 1/3 (см. рис. 5). Если в квадрате точек больше девяти, то по принципу Дирихле найдется пара, попавшая в один и тот же маленький квадрат. Расстояние между этими точками не превосходит длины диагонали этого квадрата. Но диагональ квадрата со стороной 1/3 равна J2/3 <0,5. Значит, и расстояние между этими точками меньше 0,5.
72
Рис. 4 .
Рис. 5 .
91.	Докажем методом индукции по п (см. [18-19]). При п = = 1 мы имеем треугольник с вершинами разного цвета и ничего проводить не надо. При п = 2 у нас будет пятиугольник. Цветов три, а вершин пять, поэтому найдется цвет, которому соответствует только одна вершина А, а остальным цветам - по две верппшы. Соединим вершину А с остальными диагоналями и получим разбиение на треугольники с вершинами разного цвета.
Пусть для п = к-1 утверждение задачи выполнено. Покажем тогда, что это верно и для п = к. Для того, чтобы получил (2к-1)-угольник из (2к+1)-угольника, необходимо выделить два крайних треугольника, удовлетворяющих условию задачи. Попробуем это сделать. Так как вершин нечетное число и все соседние из mix окрашены в разные цвета, найдутся три вершины подряд различных цветов. Допустим, что это не так. Тогда при раскраске используются только два цвета, но в этом случае число вершин должно быть четно, а оно нечетное. Если у нас есть две ра?личные тройки вершин разного цвета, то мы проводим диагонали, отрезающие эти треугольники, и получим многоугольник с (2п-1) вершинами, который можно разрезать по предположению индукции. Если же таких троек только одна, то есть вершина А, имеющая цвет, отличный от всех остальных вершин. Соединяя их с вершиной А, получаем треугольники с вершинами разного цвета.
92.	Проведем диагональ АВ, делящую 2п-угольник на два (п+1)-угольника. Тогда точка Р лежит либо на этой диагонали, либо внутри одного из полученных многоугольников (назовем его G). Проведем прямые, проходящие через Р и вершины G.
73
Рассмотрим стороны оставшегося многоугольника. Его могут пересечь только прямые, проведенные из вершин многоугольника G, кроме А и В. Всего прямых мы построим п-1 (по числу оставшихся вершин), а сторон, свободных для пересечения с прямыми в многоугольнике G, - п. Следовательно, найдется сторона, которую построенная прямая не пересечет, что и требовалось доказать.
93.	Закрасим все клетки на бумаге в 4 цвета, как показано на рис. 6, так, что никакие две клетки одного цвета не
граничат между собой. Множество отме-
1	2	1	2	ценных клеток можно разбить на 4 под-
3	4	3	4	множества по цвету клеток, в них вхо-
1	2	1	2	дящих. По принципу Дирихле найдется
3	4	3	4	подмножество, содержащее не менее п/4
клеток. Эти клетки не будут сопри-
Рис.6.	касаться, так как они одного цвета.
94. Допустим, что различных попарных расстояний - к. Выберем две произвольные точки А и В. Проведем с центрами < данных точках по к концентрических окружностей (их радиусы -попарные расстояния). Тогда данные точки могут быть только точками пересечения этих окружностей. Каждая окружность с центром в точке А пересекает максимум все к окружностей с центром в точке В в 2k точках. Всего максимум точек Пересе-
2
чения - 2k . Да точки А и В. Значит, если попарных расстояний - к, то всего точек не более 2kz+2. Возьмем к = 31. Тогда точек должно быть не более 2-31* 2+2 = 1934 < 1978. Поэтому различных попарных расстояний более 31, а значит, и не менее тридцати.
95. Площадь треугольника с вершинами в целых точках -это число вида п/2, где п - целое число. Докажем это. Пусть нам даны точки В, Е, F с целыми координатами. Тогда треугольник BEF можно заключить в прямоугольник ABCD, вершины которого имеют целые координаты (см. рис. 7). Тогда длины отрезков АВ = CD = a, AD = ВС = b, АЕ = с, ED = d, DF = е, FC = f - натуральные числа. Поэтому площадь прямоугольника ABCD, равная S = ab, - натуральное число. В свою очередь ABCD
74
Рис.7
площади треугольников 5две = = ас/2, S = de/2, S = bf/2 EOF	BFC
- числа вида п/2, где n -натуральное число. Так как Sbee = S - S - S - S , то и ABCD ABE EDF BFC
площадь треугольника BEF - также число вида п/2.
Поскольку площадь треугольнике! не больше площади круга л-19902 <
< 12,6-106, она принимает не более 25,2-106 различных значе ний. С другой стороны (см. (20]), количество разных (неупорядоченных) троек из 555 точек равно 555-554-553/6 > 25,2-106. Значит, по принципу Дирихле найдутся два треугольника с равными площадями.
96.	Каждая прямая, разбивающая квадрат на две трапецш (или прямоугольника) с отношением площадей 2:3, в таком ж< отношении делит среднюю линию квадрата. Докажем это. Пуси дан квадрат ABCD (см.рис. 8). Его пересекает прямая MN
в	с
	г V -
X	Л
А  в
Рис. 8.
Рис. 9.
75
Пусть PQ - средняя линия квадрата ( Р - середина АВ, Q -середина CD ) и К - точка пересечения PQ и MN. Площади трапеций ABMN и NMCD равны соответственно АВ-РК/2 и AB*KQ/2. Поэтому если они относятся как 2:3, то и PK.-KQ = 2:3.
Таких точек, которые делят средние линии квадрата в отношении 2:3, всего четыре (рис. 9), а прямых - девять. По принципу Дирихле найдется точка, через которую проходят по крайней мере три прямые, что и требовалось доказать.
97.	Сделаем 12 выстрелов, как показано на рис. 10. Тогда как бы соперник не размещал корабль, всегда наздегся выстрел, который его поражает. С другой стороны, за И нельзя разместить в квадрате 7x7 (см.
98.	И фигур. В каждом квадрате 2x2 должно быть покрыто
Рис.12.
не меньше двух клеток, иначе на три клетки мы всегда можем наложить наш уголок (может быть, переворачивая). Таких квадратов 16, значит, должно быть обязательно покрыто 32 клетки. Десять уголков покрывают только 30 таких клеток. Поэтому таких фигур как минимум И. Размещение И уголков, удовлетворяющее условиям задачи, показано на рис. 12 (звездочками отмечены
непокрытые точки).
99. Из 9'вершин, закрашенных в два цвета, хотя бы пять имеют одинаковый цвет. Можно считать, что этот цвет - белый
76
(замена каждого цвета на противоположный не влияет на 5-4-3
утверждение задачи). Пять белых вершин образуют С3 =-------
5	2-3
= 10 различных белых треугольников (см. [20-21]). Каждый из них, поворачиваясь вокруг центра данного правильного девятиугольника, отмечает кроме себя еще 8 треголышков, вершины которых находятся в вершинах девятиугольника. Число всевозможных треугольников, образованных вершинами многоугольника, 9-8-7
равно С3 =--------= 78. Это число меньше 90 - количества от-
2-3
меченных треугольников. Поэтому по принципу Дирихле найдутся два отвеченных треугольника, которые совпадают. Причем заметим, что треугольники, отмеченные одним белым цветом, не могут совпасть: они отличаются друг от друга поворотом вокруг центра девятиугольника. Значит, существуют два белых треугольника, которые отметили один и toi же треугольник. Так как при повороте конгруэнтность (равенство) сохраняется, а эти два белых треугольника могут быть совмещены поворотом, они и есть искомые треугольники.
100.	Покроем квадрат 12x12 четырьмя правильными треугольниками со стороной И так, как показано на рис. 13. Для этого через центр 0 квадрата проведем два взаимно перпендикулярных отрезка EF и КМ так, чтобы z КМА = 60°. Тогда правильные треугольники XYF, PQM, EGR, SKZ со сторонами 11 полностью покрывают квадрат ABCD. Так как картина не меняется при повороте квадрата на угол 90° относительно центра 0, чтобы доказать это, нам достаточно показать, что АЕ < АТ (см. рис. 13). Рассмотрим перпендикуляр ОН на сторону AD квадрата. Он равен половине стороны квадрата, значит, ОН = = АН = 6. Рассмотрим прямоугольный треугольник ОНМ с острым углом НОМ, равным 30°. Отношение его катетов равно -1з. Поэтому НМ = ОН/4з = 6/-Гз = 2-1з. Следовательно, АЕ = MD = HD -- НМ = 6-2-Гз. Пользуясь тем, что МР = И, находим, что РА = = МР - АН - НМ = И - 6 - 2-Гз = 5 -2-Гз. Заметим, что
77
Рис. 13.
треугольник APT является прямоугольным с острым углом РТА, равным 30°. Поэтому АТ = РаТз = (5 -	=sl?-6.
Рассмотрим неравенство 3-49 = 147 > 144. Из него следует, что 7<[з > 12 или АТ = 5-Гз - 6 > 6 - 2-1з = АЕ.
Итак, четыре равносторонних треугольника со стороной 11 покрывают квадрат со стороной 12. По принципу Дирихле всегда найдется 498 точек из 1990 расположенных в квадрате точек, принадлежащих одному треугольнику. Действительно, если это не так, то в каждом из четырех треугольников не более 497 точек, а значит, всего точек в квадрате не более 4-497 = 1988. А их 1990. Получили противоречие.
101.	Допустим, что это не так. Пусть для красного цвета найдется натуральное число а такое, что точек этого цвета с координатами, делящимися на а, конечное число - п. Для синего цвета пусть таким же числом будет Ъ, а синих точ^к, координаты которых делятся на Ь, пусть будет т. Рассмотрим числа, которые делятся на ab. Их бесконечное число. Выберем, скажем, (n+m+1) таких чисел. Рассмотрим множество точек, соответствующих • этим числам. Среди них красных не более п, а синих - не более гл. Значит, в сумме в этом множестве не более п+ш точек, а мы их выбрали больше. Следовательно, най
78
дется цвет, для которого при любом натуральном к имеется бесконечно много точек этого цвета, координаты которых делятся на к.
102.	Каждому прямоугольнику со сторонами а и b (а & Ь) поставим в соответствие точку (а,Ь) га координатной плоскости. Всевозможные точки (х,у), где х и у - натуральные, у s х з 100 (см. рис. 14), можно включить в 50 цепочек -"уголков", показанных на рисунке звездочками, - так, что точки в каждой цепочке будут соответствовать прямоугольникам, которые можно вложить друг в друга.
Теперь обе задачи решаются без труда :
а)	поскольку мы имеем 101 прямоугольник, а цепочек - 50, то по принципу Дирихле найдутся по крайней мере 3 точки, соответствующие прямоугольникам, лежащие в одной цепочке;
б)	поскольку 39-50 = 1950 < 1989, по принципу Дирихле по крайней мере 40 точек из 1989, соответствующих прямоугольникам, лежат в одной цепочке.
Рис. 14.
79
103.	Расположим семь звездочек, как показано на рис. 15. Тогда как бы мы ни вычеркивали две строки, среди оставшихся клеток найдутся три, стоящие в различных столбцах. Если мы вычеркнем две строки из первых трех, то у нас останется одна из первых трех и четвертая строка. В первой из них стоят две звездочки в клетках из первых трех столбцов, а в
Рис.15. четвертой строке - звездочка из четвертого столбца. Поэтому все три оставшиеся звездочки стоят в разных столбцах. Вычеркивая два столбца, по принципу Дирихле одну из звездочек мы вычеркнуть не сможем. Аналогичны рассуждения, если мы вычеркиваем вначале четвертую строку.
Если же звездочек шесть или меньше, то найдутся две строки, в каждой из которых не более одной звездочки. Докажем это. Допустим, что это не так. Выберем пару строк - в ней не менее трех звездочек. В остальных строках тоже не менее трех звездочек. Так как всего звездочек не более шести, значит, в каждой паре выбранных строк по три звездочки. По принципу Дирихле среди двух строк, содержащих три звездочки, найдется строка, в которой не более одной звездочки. Следовательно, из двух пар строк можно выбрать по строке, вместе которые содержат не более двух звездочек. Получили противоречие.
Итак, выделим две строки, содержащие не более двух звездочек. Вычеркнем оставшиеся строки. После этого вычеркнем столбцы' в которых стоят не более двух звездочек. Тем самым мы вычеркнем все звездочки.
104.	а) Вычеркнем п строк с наибольшим количеством звездочек. Менее 2п звездочек в них быть не может - это означало бы, что в одной из этих п строк не более одной звездочки, тогда и в оставшихся п строках не более чем по одной звездочке, так что всего звездочек меньше 2n + п = Зп. Итак, вычеркнуто не менее 2п звездочек, оставшиеся (не более п) звездочки можно убрать, вычеркнув соответствующие столбцы.
б) Расставим звездочки так, как показано на рисунке 16 : 2п - по диагонали, еще п - на пересечении i-й строки с (i+D-м столбцом (i= 1, 2,..., п) и последнюю - на пересечении (п+1)-й строки с 1-м столбцом. Предположим, что удалось
80
убрать все эти звездочки, вычеркнув п строк и п столбцов. Пусть из них k is п-1 строк (и тем самым п-1-k столбцов) приходятся на нижние (п-1) звездочки, то есть на последние п-1 строк и столбцов. Тогда среди первых п-1 строк вычеркнуто п-k. Остальные строки разбиваются на несколько зон : из р^ Р2„.., р^ строк (г s' 1), pt + р2 +...+ р = (п + 1) - (п -- k) = k + 1 (Мы считаем здесь, что вслед за (п+1)-й строкой идет первая.) В этих зонах останется (р^+1) + (р2+1) +...+ + (р^+1) = к + г+ _1>к + 1 звездочек, стоящих в разных столбцах. Столбцов же останется п - (n-1-k) = к + 1. Таким образом, вычеркивая столбцы, все звездочки убрать нельзя.
											
г	I	•	*									
to		»									
П ’			*	*							
				*	♦						
					«	*					
	«					*					
							*				
п *								*	-		
									*		
										»	
											
Рис. 16.
105.	Эта задача легко сводится к тс,реме 4 и может быть решена с помощью теории графов. Каждому члену компании поставим в соответствие вершину графа. Между вершинами проведем красное ребро, если им соответствующие члены компании знакомы, и - синее в обратном случае. Тогда получешшй граф удовлетворяет условиям теоремы 4. Согласно утверждению этой теоремы в графе найдется треугольник с ребрами одного цвета. Это означает, что среди шести человек найдутся либо трое попарно незнакомых (синий треугольник), либо трое попарно знакомых (красный треугольник).
Задачу можно решить и непосредственно логическими рассуждениями. Пусть А - один из членов компании. Так как
81
оставшихся - пятеро, то по принципу Дирихле либо найдется по крайней мере трое, знакомых с А, либо найдется по крайней мере трое, не знакомых с А. Выберем первый случай. Если какие-то двое из тройки, знакомых с А, знакомы между собой; то вместе с А они образуют искомую тройку. Если двух знакомых среди этой тройки нет, то эти трое и образуют искомую группу попарно незнакомых людей.
Аналогичны рассуждения и во втором случае. Если какие-то двое из тройки, не знакомых с А, не знакомы между собой, то вместе с А они образуют искомую тройку. Если двух незнакомых среди этой тройки нет, то эти трое и образуют искомую группу знакомых друг с другом людей.
106.	Каждому школьнику поставим в соответствие вершину графа. Между двумя вершинами проведем красное ребро, если им соответствующие школьники уже сыграли между собой, и синее, если нет. Получим граф из шести вершин с ребрами двух цветов. По теореме 4 найдется треугольник одного цвета, то есть найдутся трое школьников, которые либо сыграли между собой все партии, либо еще не сыграли ни одной.
107.	Будем рассуждать как при решении предыдущей задачи. Каждой прямой поставим в соответствие вершину графа. Две вершины соединим красным ребром, если соответствующие прямые скрещиваются, и - синим ребром, если нет. Тогда полученный граф удовлетворяет условиям теоремы 4. Согласно утверждению этой теоремы и найдется треугольник с ребрами одного цвета. Это означает, что среди данных прямых найдутся либо три попарно нескрещивающихся {синий треугольник), либо три попарно скрещивающихся (красный треугольник). Но если три прямые попарно не скрещиваются, то, значит, они параллельны между собой, что запрещено условием задачи.
108.	Зададим граф следующим образом. Каждому ученому поставим в соответствие вершину графа. Для каждой темы выберем свой цвет. Выделим произвольную пару двух ученых. На графе им отвечают две вершины. Соединим их ребром цветом, соответствующим теме, по которой переписываются эти ученые. Таким образом, все вершины графа соединим ребрами трех цветов. Выберем произвольную вершину А полученного графа. Среди оставшихся 16 вершин по принципу Дирихле всегда найдутся 6, с
82
которыми А соединено ребрами одного цвета. Если среди этих шести вершин есть две, которые соединены между собой ребром того же цвета, то эти две вершины вместе с А образуют треугольник одного цвета. Если такой пары вершин нет, то в этой шестерке вершины соединены ребрами только двух цветов и можно воспользоваться теоремой 4. Значит, в трехцветном графе из 16 вершин всегда найдется треугольник с ребрами одного цвета. Из этого следует, что найдутся три ученых, переписывающихся между собой по одной теме.
109.	Рассмотрим граф из восьми вершин, каждая из которых соответствует одному из случайно встретившихся людей. Между вершинами проведем красное ребро, если им соответствующие люди знакомы, и - синее в обратном случае. Получим двуцветный граф иъ восьми вершин. По теореме 4 найдется треугольник в этом графе с ребрами одного цвета (пусть, к примеру, красного). Вершинам этого треугольника соответствует однородная группа людей. Если среди оставшихся пяти человек есть тройк: человек, образующих однородную группу людей, то задача решена. Предположим, что это не так. В терминах графа это означает, что оставшиеся пять вершин можно расположить так, что образованный ими выпуклый пятиугольник будет иметь красные стироны и синие диагонали. Действительно, из каждой вершины должно выходить ровно по два ребра одного цвета, иначе мы будем иметь вершину, соединенную с тремя вершинами * ребрами одного цвета. Как й при доказательстве теоремы 4, в этом случае среди этих четырех вершин найдется одноцветный треугольник.
Итак, у нас задан красный треугольник и пятиугольник В^^В^, у которого стороны - красные, а диагонали - синие. Рассмотрим, как вершины треугольника соединены с верпгд'ами пятиугольника. Возможны два варианта. Первый -одна из вершин треугольника (например. А) образует синий треугольник с двумя вершинами пятиугольника (например, В{ и З3). Тогда если вершина В2 соединена с вершинами А2 и Аэ красными ребрами (т.е. В А А - красный треугольник), то 2 2 3
83
A B B и B2A2A3 - искомые однородные группы людей. Если -нет, то из вершины В2 выходят три синих ребра : к вершинам В4 и В5> и к одной из вершин А2 или Аз. В этом случае среди этих вершин найдутся три, которые образуют одноцветный треугольник. Вместе с треугольником А В В они дают нам искомые однородные группы людей.
Второй вариант - ни одна из вершин А^ А2 и Аз не образует синий треугольник с вершинами пятиугольника. Это означает, что для каждой вершины А( найдутся три последовательные вершины пятиугольника, соединенные с А( красными ребрами. Пусть, например, вершина соединена красными ребрами с вершинами В , В2 и By Тогда вершины А2 и Аз также соединены красными ребрами с вершинами В -, В и В . В противном случае найдутся два красных треугольника с вершинами А , А2 и Аз и основаниями - сторонами пятиугольника, которые не пересекаются вершинами. Но тогда у нас образуются два красных треугольника AjB^ и А.А3Вз. Таким образом, во всех случаях найдутся два одноцветных треугольника, у которых вершины различны.
110.	Предположим, что треугольника нет. Выберем какую- . пибудь вершину А. Пусть она соединена с вершинами Bj( В2, Вз, В4 и не соединена с вершинами Су С2» С3> С4- Тогда вершины В( не соединены между собой. Значит, из каждой из них выходят по три отрезка к вершинам С , всего таких отрезков -12. Но из четырех вершин выходят 16 отрезков. Следовательно, четыре отрезка соединяют вершины С между собой. Рассмотрим вершину By Пусть она соединена с вершинами С, С , С . Среди этих вершин найдутся две, соединенные между Z W
84
собой отрезком (иначе отрезков, соединяющих Cfc между собой, не больше трех : СС, СС, СС, а их четыре). Эти две 142434
вершины вместе с вершиной образуют треугольник, что противоречит высказанному предположению. Отсюда следует, что всегда найдется треугольник с вершинами в данных точках.
111.	По принципу Дирихле среди девяти боковых ребер пирамиды найдутся пять окрашенных в какой-то один цвет (например, в красный); Пусть А’, А2, Аз, А^, А& - концы этих ребер, занумерованные подряд. Одна из сторон пятиугольника А А А А А является диагональю основания (пусть, для 1 2 3 4 5
определенности, это	Рассмотрим треугольник А^А*.
Его стороны - диагонали основания. Как и при доказательстве теоремы 4, если в этом треугольнике есть красная стирона, то она вместе с боковыми ребрами образует искомый треугольник. Если же в треугольнике А^А* нет красных сторон, то все они одного синего цвета.
Пирамида с раскрашенными боковыми ребрами и диагоналями основания образует граф, к которому, казалось бы, можно применить теорему 4. Однако, в пирамиде остались нераскрашенны-ми стороны основания. Поэтому применить сразу теорему 4 в этой задаче нельзя.
112.	Рассмотрим граф, в котором вершины соответствуют мальчикам, а между любыми двумя вершинами проведено ребро в случае, если им соответствующие мальчики - братья. По условию задачи каждая вершина такого графа имеет степень, равную 3. Покажем, что полученный граф связный (то есть из каждой вершины его можно добраться по ребрам в любую другую). Выберем произвольную пару вершин, не соединенных ребром. Среди оставшихся вершин обязательно есть одна, соединенная ребрами с данными вершинами. Действительно, так как оставшихся вершин - пять, а из заданных вершин выходит шесть ребер,' то по принципу Дирихле найдутся два ребра, идущие в одну вершину. Значит, любая пара вершин в таком графе соединена одним или парой ребер. Из этого следует, что все мальчики братья, так как если двое являются братьями
85
третьему, то они и сами братья.
ИЗ. Рассмотрим ориентированный граф (см. [12В, то есть граф в котором все ребра имеют стрелки. Поставим в соответствие каждому другу вершину графа. Две вершины А и В соединим стрелкой, если А послал открытку В. Тогда всего в графе стрелок будет 50 = 5-10 стрелок. Посчитаем, сколько различных пар образуют 10 вершин графа. Возьмем первую - она образует 9 различных пар с другими вершинами. Вторая вершина образует 8 пар (с первой она пару уже образовала), отличную от других и т.д. Всего различных пар получится - 9 + 8 +...+ + 1 = (9 + D-9/2 = 45. Между тем, как замечено, стрелок 50. По принципу Дирихле найдется пара, которой соответствуют две стрелки. Последнее означает, что двое друзей, которые соответствуют этой паре вершин, обменялись открытками.
114. Как и в предыдущей задаче, каждому человеку компании поставим в соответствие вершину графа. Из вершины А проведем стрелку в вершину В, если В нравится А. Всего проведенных стрелок будет 16-8 = 128. А всего различных пар вершин в графе из 16 вершин можно получить 15 + 14 +...+ 1 = = (15 + 1)-15/2 = 120 < 128. По принципу Дирихле найдется пари вершин графа А и В, для которой есть стрелка из А в В и стрелка из В в А. Это означает, что А и В нравятся друг другу.
115. Пусть А и В - два произвольных города. Покажем, что есть дорога из А в В (А->В). Предположим, что нет такого города С, для которого имеются дороги А—>С и С->В (иначе есть дорога из А в В). Рассмотрим города А^, А2>..., А^, в которые ведут дороги из А, и другие 40 городов В » В2  В40, из которых дороги ведут в В. По условию задачи всего городов 101. Поэтому, кроме А и В, остаются 19 городов	С2 
С]9. Из городов А. всего в совокупности выходит 40'40 = 1600 дорог. Число дорог, ведущих из них в 19 городов Су не превосходит 19'40 = 760. Так как каждая пара городов соединена не более чем одной дорогой, суммарное число дорог вида А —>А не превосходит 40-39/2 = 780. Значит, общее
86
количество дорог, выходящих из А и входящих в А и С , не 1	J к
превосходит 760 + 780 = 1540, а всего дорог, выходящих из Ар равно 1600. По принципу Дирихле найдется дорога AJ-»B.
Следовательно.
существует
дорога
А->А —>В —>В, • J
соединяющая
города А и В.
116. Назовем город "захолустным", если из него идет не более двух дорог. Сотрем с карты страны любой захолустный город, если таковой имеется , вместе с выходящими из него дорогами. Подчистим таким же образом новую карту и будем продолжать стирание захолустных городов, пока они не исчезнут. Число дорог, которые мы при этом можем стереть, не превосходит 2’1989, что меньше, чем 4000 ; поэтому хотя бы
один город останется.
Выберем любой из оставшихся городов. Из него, как и из других оставшихся городов, выходят по меньшей мере 3 дороги. Пойдем по одной из них и „каждый раз, приходя в новый город, будем двигаться дальше по одной из дорог, отличных от дороги, по которой мы пришли. Если какие-нибудь два маршрута, состоящие не более чем из 10 дорог, закончатся в одном городе, то мы получим искомый кольцевой маршрут не более чем из 20 дорог. Но иначе и быть не может, потому что число всех
2	9
таких маршрутов не меньше, чем 3 + 3*2 + 3*2 +...+ 3-2 = = 3069, а число городов, -то есть возможных концов этих маршрутов, - не больше 1989.
117-118. Выберем из пяти человек .иго, кто имеет наибольшее число знакомых среди этой пятерки. Если таких несколько, то из них можно и выбрать двоих, имеющих одинаковое число знакомых. Назовем его А. Рассмотрим тех, кто знаком с А. Если их п, то так как они уже знакомы с А, число знакомых они могут иметь в промежутке между 1 и п-1. По принципу Дирихле найдутся двое, имеющие одинаковое число знакомых. Те же рассуждения и для кинотеатра "Мир", в котором присутствовало по крайней мере 5 человек.
119.	Как и при решении предыдущих задач выберем человека, имеющего наибольшее число знакомых среди присутствующих. Если таковых двое, то задача решена. Среди его знакомых
87
(пусть их будет т) только те, кто имеют знакомых не менее одного и не более ш-1. Так как их всего - т, то по принципу Дирихле найдутся двое, имеющие одинаковое количество знакомых.
120-121. Выберем команду А, сыгравшую наибольшее количество матчей. Если таких команд несколько, то задача решена - они и дают нам пару команд, сыгравших одинаковое число матчей. Теперь рассмотрим те команды, с которыми уже сыграла команда А. Пусть таких команд п.Среди них нет команды, не сыгравшей ни одного матча, так как каждая из них сыграла с командой А. Поэтому каждая из этих команд на этот момент времени может иметь сыгранных матчей от 1 до п-1. По принципу Дирихле найдется пара команд, сыгравших одинаковое число матчей, что и требовалось доказать.
122.	Эту задачу можно решить двумя способами. Первый : выберем грань с наибольшим числом ребер. Если их несколько, то задача решена (см. решение предыдущих задач). Пусть она имеет п ребер. Тогда соседние грани (то есть имеющие общее ребро с данной гранью) имеют ребер от 3 до п-1. По принципу Дирихле найдется пара граней, имеющая одинаковое число ребер.
другое решение : пусть многогранник имеет m граней. Так как каждая грань - многоугольник, то число ребер изменяется от 3 до т-1. Всего возможных вариантов - m-З. По принципу Дирихле найдется пара граней с одинаковым числом ребер. Заметим, что здесь существенное условие - это выпуклость многогранника, так как для невыпуклого две грани могут граничить не по одному ребру (то есть число ребер в грани может быть больше т).
123.	Рассмотрим граф, вершины которого соответствуют собравшимся ученым. Соединим две вершины такого графа ребром, если ученые, соответствующие этим вершинам, знакомы. По условию задачи среди ученых есть друзья. Следовательно, найдется по крайней мере одно ребро. Докажем, что в таком графе есть вершина, из которого выходит ровно одно ребро, что на языке теории графов означает, что эта вершина имеет степень, равную 1. Предположим противное : нет вершин со степенью 1. Выберем вершину с максимальной степенью (если таких несколь-
88
ко, то - одну из них). Пусть из нее выходит ш ребер. В силу того, что в графе есть ребра, m s 1. Рассмотрим ее соседей, то есть вершины, соединенные с ней ребрами. Так как m максимально, степени соседей могут принимать (m-1) значений : 2, 3.... т. А всего соседей - т. По принципу Дирихле найдутся
две вершины с одинаковой степенью. Следовательно, среди ученых есть два, имеющих одинаковое количество знакомых и имеющих общего знакомого, которому соответствует вершина с максимальной степенью. А это противоречит условию задачи. Значит, исходное предположение неверно, и найдется ученый, который имеет ровно одного друга.
124.	Обозначим а^, а2,...,	- возрасты жильцов дома.
Тогда aj + а2 +...+ aj23 = 3813. По теореме 6 найдутся 100 чисел из а, а ,..., а такие, что их сумма не меньше
1	2	123	J
100’3813/123 = 3100, что и требовалось доказать.
Можно было рассуждать по-другому. Выберем 100 жильцов дома, имеющих наибольший возраст (100 "старейших” жильцов). Если вместе им меньше 3100, то по теореме 5 среди них найдется один, возраст которого меньше 31. А так как он стари-э оставшихся 23, то возраст каждого из оставшихся меньше 31. Следовательно, всем жильцам вместе меньше, чем 3100 + 23’13 = 3813, что противоречит условию задачи.
125.	Пусть а( т - вес груза i-ro вагона. Тогда + а2 + +...+ а52 as 261. По теореме 6 найдутся 40 чисел из { а^ }, сумма которых не менее 40*261/52 = 2610/13, что больше 200. Следовательно, найдутся 40 вагонов, суммарный вес груза которых более 200 т.
126.	Пусть а , а2. а& - очки, набранные гимнастками.
Тогда а^ + а2 +...+ а^ а 217. По теореме 6 найдутся пять чисел, сумма которых не меньше 5*217/6, что больше 180.
С другой стороны, по теореме 5 найдется девушка, набравшая не больше 217/6, или менее 37 очков. Поэтому остальные гимнастки набрали более 217 - 37 = 180 очков.
127.	Пусть а , а.. а - число лепестков на каждой
X 2	9
89
розе. Число всех лепестков равна + а2 +...+ а9 = 190. По теореме 6 в данной сумме найдутся 4 слагаемых, сумма которых не менее 4'190/9 > 84. Следовательно, найдутся 4 розы, число лепестков которых более 84.
128.	Выберем произвольные 10 чисел из 1989 заданных. Сумма их положительна. По теореме 6 найдутся среди них 9 чисел, сумма которых положительна. Остальные 1980 из исходных чисел разобьем на 198 групп по 10 в каждой. Сумма в каждой группе положительна. Следовательно, сумма всех 1980 чисел также положительна. Добавим к ним положительную сумму выделенных девяти чисел и получим число, большее нуля. Таким образом, сумма всех чисел положительна.
129.	Рассмотрим произвольную пару чисел из заданных. Сумма этих чисел больше 1. По теореме 5 найдется одно из них, которое больше 0,5. Остальные 1980 разобьем на 990 пар. Сумма этих чисел больше 990, так как сумма в каждой паре больше 1. Добавив к этим числам выделенное, получим сумму, которая больше 990,5. Следовательно, сумма всех 1981 числа больше 990,5.
Предложим еще одно решение этой задачи. Допустим, что сумма всех 1981 числа не больше 990,5. Тогда по теореме 6 найдется пара чисел, сумма которых не больше 2*990,5/1981 = = 1. Но это противоречит тому, что любая пара дает сумму, большую 1. Следовательно, сумма всех 1981 числа больше 990,5.
130.	Зафиксируем некоторое положение верхнего круга. Сумму видимых чисел обозначим 5^. Повернув на 360°/21 мы получим новое положение, сумму видимых чисел для которого обозначим и т.д. до тех пор, пока не вернемся в первоначальное положение. Всего мы получим 21 сумму, каждая из которых равна нулю, сумма этих сумм также равна нулю. Так как на верхнем круге пять окошек, то каждое число, написанное на нижнем круге встречается в построенных суммах ровно 5 раз. Поэтому S} + Sj, +,,,+ S21 равна сумме всех чисел, умноженной НА б. ОСЮДЙ сразу вытекает, что сумма всех чисел равна нулю,
90
131.	Воспользуемся правилом крайнего : среди натуральных чисел, записанных на полях бесконечной шахматной доски, непременно существует наименьшее. В этом нетрудно убедиться. Пусть к - одно из данных чисел. Если среди остальных чисел нет тех, которые меньше к, то к и есть минимальное. Если есть меньшее, то рассмотрим его. Аналогично для него либо нет меньших его (тогда оно наименьшее), либо - есть (тогда рассмотрим это число). Эта процедура не может длиться бесконечно, так как множество натуральных чисел ограничено снизу.
Итак, выберем наименьшее - т. Рассмотрим соседние к этому числа. Пусть это - a, b, с, d. По условию задачи (а + Ь + + с + d)/4 = m или a + b + c + d = 4m. По пункту б теоремы 5 либо все числа a = b = c= d = m, либо среди чисел а, Ь, с, d найдется такое, которое меньше ш. Последнее не может быть, так как m - минимальное среди написанных. Таким образом, если в некотором поле написано т, то и в соседних написаны только числа т. Значит, все числа на доске равны т.
132.	Прежде всего заметим, что числа, о которых идет речь в условии задачи все положительны, так как в противном случае среди них можно выбрать 7 чисел таких, что их произведение будет отрицательным, а значит, и меньше 1. Обозначим а, а2»..., а1д76 натуральные логарифмы заданных чисел. По условию задачи, любые семь из заданных чисел дают в произведении число, большее 1. Поэтому сумма любых семи логарифмов будет положительна. С другой стороны, нам достаточно доказать, что сумма а + а +...+ а положительна .чтобы получилось произведение заданных чисел больше 1. Выберем произвольную семерку логарифмов. Сумма их положительна. По теореме 6 найдется пара логарифмов из этих семи, сумма которых положительна. Выделим их из всех чисел. Оставшиеся 1974 логарифма разобьем на 282 семерки. Сумма в каждой семерке положительна, следовательно, сумма всех 1974 логарифмов больше 0. Поэтому она вместе с положительной суммой двух выделенных логарифмов будет больше нуля. Из этого и следует, что произведение всех чисел больше 1.
Для тех, кто не знаком с логарифмами, предлагаем другое решение методом от противного. Выпишем все числа в порядке
91
возрастания : b1 25 b2 =s..,5 По условию задачи произведение первых семи чисел Ь^.-.Ь? больше 1. Тогда все остальные числа больше 1 (иначе наименьшее из остальных b s 8
s 1 и, следовательно, b b ...b s bb ...b si). Отсюда вы-1 2	7	8 8	8
текает, что произведение всех чисел b b ’..b b b,—b >1.
133.	Вначале покажем, что периметр выпуклого многоугольника, вписанного в квадрат со стороной 1. не превосходит 4. Обозначим а, а ..... а последовательные стороны данного 1	2	п
n-угольника. Пусть х^ х2,..., х^, у, у2,..., Уп - проекции сторон на смежные стороны квадрата. Поскольку многоугольник выпуклый, то каждая точка на стороне квадрата покрывается не более чем двумя проекциями сторон п-угольника. Поэтому xt + х +...+ х JS 2, у + у +...+ у s 2. Заметим, что а = 2	n	•'i г	п	к
/2	2
х + у s х + у . Поэтому периметр а + а +...+ a s к	к	к к	1	2	п
а(х + х +...+ х ) + (у + у +...+ у ) s 4. Следовательно, 12	n	1	2	п
(а + а ) ♦ (а ♦ а ) (а + а ) + (а + а ) з 8. 1	2	2	3	n-1 п	п	1
По теореме 5 одно из слагаемых, заключенных в скобки, не превосходит 8/п, то есть найдутся две соседние стороны afc и ak i такие, что afc + а^ £ 8/п. Рассмотрим треугольник, об
разованный этими сторонами. Его площадь не превышает
Следовательно, этот треугольник и является искомым.
134.	Докажем вначале, что всегда можно выбрать машину, которой хватит бензина добраться до стоящей перед ней машины. Занумеруем машины по порядку от 1 до п. Пусть а( - количество бензина, налитого в бак i-й машины, а b - количество
92
бензина, необходимого, чтобы i-я машина доехала до стоящей перед ней машины. Так как по условию задачи общее количество бензина достаточно для того, чтобы один объехал всю кольцевую дорогу, а + а2 +...+ s b +	+...+ Ь^. Поэтому
найдется такое i, что a Ъ . В противном случае для всех i
< b^, и, следовательно, + а2 +...+ а^ <	+ Ь2 +...+
+ b , что противоречит уже написанному. Таким образом, i-я п
машина может добраться до стоящей перед ней машины. Тогда если мы доберемся до i-й машины на каком-нибудь автомобиле, то, забрав бензин из i-й машины г бак этого автомобиля, мы обязательно доберемся до следующей машины, откуда мы можем снова слить бензин. Итак, вылив из бака машины, стоящей после i-й, бензин в бак i-й машины, мы не изменим ситуацию, но машин станет на одну меньше. С оставшимися машинами проделаем ту же самую процедуру и избавимся от лишнего автомобиля. Так будем делать до тех пор, пока не останется один автомобиль. На этом автомобиле и можно объехать всю кольце
вую дорогу надлежащим образом.
135. Обозначим S ту часть площади страны А на первой UJ	1
стороне листа, которая на другой его стороне принадлежит стране (1 s i, j s 10). При этом мы не исключаем
возможности, когда S =0. Тогда сумма S = (S + S + 1.J	1,1	1,2
+...+ S ) + (S + + S +...+ S ) +...+ (S + 1,10	2,1	2,2	2,10	10,1
+ S +.. + S ) совпадает с площадью листа : s = 1. 10,2	10,10
Переставив слагаемые, запишем S в таком виде :
1.
и
Здесь последовательность вторых индексов j слагаемых S
в
каждой круглой скобке получается циклическим сдвигом первых индексов i. Поскольку в полученном равенстве имеется 10 сла-
93
гаемых в круглых скобках, по теореме 5 найдется одно из них, которое не меньше 1/10 = 0,1. Пусть при некотором k = = (S + S +...+ S + S +...+ S ь 1,к	2,к*1	11-к,10	12-к,1	10,к-1
s 0,1. Закрасим страну на второй стороне листа в ту же краску, что и страну Aj на первой стороне листа, страну В - так же, как и А ...... страну В - так же, как и А .
2	r J к-1	ю
Тогда все 10 стран на второй стороне будут закрашены в Ю различных красок, а одинаковыми с двух сторон красками закрашена площадь S 0.1. к
136.	Выберем какой-нибудь треугольник с вершинами в заданных точках, внутри которого нет других точек из числа данных. Это всегда можно сделать по следующим соображениям. Выберем произвольные две точки и проведем через них прямую а. Рассмотрим оставшиеся точки, лежащие по одну сторону от этой прямой. Выберем из них ближайшую к прямой а (если таких несколько, то выбираем любую). Тогда треугольник с выбранными точками не содержит в себе других точек, иначе они будут ближе к а, чем вершина этого треугольника. Потом к одной из сторон тем же образом пристраиваем еще один треугольник, внутри которого нет заданных точек. Этот процесс построения продолжаем до тех пор, пока не будут исчерпаны все заданные точки. 'т'ак как точек 102, а при каждом шаге построения треугольника мы используем только одну точку (вначале мы использовали сразу три), то всего треугольников будет 100. Они не будут перекрываться, и все будут лежат' внутри единичного квадрата. Общая площадь всех треугольников меньше 1. По теореме 5 найдется треугольник, площадь которого не .превосходит 0,01, что и требовалось доказать.
Читателю предлагается сравнить это решение с решением аналогичной задачи 88.
137.	Каждый девятиугольник имеет 9-6/2 = 27 диагоналей, так как из каждой его вершины выходят 6 диагоналей. Проведем через Произвольную точку 0 плоскости 27 прямых, параллельных диагоналям девятиугольника. Эти прямые разбивают полный угол 360° йокруг точки 0 иа 54 части. Среди 54 полученных углов
94
найдется один, который не превосходит 360°/54 < 7°. Поскольку при параллельном переносе прямых угол между ними не изменится, то острый угол между соответствующей парой диагоналей также не превосходит 7°.
138.	Перенесем параллельно все эти прямые так, чтобы они проходили через одну точку. Эти прямые разбивают полный угол в 360 градусов вокруг точки пересечения на 14 частей. Наименьшая из этих частей естественно имеет величину угла не большую, чем 360/14 < 364/14 = 26°. Прямые, образующие этот угол, удовлетворяют условию задачи. Для угла 25° уже это утверждение неверно. Проведем 7 прямых через одну точку так, чтобы все 14 углов, которые они образуют, были равны. Тогда каждый из этих углов равен 360/14 > 350/14 = 25°. Таким образом, наименьший из углов, образованных этими прямыми больше 25°.
139.	Каждый семиугольник имеет 7-4/2 = 14 диагоналей, так как из каждой его вершины выходит 4 диагонали. Проведем через произвольную точку 0 плоскости 14 прямых, параллельных диагоналям семиугольника. Эти прямые разбивают полный угол 360° вокруг точки 0 на 28 частей. Среди 28 полученных углов найдется один, который не превосходит 360°/28 < 13°. Поскольку при параллельном переносе прямых угол между ними не изменится, то острый угол между соответствующей парой диагоналей также не превосходит 13°.
140.	Соединим все заданные точки отрезками. Тогда мы получим выпуклый многоугольник, внутри которого находятся все остальные проведенные отрезки. Рассмотрим два различных случая: первый - это шестиугольник, второй - это п-уголышк, где п = 3, 4, 5.
В первом случае все шесть точек образуют выпуклый шестиугольник. Сумма внутренних углов шестиугольника равна 720°. По теореме 5 найдется вершина, угол при которой не превосходит 120°. Эта вершина вместе с соседними образует искомый треугольник.
Если выпуклый многоугольник имеет вершин меньше, чем 6, то разобьем его на треугольники : в треугольнике ничего делать не надо, в четырехугольнике проведем любую диагональ, в пятиугольнике - все диагонали, выходящир из одной вершины.
95
Так как по крайней мере одна из данных точек лежит внутри многоугольника, то найдется треугольник, содержащий эту точку. Рассмотрим углы, образованные отрезками, соединяющими ее с вершинами треугольника. Сумма трех углов равна 360°. По теореме 5 найдется угол, не превосходящий по величине 120°. Следовательно, найдется треугольник, удовлетворяющий условию задачи.
141.	Из 8 выбранных точек по крайней мере 7 не совпадают  с центром круга. Каждая из этих семи точек определяет радиус. Если не все радиусы различны, то какие-то две точки, не совпадающие с центром круга, лежат на одном и том же радиусе. Следовательно, расстояние между ними меньше радиуса круга.
Предположим, что все 7 точек, не совпадающих с центром круга, лежат на* 7 различных радиусах. Эти радиусы разбивают полный угол в 360° на 7 углов. По теореме 5 найдется угол не больший 360°/7 или меньший 60°. Обозначим заданные точки А и В, определяющие угрл АОВ, меньший 60°. Рассмотрим треугольник АОВ. Так как zAOB < 60°, сумма оставшихся углов ОАВ и ОВА больше 120°. Следовательно, один из этих углов больше 60°. Допустим, что это угол ОВА. Мы получили, что zAOB < < zOBA. Но во всяком треугольнике против большего угла лежит /
большая сторона. Поэтому АВ < ОА. Но ОА не превышает длины радиуса круга. Отсюда следует, что АВ меньше радиуса.
14°. Допустим, что 401 точка размещена в заданном круге так, что расстояние между любыми двумя больше 1. Построим вокруг каждой заданной точки круг радиусом 1/2. Если найдутся два пересекающихся круга, то их центры находятся ка расстоянии, меньшем или равном 1. Поэтому построенные круги не пересекаются. Кроме того, все они не будут выхолить за границу круга радиусом 10 с центром в точке, являющейся центром исходного большого круга. Суммарная площадь всех кругов радиусом 1/2 равна 401-л-(1/2)2 = 100,25л, а площадь круга радиусом 10 равна л-102 = 100л < 100,25л. По принципу Дирихле найдется точка, покрытая по крайней мере двумя такими малыми кругами, то есть они пересекаются. Получили противоречие.
143.	Центр круга диаметром 1, целиком помещающегося
96
внутри прямоугольника, должен быть расположен на расстоянии. большем 1/2, от любой из сторон прямоугольника, то есть внутри прямоугольника 19x24, площадь которого равна 19-24 = = 456. Кроме того, центр круга должен быть расположен на расстоянии, большем 1/2, от контура любого из квадратов, то есть вне фигуры, получаемой из квадрата, четырех прямоугольников размером 1x0,5 и четырех четвертинок круга радиусом 1/2 (см. рис. 1, пример 15 § 6). Площадь этой фигуры равна 1 + 4-1-0,5 + л(1/2)2 = 3 + тг/4. Суммарная площадь 120 таких фигурок равна 120(3 +' л/4) = ЗБО т 30л, что меньше, чем 360 .,+ 30-3,2 = 360 + 96 = 456. Таким образом, по теореме 7 покрыть прямоугольник площадью 456 такими фигурами нельзя -найдется точка внутри этого прямоугольника, не принадлежащая ни одной из 120 построенных фигурок. Круг радиусом 1/2 с центром*" в этой точке не пересекает брошенных квадратов и сторон исходного прямоугольника 20x25.
144.	Аналогично предыдущей задаче центр искомого круга предстоит искать в квадрате размером 60x60, получающимся из квадрата 70x70 после исключения краевой каймы шириной 5. Кроме того, искомый центр должен быть удален не менее, чем на 5, от размещенных фигур. Окружим каждую из пяти фигур каймой шириной 5. Из квадрата 30x30 получится фигура, состоящая из самого квадрата, четырех прямоугольников 30x5 и четырех четвертинок круга радиусом 5, общей площадью 30*30 + + 4-30-5 + л-52 = 1500 + + 25л. Анологично из прямоугольника 25x15 получим фигуру площадью 25-15 + 2-25-5 + 2-15-5 + л-52 = 775 + 25л, из прямоугольника 20x10 - фигуру площадью 20-10 + 2-20-5 + 2-10-5 + л-52 = 500 + 25л. Из кругов радиусом 5 получим круги радиусом 10 общей площадью 2-л-Ю2 = 200л. Все расширенные фигуры имеют общую площадь, равную 2775 + 275л
Теперь рассмотрим вершины квадрата 60x60.. Они должны быть покрыты одной из полученных фигур (иначе это будет центр искомого круга). Следовательно, одну из вершин покрывает круг радиусом 10. Покажем, что площадь той части круга, которая находится вне квадрата, не меньше площади двух
97
Рис. 17.
попала в квадрат, равна 50(а
90-градусных сегментов этого круга. Рассмотрим круг радиусом 10 с Петром в точке О. Пусть в нем находится вершина А малого квадрата. Точки пересечения окружности со сторонами квадрата обозначим В и С (см. рис. 17). Пусть zBOA = a, zAOC = р. Так как угол ВАС прямой, то z ВОС = = а+Д я. Продолжим прямую ОА до пересечения с окружностью в точке Е. Площадь сектора ОЕВ равна 50а, а сектора ОЕС - 50Д. Площадь S той части крута, что не + В) - S - S , где S OAB ОАС	OAB
площадь треугольника OAB, aS - треугольника ОАС. Оценим оас	t	х
площаги треугольников сверху	: S	=	—OA-OB-sina	£	—102,
0АВ	2	2
1 . 1
S = —OA-OC-sinfi £ —102, так как ОА s 10, ОВ = ОС = 10, 2	2
sina - 1, sin# s 1. Следовательно, S + S s 100. Так OAB ОАС
как а + Д ь я, из этого следует, что S & 50я - 100 > 57.
В итоге мы имеем, что площадь покрытой построенными фигурами части квадрата не больше,чем 2775 + 275я - 57 < 3585. Между тем площадь всего квадрата 3600. Поэтому по теореме 7 найдется точка, не покрытая ни одной из построенных фигур. Круг радиусом 5 с центром в этой точке не пересечет исходные пять фигур, размещенных в квадрате 70x70.
145.	Во-первых, заметим, что прямоугольник размером 20x10 м полностью помещается в круг радиусом 11,2 м. Действительно, по теореме Пифагора диагональ этого прямоугольника
/2	2
равна г 10 + 20
500
< 22,4. Поэтому нам достаточно
98
найти точку в парке, удаленную от границы парка, озера и всех деревьев на расстояние 11,2 м. Для этого окружим каждое дерево и озеро кольцами шириной 11,2 м. Тогда получим 1500 кругов радиусом 12 м и круг радиусом 299,2 м общей площадью,
меньшей, чем 1500-тг-122 + Л-2202 = п-264400 < 840000 м2. Из квадрата со стороной 1 км вырежем кайму шириной 11,2 м по всей его границе. Получим квадрат со стороной 977,6 м. Его
площадь более 9702 =’940900 м2, что намного больше общей площади построенных фигур. По.теореме 7 все эти фигуры не покроют малый квадрат. Значит, найдется точка, удаленная от границы парка, озера и деревьев на расстояние не менее, чем 11,2 м. Круг с центром в этой Точке радиусом 11,2 м содержит прямоугольник 20 х Юм.
146.	“Из каждого брошенного в квадрат многоугольника построим фигуру следующим образом. На каждой его стороне как к* основании построим прямоугольники высотой 1, расположенные вне многоугольника (См. рис. 18). При каждой вершине получим углы, составленные из сторон построенных прямоугольни
ков. Покроем их круговыми секторами радиусом 1 с центрами в вершинах многоугольника. Каждый такой угол дополняет до .180° внутренний угол многоугольника при этой вершине. Гак как сумма внутренних углов п-угольника равна 180°(п-2), отсюда вытекает, что сумма всех углов построенных круговых секторов равна 180°п - 180°(п-2) = 360°. Это означает, что, расположив секторы без наложений и совместив их центры, мы
получим круг радиусом 1. Площадь его равна я. Так как по условию задачи периметр многоугольника не превосходит 2л, то
99
и суммарная площадь построенных прямоугольников не превосходит 2я. Вместе с условием, что площадь самого многоугольника не превосходит п, из этого следует, что общая площадь построенной фигуры не превосходит 4я. Всего таких фигур 100, значит, их суммарная площадь не превосходит 400я < 400*3,15 = 1260. Площадь меньшего квадрата (он получается из большего, если сдвинуть каждую сторону исходного внутрь на 1), в который они помещены, равна 362 = 1296, что больше общей площади построенных фигур. Поэтому в силу теоремы 7 фигуры не могут покрыть весь квадрат, то есть найдется точка, не принадлежащая ни одной из данных фигур. Эти фигуры таковы, что любая точка, расположенная вне этой фигуры, находится на расстоянии, большем, чем 1, от многоугольника, вокруг которого построена данная фигура. Следовательно, найденная точка удалена от каждого многоугольника и от границ большого квадрата на расстояние, большее, чем 1. Это означает, что круг радиусом 1 с центром в этой точке не пересекает ни одного многоугольника, ни границ большого квадрата, что и требовалось доказать.
'47. Рассмотрим для каждого отрезка геометрическое место точек плоскости, удаленных от отрезка на расстояние не более 1/8. Это будет фигура, состоящая из прямоугольника длиной 1/2 и шириной 1/4 и двух полукругов радиусом 1/8. Площадь такой фигуры равна сумме площадей прямоугольника и круга радиусом 1/8: 1/8 + я(1/8)2 = 1/8 + д/64 > 1/8 + 3,1/64 = в 11,1/64. Окружив все отрезки, мы получили 9 фигур общей площадью 9*11,1/64 = 99,9/64. Понятно, что эти фигуры могут выползать за квадрат со стороной 1, но не далее, чем на 1/8. Поэтому рассмотрим фигуру, состоящую из самого квадрата 1x1, четырех прямоугольников высотой 1/8, построенных на сторонах исходного квадрата, и четырех четвертинок круга радиусом 1/8. Общая площадь этой фигуры равна 1 + 4*1/8 + л(1/8)2 < < 3/2 + 3,2/64 = 3/2 + 1/20 = 3,1/2 = 99,2/64. Это меньше 99,9/64 - площади фигур, вложенных в квадрат. По теореме 8 найдется точка А, принадлежащая одновременно каким-то двум фигурам. Эта точка удалена от каждого из данных** отрезков менее, чем на 1/8. Пусть М и N - точки отрезков, для которых
1ОО
AN < 1/8 и AM < 1/8. По неравенству треугольника MN s AN + +АМ<1/4, что и требовалось доказать. Заметим, что совсем необязательно, чтобы точка А принадлежала исходному квадрату.
148. Центр искомого шара должен находиться на расстоянии, большем, чем 1/2, от границ параллелепипеда и данных единичных кубов. Будем искать его внутри параллелепипеда 4x9x24, получающегося из исходного, если сдвинуть каждую грань параллелепипеда внутрь на 1/2. Из каждого единичного куба построим тело следующим образом. На каждой грани вне куба как на основании построим параллелепипед высотой 1/2. Грани полученных параллелепипедов образуют 12 двугранных углов величиной 90° каждый. Вставим в них по четвертинке цилиндров высотой 1 с круговым основанием радиусом 1/2. Теперь вокруг каждой вершины получится трехгранный угол, составленный из трех попарно перпендикулярных плоскостей. Покроем его 1/8 шара радиусом 1/2, получаемой проведением трех попарно перпендикулярных плоскостей через центр шара. В итоге получим тело, любая точка вне которого, находится на большем, чем 1/2, расстоянии от куба, на котором построено данное тело. Вычислим объем полученного тела. Оно состоит из куба объемом 1, 8 параллелепипедов объемом 1/2, 12 четвертинок цилиндра (Х/Щим объемом 3*я/4 и шара радиуса 1/2. Объем тако-
3	4 х И
го тела равен 1 + 3 + —я +-----= 4 +-----я. Следовательно,
4'38	12
11
объем всех 120 тел равен 120(4 + —*я) = 480 + + ИОя < 480 *	12
+ 110*3,2 = 832. Но объем малого параллелепипеда равен 4*9*24 = 864, что больше объема построенных тел. По принципу Дирихле найдется точка из малого параллелепипеда, не принадлежащая ни одному из данных тел. Это и есть центр искомого шара радиусом 1/2.
149-150. На каждой стороне как на основании построим с той же стороны, где лежит многоугольник, прямоугольник высотой S/Р. сумма площадей этих прямоугольников равна S. Поскольку они частично перекрываются, то они не могут покрыть многоугольник, площадь которого равна также S. По теореме 7
101
найдется точка, которую не покрывает ни один из построенных прямоугольников. Расстояние от нее до любой из сторон многоугольника превышает S/Р. Следовательно, окргкность радиусом S/Р с центром в этой точке будет полностью лежать внутри данного многоугольника.
151.	Поместим начала всех векторов в одну точку и построим сферу радиусом 1 с центром в этой точке. Возьмем точки пересечения наших векторов (или их продолжений) с построенной сферой и окружим каждую из них шапочкой диаметром 45° следующим образом. Из центра шара проведем всевозможные лучи, образующие с направлением данного вектора угол, равный 22,5°. Эти лучи, пересекая шар, образуют окружность на поверхности шара. Меньшая часть сферы, ограниченная этой окружностью, и есть шапочка диаметром 45°. Площадь поверхности такой шапочки больше площади круга, образованного данной окружностью. Заметим, что радиус полученной окружности равен sin 22,5°. Поэтому площадь такого круга равна я-sin 22,5° = л(1 - cos 45°)/2. Таким образом, суммарная поверхностная площадь построенных 30 шапочек больше, чем 15(1 - cos 45°)я. Покажем.что это больше 4я - площади повер .кости шара радиусом 1. Заметим, что 484 > 450 или 22 > > 15I2. Отсюда следует, что 15(2 - 4*2) > 8. Из этого неравенства сразу вытекает, что 15(1 - I2/2) = 15(1 -- cos 45°) < 4. Следовательно, площадь сферы радиусом 1 меньше суммарной площади построенных шапочек. По принципу Дирихле найдется точка на сфере, покрытая по крайней мере двумя шапочками.
Пусть это точка А. Центр шара обозначим через 0, а центры шапочек, которым принадлежит точка А, - через В и С. Проведем плоскость через точки О, В и С. На дуге ВС, полученной пересечением плоскости со сферой, найдется точка, принадлежащая шапочкам, построенным вокруг точек В и С. Это означает, что дуга ВС будет меньше 45°. Следовательно, найдутся два вектора из заданных, угол между которыми меньше 45°.
152.	Проведем через центр сферы произвольную плоскость а. Каждую точку, симметричную относительно плоскости а точке черного цвета, закрасим в черный цвет. Тогда общая "площадь
102
закрашенной части сферы не более чем удвоится, то есть будет менее 24% площади сферы. Проведем теперь произвольную плоскость 0, проходящую через центр и перпендикулярную а. Полученную закрашенную область отобразим симметрично относительно плоскости Д. Таким образом, закрасится часть поверхности сферы, занимающая менее 48/ ее площади. Наконец, проведем плоскость у, проходящую через центр сферы и перпендикулярную построенным плоскостям а и fi. Относительно ее произведем ту же операцию с закрашенной областью. Получим область черных точек, занимающую менее 96/ всей поверхности сферы. По принципу Дирихле найдется точка белого цвета. Она обладает тем свойством, что и остальные семь точек, получаемые при всевозможных композициях симметрий относительно плоскостей a, fi и у, будут также белого цвета. Эти восемь точек образуют искомый прямоугольный параллелепипед.
153.	Одно из самых простых решений задачи а) опирается на задачу б), поэтому начнем с пространственной задачи.
б) Площадь поверхности части сферы радиусом г, заключенной между пересекающими сферу параллельными плоскостями, равна 2ягЪ, где h - расстояние между этими плоскостями. Э"^ значит, что площадь сферы диаметром 1, содержащейся в слое толщшюй h, рвана »h. Поэтому сумма площадей частей сферы, содержащихся в нескольких слоях, не больше xs, где s - суммарная толщина всех слоев (слои могут пересекаться). А та» как s < 1, площадь покрытой слоями части сферы меньше площади поверхности всей сферы, равной п. Следовательно, на сфере найдутся непокрытые точки.
а) Рассмотрим круг диаметром 1 как проекцию шара диаметром 1 на плоскость. Каждой полоске поставим в соответствие слой, толщина которого равна ширине полоски (этот слой заключен между двумя плоскостями, перпендикулярными плоскости ГФ.’Г'» и проходящими через границы полоски). Если бы круг был полностью покрыт полосками, то весь шар был бы покрыт слоями, суммарная толщина которых была бы меньше 1. Но это пс доказанному в пункте б) невозможно.
154.	Построим для каждой из наших 650 , точек кольцо с центром в этой точке, ограничиваемое окружностями радиусом < и 3. Все эти кольца содержатся в круге радиусом 16 + 3 = 19
103
и сумма их площадей равна 650(9л-4л) = 3250тс, что больше, чем в 9 раз, площади 361» круга радиусом 19. Следовательно, по теореме 10 хотя бы одна точка А этого круга покрывается по крайней мере 10 кольцами. Если теперь построить кольцо шириной 1 и внутренним радиусом 2 с центром в точке А, то центры покрывающих колец будут лежать внутри этого кольца. Значит, найдется 10 точек, лежащих в таком кольце.
155.	Спроектируем данные круги на одну из сторон квад- ’ рата. Проекцией одного круга является отрезок, длина которого равна диаметру круга. Поэтому сумма длин проекций кругов равна 2'0,51 = 1,02. Поскольку длина стороны равна 1 < 1,02, то по теореме 8 по крайней мере проекции двух кругов будут иметь общую точку. Перпендикуляр, восстановленный к стороне квадрата в этой точке, пересечет эти два круга и, следовательно, будет искомой прямой.
156.	Спроектируем данные окружности на одну из сторон квадрата. Проекция каждой окружности - отрезок, длина которого равна диаметру этой окружности. Сумма диаметров всех окружностей равна 10/л. Поскольку 10/л > 3, то сумма длин проекций всех окружностей больше 3. Длина стороны квадрата равна 1, поэтому в силу теоремы 10 найдется точка на этой стороне, которую покрывают по крайней мере 4 проекции окружностей. Перпендикуляр к стороне квадрата, восстановленный в этой точке, пересекает по крайней мере 4 данные окружности, то есть является искомой прямой.
157.	Каждой окрашенной дуге соответствует ей центральна -симметричная. Окрасим ее тоже. Тогда окрашенные дуги будут иметь в сумме длину не большую, чем длина всей окружности. По теореме 7 покрыть всю окружность окрашенные дуги не смогут. Значит, найдется неокрашенная точка А. Центрально-симметричная ей точка В также не окрашена (иначе должна быть окрашена и точка А). Таким образом, мы нашли диаметр АВ, оба конца которого не окрашены.
158.	Для каждой хорды диаметр, проведенный через любую точку меньшей из стягиваемых ею дуг или через любую точку дуги, ей центрально-симметричной, пересекает эту хорду. Длина дуги, стягиваемой хордой, больше длины этой хорды. Таким образом, длина всех таких дуг больше 2-7л и, значит,
104
по теореме 10 некоторая точка окружности окажется покрыто по крайней мере восемью дугами.
159.	Предположим обратное : пусть сумма длин хорд н< меньше лк. Для каждой хорды отметим меньшую из стягиваемых ею дуг и центрально-симметричную ей дугу. Тогда сумма длин отмеченных дуг больше удвоенной суммы длин хорд, т.е. 2лк. Поскольку длина окружности равна 2л, в силу теоремы 10 найдется точка, покрытая по крайней мере к+1 отмеченными дугами. Как и в предыдущей задаче для каждой хорды диаметр, проведенный через любую точку меньшей из стягиваемых ею дуг или через любую точку дуги, ей центрально-симметричной, пересекает эту хорду. Поэтому диаметр, проведенный из полученной точки, пересекает по крайней мере к+1 данную хорду, что противоречит условию задачи. Из этого следует, что наше предположение неверно и, значит, сумма длин хорд меньше лк.
160.	Проведем прямую 0, перпендикулярную данной прямой а. Спроектируем все отрезки на полученные прямые. Заметим, что в силу неравенства треугольника каждый отрезок длины 1 дает две проекции, сумма длин которых не меньше 1. Поэтому сумма длин проекций заданных отрезков на обе прямые не меньше 4п. По теореме 5 на одной из прямых сумма длин проекций не меньше 2п, а проекция всего круга есть отрезок длиной 2п. Следовательно, по теореме 8 на проекции круга найдутся две точки, принадлежащие проекциям двух заданных отрезков. Перпендикуляр, восстановленный в этой точке, пересекает эти отрезки и параллелен или перпендикулярен прямой а.
161.	Рассмотрим проекцию на прямую, перпендикулярную данной плоскости. Исходный шар проецируется при этом в отрезок длиной 6, а внутренние шары - в отрезки, сумма колрых равна 50. По теореме 10 найдется точка большого отрезка, принадлежащая по крайней мере девяти маленьким отрезкам, покрывающих большой. Плоскость, проведенная через эту точку и перпендикулярная данной прямой, является искомой. Она параллельна заданной плоскости и пересекает по крайней мере девять внутренних шаров. /
162-163. Докажем более общее утверждение, из которого
105
следует решение этих задач. Пусть нам даны две одинаковые окружности длиной а. На одной окружности даны п точек, на другой - несколько дуг суммарной длины меньшей чем а/п. Докажем, что можно наложить одну окружность на другую так, чтобы отмеченные дуги одной окружности не покрывали отмеченные точки другой. Произведем следующую операцию. Зафиксируем произвольную отмеченную точку первой окружности. Назовем ее А. Рассмотрим величины дуг, один конец которых -точка А, а другой - одна из отмеченных точек против часовой стрелки. Пусть это -	а2,..., ап1 (0 s а < 2я).
Зафиксируем положение второй окружности, на которой отмечены дуги г. Из них получим новые дуга Г2 поворотом окружности на угол по часовой стрелке. Соответственно, из дуг Г получим дуги Г3 поворотом на угол а2 по часовой стрелке. Аналогично получим наборы дуг Г., 1 s i s п. Так как при повороте длина дуга не меняется, то каждый набор дуг Г
имеет суммарную длину, меньшую а/n. Следовательно, объединение полученных дуг имеет длину меньше», чем длина окружности а. Поэтому найдется на окружности точка, которую не покрывает ни один из построенных наборов дуг. Пусть она отличается от фиксированной точки на угол а против часовой стрелки. Повернем тогда первую окружность на угол а по часовой стрелке (то есть совместим точку А с той, которая не покрыта ни одной из построенных дуг). Полученное наложение двух окружностей искомое. Так как точка А в этом положении не покрыта набором дуг Гр то и отмеченная точка, отличающаяся от А на угол а , не будет покрыта набором отмеченных дуг Гр что и требовалось доказать.
106
СПИСОК ЛИТЕРАТУРЫ
1.	Орлов А.И. Принцип Дирихле // Квант. 1971. N 7.
2.	Болтянский В.Г. Шесть зайцев в пяти клетках // Квант. 1977. N 2.
3.	Болтянский В.Г. Как часто степень двойки начинается с единицы? // Квант. 1978. N 5.
4.	Гейн А.Г. Перед школьной олимпиадой // Квант.1983. N 10.
5.	Бабинская И. Л. Задачи математических олимпиад. М.: Наука, 1975.
6.	Вышенский В.А., Карташов Н.В., Михайловский В.И., Ядрен-ко М.И. Сборник задач киевских , математических олимпиад. Киев: Вища школа, 1984.
7.	Васильев Н.Б., Гутенмахер В.Л., Раббот Ж.М., Тоом А.Л. Заочные математические олимпиады. М.: Наука, 1981.
8.	Васильев Н.Б., Егоров А.А. Задачи всесоюзных математических олимпиад. М.: Наука, 1988.
9.	Венгерские математические олимпиады / Пер. с венг. М.:. Мир, 1976.
10.	Зарубежные математические олимпиады / Под р^ч. И.Н.Сергеева. М., Наука, 1987.
И. Львовский С.М., Тоом А.Л. Можно и нельзя // Квант. 1989. N 1.
12.	Харари Ф. Теория графов. М.: Мир, 1973.
13.	Бекламов Б.В. Применение теоремы Эйлера к некоторым задачам // Квант. 1975. N 11.
14.	Кац М.0. О плоских правильных графах //Квант.1975. N 11.
15.	Березина Л.Ю. О графах с цветными ребрами // Квант. 1973. N 8.
16.	Сграшевич С., Бровкин Е. Польские математические олимпиады / Пер. с польск., М.: Мир, 1978.
17.	Прасолов В.В., Шарыгин И.Ф. Задачи по стереометрии. М.: Наука, 1989.
18.	Воробьев Н.Н. Признаки делимости. М.: Наука, 1974.
19.	Воробьев Н.Н. Числа Фибоначчи. М.: Наука, 1978.
20.	Виленкин Н.Я. Комбинаторика. М.: Наука, 1969.
21.	Вагутен В.Н. Числа с\ многочлены, последовательности //
Квант. 1973. N 2.
107
ОГЛАВЛЕНИЕ
Введение................................... 5
§ 1.	Дискретный принцип Дирихле................. 7
§ 2.	Теория чисел.............................. 13
§ 3.	Геометрия................................. 22
§ 4.	Графы. Принцип крайнего................... 26
§ 5.	Принцип усреднения........................ 30
§ 6.	Геометрический принцип Дирихле.........	36
Решения. . , ...............	42
Список литературы........................ 107
Андрей Владимирович Летчиков ПРИНЦИП ДИРИХЛЕ
Задачи с указаниями и решениями Учебное пособие
План 1992 г., резерв.
Редактор В.И.Бацекало. Корректор Н.В.Стружкина.
Подписано в печать 15.03.92.
Формат 60x84’z^. Бумага писчая.
Печать офсетная. Усл. печ. л.6.25.
Уч.-изд. л. 6,0 . тираж 1500. Заказ 7*0 Цена договорная.
Издательство Удмуртского университета. 426037. Ижевск. Красногеройская, 71. Объединение "Полиграфия*.
426037. Ижевск. Удмуртская. 237.