Разберём все варианты

42

Разберем все варианты

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

Метод тут примерно такой, как при поисках одной горошины в мешке гороха: преждевое необходимо терпение, молодой человек.
К. Чапек. «Купон»

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

Но Природа не считается с нашими вкусами. Поэтому профессионалматик, решая задачи, возникло еще развития естественногония, постояно стalkивается с задачами, которые то не имеют решения, то имеют много решений, то требуют непrivibuных, а подчас и громоздких, «некрасивых» методов решения.

Таким «некрасивым» методом ученики младших классов часто считают метод перебора. Некоторые даже думают, что метод перебор — это «неправильный» метод, и им решать задачи якобы нельзя. На самом деле задачу можно решать любым способом, лишь бы получить верный и обоснованный ответ. Найти все ответы и доказать, что других нет, — это и значит решить задачу. А оказаться этих ответов может сколько угодно: один, несколько, ни одного или бесконечного много.

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

43

любо сможет осуществить, — это конечный перебор, и никакая вычислительная техника этого не изменит. Но даже конечный перебор осуществим лишь в ограниченных пределах. Фактически при решении задач «вручную», при помощи авторучки и бумаги, можно перебрать десять, ну — сотно вариантов. Компьютер уведомляется это число до тысячи, ну — миллионов. Однако сплошь и рядом возникают задачи, решения которых методом перебор приводит к гораздо большему числу вариантов. Уже простые настольные игры типа шахмат дают такое число позиций, с которым не справится никакая машина. Поэтому искусство программирования, как и искусство решать математические задачи, включает умение сокращать перебор до осуществимых масштабов.

Сплошной перебор всех вариантов осуществим лишь в самых простых случаях. Для. Свифт остроумно выместел его в своей книге «Путешествия Гулливера». В пятой главе третьей части он описывает машину, осуществлявшую перебор всегоможет составить полный обзор всех искусств и наук». Сатира Свифта метила во вполне реальную цель: создание «думающих» машины, связанное с идеей перебор. Еще в XII века рыцарь-монах Раймуд Луллий сконструировал машину для механического доказательства всех положений ХристIANства и отправился с ней к маврам, уверенный, что эта «наука» обратит их в истинную веру. Идеи Лулляй интересованы Джордано Бруно и Лейбница, мечтавшего о таком прогрессе науки, который позволяет не спорить, а вычислить.

Великий немецкий ученый Лейбницц (1646—1716), бывший старшим современником Свифта (1667—1745), во жизни развивал идею «всеобщей характеристики», т. е. равного по точности математике описания всех процессов человекаского мышления.

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

Задача 1. На складе стоит 5 станков массой соответствующего 1500 кг, 1020 кг, 800 кг, 750 кг и 600 кг. Требуется увеличить часть из них на машинерузоподъемности 3 тонны, загрузив ее максимально, но не перегрузив. Какие станки надо порезать на машину?

Решение. Предположим, что мы решили не быть самый тяжелый станок. Тогда масса остальных станков 1020+800+750+600=3170 кг, что больше трех тонн. Значит, придется оставить еще какой-нибудь станок. Мы захватим самый большой вес, если оставим самый легкий станок — в 600 кг. Надо, конечно, еще

44

проверить, сможет ли трехонка увеличти оставшиеся станки: 1020+800+750=2570 кг<3 т. Итак: если не брать самый тяжелый станок, то мы увеличем, самое больше, 2570 кг. Пусть теперь мы погрузили на машину станок в 1500 кг; тогда в машине еще остается места на 1500 кг. Уложиться в эти 1500 кг можно взяв только один станок, что даст нам, самое больше, 1020 кг (а всего в грузовике будет 2520 кг), либо взять два станка, что даст, самое больше, 800+600=1400 кг, а всего на грузовике будет 2900 кг.

Сравнивая все варианты, мы видим, что последний — наиболее. Итак, надо погрузить станки массой 1500 кг, 800 кг, и 600 кг.

Подобный прямой перебор не всегда возможно. Чаще приходится применять его в сочетании с другими методами. Вот пример.

Задача 2.*) Найдите все натуральные трехначные числа, каждое из которых обладает следующим двумя свойствами:

— первый цифра в 3 раза меньше последней его цифры;
— сумма самого числа с числом, получающимся из него перестановкой второй и третьей его цифр, делится на 8 без остатка.

Здесь прямой перебор метод перебора значило бы перебрать все трехначные числа и выбрать из них те, которые удовлетворяют условиям. Делать это вручную — все равно, что искать иголку в стоне сена или нужную горошину в мешке гороха. Правда, с помощью комьютера перебрать все трехначные числа недолго, но «спортивнее» решать простые задачи простыми средствами: это заставит нас выработать приемы сокращения перебора; кстати, эти приемы резко увеличitat наши возможности, когда у нас будет комьютер.

