Такой невероятный турнир...

39

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

Встреча первая
11 марта, 8 часов утра
Они ежедневно ходили по одной и той же тихой улице — ученик селього класса Саша Тихомиров и учитель математики Георгий Данилович Селиванов. Они давно зали друг друга, а с прошло года Саша стал ходить в городской математический кругок, который руководил Георгий Данилович. Сегодня, увидев Сашу, учительpointerсовался:
— Ну как, отослал ты уже вступительно контрольную работу в Заочную школа? Ведь срок истекает 20 марта *).
— Нет еще, — ответил Саша, — из 11 задачи я пока решил 10, а самую первогоника кешить не могу.
— Что же это за коварная задача?
Саша извлек из своего портфеля журнал «Квант» № 1 за 1974 год, раскрыл его на 73 странице и стал читать.
«Задача 1. Три друга сырали некоторое число партий в шахматы, причем каждый сырал с каждым одинаковое число партий. Помом стали решать, кто победил. Первый сказал: «У меня больше, чем у каждой из вас, вывершей». Второй сказал: «У меня меньше, чем у каждой из вас, произвлечей». Но когда подсчитали очки, то оказалось, что больше всего окновен набрал премей (вызеры — 1 очко, ничья — 1/2 очка, произвлечей — 0). Модел ли макое быть? Если нет, то доказите; если да, то приведите пример.»
— Любопытная задача! — сказал Селиванов. — Знаешь, ведь и я сразу не виду, как ее решить. Зайди ко мне сегодня вечером, подумаем над него вместе.

*) Имеется в виду Всегоизная Заочная математическая школа (ВЗМШ).

40

Встреча вторая
11 марта, 19 часов
Усевшись подобнее в «свое» кресно в комнате Селиванова, Саша рассказывает.

— Я рассматривал конкретные случаи, когда каждый из ребят сыграл с каждым из остальных по 2, 3, 4, 5 партий. Но так, как требуется в условиях задачи, у меня ни разу не получилось.

— Но, быть может, — размышлял всуху учитель, — это получится при большем числе партий?

— Возможно, — вздохнул Саша. — Говорят, кто-то перебал 237 вариантов возможных туриров, пока не наткнулся на требуемый. Но разве перебор вселупю—это решение? Должна же математика подсказать более умный путь! А как его найти? Я даже не знаю, с чего начать.

— Видим ли, один из первых вопросов, который полезно поставить себе при решении любой задачи, такой: «Что в задаче ищется?». Как бы ты на него ответил?

— Ищется… — Саша пожал плечами. — Ищется довольно необучная вщь: турир.

— Верно. А вот другой важный вопрос: «Нельзя ли свести решение задачи к понску каких-то чисел?»

— Вроде бы я могу это сделать,— сказал. Саша. — Чтобы восстановить вить турир, мне надо узнать, сколько всего партий первый выиграл у каждой из двух остальных, сколько партий он каждому из них проиграл, сколько сыграл с каждым вничью. Вот уже 6 неизвестных. И, пожоже, также же неизвестные надо ввести и для второго и третього… Набирается 18 неизвестных! Многоvatо…

— А нельзя ли все эти неизвестные «собрать в одну горсть», раздумывал всуху учитель. — Хорошо бы их представить себе наглядно, изобразить на схеме…

— Это я могу, — сказал Саша. — Недавно мы с Колей и Витей сыграли друг с другом по две партии, и получились вот такая итоговая таблица (см. табл. 1). Я по одной партии выиграл у каждой из них, в таблице это обозначено «+1», и по одной париграл, это обозначено «—1». А числоничих мы обозначали знаком равенства, вот в таблице стоит «=2», — это Коля с Витей обе партии сыграли вщь. И в нашей задаче можно составить похожую таблицу (см. табл. 2), в каждой строке которой записаны нужные нам сведения об игре — сколько партии и кому он проиграл, сколько выиграл, сколько свел вщь. Правда, все эти числа неизвестны и обозначены буквами. Например, второй игрок выиграл у третьего с партий, проиграл ему f партий, а k партий сыграл с ним вщь. А

