Математическая смесь [Александр Александрович Локшин] (pdf) читать онлайн

А.А. Локшин
Е.А. Иванова

МАТЕМАТИЧЕСКАЯ
СМЕСЬ

МАКС Пресс
МОСКВА – 2015

А.А. Локшин, Е.А. Иванова

МАТЕМАТИЧЕСКАЯ
СМЕСЬ
Пособие
2-е издание, исправленное и дополненное

МОСКВА – 2015

УДК 51
ББК 22.1
Л73

Локшин А.А., Иванова Е.А.
Л73

Математическая смесь: Пособие. – М.: МАКС Пресс,
2015. – 2-е изд., испр. и доп. – 112 с.: ил.
ISBN 978-5-317-04878-5
Пособие адресовано школьным учителям, а также студентам педвузов и педагогических колледжей, изучающим математику. Рассмотрены вопросы моделирования при решении текстовых задач, а также избранные авторами темы из комбинаторики, логики, алгебры, геометрии
и теории чисел. По сравнению с первым изданием, вышедшим в 2014
году, книжка существенно расширена: добавлены новые разделы, посвященные математическим играм, а также методу «диагональной индукции». Кроме того, исправлены замеченные неточности и опечатки.
УДК 51
ББК 22.1

ISBN 978-5-317-04878-5

© Локшин А.А., Иванова Е.А., 2014
© Локшин А.А., Иванова Е.А., с изменениями, 2015

Учебное издание

ЛОКШИН Александр Александрович
ИВАНОВА Елена Алексеевна
МАТЕМАТИЧЕСКАЯ
СМЕСЬ
Пособие
2-е издание, исправленное и дополненное
Подготовка оригинал-макета:
Издательство «МАКС Пресс»
Главный редактор: Е.М. Бугачева
Компьютерная верстка: Н.С. Давыдова
В книге использованы рисунки А.А. Локшина

Подписано в печать 09.12.2014 г.
Формат 60х90 1/16. Усл.печ.л. 7,0. Тираж 50 экз. Заказ 288.
Издательство ООО «МАКС Пресс»
Лицензия ИД N 00510 от 01.12.99 г.
119992, ГСП-2, Москва, Ленинские горы,
МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к.
Тел.8(495) 939-3890/91.
Тел./Факс 8(495) 939-3891.

ÑÎÄÅÐÆÀÍÈÅ

Предисловие ...................................................................................................5
1. Парадокс математической индукции .......................................................6
2. Откуда мы знаем, что такое «точка»? ......................................................9
3. Текстовые задачи: какой метод предпочесть? ......................................12
4. Мысленное моделирование при решении текстовых задач.................15
5. Усохшие проценты ..................................................................................18
6. Правило произведения в комбинаторной задаче о маршрутах............20
7. Об одном комбинаторном соотношении ...............................................25
8. Чему равен нуль-факториал? ..................................................................26
9. Задача о составлении букета...................................................................28
10. О некоторых трудностях в преподавании логики...............................30
11. Несуществующие объекты и математическая логика ........................31
12. Импликация и время..............................................................................32
13. Три задачи…………………...................................................................36
14. Почему деление не дистрибутивно слева? ..........................................37
15. Обобщенная диаграмма Эйлера ...........................................................38
16. Змей Горыныч и транзитивность..........................................................40
17. Признаки делимости на 9 и 11 и математические фокусы.................45
18. Альпинист на утёсе................................................................................50
19. Об одной задаче на разбиение геометрических фигур.......................52
20. «Нерешаемое» квадратное уравнение..................................................55
21. Необычное уравнение окружности ......................................................56
22. Принцип непрерывности в комбинаторике .........................................57
23. Странное отражение ..............................................................................60
24. Строгость или здравый смысл? ............................................................63
25. О теоретико-множественных тождествах ...........................................66
26. Кое-что о двоичной системе .................................................................69
27. О квадратных уравнениях с параметрами ...........................................73
28. Профессор Мориарти на отдыхе ..........................................................77
29. Частокол из единиц................................................................................78
3

30. О периодах десятичных дробей............................................................80
31. Загадка Мориарти ..................................................................................85
32. Дихотомия в логических задачах .........................................................86
33. Обезьяна, небоскреб и орехи ................................................................92
34. Магический квадрат и стратегия Шеня ...............................................97
35. Переправы и симметрия ........................................................................99
36. «Диагональная» индукция ..................................................................101
37. Букеты и НОД ......................................................................................103
38. Обманчивое сходство ..........................................................................106
Ответы к задачам из пп. 28 и 31 ...............................................................110
Список обозначений ..................................................................................110
Литература..................................................................................................111

4

ÏÐÅÄÈÑËÎÂÈÅ

В книжке рассмотрены некоторые вопросы из теории множеств, логики, комбинаторики и элементарной геометрии, недостаточно освещенные в имеющейся литературе и представляющие, на взгляд авторов, интерес для студентов пединститутов
(в особенности, для студентов факультетов начальных классов),
школьников-старшеклассников и учителей математики.
Авторы

5

1. ÏÀÐÀÄÎÊÑ ÌÀÒÅÌÀÒÈ×ÅÑÊÎÉ ÈÍÄÓÊÖÈÈ1
Метод математической индукции является, как известно, могучим инструментом, позволяющим доказывать многие математические утверждения, не поддающиеся иным методам. Соль метода в
том, что он позволяет, так сказать, «опереться на недоказанное».
В простейшем случае действие метода выглядит так. Пусть
имеется некоторое утверждение A(n), зависящее от натурального
номера n (n = 1,2,…). Тогда если A(1) истинно и если при каждом
натуральном n из истинности A(n) следует истинность A(n+1), то
A(n) истинно при всех натуральных n.
Приведенная выше распространенная формулировка метода
математической индукции может быть кратко записана, с использованием общепринятых математических терминов, в следующем
виде:
A(1)
(∀n ∈ N ) A( n ) → A( n + 1)
.
(1.1)
(∀n ∈ N ) A( n )
Здесь формулы над чертой – так называемые посылки, истинность которых мы должны предварительно установить, формула
под чертой – вывод, истинность которого обеспечивается истинностью посылок; N обозначает множество натуральных чисел.
Парадокс, однако, заключается в том, что, «применяя математическую индукцию», мы пользуемся не методом (1.1), а другими
соображениями.
Действительно, посмотрим, как фактически проводится доказательство «по индукции». Вначале устанавливается База индукции – доказывается справедливость A(1), и пока мы, как будто, действуем в согласии со схемой (1.1). Однако наши следующие действия представляют собой мыслительные операции, в
корне отличные от второй строчки в схеме (1.1). Фактически, мы
рассуждаем так:
«Предположим, что A(n) истинно при некотором произвольном n (Предположение индукции). Докажем, что тогда A(n+1)
тоже истинно (Шаг индукции)».
____________
Cм. [1].
6
1

Без слова «некоторый» здесь обойтись невозможно, так как в
противном случае наше предположение звучало бы так:
«Предположим, что A(n) истинно при произвольном n», т.е.
мы предположили бы то, что требуется доказать! Без слова «произвольный», очевидно, тоже невозможно обойтись. В итоге вместо (1.1) мы пользуемся на самом деле следующей (вполне общепринятой) схемой:
A (1)
A(n ) истинно при некотором произвольном n → A(n + 1) истинно
(1.2)
(∀n ∈ N ) A( n )

Замечание 1. Заметим, что понятие «некоторый произвольный» не удается выразить с помощью математических кванторов
∀ (для любого) и ∃ (существует).
Замечание 2. В следующем параграфе мы постараемся прояснить возникающую здесь ситуацию. Заодно мы увидим, что в
схеме (1.2) пропущен, но используется «по умолчанию» еще один
этап – обобщение и, по сути, объединим схемы (1.1) и (1.2).
Î ÏÐÎÈÇÂÎËÜÍÎÌ ÂÛÁÎÐÅ, ÎÁÎÁÙÅÍÈÈ
È ÏÎÍÈÌÀÍÈÈ

Существует ли на самом деле «произвольный выбор»?
Возможно ли раз и навсегда избавиться в проводимых доказательствах от «произвольного выбора», заменив его «случайным
выбором» (или выбором, основанным на аксиоме выбора) и использованием общих свойств элементов множества, откуда выбираются упомянутые элементы?
Посмотрим, так ли это. Напомним вначале, что такое содержательная аксиоматическая теория. Это такая математическая
теория, в которой логические выводы из аксиом делаются на основе общепринятой логики, восходящей к Аристотелю. Приведем
теперь две аксиомы, используемые в содержательной аксиоматической теории вещественных чисел:
Аксиома № 1.

(∀x, y ∈ R ) x + y = y + x

(1.3)

(здесь R обозначает множество вещественных чисел).
7

Аксиома № 2.

(∀x, y, z ∈ R ) ( x + y ) + z = x + ( y + z ).

(1.4)

Теперь рассмотрим следующее несложное утверждение.
Теорема.

(∀x, y, z ∈ R ) ( x + y ) + z = ( z + x ) + y.

(1.5)

Мы приведем два различных доказательства этой теоремы,
сравнивая которые, попытаемся разобраться в том, что такое
«произвольный выбор».
Доказательство № 1. (Пользуемся понятием «произвольно
выбранного элемента».) Из аксиом (1.3) и (1.4), понимая их содержание, последовательно заключаем, что для произвольно взятых x, y, z:
(x + y) + z = z + (x + y) = (z + x) + y.
Так как х, у, z были взяты произвольными, заключаем, что отсюда следует утверждение теоремы.
Подчеркнем, что несмотря на то, что операция «произвольного выбора» так и не была определена, доказательство № 1 воспринимается как полностью понятное.
Доказательство № 2 (См. дискуссию в [26], сообщение Vladimir’a iz Chikago). Понятием «произвольного выбора» не пользуемся. Рассуждаем так: берем три случайно выбранных числа из
множества R (например, числа 1, 2 и 3), пользуемся только свойствами, указанными в аксиомах и получаем соотношение
(1 + 2) + 3 = (3 + 1) + 2.

(1.6)

Понимаем, что полученный результат имеет общий характер,
т.е. для всех остальных троек чисел должны иметь место аналогичные соотношения и тем самым верна доказываемая теорема.
Замечание 1. Итак, выбор «произвольных элементов из R»
(см. доказательство № 1) отсутствует в доказательстве № 2, которое состоит из последовательных операций:
а) случайный выбор элементов из R;
б) использование аксиом (1.3) и (1.4) (т.е. только общих
свойств всех элементов из R);
8

в) использование неформально осознаваемой операции
обобщения (включающей в себя – в данной задаче – охват мысленным взором одновременных однотипных действий со всеми
элементами из R). Этот мысленный охват оказывается возможен
потому, что действие, о котором идет речь, ранее было применено к конкретным элементам (в доказательстве № 2 – к числам 1, 2
и 3) и тем самым была «проторена дорога» нашему воображению.
При этом понимание смысла всех действий, производимых в
процессе доказательства, сохраняется.
Замечание 2. По-видимому, для устранения неопределенности термина «выбор произвольного элемента» этот термин можно
понимать в духе пунктов а) – в) Замечания 1. (При этом встречавшийся нам в предыдущем параграфе термин «выбор некоторого произвольного элемента» естественным образом может быть
истолкован в духе пунктов а) – б) Замечания 1.)
Замечание 3. Похоже, что мы имеем дело с закономерностью: без ущерба для понимания математического содержания
достаточно богатой теории обойтись без неформально осознаваемой операции обобщения невозможно.
Замечание 4. В методе математической индукции упомянутое неформально осознаваемое обобщение, очевидно, присутствует в неявном виде. Нетрудно видеть, что метод индукции – если без пропусков следовать за пониманием – состоит из двух
умозаключений, первое из которых имеет вид
A( n ) истинно при некотором произвольном n → A( n + 1) истинно
,
(∀n ∈ N ) A( n ) → A( n + 1)
а второе – совпадает с (1.1).

2. ÎÒÊÓÄÀ ÌÛ ÇÍÀÅÌ, ×ÒÎ ÒÀÊÎÅ ÒÎ×ÊÀ?
Обсудим теперь один из интереснейших вопросов, лежащих на
стыке математики и психологии. Выше мы уже обсуждали операцию выбора произвольного элемента. Эта не имеющая формального определения операция кажется совершенно естественной и дос9

тупной нашему пониманию. Пытаясь разобраться в природе этой
операции, мы выяснили, что она – по своим результатам – эквивалентна случайному выбору и последующему неформальному
обобщению.
Но не будем останавливаться на достигнутом. Зададим себе
вопрос:
– Отчего неформальное обобщение, о котором шла речь выше, правомерно?
Ответ, доступный нашему пониманию, будет примерно таким:
– Это нетрудно объяснить. Достаточно рассмотреть произвольно взятый элемент…
Мы очевидным образом столкнулись с порочным кругом. «Произвольный выбор» объяснили при помощи «неформального
обобщения», а правомерность «неформального обобщения»
обосновали при помощи «произвольного выбора».
Похоже, что представление о возможности осуществить
«произвольный выбор» является для человека врожденным. (Естественно предположить, что тем самым врожденной должна
оказаться и способность к неформальному обобщению.) К такому
выводу нас подталкивают следующие обстоятельства.
Процитируем вначале учебник по высшей геометрии [3,
с. 205]: «…точки, прямые и плоскости как образы нашего геометрического воображения не поддаются математическому
описанию».
– Как же так? – может воскликнуть читатель, искушенный в
математике. – А как же аксиомы Гильберта или аксиомы Клейна?
Наконец, аксиомы Евклида? Разве они не определяют, что такое
точка, прямая и плоскость?
– Конечно, определяют, – ответим мы. – Но только в некоем
абстрактном пространстве, а не в пространстве наших зрительных образов. То есть определяют, но не то, что нужно…
Иными словами, с помощью логики, опираясь на информацию, поступающую от органов чувств, сформировать зрительный
образ точки, по-видимому, невозможно.
Но откуда же тогда взялся этот мысленный зрительный образ?
Процитируем в этой связи статью Александра Маркова
(«Элементы», 21.06.10):
10

