И. О. Соловьева. Практикум по решению олимпиадных задач по матем. Практикум по решению олимпиадных задач по математике
 Скачать 1.1 Mb.
|
|
2. Принцип Дирихле Принцип Дирихле 1 имеет несколько формулировок. Наиболее простая следующая: «Если пять кроликов сидят в двух клетках, то в некоторой клетке сидит не менее трех кроликов». В обобщенной формулировке принцип Дирихле звучит так: «Если в k клетках больше nk кроликов, то хотя бы в одной сидит больше n кроликов». Немного иначе это утверждение формулируется так: «Если n кро- ликов сидят в k клетках, то найдется клетка, в которой сидит не меньше чем k n / кроликов, и найдется клетка, в которой сидит не больше чем k n / кроликов». Пусть вас не смущает дробное число кроликов: в первой формулировке получится, что в клетке сидит не менее 2 / 5 кроликов, значит, не меньше трех. Принцип Дирихле известен также как принцип голубей и ящи- ков, когда роль кроликов играют голуби, а клеток – ящики. Это название распространено в английском и некоторых других языках. Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются. 1 Петер Густав Лежён Дирихле (1805-1859) – немецкий математик, основ- ные труды посвящены теории чисел и математическому анализу. Значи- тельные работы посвящены механике и математической физике. 13 Проведем доказательство методом от противного для обобщенной формулировки принципа Дирихле. Предположим противное: в каждой клетке сидит не более k кроликов. Тогда всего кроликов не более nk, а их по условию больше nk. Получили противоречие, ко- торое опровергает наше предположение. Принцип Дирихле кажется очевидным, однако, чтобы его при- менить, бывает не просто догадаться, что считать кроликами, а что – клетками. Можно дать такой совет: если каждому элементу множества A соответствует ровно один элемент множества B, то элементы A можно назвать кроликами, а элементы B – клетками. Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше n m / кг и какой-то съел не больше n m / кг» (а если кто-то съел больше сред- него, то кто-то съел меньше среднего). Заметим, что в этой форму- лировке кролики играют роль клеток для травы, а трава – роль кро- ликов, сидящих в клетках. Рассмотрим примеры решения задач. Задача 17. В классе 40 учеников. Найдется ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса? Решение (метод от противного). Предположим, что такой ме- сяц не найдется. Тогда в каждом из 12 месяцев года отмечают свой день рождения не более трех одноклассников. В этом случае уча- щихся всего не более 36 3 12 , что противоречит условию задачи. Наше предположение неверно, значит, найдется месяц, в котором день рождения не менее чем у четырех учеников этого класса. ■ Решение (с использованием принципа Дирихле). Докажем, что такой месяц найдется. Поскольку каждому ученику соответствует ровно один месяц, в котором он родился, то роль «клеток» играют месяцы года (их 12), а роль «кроликов» – учащиеся (их 40). По принципу Дирихле найдется клетка, в которой сидит не менее чем 12 40 кроликов, т.е. 4 кролика. Следовательно, найдется месяц в го- ду, в котором не менее 4 учащихся класса отмечают свой день рождения. ■ Примечание. Это довольно простая задача. В математической олимпиаде школьников может встретиться задача, в которой дока- 14 зательство аналогичного факта является лишь частью более слож- ной задачи. В этом случае, как правило, просто пишут: «согласно принципу Дирихле, найдется месяц в году, в котором не менее 4 учеников класса (в котором всего 40 учащихся) отмечают свой день рождения». Рассмотрим две более сложные задачи. Задача 18. В Москве живет около 10 млн. жителей 1 , на голове у каждого не более 150 000 волос. Докажите, что в Москве есть по крайней мере 60 человек с одинаковым числом волос на голове. Решение. Поскольку каждому жителю Москвы соответствует определенное количество волос на голове, то жители будут играть роль зайцев, а количество волос – роль клеток (их 150 001: можно пронумеровать от 0 до 150 001), каждый «кролик» попадает в ту «клетку», которая соответствует количеству волос у него на голове. Поскольку в 150 001 «клетке» сидит более 059 850 8 001 150 59 «кроликов», значит хотя бы в одной сидит не менее 60 «кроликов». Следовательно, по принципу Дирихле, в Москве есть по крайней мере 60 человек с одинаковым числом волос на голове. ■ При решении задачи 18 иногда допускается ошибка: количе- ство возможных вариантов («клеток») считают равным 150 000, забывая о допустимом варианте 0 волос. Задача 19. В первенстве по футболу участвуют 12 команд, каждые две из них должны сыграть между собой один матч. Дока- жите, что в любой момент состязаний имеются две команды, сыг- равшие одинаковое число матчей. Решение. Количество матчей, сыгранное каждой командой, из- меняется от 0 (в начале первенства) до 11 (в конце первенства). Ес- ли предположить, что к какому-то моменту состязаний все коман- ды сыграли разное количество матчей, то это означает, что одна команда еще не сыграла ни одного матча, вторая – 1, третья – 2, …, двенадцатая – все 11 матчей. Тогда получается, что двенадцатая команда сыграла уже со всеми командами, а первая – ни с одной. Получили противоречие. Следовательно, в любой момент состяза- ний хотя бы две команды сыграли равное количество матчей. ■ 1 Согласно статистическим данным на 1 января 2009 года в Москве про- живает 10 миллионов 509 тысяч человек. 15 Задачи. 20. В школе 30 классов и 1000 учащихся. Докажите, что есть класс, в котором не менее 34 учеников. 21. В классе учится 22 ученика. а) Докажите, что найдутся два ученика, родившихся в одном месяце. б) Обязательно ли найдутся три таких ученика? 22. В классе 30 учеников. В диктанте Вова сделал 13 ошибок, а остальные – меньше. Докажите, что по крайней мере три ученика сделали одно и то же количество ошибок. 23. Числа от 1 до 10 записали в строчку в произвольном поряд- ке и каждое из них сложили с его порядковым номером. Могли ли все полученные суммы оканчиваться разными цифрами? 24. 15 ребят собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов. 25. Докажите, что из любых 12 натуральных чисел можно вы- брать два, разность которых делится на 11. 26. Докажите, что из любых 1 n натуральных чисел можно выбрать два, разность которых делится на n . 27. Тридцать студентов с пяти курсов придумали 40 задач для олимпиады, причем однокурсники – одинаковое количество задач, а студенты с разных курсов – разное. Сколько студентов придума- ли по одной задаче? 28. На собеседование пришли 65 школьников. Им предложили 3 контрольные работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, полу- чившие одинаковые оценки на всех контрольных? 29. В квадрат со стороной 1 м бросили произвольным спосо- бом 51 точку. Докажите, что какие-то три из них можно накрыть квадратиком со стороной 0,2 м. 30. В квадрат со стороной 1 м бросили произвольным спосо- бом 51 точку. Докажите, что какие-то три из них можно накрыть кругом радиуса 7 1 м. 31. На квадратном столе со стороной 70 см лежит 100 квадрат- ных салфеток со стороной 10 см. Докажите, что в стол можно вбить гвоздь, который проткнет не менее трех салфеток. 32. На плоскости даны 7 прямых, никакие две из них не парал- лельны. Докажите, что найдутся две прямые, угол между которыми 16 меньше 0 26 . 33. В сфере радиуса 1 летают 9 мух. Верно ли, что в любой момент времени найдутся две из них, расстояние между которыми не превосходит 3 ? 34. На плоскости отмечено 5 точек с целочисленными коорди- натами. Докажите, что середина по крайней мере одного из соеди- няющих их отрезков также имеет целочисленные координаты. 35. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 6 из чисел +1, −1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагона- лям были различны. Помогите Буратино. 36. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не ме- нее 12 друзей. 37. На плоскости отмечена 101 точка, не все они лежат на од- ной прямой. Через каждую пару отмеченных точек красным каран- дашом проводится прямая. Докажите, что на плоскости существует точка, через которую проходит не менее 11 красных прямых. 38. На Земле океан занимает больше половины площади по- верхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки. 3. Процессы и операции В задачах этой темы описываются некоторые процессы, вы- полняются некоторые операции. Для решения нужно обнаружить некоторую закономерность. Рассмотрим примеры решения задач. Задача 39. В колонию, состоящую из двухсот бактерий, попа- дает один вирус. В первую минуту он уничтожает одну бактерию, затем делится на два новых вируса, и одновременно каждая из оставшихся бактерий тоже делится на две новые. В следующую минуту возникшие два вируса уничтожают две бактерии, и затем каждый из вирусов и каждая из оставшихся бактерий снова делится пополам и так далее. Будет ли эта колония жить бесконечно долго или, если она в конце концов погибнет, то через какое время это произойдет? 17 Решение. Рассмотрим данный процесс шаг за шагом и запол- ним таблицу: Время (мин.) Количество вирусов Количество бактерий 0 1 200 1 2 199 2 2 2 2 198 2 2 3 3 2 197 2 3 ··· ··· ··· n n 2 ) 200 ( 2 n n ··· ··· ··· 200 200 2 ) 200 200 ( 2 200 Таким образом, колония будет существовать ровно 200 минут. Возможен и другой подход к решению этой задачи. Предста- вим себе, что каждый вирус имеет дело со «своей» колонией бакте- рий. Тогда к исходу первой минуты на каждый вирус будет прихо- диться по 199 бактерий, к исходу второй минуты – по 198 и так да- лее, к исходу 199 минуты – по одной бактерии, к исходу 200 мину- ты бактерий не останется. Ответ: колония погибнет через 200 минут. ■ Задача 40. В клетки таблицы n m вписаны некоторые числа. Разрешается одновременно менять знак у всех чисел из одного столбца или из одной строки. Докажите, что несколькими такими операциями можно добиться того, чтобы суммы чисел, стоящих в любой строке и в любом столбце, были неотрицательны. Решение. Организуем следующий процесс: если сумма чисел, стоящих в какой-то строке (или в каком-то столбце), отрицательна, то у всех чисел этой строки (этого столбца) меняем знаки. После каждого такого шага сумма всех чисел, стоящих в таблице, должна увеличиваться. Так как количество возможных расстановок знаков у чисел в таблице конечно, то процесс будет конечным и приведет к тому, что суммы чисел, стоящих в любой строке и в любом столбце, станут неотрицательными, что и требовалось доказать. ■ К данной теме можно также отнести задачи на переливание (см. задачи 48-52) и на взвешивание (см. задачи 53-59). В этих за- 18 дачах нужно описать последовательность операций, которая при- ведет к решению задачи. Задача 41. Отлейте из цистерны 13 литров молока, пользуясь бидонами емкостью 17 и 5 литров. Решение. Наберем в 17-литровый бидон 15 л (наливая в 5- литровый бидон и переливая затем в 17-литровый). Затем заполним 5-литровый бидон, перелить сможем в 17-литровый только 2 л, в 5- литровом останется 3 л. Выльем из 17-литрового бидона молоко в цистерну, перельем 3 л в 17-литровый, а затем добавим 10 л (два раза по 5 л), получим требуемые 13 л. ■ Процесс решения задач на переливание можно представить в виде таблицы. Например, решение задачи 41 будет выглядеть сле- дующим образом: Задачи. 42. На доске написано число 12. Каждую минуту число умно- жают или делят либо на 2, либо на 3, и результат записывают на доску вместо исходного числа. Докажите, что число, которое будет написано на доске ровно через час, не будет равно 54. 43. Последовательность чисел строится по следующему зако- ну: вслед за каждым числом стоит сумма цифр его квадрата, увели- ченная на единицу. На первом месте стоит число 7, поэтому на втором месте стоит число 14 ( 49 7 2 , 14 1 9 4 ). На третьем месте стоит число 17 и так далее. Какое число стоит на 2010-м ме- сте? 44. Вокруг города Зурбагана проходит кольцевая дорога. Все улицы начинаются и заканчиваются только на этой дороге, и ника- кие две улицы не имеют двух различных пересечений. Части, на которые улицы разбивают город, называются микрорайонами. В городе ввели одностороннее движение на всех улицах и на кольце- вой дороге. Докажите, что хотя бы один из микрорайонов города можно объехать по правилам. 45. В каждом из двух сосудов находится по А литров воды. Из первого сосуда переливают половину имеющейся в нем воды во Бидон, 17 л 0 5 5 10 15 15 15 17 3 8 8 13 Бидон, 5 л 5 0 5 0 5 0 5 3 5 0 5 0 19 второй сосуд, затем из второго переливают треть имеющейся в нем воды в первый, затем из первого переливают четверть имеющейся в нем воды во второй и т.д. Сколько воды окажется в каждом из сосудов после ста переливаний? 46. В парламенте у каждого есть не более трех врагов. Дока- жите, что парламент можно разделить на две палаты так, что у каждого парламентария в своей палате будет не более одного врага. 47. Поток студентов пять раз сдавал один и тот же зачет (не сумевшие сдать зачет приходили на следующий день). Каждый день успешно сдавали зачет треть всех пришедших студентов и еще треть студента. Каково наименьшее число студентов, так и не сдавших зачет за пять раз? 48. Имеются два ведра: одно емкостью 4 литра, другое – 9 литров. Можно ли набрать из реки ровно 6 литров воды? 49. Можно ли отмерить 8 литров воды, находясь у реки и имея два ведра: одно вместимостью 15 литров, другое – вместимостью 16 литров? 50. Из полного восьмилитрового ведра отмерьте 4 литра с по- мощью пустых трехлитровой банки и пятилитрового бидона. 51. Имеются три бочонка вместимостью 6 ведер, 3 ведра и 7 ведер. В первом и третьем содержится соответственно 4 и 6 ведер кваса. Требуется, пользуясь только этими тремя бочонками, разде- лить квас поровну на две части. 52. Имеются двое песочных часов: на 7 минут и на 11 минут. Каша должна вариться 15 минут. Как сварить ее, перевернув часы минимальное количество раз? 53. Имеются монеты, одинаковые по внешнему виду. Одна из монет тяжелее остальных. Есть рычажные весы без гирь. Сколько взвешиваний надо сделать для гарантированного нахождения тя- желой монеты, если всего монет а) 21; б) 200; в) n? 54. Имеется 7 внешне одинаковых монет, среди которых 5 настоящих (все одинакового веса) и 2 фальшивых (одинакового между собой веса, но легче настоящих). Как с помощью двух взве- шиваний на чашечных весах без гирь выделить 3 настоящие моне- ты? 55. Имеется 6 одинаковых по виду монет, 4 из них настоящие, а 2 – фальшивые: обе легче настоящих, но их массы различны. За 20 три взвешивания на чашечных весах без гирь найдите обе фальши- вые монеты. 56. а) Среди 18 монет одна фальшивая, причем фальшивая мо- нета отличается по массе от настоящих. За какое наименьшее ко- личество взвешиваний на чашечных весах без гирь можно опреде- лить, легче или тяжелее настоящей фальшивая монета (находить фальшивую монету не нужно). б) Условие задачи то же, но монет n 2 n . Найдите наименьшее число взвешиваний. 57. Имеется 4 пакета разной массы и чашечные весы без гирь. Как за 5 взвешиваний расположить пакеты в порядке возрастания массы? 58. Имеется 40 внешне одинаковых монет, среди которых 2 фальшивые – они легче, чем остальные и весят одинаково. Как с помощью двух взвешиваний на чашечных весах без гирь отобрать 20 настоящих монет? 59. В ряд выложено восемь внешне одинаковых монет. Вам известно, что монеты с первой по седьмую – фальшивые, а восьмая – настоящая. В Вашем распоряжении чашечные весы без гирь. Как за три взвешивания Вы можете доказать, что монеты с первой по седьмую фальшивые, человеку, который знает только то, что есть сколько-то фальшивых монет, фальшивые монеты весят одинаково и фальшивые монеты легче настоящих? 4. Инварианты и полуинварианты В задачах, где требуется выяснить, можно ли с помощью за- данных операций перейти от одного из объектов к другому (из од- ной позиции в другую), часто полезно найти «инвариант» – число- вую характеристику объектов (или функцию с какими-то другими значениями на множестве объектов), которая не меняется при ука- занных операциях. Например, разрезание и перестановка частей фигур не меняет суммарной площади. В качестве инварианта мо- жет использоваться, например, остаток от деления на 2 (четность) или другое натуральное число. Если инвариант различает два по- ложения, то от одного положения нельзя перейти к другому. Рассмотрим задачу, в которой инвариантом является четность некоторой величины. 21 Задача 60. Даны числа 1, 2, 3, 4, 5, 6. Разрешено к любым двум из них прибавить по 1. Можно ли уравнять числа, сделав это не- сколько раз? Решение. Нужно найти инвариант указанных в условии опера- ций. За одну операцию сумма данных чисел увеличивается на 2, значит, инвариантом является нечетность суммы всех чисел. Ис- ходная сумма равна 21, следовательно, после любого числа опера- ций она будет нечетной. С другой стороны, если удастся уравнять числа (сделать их все равными некоторому числу a ), то сумма по- лученных чисел должна делиться на 6 (так как она будет равна a 6 ), а значит, быть четной, что невозможно. Следовательно, числа уравнять нельзя. ■ Рассмотрим более сложную задачу, в которой инвариант найти не просто. |