| | Саша | Коля | Витя | Итого | очков |
| :— | :— | :— | :— | :— | :— |
| Саша | | +1 -1 =0 | +1 -1 =0 | +2 -2 =0 | 2 |
| Коля | +1 -1 =0 | | +0 -0 =2 | +1 -1 =2 | 2 |
| Витя | +1 -1 =0 | +0 -0 =2 | | +1 -1 =2 | 2 |

Табл. 1.

Табл. 2.

41

ведь неизвестных оказывается не 18,
а только девять!
— Хорошая схема, — одобрил
таблицу Георгий Данилович, — Что
же ты дальше намерен делать?
— Подобрать числа $a, b, \dots, k$
так, чтобы выполнялись все условия задачи. А, может быть, такого
набор чисел нет? Тогда как это доказать? Нясно…
— А что тебе известно об исключых
числах? Нельзя ли это записать в
виде уравнения или неравенства? Подумай над этим дома, и давай встретися завтра.

Встреча третья
12 марта, 19 часов
— Я заполил дома пустые клетки
в таблице 2, — сказал Саша, — и из
условия задачи получились неравенства

$$\begin{cases} a+b>c+d, \\ a+b>e+f, \\ a+f<d+e, \\ a+f<b+c, \\ e+\frac{1}{2}h+f+\frac{1}{2}k> \\ >a+\frac{1}{2}g+b+\frac{1}{2}h, \\ e+\frac{1}{2}h+f+\frac{1}{2}k> \\ >d+\frac{1}{2}g+c+\frac{1}{2}k. \end{cases}$$

— И это все? — спросил учитель.
— Нет. Если обозначить через $n$ число партий, сыгранных каждой
игроком с каждой из остальных, то еще
$$a+d+g=b+e+h=c+f+k=n.$$

Причем все эти 10 чисел — целые и
неотрицательные. С помощью по-
следних равенств мне удалось изнезить из неравенств $g, h$ и $k$. Получилась такая система:

$$\begin{cases} a+b-(c+d)>0, \\ a+b-(e+f)>0, \\ d+e-(a+f)>0, \\ b+c-(a+f)>0, \\ d+2e+f-(a+2b+c)>0, \\ a+2f+e-(b+2c+d)>0, \\ a+d+g=b+e+h= \\ =c+f+k=n. \end{cases}$$

— Как же ты станешь ее решать?
— Дажке не представляю себе. Ведь
в школе мы такое не проходили.
— А нельзя ли свести данную задачу к другой, более простой?
— А что значит «более простой»? Чтоы неравенства стало меньше? Или
чтоы неизвестных в неравенствах стало меньше?
— Пожалуйста.
— Ну, вот первые шесть строк — это шесть неравенств с шестью неизвестными. Если решить эту систему, то есть найти $a, b, c, d, e, f$, то в последних равенствах можно положить $n$ равным достаточно большому натуральному числу и найти $g, h$ и $k$. Значит, надо решить лишь система из шести неравенств с шестью неизвестными.
— А нельзя ли упрощить неравенства введением новых неизвестных?
— Попробую. В первое неравенство входят четыре неизвестных. А было бы, наверное, проще иметь дело только с двумя. И пожая картина в других неравенствах. Положу-ка я

$$\begin{cases} a+b=x, \\ c+d=y, \\ e+f=z, \\ a+f=t, \\ d+e=u, \\ b+c=v. \end{cases}$$

Тогда неравенства системы (1) станут проще:

42

А можно еще упростить, ввести неизвестные… зге, их будет всего четыре:

$$\begin{cases} x - y > 0, \\ x - z > 0, \\ u - t > 0, \\ v - t > 0, \\ z + u - (x + v) > 0, \\ z + t - (y + v) > 0. \end{cases}$$

А можно еще упростить, ввести неизвестные… зге, их будет всего четыре:

$$\begin{cases} x - y = \alpha, \\ x - z = \beta, \\ u - t = \gamma, \\ v - t = \delta, \end{cases}$$

и тогда система (3) примет вид

$$\begin{cases} \alpha > 0, \\ \beta > 0, \\ \gamma > 0, \\ \delta > 0, \\ \gamma - (\beta + \delta) > 0, \\ \alpha - (\beta + \delta) > 0. \end{cases}$$

