Можно и нельзя

52

Можно и нельзя

Кандидат физико-математических наук
С. М. ЛЬВОВСКИЙ,
кандидат физико-математических наук
А. Л. ТОOM

Формулировки школьных задач чаще всего начинаются с словами вроде «вычислите» или «найдите». Оdnako в математике очень часто встречаются и задачи, в которых требуется не вычислить что-либо, а выязывать, существует ли объект с заданным свойством. Формулировки таких задач начинаются обычно с словами «можно ли…» или «существует ли…». Ответ на такие вопросы должен быть, естественно, обоснованным. Если мы утверждаем, что нечто сделать можно, то достаточно указать конкретный способ сделать это. Если же мы утверждаем, что чего-то сделать нельзя, то примерми тут уже не обойтись, надо придумывать доказательство. Общего рецепта для такого рода доказательств не существует; в этой статье мы показем вам лишь некоторые из примеров, которые могут при этом использоваться.

Вот первый пример на тему «можно и нельзя».

Задание 1. Для каких натуральных чисел n существует замкнутая ломанная из n звенев, пересекающая каждое свое звеноровно один раз? Все пересечения должны проискать внутри звенев, а не в вершинах; никакие три звена не должны пересекаться в одной точке.

Решение. Прежде всего заметим, что для некоторых n такой ломанной не существует: например, для n=1, n=2, n=3, n=4. С другой стороны, при некоторых n таких ломанную можно найти; например, на рисунке 1 показана нужная ломанная при n=6. Обратим внимание на следующие свойства этой ломаной: ее звеня образуют три пары, причем звеня каждой пары пересекаются друг с другом, а с другими звенями

53

не пересекаются (на рисунке 1 каждая пара звеньев начерчена своим цветом). Это свойство вытекает из самого условия задачи: если какая-то ломанная пересекает каждое свое звеноровно один раз, то каждое звено образует пару с пересекающим его звеном. Но, чтобы звенья могли разбится на пары, их число обязано быть четным. Итак, мы доказали, что для нечетных $n$ требуемой ломанной не существует. Оказывается, что для всех четырех ломанные существуют. Придумайте сами общий способ построения такой ломанной для каждой четверго $n \geq 6$. Вам помогет в этом рисунок 2.

Задача 2. Существует ли такое натуральное число, которое после умножения на 2 становится квадратом, а после умножения на 4 — четвертой степени целого числа?

Решение. Давайте предположим, что такое число $m$ существует, и разложим его на простые множители. Собственно, из его простых множителей нас интересют только двойки; поэтому мы запишем:

$$m = 2^k \cdot p,$$

где $p$ нечетно. Согласно первому условию число

$$2m = 2^{k+1} \cdot p$$

квадрат целого числа, откуда $k+1$ четно, а потом $k$ нечетно. Согласно второму условию число

$$4m = 2^{k+2} \cdot p$$

четвертая степень целого числа, откуда $k+2$ делится на 4. Но если $k$ нечетно, то и $k+2$ нечетно, и потом не может делиться на 4. Полученное противоречие показывает, что исключого числа не существует.

Рис. 1.

Задача 3. Какое наиболее количество точек можно расположить в квадрате со стороны 1 так, чтобы все расстояния между этих точками были не меньше 0,5? («В квадрате》 означает «внутри квадрата или на его границе»).

Эта задача тоже из серии задач «можно или нельзя». Ее решение должно состоять из двух частей: доказательства того, что столько точек расположить требуемым образом можно, и того, что большего количество точек расположить уже нельзя. Нетрудно понять, как расположить требуемым образом девятый точек; одну точку поставить в центре квадрата, четыре — в вершинах и еще четыре — в серединах сторона (рис. 3, а). Возникает предположение, что больше чем девятый точек требуемым образом расположить нельзя. Как это доказывается? Весьма привлекательно выгляделит, например, такой путь доказательства: рассмотреть вышеуказанную расстояние девяты точек (в центре, вершинах и серединах сторона) и поставаться после этого установлен, что еще одна точка, добавленная к этим.devятии, будет находиться на расстоянии, меньше 0,5, от хотя бы одной из первых.devятии. Это утверждение совершено верно (например, потому, что круги радиусом 0,5 с центрами в первых.devятии точках покрывают весь квадрат — рис. 3, б), но, к сожалению, оно не дает решения нашей задачи. В самом деле, откуда уверенность, что единственный способ требуемого расположения.devяты точек — это рисунок 3, а? Вдруг.devяты точек удаться расположить как-то по-другому, да так, что к ним можно будет добавить еще и десятию?

