Неэлементарные задачи
в элементарном изложении

DjVu

      ПРЕДИСЛОВИЕ
      Эта книга первоначально была задумана как последняя, заключительная часть сборника «Избранные задачи и теоремы элементарной математики», составляющего первые три выпуска «Библиотеки математического кружка». Однако в процессу работы выяснилось, что новая книга значительно отличается от предыдущих и прежнее название к ней уже мало подходит.
      Основное отличие этой книги от первых выпусков «Библиотеки» заключается в тематике задач. Если в первых выпусках темы задач, как правило, черпались из элементарных областей математики, изучаемых в средней школе (арифметика, алгебра, геометрия), то в настоящей книге большая часть задач фактически относится к математическим дисциплинам, изучаемым только в высшей школе, — к теории вероятностей, проективной геометрии, топологии, интегральному исчислению, теории чисел. Назвать все эти задачи «задачами н теоремами элементарной математики» было бы уже очень большой натяжкой. В то же время ни одна из собранных здесь задач не требует для своего решения знаний, выходящих за пределы школьного курса математики (кроме кратких разъяснений, приведенных в отдельных местах книги перед условиями соответствующих задач), — и по формулировкам и по методам решения все эти задачи вполне элементарны. Иначе говоря, большинство собранных здесь предложений относится к элементарным вопросам высшей («неэлементарной») математики — это обстоятельство и имеет в виду название книги.
      Главная цель настоящей книги — познакомить читателя с рядом новых математических фактов, идей и методов; форма задачника выбрана для того, чтобы стимулировать активную, творческую работу над всем этим материалом.
      Перед чтением книги следует ознакомиться с «Указаниями К пользованию книгой» (стр. 8). Книга рассчитана на увлекающихся математикой школьников старших классов и студентов младших курсов вузов, на преподавателей математики и вообще на всех любителей этой науки; она может быть использована в работе школьных и студенческих математических кружков.
      Два раздела книги объединяются общностью цели и обращены к одному и тому же читателю, но значительно различаются по своему характеру. В разделе первом «Задачи по комбинаторике и теории вероятностей» собрано 100 задач, которые при большом различии формулировок и методов решения объединены общей постановкой вопроса. Все эти задачи относятся к одной сравнительно узкой области математики — к комбинаторике, лишь слегка затрагиваемой в курсе средней школы. Задачи первого раздела, как правило, не очень сложны и довольно близки к школьным; исключение в этом отношении составляет лишь последний цикл «Задачи на подсчет вероятностей», содержащий ряд очень трудных задач.
      В противоположность этому второй раздел «Задачи из разных областей математики» очень разнообразен по содержанию. Собранные здесь задачи заимствованы из различных областей математики, чаще всего высшей, — название книги имеет в виду в первую очередь именно этот раздел. Указания на то, к каким математическим дисциплинам относятся те или иные задачи, вместе с дополнительной литературой, по которой можно более подробно ознакомиться с этими дисциплинами, даны в кратких введениях к отдельным циклам. Сами циклы задач здесь чаще всего не связаны друг с другом. И если в первом разделе авторы стремились отразить элементарные методы комбинаторики с известной полнотой, то второй раздел по самому своему характеру, разумеется, не может претендовать ни на какую полноту.
      Ряд задач книги посвящен классическим теоремам, играющим значительную роль в современной науке; так, например, предложения задач 132 и 166 относятся к числу наиболее глубоких результатов замечательного русского математика П. Л. Чебышева. Другие задачи заимствованы из серьезных математических журналов, иногда из самых свежих их номеров. Некоторые из приведенных в книге задач предлагались на занятиях школьного математического кружка при Московском государственном университете и на олимпиадах московских школьников (номера задач, предлагавшихся на олимпиадах, приведены на стр. 10).
      Первый раздел книги составлен А. М. Ягломом, а второй — совместно обоими авторами; окончательное редактирование всей книги производилось авторами коллективно. Отдельные задачи были сообщены авторам В. Г. Болтянским, Е. Б. Дынкиным, М. И. Граевым, С. Л. Каменомостской,
      Н. И. Коробовым, Я. А. Смородинским, В. А. Успенским и Н. Н. Ченцовым; последний, а также Г. М. Адельсон-Вельский и А. М. Бонгард принимали участие также и в написании решений некоторых задач. Ряд замечаний, способствующих улучшению книги, был сделан сотрудниками редакции математики Гостехиздата А. 3. Рыбкиным и В. А. Солодковым. Авторы искренне благодарны всем, помогавшим им в той или иной форме в работе над книгой.
      А. М. Яглом, И. М. Яглом.
     
      УКАЗАНИЯ К ПОЛЬЗОВАНИЮ КНИГОЙ
      После того как задача будет решена, следует проверить себя, посмотрев ответ задачи; если ответы не совпадают, то надо попытаться найти свою ошибку; если же ответы совпадают, то полезно сравнить найденное решение с приведенным в книге. Если решить задачу самостоятельно не удается, то следует посмотреть в конце книги указание (или ответ, который тоже может помочь прийти к верному решению). Если и это не поможет, то следует ознакомиться с решением. Надо иметь в виду, что попытка решить задачу, даже окончившаяся неудачно, все же приносит пользу; она позволяет лучше вникнуть в суть вопроса и более сознательно отнестись к приведенному в книге решению.
      Впрочем, указанный выше порядок пользования книгой может быть рекомендован не во всех случаях. Книга содержит много трудных задач, обозначенных в порядке возрастающей трудности одной, двумя и тремя звездочками. Задачи, обозначенные двумя и тремя звездочками, зачастую представляют собой выдающиеся достижения крупнейших математиков (см., например, задачи 132 или 166); естественно, вряд ли можно рассчитывать, что читатель сможет получить эти результаты совершенно самостоятельно. Поэтому в случае более трудных задач можно посоветовать с самого начала ознакомиться с приведенным в конце книги указанием; даже и после этого решение задачи, как правило, будет представлять значительные трудности.
      Книгой (особенно вторым ее разделом) можно пользоваться и не как задачником, а смотреть на нее как на собрание отдельных математических предложений, в среднем более сложных, чем те, которые собраны в превосходной книге С. Штейн-
      гауза «Математический калейдоскоп» (М. — Л., Гостехиздат, 1949), и облеченных в форму задач, снабженных подробными решениями. При таком подходе к книге решения задач надо разбирать сразу после ознакомления с условием. Некоторые части книги написаны так, что их лучше всего читать именно таким образом (циклы 12 — 14 второго раздела, задачи 51 — 52, 81 — 82 первого раздела и вообще большинство задач, обозначенных тремя звездочками; в несколько меньшей мере — циклы 6Б и 6В первого раздела или цикл 10 второго раздела).
      Курсивом набраны номера задач, не требующих для решения знаний, выходящих за пределы программы восьми классов средней школы.
      Первый раздел книги проще второго, поэтому читателю-школьнику рекомендуется начинать с него. Задачи первого раздела естественно решать в той последовательности, в которой они расположены в книге, постепенно переходя от одного цикла к следующему (с возможными пропусками тех циклов, которые покажутся читателю менее интересными); при этом, разумеется, вовсе не необходимо решить все задачи какого-либо цикла, прежде чем перейти к следующему. В последнем цикле первого раздела имеется несколько задач, решения которых опираются на предложения, составляющие содержание задач второго раздела; все такие задачи отмечены тремя звездочками, и указания к ним содержат ссылки на используемые в их решении результаты. Первый раздел книги может быть положен в основу работы школьного или студенческого математического кружка, занимающегося комбинаторикой и ее приложениями к теории вероятностей. При этом может оказаться полезной дополнительная литература, указанная в тексте книги. Можно рекомендовать такой порядок работы кружка: более легкие задачи решаются участниками самостоятельно, а более трудные рассматриваются как «теория»: их решения разбираются по книге и докладываются на собраниях кружка.
      Второй раздел книги построен по иному плану. Циклы здесь содержат, как правило, значительно меньше задач (иногда только одну); отдельные циклы чаще всего совершенно независимы один от другого. Также и внутри отдельного цикла задачи обычно не зависят одна от другой; лишь в циклах 10 — 14 решения задач весьма существенно опираются на результаты предыдущих задач. Ряд задач второго раздела (например, задачи 102 — 103, 105 — 107, 109, 111 — 112, 115 — 116, 117, 118, 122, 123 — 124, 128 — 129, 130 — 135, 142 — 145) может послужить хорошей темой доклада на студенческом математическом кружке; опытный руководитель сумеет воспользоваться этим материалом и в работе школьного кружка. В работе кружка будет полезной и дополнительная литература, указанная во введениях к отдельным циклам задач.
      Особое место в книге занимают последние три цикла задач второго раздела. Они тесно связаны между собой: решения нескольких задач цикла 12 опираются на результаты задач цикла 13 (все такие задачи помечены одной звездочкой); все задачи цикла 13 решаются с применением геометрических методов, развитых в цикле 12; решения задач цикла 14 зачастую опираются на результаты задач двух предшествующих циклов. Таким образом, циклы 12 — 14 представляют собой единое целое. Они содержат большой и важный теоретический материал и относятся к числу труднейших в книге; их разбору можно посвятить работу специального математического кружка.
     
      НОМЕРА ЗАДАЧ, ПРЕДЛАГАВШИХСЯ НА МОСКОВСКИХ МАТЕМАТИЧЕСКИХ ОЛИМПИАДАХ
      Олимпиады проводятся в два тура: первый тур имеет отборочный характер, второй является основным этапом соревнования.
      Олим- пиада I тур 11 тур Олимпиада I тур II тур
      Для учащиз VI (1940) VIII (1945) IX (1946) X (1947) XIII (1950) сся 7 — 8 18 -го классов 14, 33а) 60а) 102 52а) Для учащиз I (1935) II (1936) III (1937) IV (1938) V (1939) VI (1940) VIII (1945) IX (1946) X (1947) XI (1948) XII (1949) XIII (1950) сся 9 — И 1 2 47а) )-го классов 4, 25 15 45 11а), 43а) 436)г) 13 606) 1036) 108а), 113 24 88а) 101
      1) Для пяти сфер.
     
      ЗАДАЧИ
      РАЗДЕЛ I
      ЗАДАЧИ ПО КОМБИНАТОРИКЕ И ТЕОРИИ ВЕРОЯТНОСТЕЙ
      Задачи, собранные в этом разделе, объединяются постановкой вопроса: почти во всех из них требуется ответить на вопрос «сколько?» или «сколькими способами?». Такие задачи часто называются комбинаторными (это задачи на подсчет числа различных комбинаций), а часть математики, занимающаяся решением подобных задач, — комбинаторикой. Некоторые сведения по комбинаторике входят в 'курс 10-го класса средней школы (решение задач о числе различных перестановок, размещений и сочетаний); в большей части приведенных ниже задач знание этого теоретического материала не предполагается (исключение составляют задачи 5 — 7, 29, 48, 49, 55 — 60, 66 — 71, 77 — 80).
      Помимо задач, начинающихся словами «сколько» и «сколькими способами», в настоящий задачник включены также некоторые задачи, посвященные свойствам биномиальных коэффициентов С™, определяющих число сочетаний из п элементов по т (эти задачи составляют цикл 5), и ряд задач на подсчет вероятностей (цикл 6). Последние задачи не претендуют на то, чтобы дать читателю представление о содержании и методах теории вероятностей, которая выступает в настоящей книге не как самостоятельная математическая дисциплина, а только как область, в которой комбинаторные расчеты находят наиболее значительные применения. По этой причине в цикл 6 включены только такие задачи, решения которых не используют никаких специальных теоретико-вероятностных методов. Некоторые более характерные для теории вероятностей вопросы разобраны в третьем разделе книги Е. Б. Дынкина и В. А. Успенского «Математические беседы», составляющей выпуск 6 «Библиотеки математического кружка» (М. — Л., Гостехиздат, 1952); приведенный там материал может рассматриваться как естественное продолжение цикла 6 настоящего раздела.
      Чтобы не увеличивать чрезмерно объем книги, мы вынуждены были отказаться от включения сюда задач, использующих самый важный из общих методов комбинаторики — так называемый «метод производящих функций» (отметим, впрочем, что первые задачи цикла 5 подводят читателя вплотную к основной идее этого метода). По этому поводу см. очень интересную книгу Л. Эйлера «Введение в анализ бесконечно малых», т. 1 (М. — Л., ОНТИ, 1936), особенно гл. XVI этой книги, а также первый параграф книги Г. Полна и Г. Сеге «Задачи и теоремы из анализа», ч. 1 (М. — Л., ОНТИ, 1937). Применения метода производящих функций к теории вероятностей освещены в гл. 6 второй части книги С. Н. Бернштейна «Теория вероятностей» (М. — Л., Гостехиздат, 1946)и в книге В. Феллера «Теория вероятностей и ее применения» (М., ИЛ, 1952).
     
      1. Вводные задачи
      1. В пространстве даны 4 точки, не лежащие в одной плоскости. Сколько можно провести плоскостей, равноудаленных от этих точек?
      2. В пространстве даны 5 точек, не лежащих ни в одной плоскости, ни на одной сфере. Сколько существует плоскостей или сфер, равноудаленных от этих 5 точек?
      [Расстоянием от точки М до сферы 2 с центром О называется длина кратчайшего из двух отрезков МА и MB, где А и В — точки пересечения прямой МО со сферой 51*).
      *) Можно доказать, что меньший из отрезков МА и MB является самым коротким из всех отрезков, соединяющих точку М со всевозможными точками сферы 2.
      3. Сколько существует сфер, касающихся плоскостей всех граней данной трехгранной пирамиды 7?
      4. Сколькими различными способами можно раскрасить грани куба в шесть данных цветов (каждая грань должна быть закрашена целиком одной краской), если различными считаются лишь те раскраски, которые не могут быть совмещены вращением куба?
      5. Сколькими различными способами можно из 30 рабочих создать 3 бригады по 10 человек в каждой?
      6. Сколькими различными способами можно выбрать 6 одинаковых или различных пирожных в кондитерской, где имеется 11 различных сортов пирожных?
      7. Комиссия состоит из 11 человек. Материалы, над которыми работает комиссия, хранятся в сейфе. Сколько замков должен иметь сейф и сколькими ключами следует снабдить каждого члена комиссии для того, чтобы доступ к сейфу был возможен, когда соберется большинство членов комиссии, но не был возможен, если соберется лишь меньше половины ее членов?
      8. Числа от 1 до 1000 выписаны подряд по кругу. Начиная с первого, вычеркивается каждое 15-е число (т. е. числа 1, 16, 31 и т. д.), причем при повторных оборотах учитываются также и уже зачеркнутые числа. Вычеркивание продолжается до тех пор, пока не окажется, что все вычеркиваемые числа уже были зачеркнуты ранее. Сколько чисел останутся незачсркнутнмн?
      9. Все числа от 1 до 10 000 000 000 выписаны подряд. Каких чисел среди них будет больше — таких, в записи которых встречается цифра 1, или таких, в записи которых 1 не встречается?