От школьной задачи — к проблеме

2

А. Савин

ОТ ШКОЛЬНОЙ ЗАДАЧИ

• К ПРОБЛЕМЕ

Расстановки и транспозиции

Как-то раз, перелистывая учебник своего сына «Математика-5», я наткнулся на следующую задачу *).

Тoma «Детской энциклопедии» стояли в маком порядке: 1, 2, 6, 10, 3, 8, 4, 7, 9, 5. Как поставить их по порядку, если можно брать два соседних тома и ставить их, не меняя порядка, рядом на новое место (в начало, конец или между двумя томами)?

Довольно быстро мне удалось найти решение. Оно изобразено на рисунке 1. Но у меня давно выработалась привчка анализировать решенную задачу, и сразу же возникло вопрос: «А если бы тогда ничего иначе?». Тут же в голову пришел способ перестановки, не зависящий от первого расстановки томов. Сначала взять 1-й том и том, стоящий справа от него, и поставить их в начало, затем 2-й том и том, стоящий справа от него, и поставить их за 1-м томом и т. д. Если нужный том стоит в конце ряда, то сначала следует взять любую пару из еще не установленных томов и переставить их в конец ряда, после чего перестановка нужного тома оказется возможной.

Я испробовал этот способ на расстановке, предложенной в задание, и четырьмя перестановками поставил тома в нужном порядке. Затем взял расстановку: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. После шести перестановок (см. рис. 2) пришел к следующей расстановке: 1, 2, 3, 4, 5, 6, 7, 8, 10, 9. Тут я обнаружил, что дальней метод не действует. Кроме 9-го, остался лишь один 10-й том, и переставлять в конец ряда нечего.

Я проделал перестановку томов еще раз и тем же способом, но ставя в конец ряда уже другие пары. Переставлять пришлось дольше, но результат остался прежним — снова на конце ряда сочетание 10, 9, с которой мой способ не может справиться. И тут я вспомнил, что аналогичная ситуация возникнет в знаментий игре «15» *). Там передвижениями фище невозможно из положения на рисунке 3 перейти в положение на рисунке 4.

Идея доказательства этого факта основана на операции «транспозиция». Транспозиция неокоторой последовательности чисел называется переменами каких-либо двух из этих чисел. При этом доказывается, что если одна последовательность чисел получается из другой при помощи четного числа транспозиций, то невозможно добавиться того же результат с помощью нечетного числа транспозиций, и, наоборот, если последо-

*) В последнем издании учебника «Математика-5» (М., «Просвещение», 1976) эта задача фигурирует под номером 1249.

*) См. «Квант», 1974, № 2, c. 26.

3

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

Осталось выяснить, четному или нечетному числу транспозиций соответствует операция, описанная в задание. Перенос одного тома на новое место эквивалентен серий транспозиций: сначала с ближайшим томом, потом со следующим и т. д., пока он не встает на свое новое место. Точно так же перенос следующего тома эквивалентен серий транспозиций с теми же томами, что и в первом случае. Общее число транспозиций будет равно удвоенному числу транспозиций при перенос одного тома, поэтому наша операция эквивалентна четному числу транспозиций.

Следовательно, некоторые расстояний томов операций, указанной в задание, можно упорядочить, а другие — нельзя. В частности, расстояния 1, 2, 3, 4, 5, 6, 7, 8, 10, 9 получается из расстояний 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 нечетным числом транспозиций, и, следовательно, не может быть в нее переведена расстояния операций.

Обратите внимание, что в наших рассужdenях мы игнорize не пользователь тем, что томов 10. С тем же успехом эти рассужdenя можно проведении для любого другого количества томов.

А вот то, что мы переставли по два тома сразу, было очень существенно. Действительно, если мы переставли по одному тому, то при любой начальной расстоянии такой операцией мы смогли бы расставить тома по порядку. А если переставлять по три тома? А по четыре?…

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

4

Hy, a если переставить по три тома? Давайте попробуем! Сколько же для начала взять томов? Три — мало, возьмем четыре. Посмотрим, какие расстановки можно получить из расстановки по порядку: 1, 2, 3, 4 — из нее 2, 3, 4, 1 и 4, 1, 2, 3, из них 3, 4, 1, 2… и все! Такие перестановки называют циклическими, потому что они переставляют числа по кругу — если одну расстановку выписать по окружности, то любую другую можно прочитать, начав с некоторого места (рис. 5). Но никакие две из расстановок
1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
нельзя перевести друг в друга циклическими перестановками, а ведь каждой из них соответствует еще по три расстановки, получающей циклическими перестановками. Таким образом, все 24 различные расстановки чисел 1, 2, 3 и 4 (проверьте, что их 24) разбиаются на 6 групп по 4 расстановки в группе, причем нашей операцией мы не можем получить из расстановки одной группы расстановку другой группы.