54

Рис. 3.

Чтобы доказать, что больше девяты точек расположить в квадрат требуемым образом нельзя, воспользоваться вот каким приемом. Разобъем наш квадрат на 9 равных квадратков состоями 1/3 (рис. 4). Если в большом квадрате расположено больше девяты точек, то хотя бы две из них попадут в один и тот же маленький квадратик. Расстояние между любыми двумя точками квадрата не превыходит, очевидно, длины диагонали этого квадрата. Но диагональ квадрата со стороны 1/3 равна $\sqrt{2/3} \leq 0.5$. Значит, более девяты точек расположить требуемым образом невозможно, и ответ к задаче 2 — это де вять точек.

Соображение, который мы воспользовались при решении задачи 2: «если более чем 9 точек распределить по 9 квадраткам, то хотя бы две из этих точек попадут в один квадратик» — часто называют «прииципом Дирихле» в честь заменительного немецкого математика П. Г. Дирихле (1805—1859).

В задачах 2 и 3 утверждение о существовании доказываюсь построением конкретного примера. В задаче 4 приходит действовать по-иному.

Задача 4. Последовательность чисел строится следующим образом. Первое число в ней равно двум. Каждый следующее число равно сумме десятих степеней цифр предыдущего числа. Доказите, что в этой последовательности встречается два одинаковых числа.

Посмотрим, что за числа получится в этой последовательности. Второе число равно $2^{10}=1024$. Третье число равно $1^{10}+2^{10}+4^{10}=1+1024+1024^2=1049601$.

Четвертое число уже так велико, что становится ясно: «вручную» мы двух одинаковых чисел не найдем. Более того, возникает сомнение, верно ли вообще то, что нас просто доказать? На первый взгляд, числа быстро растут, и повторов не предвидится. Однако не будем спешить с выводами; вместо точных вычислений наших чисел посмотрим, сколько цифр может быть в их записи.

Четвертое число равно $1^{10}+4^{10}+9^{10}+6^{10}+1^{10}$, а это меньше, чем $10^{10}+10^{10}+10^{10}+10^{10}=5 \cdot 10^{10}$. Однако $5 \cdot 10^{10}$ — одинаковатизначное число (это пятерка с десятью нулями); значит, в четвертом числе не более одинаковати цифр. Пятое число — это сумма десятих степеней цифр четырого числа. Каждый из этих десятих степеней меньше чем $10^{10}$, всего цифр не больше 11, значит, пятое число меньше, чем двенадцатизначное число $11 \cdot 10^{10}$. Стало бы пять, пятое число содержит не более 12 цифр. Рассуждая аналогично, получаем, что шестое число меньше $12 \cdot 10^{10}$, и стало бы, опять имеет не более 12 цифр. Поэтому то же рассужждение, получаем, что в записи седьмого, восмого и вообще всех последующих чисел нашей последовательности содержится не более 12 цифр. Поскольку чисел, в записи которых содержится не более 12 цифр, конечное число, у нас не смогут все получаться числа, отличные от прежних, и когда-нибудь встретиется два одинаковых числа.

В заключение предлагаем вам задачи для самостоятельного решения (задачи 1—12 составляют задание для

55

семиклассиков, железших поступить во Всесоюзную заочную математическую шкалу — рассказ об этой школе см. на с. 65).

Задчич

1. Имеются три раствора. Первый из них содержит 2 % вещества A и 3 % вещества B. Второй раствор содержит 5 % вещества A и 7 % вещества B. Третьий раствор содержит 11 % вещества A и 12,5 % вещества B.

Можно ли смешать эти растворы в такой пропорции, чтобы полученная смесь содержала 7,5 % вещества A и 7 % вещества B?

2. Цифры 1, 2, 3, 4, 5, 6, 7, 8, 9 написаны подряд. Можно ли так растворить скобки и знаки математических действий, чтобы получилось выражение, равное нулю?