«Ключевую роль в пространственном мышлении у млекопитающих играют три группы нейронов: “клетки места”,
“клетки направления” и “клетки координатной сетки”. Две
команды исследователей независимо друг от друга обнаружили, что у маленьких крысят, впервые в жизни отправившихся
на прогулку, уже есть нормально работающие клетки первых
двух типов, и только клетки третьего типа появляются немного позже. По-видимому, это означает, что восприятие
пространства у млекопитающих в значительной мере является врожденным».
Любопытно сравнить результаты этих опытов с методикой
обучения младших школьников понятию «точка» (сообщено авторам Н.Ю. Лукановой):
Если просто нарисовать на листе бумаги точку фломастером
или ручкой, то у ребенка может создаться впечатление, что точка –
это небольшая клякса, поэтому добавляют: «Точка не имеет
толщины, точка – это место». Замечательно, что дети легко понимают, что именно имеется в виду.
Приведем теперь еще одну цитату из вышеупомянутой статьи
А. Маркова:
«…известно, что основные нейрологические механизмы
пространственного восприятия у людей и крыс примерно одинаковы, поэтому результаты этих исследований почти наверняка приложимы к людям».
Однако, если допустить, что представление о точке является
для человека врожденным, то, похоже, приходится признать, что
врожденным является и (неявное) представление об осуществимости «произвольного выбора». Действительно, в этом случае
врожденным должно быть и представление об окружающем пространстве как о континууме, состоящем из точек. Но что значит
добраться из точки А в точку В по пути АВ? Это значит, что какова бы ни была произвольно взятая точка на этом пути, в ней придется побывать…
Замечание 1. Попробуем выяснить, как обстоят дела с обычным (количественным) натуральным числом – неужели и оно
опирается на понятие «произвольный выбор»? На наш взгляд,
ответ на этот вопрос, как ни странно, положителен. Действитель11

но, чтобы определить, например, (количественное) число «пять»,
нам нужно мысленно соединить тоненькими ниточками пальцы
руки с рассматриваемым набором предметов, устанавливая таким
способом взаимно-однозначное соответствие между пальцами и
этими предметами. Но эта процедура невозможна без представления о том, что ни одна мысленно проведенная нить не должна
рваться и мы, путешествуя взглядом вдоль нее, должны побывать
в произвольно взятой точке этой нити.
Замечание 2. Способность к «произвольному выбору» очевидным образом необходима для распознавания образов (например, если нужно узнать объект, когда он повернут на произвольный угол). Предположение о том, что эта способность является
для человека врожденной, а не приобретается с опытом, получила
недавно еще одно косвенное подтверждение в серии опытов над
новорожденными цыплятами – цыплята продемонстрировали
врожденное умение распознавать образы; см. http://elementy.ru/
news/432084, а также Justin N. Wood. Newborn chickens generate
invariant object representations at the onset of visual object experience // Proceedings of the National Academy of Sciences of the United
States of America. 2013. 110(34). doi:10.1073/pnas.1308246110.
Замечание 3. То, что понятие «длина» не является для человека врожденным и формируется у ребенка постепенно, общеизвестно. Интересно, как обстоит с этим дело у медуз и осьминогов?
3. ÒÅÊÑÒÎÂÛÅ ÇÀÄÀ×È:
ÊÀÊÎÉ ÌÅÒÎÄ ÏÐÅÄÏÎ×ÅÑÒÜ?
Цель этого параграфа – разобраться в том, при решении какого именно класса текстовых задач алгебраический метод должен в
начальной школе уступать место арифметическому методу.
С точки зрения педагога арифметический метод хорош тем,
что он одновременно активизирует и наглядно-образное мышление ученика, и его логику. Алгебраический метод обычно быстрее ведет к цели, но в значительно меньшей степени нацелен на
развитие мышления в широком смысле этого слова.
Решая задачу арифметическим способом, младший школьник,
как правило, оперирует именованными числами, что соответству12

ет наиболее развитому у него типу мышления – нагляднообразному.
В то же время решение задач алгебраическим способом минимизирует нагрузку на наглядно-образное мышление ребенка,
решение текстовой задачи в основном сводится к оперированию
символами. Научить ребенка такому оперированию, безусловно,
важно. Однако, здесь имеются «подводные камни». Дело в том,
что при решении некоторых задач, у детей происходит утрата
понимания смысла производимых ими математических действий, и задача перестает выполнять свою развивающую функцию,
превращается в рутинный «пример». Рассмотрим в этой связи
две задачи, предлагавшиеся третьеклассникам, обучавшимся по
системе Л.Г. Петерсон.
Задача А. Мышка и птичка (игрушечные) вместе стоят
10 рублей. 5 мышек и 6 птичек стоят 56 рублей. Сколько стоят
мышка и птичка по отдельности?
Решение 1 (арифметическое).
1) Сколько комплектов игрушек (мышка плюс птичка) можно
составить из 5 мышек и 6 птичек? – 5 комплектов.
2) Сколько стоят эти 5 комплектов игрушек? 5·10 = 50 (руб.).
3) Сколько птичек останется без мышек? – Одна.
4) Сколько стоит 1 птичка? 56 – 50 = 6 (руб.)
5) Сколько стоит одна мышка? 10 – 6 = 4 (руб.)
Ответ: мышка стоит 4 рубля, птичка стоит 6 рублей.
Решение 2 (алгебраическое). Пусть x – цена мышки, y – цена
птички. Тогда система из двух уравнений, соответствующая задаче
А, должна была бы содержать именованные величины и иметь вид
x + y = 10 (руб.), 5x + 6y = 56 (руб.)
Фактически же, математические преобразования обычно проводят над системой, в которой имена величин опускаются; в данном случае – над системой
x + y = 10, 5x + 6y = 56.
(3.1)
Умножая первое уравнение системы (3.1) на 5 и вычитая его
из второго, получаем y = 6, а затем из первого уравнения находим
x = 4. Теперь в ответе имена величин вспоминают:
Ответ: мышка стоит 4 рубля, птичка стоит 6 рублей.
13

Заметим, что действия при решении алгебраической системы (3.1), в сущности, те же, что и при решении этой задачи арифметическим способом. Как показывает наш опыт, дети в состоянии
объяснить смысл каждого преобразования в процессе решения
системы (3.1) на языке наглядных образов. В результате решение,
полученное алгебраическим способом, способствует закреплению
и упорядочению знаний, служит связующим звеном между наглядно-образным и абстрактным (символьным) мышлением. Рассмотрим теперь другую известную задачу (см., например [5]).
Задача Б. Десять мышек и птичек (птички и мышки настоящие, не игрушечные) съели 56 зерен. Каждая мышка съела 5 зерен, а каждая птичка – 6 зерен. Сколько было мышек и сколько
птичек?
Решение (алгебраическое). Пусть x – число мышек, y – число птичек. Составляем соответствующую задаче Б систему уравнений, содержащих именованные величины:
x + y = 10 (животных), 5x + 6y = 56 (зерен). Опуская имена величин, приходим к системе
x+y = 10, 5x + 6y = 56.

(3.2)

Решая ее, получаем: x = 4, y = 6.
Ответ: 4 мышки, 6 птичек.
Система (3.2) формально совпадает с системой (3.1) и решается тем же способом, что и система (3.1). Однако, как показывает наш опыт, дети, решив сначала задачу А алгебраическим способом и дав своему решению правильное истолкование на языке
наглядных образов, затруднялись объяснить смысл аналогичных
преобразований системы (3.2). Некоторые говорили так: «Нужно
взять пять комплектов животных и вычесть их из 56 зерен…»
Причина затруднений, очевидно, была в том, что уравнения системы (3.2), в отличие от системы (3.1), содержат величины
разных наименований.
На наш взгляд, на начальном этапе обучения область применения алгебраического метода должна быть ограничена текстовыми задачами, решение которых не приводит к системам, содержащим величины разных наименований.
14

4. ÌÛÑËÅÍÍÎÅ ÌÎÄÅËÈÐÎÂÀÍÈÅ
ÏÐÈ ÐÅØÅÍÈÈ ÒÅÊÑÒÎÂÛÕ ÇÀÄÀ×
Моделирование «в отрезках», используемое в системе Л.Г. Петерсон, существенно облегчает детям понимание текстовых
задач, в значительной степени устраняет случайное манипулирование числовыми данными.
В то же время, у некоторых детей складывается представление о том, что моделирование в отрезках есть универсальный метод, пригодный для решения «всех задач».
Мы ограничимся здесь рассмотрением текстовых задач для
начальной школы, не включающим в себя задачи «на движение».
Эти задачи, как правило, сводятся к системе двух уравнений с
двумя неизвестными.
Задача 1. В первый день портной сшил несколько костюмов,
а во второй день сшил их в три раза больше. Сколько костюмов
сшил портной в первый день, если за два дня он сшил их 16?
Решение. Пусть х – количество костюмов, сшитых в первый
день, у – количество костюмов, сшитых во второй день. В результате имеем систему из двух уравнений специального вида:
у = 3х,
(4.1)
х + у = 16.
(4.2)
Совершенно очевидно, что алгебраическая процедура решения этой системы в точности соответствует процедуре решения
при моделировании «в отрезках» (см. рис. 4.1).

Рис. 4.1

Однако, научить ребенка мыслить – это, в сущности, научить его строить разнообразные модели. Наш педагогический
опыт показывает, что желательно познакомить детей с задачами,
для которых модели «в отрезках» не работают и которые, тем не
менее, могут быть решены с помощью несложных и наглядных
рассуждений. (Что касается алгебраического подхода к решению
15

текстовых задач, то он, позволяя быстро получить ответ при помощи стандартных операций с символами, не способствует развитию образного и логического мышления.)
Задача 2 (см., например, [5]). Когда на каждую елку село по
одному соловью, то один соловей остался без елки. А когда соловьи расселись на елках парами, то одна елка осталась без соловьев. Сколько было елок и сколько было соловьев?
Решение алгебраическое. Пусть х – количество соловьев, у –
количество елок. В результате имеем систему из двух уравнений:
х = у + 1,

(4.3)

х = (у – 1)·2.

(4.4)

Подставляя х из (4.3) в (4.4), получаем
у + 1 = 2у – 2,

(4.4а)

откуда у = 3, х = 4.
Попробуем теперь решить эту же задачу при помощи «моделирования в отрезках». Соотношение (4.3), конечно, может быть
изображено графически; однако, после того как масштаб на рисунке, изображающем соотношение (4.3), выбран, соотношение
(4.4) изобразить «в отрезках» уже не удается. (Точно так же без
предварительных алгебраических преобразований не удается изобразить «в отрезках» и равенство (4.4а).)
Решение арифметическое (основанное на мысленном моделировании).
1. Представим себе ряд из нескольких елок. На каждой сидит
по соловью. Один соловей – «лишний», он висит в воздухе рядом
с последней елкой – для него не хватило елки.
2. Пересадим «лишнего» соловья на первую елку, на ней теперь два соловья.
3. Пересадим теперь соловья с последней елки на вторую елку. На второй елке теперь тоже два соловья. А на последней елке – ни одного!
4. Никакие елки, кроме первой, второй и последней уже не
нужны. Трех елок хватило, чтобы выполнить все условия задачи.
Ответ: три елки, четыре соловья.
16

В заключение приведем еще одну задачу, также не допускающую моделирование «в отрезках», но легко решаемую при
помощи мысленного моделирования.
Задача 3. В школьном саду посадили клены по 16 штук в
каждом ряду и столько же лип по 20 штук в каждом ряду, причем рядов получилось на 2 меньше. Во сколько рядов посажены
клены?
Решение алгебраическое. Пусть х – количество рядов из
кленов, у – количество рядов из лип. Тогда имеем систему:
у = х – 2,

(4.5)

16х = 20у.

(4.6)

Подставляя выражение для у из (4.5) в (4.6), получаем
16х = 20(х – 2), откуда х = 10.
Нетрудно видеть, однако, что (непосредственно, без предварительных алгебраических преобразований) при помощи моделирования «в отрезках» система (4.5), (4.6) не решается.
Решение арифметическое (основанное на мысленном моделировании). Будем пересаживать липы так, чтобы они были
посажены такими же рядами, как клены. Для этого выкопаем
4 липы из первого ряда и посадим их в новый ряд за последним
рядом лип. Чтобы заполнить первый новый ряд, нужно выкопать
по 4 липы из первых четырех старых рядов. Чтобы заполнить
второй новый ряд нужно выкопать по 4 липы из следующих четырех старых рядов. Поэтому, посадив липы так же как клены,
мы образуем 4 + 4 + 2 рядов.
Ответ: клены были посажены в 10 рядов.
Итак, мы видим, что достаточно обширный класс задач, не
поддающийся решению при помощи моделирования «в отрезках», может быть решен арифметическим способом при помощи
мысленного моделирования. Этот класс задач, безусловно, должен предшествовать в курсе математики задачам, которые рассчитаны на решение алгебраическим способом.
17

Замечание. В заключение попробуем охарактеризовать задачи, которые могут быть решены при помощи моделирования «в
отрезках».
Прежде всего, это задачи, которые сводятся к системе из двух
уравнений с диагональной матрицей (коэффициенты системы
предполагаются целочисленными). Иными словами – это системы относительно неизвестных х, у вида
x = p,
mx + ny = q.

(4.7)
(4.8)

Системы вида
x = ay,
bx + cy = d,

(4.9)
(4.10)

(где a, b, c, d – целочисленные коэффициенты) также непосредственно, т.е. без предварительного применения алгебраических
преобразований, поддаются решению при помощи моделирования «в отрезках». Обе системы (4.7), (4.8) и (4.9), (4.10) характеризуются тем, что отрезок, изображающий одно из неизвестных (х или у) может быть выбран с самого начала произвольным образом.