Сохранить ли такое положение, если мы возьмем не четыре, а пять или большие томов? Оказывается, нет! Решающего роль здесь сыгает следующая последовательность расстановок:
1, 2, 3, 4, 5 → 1, 3, 4, 5, 2 → 4, 5, 2, 1, 3 → 2, 1, 3, 4, 5.

Переставляя по три тома, мыomenяли местами первый и второй тома, вернув на место остальные. Таким же образом мы можем переставить любые два соседних тома, причем не только, когда у нас пять томов, но и для любого большого числа томов. Действительно, если эти два тома — не последние, то взяв еще и следующий за ними том, переставим эту тройку томов вперед, затем помещаем местами первые два тома (как было показано) и снова

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

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

А что будет в случае перестановки по пять томов? По семь томов? Вообще по 2n + 1 тому? Решения этой проблемы я нигде не встречал.

Можно спроить: «А кому нужны эти перестановки?» Оказывется, нужны, и очень часто, например, теория перестановок играет важнейшую роль при решении вопроса — можно ли корни данного алгебраического уравнения *). Тем самым мы решили задачу M404 («Квант», 1976, № 9).

5

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

В «Кванте» про это уже расссказывалось, последний раз — в статьях «Группы» и «Алгебра — древняя и современная» («Квант», 1976, № 10). Если вы их читали, то сразу заметите, что рассматриваемые нами переменные томов — это подстановки, порождающие группу (правда, не всю группу подстановок $S_n$ — в этом и состоит problema), а перестановки по кругу четырех элементов образуют циклическую группу. может быть, теория групп вам и поможет (хотя, скорее всего, эта задача решается «комбинаторными» сообщениями).

Тепер, пожелав успеха тем, кто решил взяться за окончательное решение поставленной проблемы, пошем в учебнике еще интересные задачи.

Одно или больше?

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

Первое, что приходит в голову,— взять все числа равными 1. Такая четверка чисел действительное удовлетворяет условием задачи. А нет ли еще решений? Где-то я видел эту задачу. Открываю книжку И. Л. Бабинской «Задачи математических оптимизации» (М., «Нayka», 1975) и нахожу ее под номером 142. Ищу ответ. Читаю — «Например, 1, 2, 3, 7». Меня этот ответ неSTRAINЕТ. Для меня это то же самое, что ответ: «Например, 2» на вопрос: «Какие корни у уравнения $x^2 - 5x + 6 = 0?$».

Нет… где-то еще я видел подобную задачу. Ну конечно, «Сборник задач Московских математических оптимизации» (М., «Просвещение», 1965), с. 70, задача 215. Вот она.

215. Наименование троей чисел $a, b, c$, отличных от 1, что про

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

В ответе — единственный набор: 2, 3, 7.

Неправда ли, ответ очень похож на ответ интерсуошей нас задачи, хотя здесь редьет не о четырех, а о трех числах. А что будет для двух чисел? Для каких пар чисел сумма каждого из них с единицей делится на другое? Задча с четырьмя числами для пятиклассников, с темя — для учеников 7—10 классов… Оdnako наберемся смелости и присутствим к решению.

Если одно из этих двух чисел 1, то второе число должно быть делителем числа 2: либо 1, либо 2. Нетрудно проверить, что обе пары (1, 1) и (1, 2) удовлетворяют условиям задачи.

Пусть ни одно из чисел не равно 1. Тогда, очевидно, эти числа взаимно просты. Пусть $a < b$, тогда $a + 1 \leq b$, но $a + 1$ делится на $b$, следовательно, $a + 1 \geq b$. Отсюда вытекает, что $a + 1 = b$. А так как $b + 1$ делится на $a$, то $a + 2$ делится на $a$, следовательно, 2 делится на $a$, и поскольку $a \neq 1$, то $a = 2$, $b = 3$.

Итак, существует все три пары таких чисел, что сумма одного из них с единицей делится на другое: (1, 1), (2, 1), (3, 2).

Достаточно простое решение этой задачи наводит на мысли попробовать решить сразу общую задачу:

«Найти $n$ чисел таких, что произведение любых $n - 1$ из них в сумме с единицей делится на оставшееся».

Докажем две леммы.

Лемма 1. Пусть числа $a_1, a_2, \dots, a_n$ обладают тем свойством, что произведение любых $(n - 1)$ из них в сумме с 1 делится на оставшееся. Тогда, добавив к ним число $a_{n+1} = 1$, получим набор чисел, произведение любых $n$ из которых в сумме с 1 делится на оставшееся. И, наоборот, если среди $n + 1$ чисел есть 1 и произведение любых $n$ из них в сумме с 1 делится на оставшееся, то, убрав из