Данную задачу мы начнем решать алгебраические и прибегнем к перебору лишь тогда, когда удastoreсти ее к немногим случям.

Решение. Пусть $x$ — цифра сотен, $y$ — цифра десятиков искомого числа. Тогда цифра его единиц равна 3x. Очевидно, 3x≤9, откуда $x\leq 3$. Нуlem первая цифра числа быть не может. Значит, $x$ не может равнять числу иному, кроме 1, 2 и 3. Эти три возможности мы рассмотрим по отдельности, но сначала запишем второе условие, обозначая время точками (:) выражение «делится на»:

$((100x+10y+3z)+(100x+30x+y))\div 8,$

т. е.

$(200x+33x+11y)\div 8.$

Мы нарочно оставили 200x и 33x отделными слагаемыми. Так легче заметить, что 200x можно отбросить (так как 200 : 8) и записать это условие так:

$((33x+11y)\div 8,$

или

$11(3x+y)\div 8.$

Для этого необходимо и достаточно, чтобы 3x+y делилось на 8. Теперь присутствим к перебору, который вполне осуществим, так как состоит всего из трех случаем.

1. $x=1$. Тогда $3+y$ : 8. Это будет при $y=5$.

2. $x=2$. Тогда $6+y$ : 8. Это будет при $y=2$.

3. $x=3$. Тогда $9+y$ : 8. Это будет при $y=7$.

Итак, задача имеет три ответа: 153, 226, 379.

Задача 3. Решите в натуральных числах уравнение

$$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1.$$

Напомним, что натуральными называются целые положительные числа. Решить уравнение в натуральных числах — значит найти все его решения, в которых неизвестные принимают натуральные значения. Сплошным перебором, рассматривая все тройки натуральных чисел по отдельности, решить эту задачу вообщество: таких трех бесконечного много. Поэтому, прежде чем присутствить к перебору, необходимо как-то свести до к конечному числу случаем. Nam будет удобнее проводится пе-

45

ребор, если мы чуть-чуть изменим условия задачи.
Задача 3’. Решите в натуральных числах систему

$$\begin{cases} \frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1, \\ x \leqslant y \leqslant z. \end{cases}$$

Решение задачи 3’. Очевидно,

$$\frac{1}{x} \geqslant \frac{1}{y} \geqslant \frac{1}{z}.$$

Предположим сначала, что $x > 3$. Тогда

$$\frac{1}{3} > \frac{1}{x} \geqslant \frac{1}{y} \geqslant \frac{1}{z},$$

откуда

$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} < \frac{1}{3} + \frac{1}{3} + \frac{1}{3},$$

что противоречит условиям. Итак, $x$ не может равняться чисему иному, кроме 1, 2 и 3. (Видите, как резко мы сократили перебор!)

1. $x = 1$. Тогда

$$\frac{1}{y} + \frac{1}{z} = 0,$$

чero не может быть.
2) $x = 2$. Тогда

$$\frac{1}{y} + \frac{1}{z} = \frac{1}{2}.$$

Если $y > 4$, то

$$\frac{1}{4} > \frac{1}{y} \geqslant \frac{1}{z},$$

откуда

$$\frac{1}{y} + \frac{1}{z} < \frac{1}{4} + \frac{1}{4},$$

чero не может быть. Итак, $y$ не может равняться чисему иному, кроме 2, 3 и 4. Подставляя каждое из этих значений, убеждаемся, что $y = 2$ не годится, а два другие значения дают два ответа: (2, 3, 6) и (2, 4, 4).
3) $x = 3$. Тогда

$$\frac{1}{y} + \frac{1}{z} = \frac{2}{3}.$$

Если $y > 3$, то

$$\frac{1}{3} > \frac{1}{y} \geqslant \frac{1}{z},$$

откуда

$$\frac{1}{y} + \frac{1}{z} < \frac{1}{3} + \frac{1}{3},$$

чero не может быть. Итак, в данном случае надо рассмотреть для $y$ только одно значение 3, что дает еще один ответ: (3, 3, 3).

Все случаи разобраны. Задача 3’ решения. Она имеет три ответа: (2, 3, 6), (2, 4, 4), (3, 3, 3).

В отличие от нее, задача 3 имеет другой список ответов, получающихся из этих всех возможных перестановками. Вот ответ задачи 3:

(2, 3, 6), (2, 6, 3), (3, 2, 6),
(3, 6, 2), (6, 2, 3), (6, 3, 2),
(2, 4, 4), (4, 2, 4), (4, 4, 2), (3, 3, 3).

(В каждом из этих ответов первое число — значение $x$, второе — значение $y$, третье — значение $z$.)