3. Пионер Сережа придумал такой признак делимости на 27: если сумма цифр числа делится на 27, то и само число делится на 27. Верен ли этот признак?

4. Можно ли разрезать квадрат на 1989 квадратников (не обязательно равных)?

5. Число 1989 возвели в куб и к результату прибавили 3; полученное число опять возвели в куб и к результату прибавили 3; полученное число опять возвели в куб, к результату опять прибавили 3 и т. д. Получалась последовательность чисел, каждое из которых на 3 больше куба предыдущого. может ли в ней встретиться число, окачивающееся на 8?

6. Существует ли такое натуральное число, которое после умножения на 2 становится квадратом, после умножения на 3 — кубом, после умножения на 5 — пятой, а после умножения на 7 — седьмой степень целого числа?

7. Существует ли такое патиизначное число, что сумма цифр делится на 13 и сумма цифр числа, на единицу большего, также делится на 13? Если нет — докажите, если да — перечислите все такие числа.

8. Простим числом называется натуральное число, большее 2 и не имеющее делитель, кроме самого себя и 1. Требуется в каждую клетку квадратной таблицы размером 4×4 клетки висать по простому числу таким образом, чтобы в каждой строке и каждом столце произведение чисел равнялось 1989. Можно ли это сделать?

9. Можно ли так растворить числа в клетках прямогольной таблицы, чтобы произведение чисел в каждой строке равнялось двум, а произведение чисел в каждой столце равнялось три?

10. Можно ли пять различных примых на плоскости раположить таким образом, чтобы каждая из них пересекаларовно три другие?

11. Расстояние между пунктами A и B — пятьдесят километров. В полдень из пункта A в пункт B отправились трое друзей. Пешком каждой из них идет со скоростью 5 км/ч. В их распоряжении есть дорогный велосипед, на котором можно ехать со скоростью 10 км/ч, и гоночный велосипед, на котором можно ехать со скоростью 20 км/ч. На каждом велосипеде помещается только один человек; велосипеды можно оставлять на дороге без пристма. Успеют ли все трое, полдзуясь только этими двумя велосипедами, добавляется по пункта B к шести часов вечера?

12. Можно ли расположить на плоскости 7 точки таким образом, чтобы среды любых трех из них нашлись хотя бы две, расположенные на расстоянии 1 см?

13. В футбольном турине участвовал 10 команд; каждая сыграла с каждой по одному матчу. Согласно опубликованным итогам турира, команда, заняшая седьмое место, набрала 11 очков, команда, заняшая воьмое место, набрала 6 очков, а команда, оказавшая на последнем месте, набрала 4 очка. Могло ли так быть? (За победом команда получает 2 очка, за ничью — 1 очко, за порожжение — 0 очков. При равенстве набранных очков учитывается количество забитых и пропущенных мячей.)

14. Послеовательность, состоящая из сорока чисел, строится следующим образом. Первое число равно нулю, второе равно единице. Каждый число, кроме первого и второго, равно сумме каких-то двух из предшествующих чисел. может ли в такой последовательности встретиться член, равный миллиону?

15. Сколько кругов радиусом 1 нужно взять, чтобы покрыть им квадрат со стороны 2?

16. Требуется перевести несколько кусков мрамора общей массой 14 т. Точная масса каждой куска неизвестно, что масса каждой не более 400 кг. Сколько машин грузоподъемностью в 1500 кг надо зааказать, чтобы заведено можно было увеличить этот груз?

17. В стране Миггов из любого города в любой можно проехать по одной-единственной дороге. При дороги проходят через 4 города каждой, две дороги проходят через 3 города каждой, а на каждой из остальных дорог лежит по 2 города. Девочка Элли расскажа, что всего в этой стране 11 городов и 35 дорог. Докажите, что она ошиблась в подсчетах.

18. Круг разбит на n одинаковых секторов, в каждой из которых стоит по шашке. За один ход можно сделать следующие: взять любые шашки и переставить их: одну — в соседней сектор по часов стрелке, другую — в соседней сектор против часов стрелки. При каких n можно с помощью таких ходов собрать все шашки в одном секторе?

19. Квадрат со стороны 1 м выкапли в две краски. Докажите, что найдет три точки одного цвета, являющихся вершинами равностороннего треугольника со стороны не менее 30 см.