А подбрать решение системы (5) — это нам запросо, — весело закончил Саша.

— Как так: запросо?
— Вот посмотрите, Георгий Данилович. Ведь можно за числа β и δ взять любые натуральные числа, скажем, единцы, а затем взять немного бóльшие γ и α… тройки.
— Да, можно. А что дальше?
— Дальше я найду x, y, z, u, t, v из системы (4), а потом из системы (2) найду a, b, c, d, e, f. Решить ее — дело пусташное.
— Допустим, — сказал учитель. — Хотел бы я посмотреть, какой получится результат. Занесим его завтра.

Встреча четвертая

15 марта, 19 часов
— Видите ли, — начал Саша смешенно, — система (4) вроде бы простенькая, но неизвестные из нее не находятся. Уравнение всего четыре, а неизвестных шесть, и найти их не удается.

— Да, такие системы называются «неопределенными», потому что неизвестные из них однозначно не находятся. У таких систем есть или бесконечно много решений, или ни одного.

— Зачем мне «бесконечно много»? Мне хватит и одного. Может, взять произвольно x и t? Тогда система можно будет решить?

— Ну, во всяком случае у тебя будет четыре уравнения и четыре неизвестных в системе (4). Но удаться ли после этого решить систему (2)? Пока я советую тебе послать в Заочную шкалу решения остальных 10 задач, ведь они же пишут, что не обязаательно решить все задачи.

Встреча пятая

21 марта, 19 часов
— Георгий Данилович! У меня получается какая-то ерунда!
— А в чем дело?
— Я положил x=4, t=1. Но тогда при β=δ=1 и α=γ=3 из системы (4) получается y=1, z=3, u=4, v=2. Система (2) принимает вид

$$\begin{cases} a + b = 4, \\ c + d = 1, \\ e + f = 3, \\ a + f = 1, \\ d + e = 4, \\ b + c = 2. \end{cases}$$

Вертел я ее и так, и этак, — не решается! Тогда я попробовал найти сумму всех шести неизвестных. Сложил первый уравнение, получил a+b+c+d+e+f=8.

А сложил последнее три, получил a+b+c+d+e+f=7.

Так же не было! Значит, система

43

(6) не имеет решений, и требуемого турнира не могло быть! А как же говоря, что кто-то нашел его?

— Ну, ты не совсем прав. Система (6) действительно не имеет решений; но ты же выбрал x и t совершенно произвольно. Можно быть, их надо подбирать более осторожно?

— А как же их подбирать? Ведь уравнения у меня больше нет.

— Почему же? У тебя получилось, что должно быть x+y+z=t+u+v. А, может быть, есть еще какие-нибудь соответствия?

— А как же искать такие соответствия?

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

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

— Ну что же, давай подумаем вместе. Зачем нам решать систему (4) при слуайном наборе чисел x, t, α, β, γ, δ? Не лучше ли выразить из нее, скажем, y, z, u, v через x, t, α, β, γ, δ, подставить их в систему (2) и решать ее методом исключения неизвестных? Скоро у тебя каникулы, времени будет много, попробуй. А пока отложи эту задачу и готовся к контрольным.

— Хорошо, я так и сделаю.

Встреча шестая

3 апреля, 14 часов

— Георгий Данилович! Я нашел, — договоря учитель, кричал Саша. — Я решил эту задачу!

— И какой же ответ?

— Такое могло быть! Вот турнирная таблица (см. табл. 3). И, наверное, она не единственная возможность.

— Как же ты ее нашел?

— А я решил сначала не искать f, временно считать его известным, а потом подобрать. Кроме того, уравнение, которое мы с вами нашли — x+y+z=t+u+v, дает после подстановки (из системы (4))

3x=3t+α+β+γ+δ, откуда

x=t+\frac{1}{3}(\alpha+\beta+\gamma+\delta),

и ясно, что сумма в скобках должна делиться на три. А дальше последовательно из четырого, первого, шестого, второго и пятого уравнений системы (2), использует (4), я нашел:

$$\begin{align*} a &= t-f, \\ b &= x-a = \frac{1}{3}(\alpha+\beta) + \gamma+\delta) + f, \\ c &= v-b = t-\frac{1}{3}(\alpha+\beta) + \gamma+\delta) - f + \delta, \\ d &= y-c = \frac{2}{3}(\alpha+\beta) + \gamma+\delta) - \alpha-\delta + f, \\ e &= u-d = t-\frac{2}{3}(\alpha+\beta) + \gamma+\delta) - f + \alpha+\delta + \gamma. \end{align*}$$

После этого я подобрал такие натуральные числа α, β, γ, δ, t, f, чтобы числа a, b, c, d, e были целыми и неотрицательными. Я положил α=5, β=1, γ=4, δ=2, t=10, f=2.

Табл. 3.

44

А затем взял $n=18$ и из равенств системы (1) нашел
$$g=7, h=1, k=10.$$
Вот и все!
— Да, все верно, — улыбнул Георгий Данилович. — Только я был положил $n=17$ и уменьшил числочных. Ведь $h$ может равнять и нулю!

«Еще раз — и лучше!»
(Д. Пойа)

Они вернулись к задаче «о трех шахматистах» через полтора года, когда обдумывали очередное занятие математического кружка. Саша готовил сообщение об общих приемах поиска решения задач. Просмотрев старое решение, они задумались над следующей задачей: указать способ нахождения в секс турниров, удовлемворяющих условий задачи 1.
— Эта задача, — заметил Саша, — оченьно, равносильно такой: указать способ нахождения в секс турниров, удовлемворяющих условий задачи (1).
— Разумеется, — подтвердил Георгий Данилович.
— Меня одно обстоятельство смущает в старых наших рассуждениях, — продолжал Саша. — Мы вошли в вспомогательные неизвестные $x$, $y$ и $t$. Д., а потом от них освобождались. А что если сразу от них освобождаются? Тогда, например, вместе неравенства $a+b-(c+d)>0$ мы сразу получим равенство $a+b-(c+d)=\alpha$. И точно так же — с остальным неравенствами системы (1).
— Хорошая идея, — сказал учитель. — Воспользовся его, чтобы дать на занятии кружка компактное окончательное решение задачи.
…Вот это решение.
«Задача сводится к нахождению всех возможных наборов из десяти целых неотрицательных чисел
$$a, b, c, d, e, f, g, h, k, n, (*)$$
удовлемворяющих системы (1) (здесь Саша расскаал, как именно она сво-

дится, мы этот рассказ не приводим).
Запишем ее в виде системы управления
$$\begin{cases} a+b-c-d & =\alpha, \quad (8_1) \\ a+b & -e-f =\beta, \quad (8_2) \\ -a & +d+e-f =\gamma, \quad (8_3) \\ -a+b+c & -f =\delta, \quad (8_4) \\ -a-2b-c+d+2e+f =p, \quad (8_5) \quad (8) \\ a-b-2c-d+e+2f =q, \quad (8_6) \\ g=n-a-d, \quad (8_7) \\ h=n-b-e, \quad (8_8) \\ k=n-c-f \quad (8_9) \end{cases}$$

и будем искать ее решения в целых неотрицательных числах при натуральных $\alpha, \beta, \gamma, \delta, p, q$. Сначала решим систему первых шести уравнений относительно $a, b, c, d, e, f$.

Складывая почленно уравнения (8$_2$) и (8$_4$) и вычитая эту сумму из уравнения (8$_3$), получаем
$$-a-2b-c+d+2e+f=\gamma-(\beta+\delta),$$
а вычитая эту сумму из уравнения (8$_1$), получаем
$$a-b-2c-d+e+2f=\alpha-(\beta+\delta).$$
Сопоставляя эти два уравнения с (8$_5$) и (8$_6$), видим, что для совместности системы (8) необходимо выполнение равенств
$$\gamma=\beta+\delta+p, \alpha=\beta+\delta+q,$$
и тогда уравнения (8$_5$) и (8$_6$) будут следовать уравнения (8$_1$) — (8$_4$). Из этих четырех уравнений можно выразить как une-lюб четые из шести неизвестных $a, b, c, d, e, f$ через два других и свободные члены. Заметим еще, что из уравнения (8$_5$) и (8$_6$) следует
$$-b-c+e+f=\frac{p+q}{3},$$
откуда видно, что число $s=\frac{1}{3}(p+q)$ — натуральное, причем $q<3s$, $p=3s-q$. Тепер выразим $a, b, d, e$ через $c, f, \beta, \delta, q, s$ (исключением переменных). Получим