6

этоо набор единцу, получим набор из n чисел, произведение любых n — 1 из которых в сумме с единцией делится на остальные.

Формулировка леммы громоздка, а доказательство тривиально. Достаточно использовать тот факт, что от умножения числа на единцу это число не меняется, и то, что на единцу делится любое число.

Более содержательной является вторая лемма.

Лемма 2. Пусть числа $a_1, a_2, \dots, a_n$ обладают тем свойством, что произведение любых $(n-1)$ из них в сумме с 1 делится на остальные. Тогда, добавив к ним число $a_{n+1} = a_1 a_2 \dots a_n + 1$, получим набор чисел, произведение любых n из которых в сумме с единцией делится на остальные.

Для доказательства нужно проверить два утверждения.

Первое — то, что произведение первых n чисел в сумме с единцией делится на $a_{n+1}$ — следует из определения числа $a_{n+1}$.

Второе — для случая, когда число $a_{n+1}$ входит в произведение. Обозначим через $A_i$ произведение первых n — 1 чисел без $a_i$: надо показать, что $A_i a_{n+1} + 1$ делится на $a_i$. Для этого достаточно заметить, что $a_{n+1} = a_i A_i + 1$; тогда $A_i a_{n+1} + 1 = A_i (A_i a_i + 1) + 1 = a_i A_i^2 + (A_i + 1)$, и первое слагаемое делится на $a_i$, второе, заключенное в скобки, тоже—по предложению леммы.

Из этих лемм следует, что в задаче с тремия числа будут следующее решение: $(1, 1, 1), (1, 1, 2), (1, 2, 3), (2, 3, 7)$; в задаче с четырьмя числами $(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 3), (1, 2, 3, 7), (2, 3, 7, 43)$. Осталось выяснить, нет ли других решений.

Новые решения, содержащих единцы, при $n=3$, очевидно, нет (убрав одну из единцы, мы по лемме 1 получили бы новое решение задачи с двумя числами, а в ней других решений нет). Пусть теперь $(x, y, z)$ — некоТОРое решение задачи с тремия числами. Легко доказать, что любые два из этих чисел должны быть взаимно простыми. Пусть $2 \leq x < y < z$.

Запишем соответствия:

$$\begin{align*} xy + 1 &= k_1 z, \\ xz + 1 &= k_2 y, \\ yz + 1 &= k_3 x. \end{align*}$$

Здесь $k_1, k_2, k_3$ — натуральные числа. Переменная эти соответствия, получим: $xyz(xyz + x + y + z) + xy + yz + xz + 1 = k_1 k_2 k_3 xyz$.

Отсюда следует, что $xy + yz + xz + 1$ делится на $xyz$, т. е.

$$xy + yz + xz + 1 = Axyz,$$

где $A$ — натуральное число. Разделив обе части этого равенства на $xyz$, получим

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

Нибольшее значение $A$ получится при наименьших значениях $x, y, z$, т. е. при $x=2, y=3, z=4$ (на самом деле $z \geq 5$). Отсюда

$$A \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{2 \cdot 3 \cdot 4} = \frac{27}{24},$$

и, поскольку $A$ — натуральное число, то оно равно 1. Итак, нужно найти все натуральные числа $x, y$ и $z$ такие, что $2 \leq x < y < z$ и

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

Покажем, что $x=2$. Действительно, если $x \geq 3$, то $y \geq 4, z \geq 5$, следовательно,

$$1 = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xyz} \leq \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{3 \cdot 4 \cdot 5} = \frac{48}{60}.$$

Получили противоречение. Итак, $x=2$. Тогда соответствие записывается так:

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

Выразив отсюда $y$, получим

$$y = 2 + \frac{5}{z - 2}.$$

Значит, $z-2$ является делителем числа 5, т. е. $z=3$, или $z=7$. В первом случае $y=7$, во втором $y=3$.

Итак, $(2, 3, 7)$ — единственное решение задачи с тремия числами, не содержащие единцы, следовательно, равнее нами были выписаны все решения этой задачи.

Посмотрим, существует ли другие решения задачи с четырьмя числами.

7