5. ÓÑÎÕØÈÅ ÏÐÎÖÅÍÒÛ
В этом параграфе мы разберем еще одну известную текстовую задачу – «на проценты». Алгебраическое решение этой задачи, как правило, вызывает у учеников недоумение и воспринимается ими в известной мере формально.
Задача. В магазин привезли 100 килограммов ягод, влажность
которых составляла 99%. Через некоторое время ягоды немного
подсохли, и их влажность стала равна 97%. Сколько стали весить
ягоды, привезенные в магазин?
Решение. Обозначим через х вес сухого вещества ягод. Имеем из условия:
х = 100 – 100·0,99 = 1 (кг).
(5.1)
18

После усушки вес сухого вещества ягод, очевидно, не изменился, поэтому, обозначая через у (общий) вес ягод после усушки, очевидно, приходим ко второму уравнению:
y−x
= 0,97.
y

(5.2)

Разрешая систему (5.1), (5.2) относительно у, неожиданно получаем:
1
y = 33 (кг).
3
1
Ответ: После усушки ягоды стали весить y = 33 кг.
3
Итак, усохнув всего-навсего на 2%, ягоды стали почему-то
весить втрое меньше…
Продвинутые ученики, понимают, конечно, в чем тут дело, но
остальным полученный ответ кажется очень странным и даже
неверным.
Тем самым возникает чисто педагогическая проблема – как
изложить решение этой задачи, чтобы ее ответ сделался не
странным, а, напротив, очевидным?

Рис. 5.1

Как показывает опыт, делу может помочь простейшая геометрическая модель (которую, впрочем, редко используют1); см.
рис. 5.1, где условно принято:
AC = 100 (кг),
A′C′ = y (кг),
AB= A′B′ = 1 (кг),
AB = 1% AC,
A′B′= 3% A′C′.
Глядя на этот рисунок, даже слабые ученики воспринимают
тот факт, что если отрезок AB составляет сотую долю известно____________
В свое время аналогичная модель обсуждалась с И. Христовой.

1

19

го отрезка AC, а отрезок, составляющий сотую долю от A′C′,
в три раза короче, чем AB, то:
A′C′ =

1
100
1
AC, и тем самым A′C′ =
= 33 (кг).
3
3
3

В результате обращения к простейшей геометрической модели, задача оказывается не формально «пройденной», а действительно понятой учениками.

6. ÏÐÀÂÈËÎ ÏÐÎÈÇÂÅÄÅÍÈß
 ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÇÀÄÀ×Å Î ÌÀÐØÐÓÒÀÕ
Хорошо известно следующее правило комбинаторики – так называемое правило произведения. Если нужно выбрать упорядоченную пару элементов (a,b) и первый элемент пары можно выбрать
k способами, а после того как первый элемент выбран, второй
элемент можно выбрать m способами, то упорядоченную пару, состоящую из этих двух элементов, можно выбрать k·m способами.
Доказывается это очень просто. Будем изображать возможный выбор первого элемента пары (a,b) в виде ствола дерева
(см. рис. 6.1), а возможный выбор второго элемента пары – в виде
ветки, растущей из верхнего конца ствола (см. рис. 6.2).
Тогда выбору упорядоченной пары вида (a,b) будет соответствовать маршрут от «подножия» одного из k деревьев до верхушки ствола и затем по одной из m веток до самого верха. Нетрудно видеть, что всего таких маршрутов будет
m + m + … + m = m·k

(6.1)

(слева в (6.1) k слагаемых). Маршруты мы считаем различными,
если они не совпадают хотя бы в одной из своих частей.
Возможна ситуация, когда, например, b11= b21, но в этом случае нам приходится сравнивать маршруты (a1,b11) и (a2,b21), а они
различны, ибо a1 ≠ a2 по предположению.
Правило произведения легко обобщается на случай, когда
требуется сосчитать число возможных способов выбрать упорядоченную тройку элементов или, более общо, упорядоченный набор из n элементов.
20

Рис. 6.1

Рис. 6.2

Применим теперь правило произведения к решению простейшей задачи. Пусть города А и В связаны сетью дорог, как показано на рис. 6.3.
Ехать из А в В можно только по направлениям, указанным
стрелками (так что мы, по существу, имеем дело с ориентированным графом). Спрашивается, сколькими способами можно
доехать из А в В? Нетрудно видеть, что выбор первого участка
маршрута (до развилки) можно осуществить пятью способами,
после чего выбрать второй участок пути всегда (т.е. при любом
выборе первого участка) можно тремя способами. Таким образом, применимо правило произведения, и общее количество
способов, которыми можно добраться из А в В, равно 5·3 = 15.
Поставим теперь следующий вопрос: а сколькими способами
можно вернуться из В в А? (Разрешается ехать только против направления стрелок на рис. 6.3).
21

Рис. 6.3

Из рис. 6.3 очевидно, что правило произведения «в обратную
сторону» не работает. Тем не менее, понятно, что каждому маршруту из А в В соответствует в точности один маршрут из В в А
(мы увидим этот маршрут, если «прокрутим киноленту» в обратном направлении). Значит, вернуться из В в А можно по-прежнему 15-ю способами.
Любопытно, что в задачах о маршрутах возникает ситуация, в
которой подсчет числа вариантов по-прежнему можно проводить
по правилу произведения, но выбор «упорядоченной пары элементов» уже не столь очевиден, как раньше.
А именно, пусть на этот раз города А и В связаны сетью дорог, изображенной на рис. 6.4.

Рис. 6.4

Понятно, что в качестве упорядоченной пары (a, b) здесь следует брать пару: (малый начальный участок маршрута, малый
конечный участок маршрута).
22

Выбор такой пары, очевидно, полностью определяет сам
маршрут из А в В, и общее количество маршрутов из А в В вычисляется по правилу произведения и равно 2·3 = 6. Число маршрутов из В в А тем самым также равно шести.
Возможны еще более любопытные конфигурации дорог между А и В, к которым по-прежнему применимо правило произведения для подсчета числа возможных маршрутов из А в В (и, соответственно, из В в А). Пример такой конфигурации приведен на
рис. 6.5.

Рис. 6.5

В ситуации, изображенной на рис. 6.5, маршрут из А в В лучше
всего задавать упорядоченной парой точек вида (a, b), которую
удается подобрать так, что она однозначно определяет выбранный
маршрут. Нетрудно видеть, что после того как выбрана первая
точка упорядоченной пары (т.е. выбрана точка a1, a2,a3 или a4) выбор второй точки осуществляется одним из четырех способов. Поэтому в полном соответствии с правилом произведения число различных маршрутов из А в В на рис. 6.5 равно 4·4 = 16.
Рассмотрим еще один пример, когда маршрут из А в В определяется выбором упорядоченной тройки точек вида (a, b, c),
расположенных на сети дорог (см. рис. 6.6).
Первая координата упомянутой упорядоченной тройки точек
может быть выбрана двумя способами (a1 или a2). После того как
этот выбор сделан, вторая координата рассматриваемой упорядо23

ченной тройки точек может быть выбрана тремя способами (b1, b2
или b3). Наконец, после того как выбраны первая и вторая координаты упорядоченной тройки (a, b, c), третья координата тоже может быть выбрана одним из трех способов. Итак, по правилу произведения, число маршрутов из А в В на рис. 6.6 равно 2·3·3 =18.

Рис. 6.6

Удобно ввести символ П3(А, В) для характеристики маршрутов, связывающих «города» А и В на рис. 6.6. Здесь буква Π указывает на то, что общее число маршрутов при движении из А в В
может быть вычислено с помощью правила произведения, индекс
«3» указывает на (минимальное) количество точек, с помощью
которых мы однозначно задаем маршрут.
Предположим теперь, что города А и В связывают две непересекающиеся системы дорог, относящиеся, например, к классам
П3(А, В) и П2(В, А) соответственно. Тогда количество маршрутов
из А в В, относящихся к первой системе, согласно правилу произведения вычисляется по формуле k·m·n, где k, m, n – количества
способов выбрать первую, вторую и третью точки, задающие каждый маршрут из А в В. Аналогично, количество маршрутов второй системы вычисляется по формуле k′·m′, где k′ и m′ – количества способов выбрать соответственно первую и вторую точки,
задающие маршруты второй системы (при движении из В в А).
Поскольку число маршрутов, принадлежащих любой системе, в
конечном итоге не зависит от того, в какую сторону направлено
движение, заключаем, что в нашей задаче общее число маршрутов из А в В (и тем самым из В в А) будет равно k·m·n+k′·m′.
(Заметим, что прямой подсчет числа маршрутов в задачах такого рода может быть весьма трудоемким делом.)
24

Дальнейшие обобщения предложенного подхода очевидны:
рассмотренные системы маршрутов типа Пk(А, В) можно использовать как «строительные блоки» для конструирования более
сложных систем.
Замечание. В дальнейшем мы увидим, что правило произведения может успешно применяться в задачах совершенно иного
сорта.
7. ÎÁ ÎÄÍÎÌ ÊÎÌÁÈÍÀÒÎÐÍÎÌ
ÑÎÎÒÍÎØÅÍÈÈ
Опыт преподавания комбинаторики говорит о том, что наглядные геометрические соображения (если, конечно, ими удается воспользоваться) значительно облегчают усвоение материала.
Например, важнейший закон комбинаторики – правило произведения – обычно иллюстрируют при помощи «деревьев»1. Эта же
иллюстрация служит заодно вполне надежным доказательством
упомянутого правила.
В этом параграфе приводится геометрическая иллюстрация
(также являющаяся одновременно доказательством) другого известного комбинаторного закона – рекуррентного соотношения
для числа сочетаний из n элементов по k элементов( Cnk ):

Cnk = Cnk−1 + Cnk−−11 .

(7.1)

Рассмотрим прямоугольник размера m×k, составленный из
единичных квадратов (см. рис. 7.1). Нас будет интересовать число маршрутов из нижнего левого угла A в правый верхний угол B
(двигаться можно только вверх или вправо по сторонам единичных квадратов). Это число мы обозначим через N(m, k).
Заметим теперь, что попасть в точку B можно только одним
из двух способов: либо из точки C, либо из точки D,
cледовательно,
N(m,k) = N(m–1,k) + N(m,k–1)

(7.2)

____________
См. предыдущий параграф.

1

25

(справедливость этого соотношения геометрически очевидна; при
этом существенно то обстоятельство, что двигаться из точки A
можно только либо вверх, либо вправо).

Рис. 7.1

Покажем теперь, что геометрически очевидное соотношение (7.2) это и есть, в сущности, другая (причем более симметричная!) форма записи комбинаторного равенства (7.1).
Действительно, длина любого маршрута из A в B равна в точности m + k. Пронумеруем теперь шаги произвольно взятого
маршрута. Очевидно, что каждый маршрут полностью характеризуется номерами шагов, направленных вверх (этих шагов всего
должно быть k штук). Тем самым каждый маршрут однозначно
соответствует выбору k чисел из множества {1,2,…, m + k}.
Следовательно,
N ( m, k ) = Cmk + k ,
и мы можем переписать (2) в виде
Cmk + k = Cmk + k −1 + Cmk −+1k −1 .
Полагая здесь n = m + k, приходим к искомому равенству (7.1).
8. ×ÅÌÓ ÐÀÂÅÍ ÍÓËÜ-ÔÀÊÒÎÐÈÀË?
Объясняя студентам – будущим педагогам начальных классов – начала комбинаторики, неизбежно приходится вводить
функцию n! («эн-факториал»). С педагогической точки зрения
здесь имеется одно довольно узкое место.
26

Мы полагаем по определению, что
n! = n(n–1)(n–2)·…·2 ·1 при n ≥ 1,
(8.1)
а при n = 0 считаем опять же по определению, что
0! = 1.
(8.2)
Соотношение (8.1) обычно не вызывает никаких затруднений – здесь все ясно: мы имеем дело с произведением всех натуральных чисел от n до 1. Но откуда берется соотношение (8.2)?
Если не дать разумного, адекватного объяснения, четко указав то
место, где действительно используется соглашение (8.2), то весь
материал, связанный с биномиальными коэффициентами, будет
воспринят отчасти на веру.
И тут у преподавателя, знакомого, естественно, с Гаммафункцией Эйлера, появляется искушение объяснить происхождение формулы (8.2) следующим образом.
При n > 1, очевидно, имеем
n! = (n–1)! · n.
(8.3)
Мы хотим сохранить это же самое соотношение при n = 1.
Подставляя в (8.3) n = 1, получаем
1! = 0!·1,

(8.4)

откуда и следует (8.2).
Однако соотношение (8.4) нигде в курсе комбинаторики не
используется, и в результате остается непонятным, нельзя ли было положить 0! равным какому-нибудь другому числу, отличному
от 1.
Выход из положения здесь, на наш взгляд, такой. Соображения (8.3), (8.4) можно (но не обязательно) рассказывать студентам
в качестве дополнительного материала, но не стоит давать их непосредственно после формулы (8.2) для ее «оправдания».
Вместо этого, чтобы оправдать соглашение (8.2), на наш
взгляд, следует сказать, что для того чтобы формулы, которые
вскоре появятся, имели единообразный вид при всех n ≥ 0 (а не
только при n ≥ 1) нужно, чтобы выражение
n!
(8.5)
0! n !
равнялось 1. (Действительно, как известно, каждое выражение
27

n!
при 0 0).
Очевидно, что
Q < M + 1,
(26.8)
поэтому в силу предположения индукции натуральное число Q
может быть представлено в виде суммы степеней двойки именно
при помощи алгоритма, рассмотренного выше в п. 2. Однако это71