45

$$a = c + \beta + s, \quad (9_1)$$
$$b = f + \beta + \delta + s, \quad (9_2)$$
$$d = f + \beta + 2s - q, \quad (9_3)$$
$$e = c + \beta + \delta + 2s. \quad (9_4)$$

Видно, что $b + e > a + d > c + f$, то есть $k > g > h$. Тепер из уравнения $(8_8)$

$$n = c + f + h + 2\beta + 2\delta + 3s, \quad (9_5)$$

и из $(8_7)$ и $(8_9)$

$$g = h + 2\delta + q, \quad (9_6)$$
$$k = h + 2\beta + 2\delta + 3s. \quad (9_7)$$

Итак, если целые неотрицательные числа () удовлетворяют системе (1), то существует такой набор целых неотрицательных чисел $\beta, \delta, s, q, c, f, h$ ($\beta > 0, \delta > 0, s > 0, 0 < q < 3s, q \leqslant f + \beta + 2s, c \geqslant 0, f \geqslant 0, h \geqslant 0$), что числа () связаны с ними соответствиями (9).

Обратно, нетрудно убедиться (например, неосредственной подстановкой), что при любом выборе целых чисел $\beta, \delta, s, q, c, f, h$, удовлетворющих перечисленным условиям, числа (*), определяющие формулики (9), будут удовлетворять системе (1). Следовательно, при всевозможных таких наборах «параметров» $\beta, \delta, s, q, c, f, h$ получаются все решения задачи о трех шахматистах.

— Хороше решение трудной задачи, — сказал учитель. — Но «все концы тщательно опущены вводу». Как же ты договора, что два уравнения в системе — следствия остальных, что следует сложить уравнения $(8_5)$ и $(8_6)$ и найти $\frac{1}{3}(p + q)$?

— Про себя, — ответил Саша, — я все время имел в виду те рассуждания, которые были ранее проведены при поиске решения. Вы посмотите: сейчас я неоторое выражение — левую часть пятого неравенства системы (1) — обозначил через $p$; а раньше, в ходе поиска частного решения, я ведь уже работал с тем же самым выражением (см. (1), (3), (5)) и видел, что оно равно $\gamma - (\beta + \delta)$; значит, должно быть: $\gamma - (\beta + \delta) = p$.

В ходе решения я и показываю справадивость этого равенства, минуты выкладки, ненужные для окончательного решения. Так же обстоит дело и с равенством $\alpha = \beta + \delta + q$. Кроме того, в ходе поиска решения я встретил выражение $\frac{1}{3}(\alpha + \beta + \gamma + \delta)$ (см. (7)), которое должно быть натуральным числом. Но это выражение равно $\beta + \delta + \frac{1}{3}(p + q)$. Значит, $\frac{1}{3}(p + q)$ должно быть целым числом. А чтобы показать это в ходе окончательного решения, я и сложил почленно равенства $(8_5)$ и $(8_6)$.

— Ну, а почему ты выбрал в качестве «свободных переменных» $f$ и $c$, а не, скажем, $a$ и $b$?

— Я имел перед глазами системы (7), полученную в ходе поиска: если в ней освободится от лишнего переменного $t$ (например, учеть, что $t = a + f$, и поставить это выражение в остальные равенства (7)), то сразу видно, что удобно выбрать за «свободные переменные» $f$ и $c$.

Оглядываясь на понск, проведенный Сашей, мы можем выделить те вопросы:

1. «Что в задаче ищется?»
2. «Нельзя ли свести задачу к понску каких-то чисел?»
3. «Что извесно из формулировки задачи об исключах? Нельзя ли это запись в виде уравнения или неравенства?»
4. «Нельзя ли свести данную задачу к другой, более простой?»
5. «Нельзя ли улучшить решение (получить более простое или более компактное решение, решить более общую задачу и т.п.)?»

Вопросы для размышления

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