Очевидно, и здесь достаточно рассмотреть лишь те решения, которые не содержат единицу. т. е. натуральные числа $x, y, z, u$ такие, что $2 \leq x < y < z < u$ и
$$xyz + 1 = k_1u,$$
$$xyu + 1 = k_2z,$$
$$xzu + 1 = k_3y,$$
$$yzu + 1 = k_4x,$$
где $k_1, k_2, k_3$ и $k_4$ — натуральные числа. Переменная эти соответствия, получим аналогично предыдущему случаю, что
$$xyz + uxy + xzu + yzu + 1 = Axyzu,$$
где $A$ — натуральное число, или
$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{u} + \frac{1}{xyzu} = A.$$
Поскольку $x \geq 2, y \geq 3, z \geq 4, u \geq 5$, то
$$A \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{2 \cdot 3 \cdot 4 \cdot 5} = \frac{31}{24},$$
следовательно, $A = 1$. Далее аналогично показывается, что $x=2, y=3$. Теперь
$$\frac{1}{z} + \frac{1}{u} + \frac{1}{6zu} = \frac{1}{6},$$
откуда
$$z = 6 + \frac{37}{u - 6}.$$
Значит, $u-6$ является делителем числа 37, т. е. либо $u=7, z=43$, либо $u=43, z=7$. Итак, снова получили лишь имеющиеся уже решения. Значит, и в этом случае были перечислены все решения.

Полученный результат нагляден нас на гипотезу, что и далее все решения задачи для $n$ чисел будут получаться из решения задачи для $n-1$ числа с помощью лемм 1 и 2. Увы! Гипотеза эта неверна, во всяком случае для $n-5$ — кроме решения (2, 3, 7, 43, 1807), получаемого с помощью леммы 2, есть еще одно: (2, 3, 7, 47, 395).

А что будет дальше? Будут ли решения задачи для большого количества чисел получаться применением лемм 1 и 2 к этим теперь уже двум решениями, не содержащим единицу, или появится еще одно или даже два? Пока это проблема.

Сколько делений?

Следующая задача «на смекалку» также фигурирует во многих книгах для школьников.

Рис. 6.

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

На рисунке 6 показано одно из решений этой задачи. Естественно попытаться выяснить, есть ли другие решения, но гораздо интереснее также вопросы: почему именно четыре деления? А если три? Какова наиболее длинна линейки, на котором нанеси 4 деления с выполненем указанным свойством? И вообще, какое наименьшее количество делений нужно нанеси на линейку длины $n$ (см), чтобы с ее помощью можно было отложить все целочисленные отрезки от 1 см до $n$ (см)?

Как всегда, начинаем с проб. Для линейки длины 1 см никаких делений не нужно. При длине в 2 см и

8

Рис. 7.

3 см достаточно одного деления. При длине в 4, 5, 6 см двух делений достаточно, а одного мало, при длине в 7, 8, 9 см надо три деления (двух не хватит), при длине в 10, 11, 12, 13 см — четыре деления (трех не хватит). Эти результаты получены перебором вариантов, соответствующие им расстановки изображены на рисунке 7, но с увеличением длины линейки становится все труднее и труднее проводить полный перебор. Нужны какие-то общее методы. Попробуем сперва оценить число делений (сверху и снизу).

Пусть на линейке длины $n$ (см) поставлено $k$ делений. Сколько существует различных отрезков (не отрезков разной длины, а просто различных отрезков) с концами в точках деления или на концах линейки? Так как любая пара из перечисленных точек определяет отрезок, а их $k+2$, то отрезков будет $(k+2)(k+1)/2$. А так как по условию задачи должно получить $n$ различных длины, а длинные некоторые отрезков могут и совпадать, то должно выполняться неравенство

$$n \geq \frac{(k+2)(k+1)}{2}.$$

Отсюда следует, что на отрезке длины $n$ необходимо поставить не менее $(\sqrt{8n+1}-3)/2$ делений (если это число не целое, то нужно быть близкой к нему больше целое число).

А какого количества делений наверняка хватит? Конечно, $(n-1)$-го хватит (можно нанести все сантиметровые деления), но нельзя ли обойтись меньшим числом?

Попробуем такую расстановку $k$ делений: сначала поставим $m$ делений через каждый сантиметр, затем деление через $(m+1)$ (см), снова через $(m+1)$ (см) и т. д., пока не поставим все $k$ делений. Расмотрим теперь линейку с правым концом в $(m+1)$ (см) от последнего деления. Длину этой линейки $l$ выразим через $k$ и $m$: $l = m + (k-m)(m+1) + m+1 = -m^2 + m(k+1) + (k+1)$.

Используя формулу деления с остатком $s = p(m+1) + q$, нетрудно показать, что при любом $m$ также расстановка делений удовлетворяет условию задачи.

Отметим еще одно важное свойство такой расстановки делений — если отрезок укоротить справа на любое целое число сантиметров, то точки деления по-прежнему будут удовлетворять