го еше недостаточно для наших целей. Необходимо показать, что
в двоичное разложение числа Q могут входить только степени
двойки с показателями строго меньшими, чем d. Прежде всего,
степени двойки с показателями >d в разложение для Q не могут
входить в силу (26.7) и (26.8).
Далее, покажем, что 2d также не может входить в упомянутое
разложение. Действительно, предположим противное, а именно,
что
Q = 2d + …,
т.е.
(M + 1) – 2d = 2d +…,
откуда
M + 1 = 2×2d + …,
что, очевидно, противоречит условию (26.7). Тем самым наше
утверждение доказано.
ÈÑÒÎÐÈ×ÅÑÊÎÅ ÍÅÄÎÐÀÇÓÌÅÍÈÅ

С двоичной системой связано одно интересное историческое
недоразумение. Дело в том, что древние египтяне не подозревали
о существовании позиционной системы счисления и, тем не менее, пользовались ею.
В непозиционной системе значение цифры не зависит от занимаемого ею места. Например, в римской системе X – это десять, а XX – двадцать.
В непозиционной системе легко складывать и вычитать, а умножать и делить, вообще говоря, трудно. И такая система является, конечно, тормозом для развития математики.
Так вот, в Древнем Египте в течение примерно трех тысячелетий существовала весьма архаичная непозиционная система
счисления [23]. Удивительно, однако, то, что древние египтяне
фактически пользовались двоичной позиционной системой, не
замечая этого!
Дело в том, что в Древнем Египте не была известна операция
умножения, а вместо нее использовалась операция удвоения. Например, если надо было умножить 17 на 19, то сначала 17 удваивали, затем получившийся результат опять удваивали, и так да72

лее. После чего из полученных последовательных удвоений «набирали» требуемый результат. Вот как это выглядело.
Таблица 26.1

Левый столбец
17
34
68
136
272

Правый
столбец
′1
′2
4
8
′16

Дополнительный
столбец
1
1
0
0
1

В правом столбце отмечали штрихом числа (степени двойки!)
которые в сумме дадут нужный множитель 19, а затем складывали соответствующие числа из левого столбца. Результат, очевидно, получался верный:
17×19 = 323 = 272 + 34+17 = 17×(16+2+1).
Заметим теперь, что штрихи и пустые места (т.е. отсутствие
штрихов) перед числами в правом столбце табл. 26.1 представляют
собой готовую позиционную двоичную запись числа 19 (расположенную, впрочем, по вертикали). Читать эту запись нужно снизу
вверх. В третьем, дополнительном столбце этой таблицы мы, для
удобства читателя, обозначили присутствие штрихов единицами, а
их отсутствие – нулями. Таким образом, в третьем столбце содержится готовая двоичная запись числа 19: 19 = 10011(2).
27. Î ÊÂÀÄÐÀÒÍÛÕ ÓÐÀÂÍÅÍÈßÕ Ñ ÏÀÐÀÌÅÒÐÀÌÈ
Коэффициенты всех встречающихся ниже квадратных уравнений предполагаются вещественными. (Материал этого параграфа был опубликован в [16].)
Рассмотрим вначале одну несложную, но довольно поучительную задачу.
Задача № 1. Даны два квадратных уравнения:
x2+ px + q = 0;
qx2+px + 1 = 0,

(27.1)
(27.2)
73

где q≠1. Требуется доказать, что если у этих двух уравнений есть
общий корень, то этот корень равен ±1.
Первое решение. Это решение основано на своеобразной
симметрии между уравнениями (27.1) и (27.2). Действительно, заменяя в (27.1) x на 1 x , замечаем, что уравнение (27.1) превратилось в (27.2). Поэтому, если x1 и x2 –корни уравнения (27.1), то тогда 1 x1 и 1 x2 – корни уравнения (27.2). Предположим, что у (27.1)
и (27.2) есть общий корень. Тогда априори возможны два случая.
1
а) Первый случай: x1 = .
x1
В этом случае, очевидно, x1 = ±1, что мы и хотели бы установить.
1
б) Второй случай: x1 = .
x2
Однако из последнего соотношения следует, что x1 x2 = 1, в то
время как из уравнения (27.1) вытекает, что должно быть x1 x2 = q.
Поскольку по условию задачи q≠1, получаем, что второй случай
на самом деле невозможен.
Тем самым требуемое утверждение доказано.
Второе решение. Предыдущее решение было основано на соображении очень специального вида, которым удается воспользоваться в очень ограниченном классе задач. Сейчас мы решим
нашу задачу, опираясь на следующий, значительно более общий
принцип: если у двух уравнений F(x) = 0, G(x) = 0 есть общий корень x0, то x0 является также корнем линейной комбинации этих
уравнений:
a(x)F(x) + b(x)G(x) = 0.
Применим это соображение к нашей задаче. Наша ближайшая
цель – построить возможно более просто решаемую комбинацию
уравнений (27.1) и (27.2). Для этого поступим следующим образом. Умножим (27.1) на q и вычтем из получившегося соотношения уравнение (27.2). В результате, очевидно, придем к уравнению первого порядка:
p(q – 1)x + q2– 1 = 0,
решение которого дается формулой
q +1
x=
.
(27.3)
p
74

Итак, если общее решение уравнений (27.1) и (27.2) существует, то оно дается формулой (27.3).
Этого, однако, для нас недостаточно. Попробуем теперь применить аналогичную процедуру к исходным уравнениям (27.1),
(27.2) и получить какое-то иное легко решаемое уравнение в качестве следствия. С этой целью умножим (27.2) на q и вычтем
получившееся соотношение из (27.1). В результате получим
уравнение второго порядка без свободного члена:
(q2 – 1)x2 + p(q – 1)x = 0,
откуда
x=−

p
q +1

(27.4)

(решение x = 0 нас не интересует, так как у исходной пары уравнений, очевидно, не может быть общего корня х = 0).
Таким образом, общее решение исходной пары уравнений
(27.1), (27.2) обязательно имеет вид (27.4). Однако при условии
q≠1 у исходной пары уравнений не может быть двух разных
общих корней (доказательство этого факта мы предоставляем читателю). Поэтому (27.3) и (27.4) – это два выражения для одного
и того же корня. Перемножая соотношения (27.3) и (27.4), снова
получаем требуемый результат.
Задача № 2 (см. [17]). Даны два квадратных уравнения:
x2 + px + q = 0;
px2 + qx + 1 = 0.

(27.5)
(27.6)

Требуется доказать, что если у этих уравнений есть общий
вещественный корень, то он равен единице.
Решение. Любопытно, что если мы попробуем буквально
скопировать второе решение задачи № 1 (то есть составить две
линейные комбинации уравнений (27.5), (27.6): одну, сводящуюся к уравнению 1-го порядка, а другую – к уравнению 2-го
порядка со свободным членом, равным нулю), то зайдем в тупик. Оказывается, чтобы решить эту задачу, нужно воспользоваться своеобразным сходством уравнений (27.5) и (27.6) и
только затем, с учетом этого сходства, строить соответствующую комбинацию этих уравнений.
75

Итак, умножим уравнение (27.5) на x, получим кубическое (!)
уравнение
x3 + px2 + qx = 0;
теперь становится ясно, о каком сходстве уравнений (27.5) и
(27.6) шла речь выше. Вычитая (27.6) из этого кубического уравнения, очевидно, получаем
x3 – 1 = 0,
откуда и следует требуемое утверждение.
Замечание. Нетрудно проверить, что у уравнения (27.5) имеется корень x = 1 в том и только том случае, когда
q = – (p + 1).
(27.7)
Поэтому полученный результат можно переформулировать
следующим образом:
Теорема. Уравнения (27.5) и (27.6) имеют общий вещественный корень тогда и только тогда, кода выполнено условие (27.7).
Этот общий вещественный корень обязательно равен единице.
Замечание. Нетрудно показать, что если левые части уравнений (27.5) и (27.6) не совпадают друг с другом тождественно, то
уравнения (27.5) и (27.6) не могут иметь общих не вещественных
корней.
Задача № 3. Даны два квадратных уравнения:
x2 + px + q = 0;
(27.8)
a2x2 + apx + q = 0,
(27.9)
где a≠1 и 0; q≠0. Требуется доказать, что если у этих двух уравнений есть общий корень, то
 q 1 2
12
p = −   + ( qa )  .
(27.10)
 a 

Решение. Прежде всего, заметим, что при замене x на x/a
уравнение (27.9) переходит в (27.8). Поэтому если x1 и x2 – корни
уравнения (27.9), то x1/a и x2/a – корни уравнения (27.8). Предположим, что у (27.8) и (27.9) есть общий корень. Тогда априори
возможны два случая.
а) Первый случай: x1 = x1/a. Однако в силу предположения о
том, что q≠0, имеем x1≠0. Поэтому рассматриваемый случай на
самом деле невозможен (ибо a≠1).
76

б) Второй случай:
x1 = x2/a.
(27.11)
Однако x1 x2 = q; подставляя сюда выражение для x1 из
предыдущего равенства, легко получаем:
12
x2 = ( aq ) .
(27.12)
Теперь из (27.11), (27.12) имеем:
12

q
x1 =   .
a

(27.13)

Из двух последних равенств и соотношения p = – (x1 + x2) следует требуемое утверждение.
28. ÏÐÎÔÅÑÑÎÐ ÌÎÐÈÀÐÒÈ ÍÀ ÎÒÄÛÕÅ
Протягивая Шерлоку Холмсу свою фотографию, сделанную
ранним утром на одном из красивейших островов Тихого океана,
Мориарти добавил:
– Что касается преступления, совершенного 13 июня 1913 года, то у меня имеется железное алиби. Достаточно взглянуть на
это фото…
– Это грубая фальшивка, профессор, – заметил Холмс. – Любой мало-мальски сообразительный ученик 5-го класса сразу же
вас разоблачит!

Что же так не понравилось Холмсу на предложенной ему фотографии?
77

29. ×ÀÑÒÎÊÎË ÈÇ ÅÄÈÍÈÖ
Оказывается, справедливо следующее
Утверждение. Любое натуральное число n можно умножить
на подходящим образом подобранный натуральный множитель
Q(n) и в качестве произведения получить 111…111000…000 (несколько единиц, за которыми может стоять некоторое количество нулей). Подчеркнем, что речь идет о записи числа nQ(n) в
десятичной системе.
На первый взгляд, это утверждение кажется очень трудным.
Попытка решить в целых числах уравнение
nQ(n) = 111…111000…000
(29.1)
методом подбора представляется вообще безнадежной.
Однако эта задача легко поддается решению, если воспользоваться аппаратом бесконечных периодических десятичных дробей. (Наше изложение до некоторой степени будет следовать
книге [13, с. 324]).
Пример 1.
Разберем в качестве примера случай n = 7.
Наш первый шаг – рассмотреть обыкновенную дробь

1 1
= и
n 7

затем представить ее в виде бесконечной периодической десятичной
дроби. Имеем (здесь удобно воспользоваться калькулятором!):
1
= 0,142857142857142857… = 0,(142857).
(29.2)
7
Умножим теперь равенство (29.2) на 10 в степени, равной
длине периода десятичной дроби из правой части этого равенства. Получим:
1
×106 = 142857,(142857).
(29.3)
7
Вычитая теперь (29.2) из (29.3), имеем:
1
×(106 – 1) = 142857,
7
откуда
1 142857
=
.
(29.4)
7 999999
78

Заметим теперь, что числитель дроби в правой части последнего равенства делится на 9 (это сразу следует из признака делимости на 9). Однако для нас важно (поскольку мы хотим на частном примере обсудить особенности общего случая) уметь доказывать этот факт, не обращаясь к признаку делимости на 9 (и, тем
более, не производя непосредственно деления). Заметим с этой
целью, что знаменатель дроби из левой части (29.4) не делится на 9
(а также на 3). Отсюда и вытекает возможность сокращения числителя и знаменателя дроби из правой части (29.4) на 9.
В результате имеем:
1 15873
=
,
7 111111
откуда
7×15873 = 111111,
что и требовалось получить.
Более интересен случай, когда число n, для которого мы ищем
подходящий множитель, само делится на 3 или на 9. В этом случае наш подход нужно слегка видоизменить.
Пример 2.
Пусть теперь n = 18. Имеем, действуя поначалу, как в преды1 1
дущем примере: = .
n 18
1
Представим
в виде периодической десятичной дроби
18
(опять на помощь может придти калькулятор):
1
= 0,0555555555555… = 0,0(5).
(29.5)
18
Проделаем теперь с равенством (29.5) не одну, а две манипуляции. Во-первых, умножим это равенство на 10 в степени, равной длине непериодической части десятичной дроби 0,0(5), то
есть на 10 в первой степени:
1
×10 = 0,(5).
(29.6)
18
А во-вторых, умножим (29.6) на 10 в степени, равной девятикратной длине периода десятичной дроби (29.5), т.е. на 109:
1
×10× 109= 555555555,(5).
(29.7)
18
79

Вычитая (29.6) из (29.7), получаем:
1
×10× (109 – 1) = 555555555,
18
откуда
10 555555555
=
.
18 999999999

(29.8)

Итак, мы почти у цели. Осталось только сократить на 9 числитель и знаменатель дроби в правой части (29.8). Однако числитель упомянутой дроби обязательно разделится на 9 в силу своего
построения – это «девятикратный» (записанный 9 раз подряд)
период десятичной дроби (29.5).
Поскольку 555555555 = 9×61728395,
окончательно имеем из (29.8):
18×61728395 = 1111111110,
что и требовалось установить.
Следствие 1. Для любого простого p, отличного от 2 и 5, найдется такое натуральное m = m(p), что число 111…1 (единица повторена m раз) делится на p.
Следствие 2. Пусть p – любое простое число, отличное от 3.
Тогда сумма цифр периода в десятичном разложении дроби 1/p
делится на 9.
Замечание. Дальнейшие результаты см. в [20].
30. Î ÏÅÐÈÎÄÀÕ ÄÅÑßÒÈ×ÍÛÕ ÄÐÎÁÅÉ
В этом параграфе мы разберем одну любопытную задачу о
периодах десятичных разложений обыкновенных дробей. При
этом мы будем опираться на известный результат о том, что если
знаменатель обыкновенной дроби c/d не содержит множителей
2 и 5, то в десятичном разложении этой дроби период начинается
сразу после запятой [13, 20].
Итак, мы собираемся доказать следующее
Утверждение (см. [20]). Пусть p – простое число. Тогда наименьший период десятичного разложения обыкновенной дроби
1/p является делителем натурального числа p – 1.
80