В задачах, которые мы do сих пор разбиали, необходимо было найти все ответы, удовлетворяющие данной условия. Для того чтобы доказать, что такой объект не существует, необходимо разбиать все случаи или проводить общее рассудение. Для того же чтобы доказать, что такой объект существует, достаточно привести всего один пример. Вот две задачи такого типа.

Задача 4. Известно, что для двух треугольников $ABC$ и $A'B'C'$ выполняются следующие три условия:

$$\angle A = \angle A', AB = A'B', BC = B'C'.$$

Могут ли треугольники $ABC$ и $A'B'C'$ быть неравны?

Ответ: могут.

46

Доказательство. Построим два неравных треугольника, для которых верны равенства в условия. Возьмем острый угол $A$ и отложим на одной его стороне отрезок $AB$ (рис. 2). Проведем окружность с центром $B$ и радиусом, который меньше, чем $AB$, но больше, чем расстояние от точки $B$ до другой стороны угла. Эта окружность пересечет другую сторону угла в двух точках, которые мы обозначим $C$ и $C'$. Треугольники $ABC$ и $ABC'$ не являются равными, хотя для них выполются три направленные выше условия.

Задача 5. Можно ли вычисать по кругу $k$ различных цифр так, чтобы из каждой двух соседних можно было составить число, делящее на 7? Здесть $k$ целое, $3 \le k \le 10$.

Фактически здесь предполагается восем различных задач для восыми различных значений $k$. Но решать их удобно все вместе при помощи следующого приема.

Выпишем все двухначные числа, делящиеся на 7 (рис. 3). Затем нарисуем на бумаге все десять цифр и соединим линяями те из них, которые составляют какое-нибудь из направленных чисел (рис. 4). Расставить требуемым образом $k$ цифр — все равно, что общий $k$ различных кругов и вернуть в начало пути.

Как видите, все цифры распалисны три «островка». Тепер ясно, что больше пяты цифр расставить требуемым образом нельзя. А три, четые или пять цифр расставить можно. Запишите требуемые расстановки самостояльно.

Задание 1. О треугольнике $ABC$ были сделаны четыре утеверждения:
a) треугольник $ABC$ равносторонний;
b) треугольник $ABC$ прямогольный;
c) $AB=BC$;
d) $AB=2AC$.

Известно, что два из этих утверждений верны, а два другие неверны. Чему может равняться перimetр треугольника $ABC$, если самая короткая его сторона равна единице?

2. Найдите два числа, квадрат каждого из которых на единицу больше другого числа.

3. Чему может равняться перimetр треугольника $ABC$, если известно, что $\angle A=60^\circ$, $AB=8$, $BC=7$?

4. Решите в целях положительных чисел уравнение

$$x^2+y^2+z^2+xyz=20.$$

5. Улитка прополлаза отрезок длиной в метр и остановилась. Потом повернула на $90^\circ$, прополлаза еще отрезок длиной в метр и остановилась. Так она сделала 6 раз подряд: прополлаза 6 прямолинейных отрезков длиной в метр, поворачивая послед каждой на $90^\circ$ вправо или влево. Каково может быть расстояние между началом и концом ее пути?

6. Найдите все трехзначные числа, каждое из которых в 19 раз больше суммы своих цифр.

7. На солнечной поляне треугольки ужи, вообьи, мыши, жуки и пашки. У всех вместе ногчетверро больше, чем голов. Если ужи уползут, то ногчетверро больше, чем голов. У мышей и жуков вместе ногчетверро больше, чем голов. У жуков и пашков вместе сто ногт. Сколько каких животных на поляне? (Надеемся, что все знают, сколько у кого нет: у уже — 0, уоворь — 2, у мыши — 4, у жука — 6, у пашка — 8.)

8. Расстояние $AB$ равно 225 км. В 12 часов дня из $A$ в $B$ выездает автобус и одновременно из $B$ в $A$ выездает автобус. Автобус прибывает в $B$ в 6 часов вечера того же дня, причем делает в пути 4 остановки через равные промежутки времени на 15 минут каждую. Автобуседет весь путь без остановок и встречает автобус на расстоянии 90 км от $A$. Какова может быть скорость автобуса?

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

10. Найдите три числа, квадрат каждого из которых на 3 большие, чем сумма двух других чисел.

11. Все вершины неокоторого четырехугольника лежат внутри квадрата, сторона которого равна 1.

a) Может ли перimetр этого четырехугольника быть больше 5?

b) Может ли перimetр этого четырехугольника быть больше 6?

12. Из пункта $A$ в пункте $B$ вышел пешекод. Спустя некоторое время из пункта $A$ вслед пешекод выехал вволоспедict. Проехав час,