Приведем вначале несколько примеров, подтверждающих
наше утверждение:
1/7 = 0,(142857); длина периода равна 6 (7 – 1 = 6);
1/41 = 0,(02439); длина периода равна 5 (41 – 1 делится на 5);
1/53 = 0,(0188679245283); длина периода равна 13 (53 – 1 делится на 13).
Замечание. Не ограничивая общности, мы будем считать в
дальнейшем, что p > 5. Действительно, для дробей 1/2, 1/3 и 1/5
наше утверждение, очевидно, верно, так как длины соответствующих периодов равны 1:
1
= 0, 50000… = 0,5(0);
2
1
= 0,33333… = 0,(3);
3
1
= 0,20000… = 0,2(0).
5
Лемма (см. [20]). Пусть p – простое (p>5), q∈{1; 2;...; р – 1}.
Тогда наименьшие периоды десятичных разложений обыкновенных дробей q/p и 1/p совпадают.
Доказательство леммы. Действительно, обозначим через S
наименьший период десятичного разложения дроби q/p, а через
T – наименьший период десятичного разложения дроби 1/p. Тогда, очевидно, будем иметь по формуле для суммы геометрической прогрессии:
q
S
= 0,(S) = S×(10–m + 10–2m + 10–3m + …) = m
(30.1)
p
10 − 1
(здесь m – длина периода S); и, аналогично,
1
T
= 0,(T) = T×(10–n + 10–2n + 10–3n + …) = n ,
(30.2)
p
10 − 1
(где n – длина периода T).
Далее, так как q и p взаимно просты, то, как известно, должны
существовать такие целые A и B, что
Ap + Bq = 1.

(30.3)

Имеем теперь из (30.2) и (30.3):
81

1 Ap + Bq
Bq
=
= A+
.
p
p
p

(30.4)

Таким образом, дробь Bq/p имеет наименьший период той
же длины n, что и дробь 1/p. Имеем теперь в силу (30.1)
Bq
BS
= m
,
p 10 − 1
откуда, выделяя целую часть дроби и пользуясь равенством
1
10 − 1
m

= 10–m + 10–2m + 10–3m + …,

легко получаем, что m является одним из периодов дроби Bq/p.
Следовательно, n является делителем m.
Теперь осталось доказать, что, наоборот, m является делителем n. Для этого умножим (30.2) на q. Рассуждая аналогично предыдущему, легко получаем, что n – один из периодов десятичного разложения дроби q/p. Поскольку в силу (30.1) m – наименьший период разложения этой дроби, приходим к выводу, что m –
делитель n. Отсюда и вытекает требуемое равенство m = n.
Доказательство утверждения. В отличие от [20] наше доказательство не будет опираться на малую теорему Ферма. Пусть
p – произвольное простое число, большее 5. Тогда каждая обыкновенная дробь вида q/p, где 1 ≤ q < p, будет представима в виде
бесконечной периодической десятичной дроби с ненулевым периодом. (В процедуре деления уголком, переводящей такую
дробь в десятичную запись, могут возникать только ненулевые
остатки от деления на p.) Всего существует p – 1 ненулевых остатков, которые могут в принципе возникать при делении на p, а
именно:
{1; 2;…; p – 1}.

(30.5)

Однако при переводе конкретной дроби q/p в десятичную запись в общем случае могут участвовать не все остатки (30.5), а
только некоторые. При этом длина периода десятичного представления конкретной дроби q/p, очевидно, в точности равна количеству m остатков, участвующих в процедуре деления уголком.
Если r – ненулевой остаток от деления на p, не участвующий в
82

процедуре перевода дроби q/p в десятичную запись, то рассмотрим дробь r/p. В силу доказанной леммы длина периода десятичной записи дроби r/p также будет равна m; тем самым будет равно m и количество ненулевых остатков от деления на p, участвующих в переводе r/p в десятичную запись. Однако множества
остатков, участвующих в переводе в десятичные записи дробей
q/p и r/p, очевидно, не могут пересекаться. Итак, у нас уже имеется 2m ненулевых остатков, которые участвуют в переводах в десятичную запись дробей со знаменателем p. Если не все возможные остатки (30.5) при этом исчерпаны, продолжим процесс. В
результате, очевидно, получим, что p – 1 кратно m. Тем самым
наше утверждение доказано.
Замечание 1. Пусть по-прежнему p – простое число, большее пяти, и пусть q∈{1; 2;...; р – 1}. Тогда если
1/p = 0,(T),
(30.6)
то
q/p = 0,(qT).
(30.7)
Действительно, из (30.6) имеем:
1
T
T
T
= n + 2 n + 3n + ...,
p 10 10
10
где n – длина периода T. Следовательно,
q qT
qT
qT
= n + 2 n + 3n + ...
p 10 10
10
Однако число qT не может быть более, чем n-значным, поскольку q/p < 1. Следовательно, qT и есть период длины n десятичного разложения дроби q/p.
С дальнейшими интересными результатами читатель может
познакомиться по работе [20].
Замечание 2. Пусть, как и выше, p – простое число, большее
пяти. Если длина периода T в десятичном разложении (30.6) в
точности равна p – 1, то такое разложение мы будем называть
полнопериодным. Как мы видели выше, полнопериодным является разложение дроби 1/7. Известны и другие полнопериодные
разложения, например, для p = 17 и для p =29 (см. в этой связи
[21], где приведены также интересные фокусы, основанные на
полнопериодных разложениях).
83

Как отмечено в [21], если T является полным периодом десятичного разложения дроби вида 1/p, то для каждого q∈{1; 2;...; р – 1}
имеет место равенство:
qT = Ti,
(30.8)
где Ti – некоторая циклическая перестановка цифр, образующих
период T. Таким образом, в рассматриваемом полнопериодном
случае
q
= 0,( qT ) = 0,(Ti ).
(30.9)
p
(Чтобы убедиться в справедливости (30.8), достаточно разобрать пример с p= 7, вычисляя десятичное разложение дроби 1/7
при помощи деления уголком.) В частности, отсюда следует, что
1−

q p−q
=
= 0, ( ( p − qT ) ) = 0,(T j ),
p
p

(30.10)

где Tj – еще одна циклическая перестановка цифр периода T.
Учитывая, что
1 = 0,9999999…,
имеем из (30.9) и (30.10):
0,9999999… – 0,(Ti) = 0,(Tj),
откуда, очевидно, следует равенство
999…9 – Ti = Tj .

(30.11)

(В (30.11) количество девяток в записи 999…9 равно длине
периода T.) Например, для p = 7 имеем:
999999 –142857 = 857142;
999999 – 428571 = 571428;
999999 – 285714 = 714285;
999999 –857142 = 142857;
(30.12)
999999 – 571428 = 428571;
999999 – 714285 = 285714.
Аналогично,
полный
период
0588235294117647, и мы имеем:

дроби

1/17

равен

9999999999999999–0588235294117647=9411764705882352. (30.13)
84

Еще один пример. Полный период дроби 1/29 равен
0344827586206896551724137931, откуда имеем:
9999999999999999999999999999 – 0344827586206896551724137931=
= 9655172413793103448275862068.
(30.14)
Задача. Верно ли, что для полных периодов вычисление разностей вида (30.12)–(30.14) всегда сводится к перестановке двух
полупериодов?
31. ÇÀÃÀÄÊÀ ÌÎÐÈÀÐÒÈ
– Вот вы и попались, профессор, – сказал Холмс, защелкивая
наручники на запястьях своего заклятого врага, – мой дедуктивный метод, как всегда, не подвел меня!
– Глупости, – отозвался Мориарти, – я попался случайно!
А ваш хваленый метод не стоит и ломаного гроша.
– И вы можете мне это доказать? – осведомился Холмс, сохраняя присущую ему невозмутимость невзирая на нанесенное
ему оскорбление.
– Да, но при одном условии: если ваш так называемый дедуктивный метод окажется бесполезен при ответе на один совершенно элементарный, можно сказать, детский вопрос – вы отпустите меня!
– Слово джентльмена!
– Итак, – начал Мориарти, – согласны ли вы, дражайший
Холмс, с таким утверждением: если мы расположим все четные
и нечетные числа в их естественном порядке, то между любыми
двумя различными четными числами всегда найдется, по крайней
мере, одно нечетное?
– Конечно, – ответил Холмс, раскуривая сигару. Прославленный сыщик заметил, как при его ответе нехорошо блеснули глаза
его собеседника, но не придал этому зловещему обстоятельству
должного значения.
– Тогда, – продолжал Мориарти, – согласитесь ли вы, любезнейший Холмс, еще с одним утверждением: если мы, как и раньше, расположим все четные и нечетные числа в общепринятом
порядке, то между любыми двумя нечетными числами обязательно найдется хотя бы одно четное число?
85

– Естественно, – сказал Холмс, пуская кольцо дыма по направлению к камину и приготовившись услышать кое-что поинтереснее.– И что же дальше?
– А дальше, дорогой Холмс, вам придется меня отпустить, –
ехидно заметил Мориарти и объяснил в двух словах ошеломленному сыщику его ошибку.

Рис. 31.1

А что же все-таки сказал проф. Мориарти Холмсу?

32. ÄÈÕÎÒÎÌÈß Â ËÎÃÈ×ÅÑÊÈÕ ÇÀÄÀ×ÀÕ
Рассмотрим вначале такую хорошо известную задачу.
Задача первая. Нам загадали число х, меньшее 88. Мы можем задавать вопросы, на которые нам будут отвечать только
«да» или «нет». За какое наименьшее число вопросов мы сможем
наверняка узнать загаданное число?
Решение № 1. Алгоритм угадывания более-менее понятен.
Сначала нужно спросить:
– Верно ли, что х > 44?
Если неверно, то спросить:
– Верно ли, что х > 22?
86

И так далее. Этот процесс называется в математике «дихотомия» – разделение пополам. За семь вопросов мы наверняка узнаем загаданное число. (Когда в процессе такого разделения пополам нам будут встречаться нечетные числа, мы будем прибавлять
к ним единицу и делить пополам получившееся четное число.)
Замечание. Можно доказать, что, задав меньшее число вопросов, нашу задачу, вообще говоря, решить нельзя. Попробуем
объяснить это «на пальцах». Действительно, если, например, делить числовой интервал, в котором ведутся поиски числа х, не на
две, а на три приблизительно равные части, то за два вопроса мы
сумеем уменьшить интервал наших поисков в три раза (примерно). А при дихотомическом процессе за два вопроса интервал поисков уменьшается в четыре раза (опять же, примерно).
Итак, кажется интуитивно ясным, что предложенный метод
неулучшаем.
Заметим, однако, что, действуя описанным выше образом, мы
не узнаем загаданного числа, пока не зададим все семь вопросов...
Решение № 2. Но можно действовать иначе. Попросим загадывающего переписать число х в двоичной системе (двузначное
десятичное число при переводе в двоичную систему будет записываться не более чем семью знаками); затем последовательно за
семь вопросов мы сможем узнать все двоичные цифры загаданного числа.
Надо сказать, что, задавая вопросы типа: «является ли такаято по счету двоичная цифра числа х нулем?», мы тоже устраиваем
дихотомию, но организуем ее по другому принципу, чем в предыдущем решении.
Замечание. Выигрыш от применения двоичной записи заключается в следующем. Примерно в одной трети случаев мы
сможем определить загаданное число, задав не 7, а только 6 вопросов! Для этого нужно узнавать цифры двоичной записи числа
х, двигаясь в направлении от младших разрядов к старшим. Действительно, если из ответа на шестой вопрос будет следовать, что
коэффициент при 25 равен 1, то седьмой вопрос не нужен, так как
коэффициент при 26 автоматически оказывается равным нулю
(поскольку 25 + 26 = 96 > 88).
87

Замечание. Преимущество подхода, основанного на применении двоичной записи, сохраняется и в случае, кода мы пытаемся угадать натуральное число х из какого-либо интервала вида
х1 < х < х2 (где х1 и х2 – тоже натуральные числа). В этом случае
нужно задавать вопросы про цифры двоичной записи разности
х – х 1.
Рассмотрим теперь еще одну задачу, принадлежащую на этот
раз к известной серии задач о лжецах и правдолюбах. Нас будет
интересовать в данном случае возможность применения дихотомической процедуры в не вполне стандартных условиях.
Задача вторая (см. также учебник В.В. Афанасьева [24,
с. 188], где приведена похожая задача, решенная автором учебника за три вопроса).
Некий путешественник оказался в одном из двух городов,
А или В, жители которых постоянно ездят друг к другу в гости.
При этом коренные жители города А всегда говорят правду, а
коренные жители города В через день на все вопросы отвечают
правдиво, а через день – лгут. Может ли путешественник, задав
всего два вопроса (предусматривающие ответы «да» или «нет»),
определить, в каком городе он сам находится и с жителем какого города он разговаривает?
Решение. Будем обозначать жителя города А через а, а жителя города В через b. Таким образом, наш путешественник должен
каким-то образом узнать, какая из четырех априори возможных
ситуаций имеет место: Aa, Ab, Ba, Bb. Очевидно (и именно это
утверждает теория информации), что лучшее, что может предпринять путешественник, – это устроить дихотомическую процедуру. Тогда за два вопроса он сумеет определить и город, и типаж
собеседника. Но существует ли в условиях задачи такая дихотомическая процедура? Оказывается, что да, существует. Вот два
вопроса, ответы на которые позволят путешественнику определить все, что ему требуется:
«Вчера ты ответил бы “да” на вопрос: “Ты житель этого города?”?»
(32.1)
«Вчера ты ответил бы “да” на вопрос: “2×2 = 4?”?»
88

(32.2)

Рис. 32.1

Замечание. Любопытно, что логическая операция «высказывание о высказывании», на использовании которой основано множество занимательных логических задач (и которой мы только что
воспользовались), не входит в основной список логических операций, изучаемых в курсе логики.
Замечание. Введем обозначения:
Q(x) = «Вчера ты ответил бы “да” на вопрос x?»
P = «Ты – житель этого города?»
R = «Дважды два равно четырем?»
Тогда вопросы (32.1) и (32.2) из решения предыдущей задачи,
очевидно, перепишутся в виде:
Q(P); Q(R).
Вопрос о том, реализуема ли дихотомическая процедура в
любых задачах о лжецах и правдолюбах, нетривиален и требует
более четкой постановки, ограничивающей круг этих задач. Рассмотрим в качестве примера еще одну задачу.
Задача третья (см. также [24, с. 190 и с. 314]). Некий путешественник оказался в одном из двух городов, А или В, жители
которых постоянно ездят друг к другу в гости. При этом коренные жители города А два дня подряд говорят правду, а на третий день лгут; что касается коренных жителей города В, то
они через день отвечают на вопросы правдиво, а через день –
лгут. Может ли путешественник, задав всего два вопроса (предусматривающие ответы «да» или «нет»), определить, в каком
89

городе он сам находится и с жителем какого города он разговаривает?
Решение. Путешественнику достаточно задать всего два вопроса, чтобы определить город, в котором он находится, и типаж
собеседника. Вот эти вопросы:
Q(Q(Q(Q(Q(P)))));
Q(Q(Q(Q(Q(R))))).
Задача четвертая (аналогичная задача имеется в [24]). Допустим, что нам загадали целое число х, принадлежащее числовому отрезку от 0 до 127. Требуется отгадать это число, задав
возможно меньшее число вопросов (предусматривающих ответы
«да/нет»), при дополнительном условии, что отвечающий может
один-единственный раз солгать.
Решение. Прежде всего, заметим, что число х может быть однозначно представлено в виде
x = a0 + a12 + a222 + … + a626,
(32.3)
где коэффициенты ai могут быть равны 0 или 1. Итак, задав семь
вопросов (о семи коэффициентах ai) мы могли бы окончательно
узнать загаданное нам число, если бы мы были уверены, что отвечающий ни разу не солгал. Заметим теперь, что, каков бы ни
был предъявленный нам (возможно, содержащий ошибку) набор
из семи коэффициентов (a0,a1,a2, …,a6), перед нами раскрываются
восемь возможностей:
(1) ошибка в коэффициенте a0;
(2) ошибка в коэффициенте a1;
….
(7) ошибка в коэффициенте a6;
(8) все коэффициенты a0,a1,a2, …,a6 – верные.
При этом мы все еще не знаем, осталась ли у отвечающего
возможность солгать или он ее уже израсходовал. Поэтому дважды задаем вопрос:
«Правда ли, что все коэффициенты a0,a1,a2, …,a6 – верные?» (32.4)
Если мы получим на этот (дважды заданный) вопрос хотя бы
один ответ «да», то, очевидно, что имеет место ситуация (8), и мы
определили загаданное число за 7 + 2 = 9 вопросов.
90

Если же дважды прозвучит ответ «нет», то имеет место один из
случаев (1) – (7). Применяя дихотомическую процедуру, за три
дополнительных вопроса определяем все семь коэффициентов в
двоичном разложении (32.3). Таким образом, в этом случае нам
потребуется 7 + 2 + 3 = 12 вопросов. Итак, для решения поставленной задачи в любом случае достаточно двенадцати вопросов.
Попробуем, однако, обойтись меньшим числом вопросов. Для
этого заменим двукратный вопрос (32.4) на следующий однократно задаваемый вопрос:
«Так же ли верно, что ты ни разу не лгал, отвечая на вопросы о
коэффициентах a0,a1,a2, …,a6, как то, что ты сейчас не солжешь?»
(32.5)
Возможны следующие три ситуации:
а) Отвечающий раньше не лгал и сейчас не лжет. Его ответ в
этом случае: «да».
б) Отвечающий раньше лгал, а сейчас говорит правду. Его ответ в этом случае: «нет».
в) Отвечающий раньше не лгал, а сейчас лжет. Его ответ в
этом случае: «да».
Итак, по ответу на однократно заданный вопрос (32.5) мы
сразу же узнаем, лгал или нет отвечающий в ответ на один из
предыдущих семи вопросов.
В итоге нам для определения загаданного числа будет достаточно 7 +1+3 = 11 вопросов. По-видимому, этот результат улучшить уже нельзя.
Замечание. Как мы уже отмечали выше, дихотомическая
процедура(если она возможна) является наилучшим способом
поиска недостающей информации при ответах «да/нет». Однако в
некоторых задачах (похожих на вышеприведенные) дихотомическая процедура не является оптимальной. В частности, так обстоит дело в задаче о поиске фальшивой монеты среди настоящих
при помощи взвешивания на чашечных весах. Дело в том, что
процедура взвешивания дает нам не два варианта возможных ответов (как при ответах «да/нет»), а три: а) весы уравновешены;
б) перевешивает левая чашка весов; в) перевешивает правая чашка весов. В соответствии с этим оптимальная стратегия поиска
фальшивой монеты (которая, допустим, легче настоящих), состо91

ит в разделении всей исследуемой совокупности монет не на две,
а на три части. Дальнейшие подробности см. в [24].
Задача пятая. а) Известно, что среди четырех монет одинакового достоинства – одна фальшивая, отличающаяся от настоящих по весу. Заранее неизвестно, однако, фальшивая монета тяжелее или легче настоящих. Требуется изобрести весы, на которых за одно (!) взвешивание можно определить фальшивую монету.
б) Та же задача, когда всех монет N штук.
Решение. а) Нужно воспользоваться «трехчашечными» весами, изображенными на рис. 32.2. (Углы между соседними плечами трехчашечных весов равны 120°.)

Рис. 32.2. «Трехчашечные» весы

б) Здесь все зависит от четности общего числа монет. При
N = 2k + 1 нужны N-чашечные весы, на которые укладываются
все монеты (по одной на каждую чашку). При N = 2k нужны
(N – 1)-чашечные весы, на которые нужно уложить N – 1 монету.)
Замечание. С дальнейшими интересными результатами можно познакомиться в [28]–[30].
33. ÎÁÅÇÜßÍÀ, ÍÅÁÎÑÊÐÅÁ È ÎÐÅÕÈ
В этом параграфе мы рассмотрим одну любопытную задачу, в
которой дихотомическая процедура оказывается не только не оптимальной, но вообще непригодной для поиска недостающей информации. Задача эта, принадлежащая математическому фольк92

лору, в несколько иной формулировке рассматривалась в [28].
В отличие от [28], мы приведем здесь ее полное решение. Итак,
вот классическая формулировка:
Задача № 1. Обезьяне, живущей в 100-этажном небоскребе,
дают два кокосовых ореха. Цель обезьяны – определить, начиная
с какого этажа брошенные вниз орехи будут раскалываться.
(Если орех не раскололся, обезьяна может за ним спуститься и
использовать орех снова. Расколовшийся орех использовать вторично нельзя.) Каково наименьшее число попыток, за которое
обезьяна может наверняка определить номер искомого этажа?
Нам, однако, будет удобнее рассматривать эту задачу в измененной постановке:
Задача № 2. Обезьяне, живущей в небоскребе, дают два кокосовых ореха. Каким может быть наибольшее количество
этажей в небоскребе, если известно, что обезьяна, используя
подходящую стратегию, может за 14 попыток наверняка определить этаж, начиная с которого орехи раскалываются?
Нам будет удобно ввести следующее
Определение. Если за заранее заданное число попыток обезьяна может, используя некоторую подходящую стратегию, наверняка определить в данном небоскребе этаж, начиная с которого
раскалываются орехи, то мы будем говорить, что такой небоскреб
допускает абсолютно надежное обследование.
Решение задачи № 2.
1) Прежде всего, заметим, что при правильной стратегии
обезьяна не должна бросать первый орех ни с какого этажа, расположенного выше четырнадцатого. Действительно, если (первый) орех, брошенный вниз, например, с 17-го этажа, расколется,
то за оставшиеся 14 – 1 = 13 попыток с помощью одного оставшегося ореха определить искомый этаж, вообще говоря, нельзя.
2) Заметим теперь, что в случае, когда раскалывается (первый)
орех, брошенный с 14-го этажа, обезьяна может с помощью второго ореха определить искомый этаж за оставшиеся 14 – 1 = 13 попыток. Действительно, обезьяне достаточно начать сбрасывать
орех поочередно с 1-го этажа, со 2-го, и т.д.
93

3) Так как нас интересует максимальная высота («этажность»)
небоскреба, в котором можно за 14 попыток наверняка определить номер искомого этажа, то первый орех обезьяне следует
сбрасывать именно с 14 этажа. Действительно, если сброшенный,
например, с 9-го этажа, (первый) орех не раскалывается, обезьяне
придется в дальнейшем обследовать на 14 – 9 = 5 этажей больше,
чем в случае, когда первый орех был сброшен с 14 этажа.
4) Дальнейшие рассуждения фактически повторяют рассуждения из предыдущих пунктов. Если первый орех, сброшенный с
14-го этажа, не раскололся, то истрачена одна попытка, и теперь
бросать первый орех следует 27-го этажа (27 = 14 +13). Если первый орех, сброшенный с 27-го этажа, не раскололся, то истрачено
две попытки, и в следующий раз этот орех следует бросать с 39го этажа (39 = 14+13+12). И так далее. В результате максимальная высота небоскреба, доступного для абсолютно надежного
обследования за 14 попыток, составляет
14+ 13+12+… +1 = 14×15/2 = 105 этажей.
Замечание 1. Точно так же, максимальная высота небоскреба,
доступного для абсолютно надежного обследования за 13 попыток, составляет
13+12+…+1 = 13×14/2 = 91 этаж.
Тем самым, мы получаем ответ на задачу № 1: наименьшее
число попыток, за которое обезьяна сможет наверняка определить номер искомого этажа в 100-этажном небоскребе, равно 14.
Замечание 2. Вернемся теперь к задаче № 2 и постараемся
обобщить полученные результаты. Обозначим через n число попыток, которые разрешено сделать обезьяне, а через N – соответствующее максимальное количество этажей в небоскребе, доступном для абсолютно надежного обследования. Тогда из предыдущего, очевидно, следует, что величины n и N связаны соотношением:
n( n + 1)
N=
,
(33.1)
2
откуда
n2 + n – 2N = 0.
(33.2)
94

Следовательно,
n=

−1 + (1 + 8 N )1 2
2

(33.3)

(мы по очевидным соображениям выбрали положительный корень квадратного уравнения (33.2)). Если теперь нам, как в задаче
№ 1, задано число этажей N в небоскребе и требуется определить
наименьшее число попыток n, за которое обезьяна сможет наверняка найти искомый этаж, то:
а) в случае, когда выражение справа в (33.3) не является целым числом, вместо (33.3) следует, очевидно, воспользоваться
соотношением:
 −1 + (1 + 8 N )1 2 
n=
(33.4)
 + 1,
2


где квадратные скобки обозначают целую часть числа;
б) если же выражение справа в (33.3) – целое число, то искомый ответ дает непосредственно формула (33.3).
Задача № 3 (в более общей постановке эта задача приведена в
[28]). Обезьяне, живущей в небоскребе, дают три кокосовых ореха. Каким может быть наибольшее количество этажей в небоскребе, если известно, что обезьяна, используя подходящую
стратегию, может за 15 попыток наверняка определить этаж,
начиная с которого орехи раскалываются?
Решение. Наши рассуждения будут аналогичны рассуждениям, проведенным при решении задачи № 2. Очевидно, что бросать (первый) орех ни с какого этажа, расположенного выше
106-го, нельзя. Действительно, если бросить первый орех, например, со 125-го этажа и этот орех разобьется, то останется 14 попыток, два ореха и 124 этажа, которые, как мы уже знаем из
решения предыдущей задачи, абсолютно надежно обследовать,
вообще говоря, не удастся. Повторяя рассуждение из пунктов
2) и 3) решения предыдущей задачи, получаем, что при оптимальной стратегии бросать первый орех следует именно со 106-го
этажа. Если этот орех разбился, то дальнейшие действия очевидны (см. решение задачи № 2). Если же первый орех не разбился,
то у нас остается 14 попыток. Следовательно, во второй раз пер95

вый орех нужно бросать с этажа, номер которого вычисляется по
формуле (см. замечание 1):
(105+1) + (91+1) = 106 + 92 = 198.
И так далее. В результате, максимальное количество этажей
небоскреба, доступного для абсолютно надежного обследования,
оказывается равным
 14 × 15   13 × 14 
 1× 2 
+ 1 + 
+ 1 + ... + 
+ 1 .
(33.5)

 2
  2

 2

Замечание 3. В общем случае снова обозначим через n число
попыток, которые разрешено сделать обезьяне (располагающей
теперь тремя орехами), а через M – соответствующую максимальную этажность небоскреба, в котором обезьяна может наверняка
определить искомый этаж. Тогда по аналогии с (33.5) имеем:
 ( n − 1)n   ( n − 2)( n − 1) 
1 × 2 
M =
+ 1 + 
+ 1 + ... + 
+ 1 + 1 =
2
 2
 

 2

(33.6)
2
1
n( n + 5)
= [1 × 2 + 2 × 3 + ... + ( n − 1)n ] + n =
.
2
6
(Соотношение (33.6) нетрудно доказать по индукции.) В частности, из этой формулы следует, что при n = 15 величина M
(т.е. сумма (33.5)) равна 575.

Рис. 33.1

96

Замечание 4. Из (33.6) следует также, что:
M =469
M = 377
M = 298
M = 231
M = 175
M = 129
M = 92
M = 63
M = 41
M = 25
M = 21
M=7
M=3
M=1

при n = 14;
при n = 13;
при n = 12;
при n =11;
при n =10;
при n = 9;
при n = 8;
при n = 7;
при n = 6;
при n = 5;
при n = 4;
при n = 3;
при n = 2;
при n = 1.

34. ÌÀÃÈ×ÅÑÊÈÉ ÊÂÀÄÐÀÒ È ÑÒÐÀÒÅÃÈß ØÅÍß
В этом параграфе мы рассмотрим одну красивую идею, связывающую магический квадрат с игрой в крестики-нолики. Идея
эта, по-видимому, принадлежит А. Шеню [29, с. 19–20].
Напомним, прежде всего, что магическим квадратом n-го порядка называется квадратная таблица размера n×n, заполненная
числами 1, 2, … n2, причем так, что сумма этих чисел вдоль каждой
строки, каждого столбца и каждой из двух диагоналей одна и та же.
Рассмотрим магический квадрат третьего порядка (см. рис. 34.1).

Рис. 34.1

97

Можно показать, что все остальные магические квадраты
размера 3×3, заполненные девятью различными ненулевыми
цифрами, получаются из квадрата, изображенного на рис. 34.1,
при помощи отражений относительно горизонтальной и/или вертикальной средней линии, а также относительно диагоналей этого квадрата. (Заметим, что суперпозиция отражения относительно
какой-либо средней линии квадрата и отражения относительно
диагонали квадрата представляет собой поворот на 90 градусов с
центром в центре квадрата.)
А. Шень в [29] предложил следующую игру:
На столе выложены карточки с номерами от 1 до 9. Двое играющих по очереди берут карточки; выигрывает тот, кто первым соберет три карточки с общей суммой 15.
Как заметил А. Шень, если расположить эти карточки в виде
магического квадрата (см. рис. 34.1), предложенная им игра сведется к обычной игре в крестики-нолики! Дело здесь в том, что
существует в точности восемь различных комбинаций из трех
ненулевых цифр, которые в сумме дают 15, и все эти комбинации
представлены на рис. 34.1. (Общеизвестно, что при правильной
игре в крестики-нолики на квадрате 3×3 неизбежна ничья.)
Ниже предлагается следующая модификация игры Шеня.
На столе выложены десять карточек с написанными на них
номерами: 1, 2, 3, 3, 4, 5, 6, 7, 9 (номер «три» встречается дважды). Двое играющих по очереди берут карточки; выигрывает
тот, кто сможет составить из каких-либо трех своих карточек набор с общей суммой 15 за меньшее число ходов.
Таблица 34.1

Пример.
Ходы 1-го игрока
Ходы 2-го игрока

5
3

8
2

4
6

7
3

9
1

Как видно из табл. 34.1, результат проведенной игры – ничья
(ни один из игроков не может из своих пяти карточек выбрать
три с общей суммой 15).
Задача. Проводится модифицированная игра Шеня. Каким
будет ее итог, если оба игрока действуют оптимально?

98

35. ÏÅÐÅÏÐÀÂÛ È ÑÈÌÌÅÒÐÈß
Задачи о переправах имеют давнюю историю. Наиболее знаменитая из этой серии задач – это задача о том, как крестьянину
переправить с одного берега реки на другой волка, козу и капусту. (Волка без присмотра нельзя оставлять с козой, а козу – с капустой; в лодку крестьянин может взять с собой либо волка, либо
козу, либо капусту.)
Решение этой задачи представляет собой простой, но все же
нетривиальный алгоритм, который мы здесь не приводим ввиду
его общеизвестности.
В последние годы появились новые задачи о переправах, требующие намного большей изобретательности. Одну из таких задач мы здесь разберем; она интересна тем, что для ее решения
удается привлечь соображения, связанные с симметрией (что,
вообще говоря, не характерно для задач о переправах).
Задача эта реализована в виде головоломки on-line:
http://online-igra.com.ua/IQ-challenge-animal-cross_YHjFE4i
http://www.willinggames.com/kids-games/kids-595.html
Здесь мы приведем усиленную (по сравнению с упомянутой
выше головоломкой on-line) формулировку рассматриваемой
задачи.
Задача. На другой берег реки хотят переправиться шесть
пар зверей: Мамонт с мамонтенком, Лев с львенком и Тигр с
тигренком. Лодка вмещает только двоих, грести умеют Лев,
Тигр и, кроме того, мамонтенок. Ни одного маленького звереныша нельзя оставлять без его собственного родителя в компании
взрослого зверя другой породы. Как организовать переправу?
Решение. Будем обозначать зверей соответствующими начальными буквами, заглавными для взрослых зверей и строчными для зверят.
Тогда начальное положение, описанное в условии задачи
можно условно изобразить так:
Левый берег
Правый берег
1) М, м; Л, л; Т, т; |||
Нетрудно заметить, что вначале нужно переправить на другой
берег львенка или тигренка (безразлично, кого – львенок и тигре99

нок входят в условие задачи симметрично). Итак, пусть, для определенности, мамонтенок везет львенка:
2) М; Л; Т, т
||| м; л;
После чего мамонтенок, естественно, возвращается (надо же
вернуть лодку для перевозки остальных зверей!):
3) М, м; Л; Т, т
||| л
Следующие две переправы также очевидны – мамонтенок
должен перевезти тигренка и затем вернуться обратно:
4) М; Л ; Т
||| м; л; т;
5) М, м; Л; Т;
||| л; т
Далее, единственный естественным образом напрашивающийся шаг – это переезд Льва и Тигра к своим детенышам:
6) М, м
||| Л, л; Т, т ;
Теперь, наконец, задача становится трудной. Единственная
возможность как-то изменить ситуацию, не допуская повторения
ходов – это перевести Льва и львенка (или Тигра с тигренком)
обратно, но при этом мы как будто не приближаемся к цели, а
удаляемся от нее! Итак,
7) М, м; Л, л;
||| Т, т
Что же делать дальше? Снова единственная возможность избежать повторения ходов – это перевести Мамонта с мамонтенком на правый берег. Но не тупик ли это? Ситуация
-7) Л, л
||| М, м; Т, т;
на первый взгляд не внушает оптимизма – рещение, вроде бы, не
просматривается… (И это легко объяснить – до окончательного
решения задачи еще шесть ходов.) И тут на помощь приходит
математика!
Действительно, Лев с львенком и Тигр с тигренком входят в
нашу задачу равноправно. Поэтому расположения 7) и -7) можно
считать симметричными относительно реки. Но это значит, что,
повторяя (в обратном порядке) предыдущие ходы с заменой Л, л
на Т, т, мы придем к расположению зверей, симметричному по
отношению к расположению 1) относительно реки, т.е. решим
задачу.
Действительно, вот эти ходы:
-6) Л, л; Т, т;
||| М, м
-5) л; т
||| М, м; Л; Т;
100

-4) м; л; т;
-3) л
-2) м; л;
-1)
Задача решена.

||| М; Л; Т
||| М, м; Л; Т, т;
||| М; Л; Т, т
||| М, м; Л, л; Т, т;

Замечание. Начиная с хода -3) можно было бы заканчивать
переправу зверей по-другому. За львенком мог бы поехать не мамонтенок, а Лев.
36. «ÄÈÀÃÎÍÀËÜÍÀß» ÈÍÄÓÊÖÈß
Этот параграф посвящен доказательству следующей теоремы.
Теорема. При каждом натуральном n справедливо утверждение:
2 n −1
n n +1 + ( n + 1)
делится нацело на ( n 2 + n + 1)
(36.1)
Замечание. Трудно сказать, может ли утверждение (36.1) быть
доказано по индукции «лобовым» способом. Однако (36.1) очень
просто выводится в качестве побочного результата из несложной
задачи на делимость полиномов.
Лемма. Пусть a – вещественный параметр. Тогда справедливы соотношения:
a n +1 + ( a + 1) 2 n −1 = ( a 2 + a + 1) Pm ( n ) ( a ),
(36.2)
( a + 1) n +1 + ( −1)n a 2 n −1 = ( a 2 + a + 1)Qm ( n ) ( a ),

(36.3)

(в (36.2) и (36.3) n = 1, 2, 3, …);
a n ( a + 1)n +3 + ( −1) n = ( a 2 + a + 1) R2 n +1 ( a ),

(36.4)

a n +3 ( a + 1) n + ( −1) n +1 = ( a 2 + a + 1) S2 n +1 ( a ),

(36.5)

( a + 1)n + ( −1) n +1 a 2 n +3 = ( a 2 + a + 1)T2 n +1 ( a ),

(36.6)

a n + ( a + 1) 2 n + 3 = ( a 2 + a + 1)U 2 n +1 ( a )

(36.7)

(в (36.4)–(36.7) n = 0, 1, 2, 3, …).
Здесь P, Q, R, S, T, U – целочисленные полиномы по a (т.е.
полиномы с целочисленными коэффициентами), степени которых
указаны в нижнем индексе; при этом m(n) = max{n–1, 2n–3}.
101

Доказательство леммы. Сосредоточимся вначале на доказательстве утверждения (36.2) леммы. Будем рассуждать по индукции. При n =1 утверждение (36.2), очевидно, верно. Предположим, что (36.2) справедливо при n, равном некоторому произвольно выбранному натуральному k, т.е.
a k +1 + ( a + 1) 2 k −1 = ( a 2 + a + 1) Pm ( k ) ( a ),

и докажем, что тогда (36.2) будет справедливо при n = k + 1.
Действительно, полагая в левой части (36.2) n = k + 1, проведем тождественные преобразования с учетом сделанного предположения:
a k + 2 + ( a + 1) 2 k +1 =  a k +1 + ( a + 1)2 k −1  a − a ( a + 1) 2 k −1 + ( a + 1)2 k +1 =
= ( a 2 + a + 1)aPm ( k ) ( a ) + ( a + 1)2 k −1  −a + ( a + 1) 2  =
= ( a 2 + a + 1)  aPm ( k ) ( a ) + ( a + 1)2 k −1  ,

что и требовалось установить. Утверждение (36.2) леммы доказано.
Для доказательства (36.3) достаточно сделать в (36.2) замену
a → −1 − a ,
(36.8)
затем для доказательства соотношения (36.4) нужно сделать в
(36.3) замену
a → 1/ a.
(36.9)
Применяя к каждому новому получающемуся соотношению
по очереди преобразование (36.8) или (36.9) переменной a, получаем остальные соотношения (36.5), (36.6) и (36.7).
Лемма доказана.
Замечание. Соотношение (36.7)получается из (36.6) в результате замены (36.8). Если теперь (соблюдая очередность производимых замен) применить замену (36.9) к соотношению (36.7), то
получим исходное соотношение (36.2). Тем самым, продолжать
процесс после получения соотношения (36.7) не имеет смысла –
мы будем получать уже полученные ранее результаты.
Замечание. Мы могли бы, отправляясь от (36.2), чередовать
замены (36.8) и (36.9) в другом порядке. Сначала применить к
(36.2) замену (36.9), затем к получившемуся соотношению – замену (36.8) и так далее. В результате мы пришли бы все к тому
102

же набору соотношений (36.2)–(36.7), расположенных в другом
порядке.
Замечание. Нетрудно видеть также, что каждое из преобразований (36.8), (36.9), будучи применено дважды, превращается в
тождественное преобразование переменной a.
Следствие из леммы. Полагая, например, a =3, получаем из
(36.2)–(36.7), что:
3n +1 + 42 n −1 делится на 13 при n = 1, 2, 3,…;
4n +1 + ( −1)n 32 n −1 делится на 13 при n =1, 2, 3,…;
3n 4n + 3 + ( −1) n делится на 13 при n = 0, 1, 2, 3, …;
3n + 34n + ( −1) n +1 делится на 13 при n = 0, 1, 2, 3, …;
4n + ( −1)n +1 32 n +3 делится на 13 при n = 0, 1, 2, 3,…;
3n + 42 n+ 3 делится на 13 при n = 0, 1, 2, 3,… .

Точно так же, выбирая, например, натуральный параметр a в
пределах от 3 до 7, мы можем с помощью вышеприведенной
леммы легко получить 30 однотипных (но различных!) задач на
применение метода полной математической индукции. Результат,
который может оказаться полезным при проведении контрольных
работ.
Перейдем теперь к вопросу, сформулированному в начале параграфа.
Доказательство теоремы. Полагая в (36.2) a = n, немедленно
получаем (36.1). Теорема доказана.
37. ÁÓÊÅÒÛ È ÍÎÄ
Задача 1(см. [9]). В Тридевятом царстве королю на день рождения подарили 323 белых пиона и 221 красный пион. Король
повелел понаделать из всех этих цветов максимально возможное
количество букетов – причем так, чтобы а) все букеты были совершенно одинаковы и б) все цветы были использованы. (В случае невыполнения хотя бы одного из своих требований король
обещал отрубить садовнику голову.) Из скольких цветков должен
был состоять каждый букет?
103

Решение. Здесь мы имеем дело с той довольно часто встречающейся ситуацией, когда задачу проще решать в общем виде,
чем в частной постановке (т.е. с заданными в условии конкретными числами). Будем поэтому временно считать, что белых
пионов А штук, а красных пионов В штук.
Обозначим, далее, через x количество букетов, через a – количество белых пионов в одном букете, через b – количество
красных пионов в одном букете. Нетрудно видеть, что тогда
должны выполняться соотношения:
ax = A, bx = B,
(37.1)
так что число x оказывается общим делителем чисел А и В. Однако по условию задачи количество букетов должно быть максимально возможным. Следовательно, x – наибольший общий делитель чисел А и В:
x= НОД (А, В).
(37.2)
Отсюда очевидным образом следует, что в каждом букете
A+ B
НОД( A, B )

(37.3)

цветков. Поскольку 323 = 17×19,221 = 17 ×13, сразу же получаем,
что НОД (323; 221) = 17, откуда вытекает, что в условиях задачи
количество цветков в одном букете равно
(323 + 221):17 = 19 + 13 = 32.
Ответ: в каждом букете должно быть по 32 пиона.
Наиболее интригующим в решении задачи 1 выглядит равенство (37.2), так как его геометрическая интерпретация сразу не
очевидна. Рассмотрим теперь еще одну задачу, связанную с предыдущей; ее мы сразу сформулируем «в общем виде».
Задача 2. В Тридевятом царстве королю на день рождения
принесли А белых пионов и В красных. Король повелел понаделать из них минимально возможное количество букетов, соблюдая следующие условия: а) во всех букетах должно быть одно и
то же количество пионов; б) в каждом букете пионы должны
быть одного цвета; в) все пионы должны быть использованы. (В
случае невыполнения хотя бы одного из своих пожеланий король
обещал отрубить садовнику голову). Из скольких пионов должен
был состоять каждый букет?
104

Решение.Так как количество букетов должно быть минимальным, количество цветков в каждом букете, очевидно, должно
быть максимально возможным (при выполнении условий задачи).
Обозначим это число (количество цветков в каждом букете) через
y. Далее, из условий задачи следует, что yдолжно целое число раз
укладываться как в А, так и в В. Иными словами, должны выполняться равенства (аналогичные равенствам (37.1)):
ky = A, py =B,
где k и p – целые числа. Итак, y – общий делитель чисел А и В.
Однако, как мы заметили выше, число y должно быть максимально возможным; следовательно,
y = НОД (А, В).
(37.4)
Ответ: искомое число пионов в одном букете дается формулой (37.4).
Замечание. Итак, налицо формальное совпадение выражений
(37.2) и (37.4) в двух, казалось бы, разных задачах. Как объяснить
это совпадение?
Мы объясним, в чем тут дело, на конкретном простом примере. Пусть А = 6, В = 9 так что НОД(А, В) = 3. Будем обозначать
белые пионы нулями, а красные – единицами:
000; 000; 111; 111; 111
(37.5)
(при помощи точки с запятой мы отделяем трехэлементные
однородные «букеты» друг от друга). Геометрически очевидно,
что три – это наибольшая численность группы объектов, одновременно укладывающейся целое число раз в группу численности
6 и в группу численности 9. Таким образом, соотношение (37.4)
допускает простую геометрическую интерпретацию.
Перейдем теперь к геометрической интерпретации соотношения (37.2). Для этого расположим трехэлементные группы «пионов» из (37.5) вертикально:
00111
00111
(37.6)
00111
и образуем новые «букеты одинакового состава»из горизонтальных строк. Опять же геометрически очевидно, что количество новых «букетов одинакового состава» из (37.6) неизбежно
105

оказывается равным числу элементов в прежних «однородных
букетах одинаковой численности» из (37.5). Тем самым связь
между соотношениями (37.2) и (37.4) установлена. (Похожее рассуждение имеется также в [4].)
38. ÎÁÌÀÍ×ÈÂÎÅ ÑÕÎÄÑÒÂÎ
В учебниках по математике в теме «Делимость» довольно
часто встречается следующая задача.
Задача № 1 (см., например, [9]). Доказать, что среди любых
ста натуральных чисел (не обязательно различных) всегда можно выбрать пятнадцать таких, которые дают одинаковые остатки при делении на семь.
Решение. Как известно, при делении на натуральное число n
в принципе возможны следующие остатки: 0, 1, 2, …, n-1. Таким
образом, различных остатков оказывается всего n штук. Соответственно, при делении на 7 в принципе возможны остатки: 0, 1,
2,…,6 (всего 7 штук). Будем теперь рассуждать от противного (и
заодно оценим силу этого метода!). Предположим, что существуют такие сто не обязательно различных натуральных чисел, из
которых невозможно выбрать 15 чисел, дающих одинаковые остатки при делении на 7. Обозначим эту сотню чисел через А. Но
тогда для каждого из семи в принципе возможных остатков найдется в наборе А не более 14 чисел, дающих этот остаток при делении на 7. Однако отсюда следует, что численность набора А не
может превосходить 14×7 = 98, что противоречит условию. Тем
самым требуемое утверждение доказано.
Та же самая идея эксплуатируется в следующей задаче.
Задача 1а. Доказать, что среди произвольно взятых ста натуральных чисел (не обязательно различных) всегда найдутся: а)
семь чисел, сумма которых делится на 7; б) четырнадцать чисел, сумма которых делится на 7.
Решение. Как мы знаем из решения предыдущей задачи, среди произвольно взятой сотни натуральных чисел всегда можно
найти пятнадцать чисел, дающих одинаковые остатки при делении на 7. Выберем среди этих пятнадцати чисел произвольные
106

семь (произвольные четырнадцать); их сумма, очевидно, будет
делиться на 7 (соответственно, на 14). Задача решена.
Приведем теперь одну любопытную задачу, которая давалась
на математических олимпиадах в пятидесятые годы прошлого
столетия. Внешне эта задача похожа на предыдущую, однако
сходство это обманчиво.
Задача 2. Доказать, что среди произвольно взятых ста целых неотрицательных чисел (не обязательно различных) всегда
можно выбрать несколько таких, что их сумма будет делиться
на 100. (Если среди упомянутых ста чисел имеется число z, делящееся на 100, то разрешается выбирать именно это число z в
качестве «суммы», состоящей из одного слагаемого.)
Первое, что приходит в голову, – это действовать в духе решения задачи 1а. Однако произвольно взятые сто чисел вовсе не
обязаны давать один и тот же остаток при делении на 100. Итак,
желание действовать, опираясь на соображения, приведшие к успеху в предыдущей задаче, ведет в тупик. Заметим теперь, что в
предыдущей задаче строение числа 100 (его представление в виде
произведения простых множителей) для нас не играло никакой
роли, число 100 можно было заменить на 99, и утверждение задачи 1а осталось бы в силе. Может быть, теперь имеет смысл обратить внимание на строение числа 100?
Оказывается, что именно этот путь ведет нас к успеху. Нам
придется воспользоваться тем фактом, что 100 = 10×10, 10 = 2×5.
Утверждение 1. Пусть a и b – два произвольно взятых (возможно, совпадающих) натуральных числа. Тогда верно по крайней мере одно из двух положений:
а) среди чисел a и b найдется четное;
б) сумма этих чисел четная.
Доказательство очевидно.
Утверждение 2. Пусть a, b, c, d, e – пять произвольно взятых
(не обязательно различных) натуральных чисел. Тогда среди них
можно выбрать несколько чисел, сумма которых делится на 5.
(Если среди упомянутых пяти чисел имеется число z, делящееся
на 5, то разрешается выбирать именно это число z в качестве
«суммы», состоящей из одного слагаемого.)
107

Доказательство. Очевидно, что, не ограничивая общности,
можно считать числа a, b, c, d, e принадлежащими множеству
{0, 1, 2, 3, 4}. Теперь доказательство утверждения сводится к перебору не слишком большого числа вариантов. Действительно,
если в набор a, b, c, d, e входит ноль, то именно этот ноль мы и
выбираем, и доказывать нечего. Таким образом, нас будут интересовать лишь варианты, когда числа a, b, c, d, e принадлежат
множеству{1, 2, 3, 4}. Непосредственный перебор вариантов доказывает справедливость сделанного утверждения.
Утверждение 3. Среди произвольно взятых десяти целых неотрицательных чисел (не обязательно различных) всегда можно
выбрать несколько таких, что их сумма будет делиться на 10.
(Если среди упомянутых десяти чисел имеется число z, делящееся на 10, то разрешается выбирать именно это число z в качестве «суммы», состоящей из одного слагаемого.)
Доказательство. Рассмотрим десять произвольно взятых целых неотрицательных чисел и распределим их (опять же, произвольным образом) по двум наборам А и Б, по пять чисел в каждый набор. В силу утверждения 2 из совокупности А можно выбрать несколько чисел, сумма которых делится на 5; обозначим
эту сумму через v. Точно так же, из совокупности Б можно выбрать несколько чисел, сумма которых тоже делится на 5; обозначим эту сумму через w. Далее, в силу утверждения 1 по крайней мере одна из трех сумм: v, w, v+w будет четной, и, следовательно, будет делиться на 10. Утверждение доказано.
Решение задачи 2. Рассмотрим набор А, состоящий из ста
произвольно взятых целых неотрицательных чисел, и распределим эти числа (произвольным образом) по десяти совокупностям,
отправив по десять чисел в каждую совокупность. Совокупности
эти обозначим соответственно А1, А2, … А10 . Как следует из утверждения 3, в каждой из этих совокупностей можно найти несколько чисел, сумма которых делится на 10. Обозначим упомянутые суммы через 10w1, 10w2, …,10w10 . Вновь в силу утверждения 3 среди чисел w1, w2, …, w10 можно найти несколько, в сумме
делящихся на 10. Пусть, например, w1 + w2 делится на 10. Тогда
выражение 10w1 + 10w2 =10 × (w1 + w2), представляющее собой
108

сумму нескольких чисел из исходного набора А, очевидно, будет
делиться на 100. Задача решена.
Похоже, что справедливо следующее утверждение, обобщающее задачу 2.
Гипотеза. Среди произвольно взятых n целых неотрицательных чисел (не обязательно различных) всегда можно выбрать
несколько таких, что их сумма будет делиться на n. (Если среди
упомянутых n чисел имеется число z, делящееся на n, то разрешается выбирать именно это число z в качестве «суммы», состоящей из одного слагаемого.)

109

Îòâåòû ê çàäà÷àì èç ïï. 28 è 31
1. Ответ к задаче из п. 28: на рассвете (когда Солнце показалось по крайней мере на четверть своего диаметра) тень профессора Мориарти, сидящего у кромки воды, не могла быть выше самого Мориарти.
2. Ответ к задаче из п. 31: например, между 31-м января и
1-м февраля нет ни одного четного числа.

ÑÏÈÑÎÊ ÎÁÎÇÍÀ×ÅÍÈÉ
∀ – квантор общности (∀
∀х – «для всех х»);
∃ – квантор существования (∃
∃х – «найдется х»);
∨ – дизъюнкция высказываний (А∨
∨В – «А или В», в смысле «хотя
бы одно из двух»);
∧ – конъюнкция высказываний (А∧
∧В – «А и В»);
¬ – отрицание высказывания (¬А – «не А», «неверно, что А»);
→ – импликация высказываний (А→В – «если А, то В»);
↔ – эквиваленция высказываний (А↔В – «А тогда и только
тогда, когда В»);
k
Cn – число сочетаний из n элементов по k элементов, т.е. число
различных k-элементных подмножеств n-элементного
множества;
Cnk =

110

n!
.
k !( n − k )!

ËÈ ÒÅ Ð À Ò Ó Ð À
1. Иванова Е.А., Локшин А.А. О парадоксе математической индукции // Актуальные проблемы современной науки, 2008, № 2, с. 194–195.
2. Локшин А.А. Свободная воля и математика // Знание-Сила, 2010, № 3, с. 86–90.
3. Ефимов Н.В. Высшая геометрия. – М.: Наука, 1978.
4. Мерзон А.Е., Добротворский А.С., Чекин А.Л. Пособие по математике для
студентов факультетов начальных классов. – М., 1998.
5. Козлова Е.Г. Сказки и подсказки. Задачи для математического кружка. –
М.: МЦНМО, 2004.
6. Энгелер Э. Метаматематика элементарной математики. – М.: Мир, 1987.
7. Локшин А.А., Иванова Е.А. Признаки делимости и математические фокусы // Математика для школьников, 2012, № 6, c. 49–52.
8. Кордемский Б.А., Ахадов А.А. Удивительный мир чисел. – М., 1996.
9. Добротворский А.С. и др. Задачник по математике для факультетов начальных классов. – М., МГПИ, 1983.
10. http://zagadki.pp.ru/zagadki-golovolomki/fokus-s-telefonnoj-knigoj.html
#comments
11. Иэн Стюарт. Истина и красота. – М.: Астрель, 2010, с. 19–42.
12. Румшиский Л.З. Элементы теории вероятностей. – М.: Наука, 1976.
13. Виленкин Н.Я. и др. Математика. Пособие для студентов пединститутов. –
М.: Просвещение, 1977.
14. Локшин А.А., Сагомонян Е.А. Логика и множества. – М.: Вузовская книга, 2002.
15. Кордемский Б.А. Математические завлекалки. – М., 2005.
16. Локшин А.А., Иванова Е.А. О квадратных уравнениях с параметрами //
Математика для школьников, 2013, № 3, с. 25–27.
17. Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И. Алгебра. 8 класс. Учебник
для школ и классов с углубленным изучением математики. – М.: Мнемозина,
2004.
18. Спивак А.В. Тысяча и одна задача по математике. – М.: Просвещение, 2012.
19. Харт-Дэвис А. Удивительные математические головоломки. – М.: Астрель, 2003.
20. http://ega-math.narod.ru/Quant/Fracti.htm
21. Кордемский Б.А. Математическая смекалка. – СПб.: 1994, с. 264–270.
22. Игошин В.И. Математическая логика и теория алгоритмов. – М., 2010, с. 192.
23. Ван дер Варден Б.Л. Пробуждающаяся наука. – М., 2009.
24. Афанасьев В.В. Теория вероятностей. – М., 2007.
25. http://acadclasses.narod.ru/math/lecture13.htm
26. http://club.berkovich-zametki.com/?p=5892
27. Успенский В.А. Апология математики. – СПб., 2009.
28. Журавлев В., Самовол П. Быстрее быстрого, или Можно ли обогнать бинарный алгоритм / Квант, 2013, № 2, с. 7–15.
29. Шень А. Игры и стратегии с точки зрения математики. – М.: Издательство МЦНМО, 2008.
30. http://elementy.ru/problems/698

111