14, 15, 10, 6, 7, 11, 15, 10, 13, 9,
5, 1, 2, 3, 4, 8, 12, 15, 10, 13,
9, 5, 1, 2, 3, 4, 8, 12, 15, 14,
13, 9, 5, 1, 2, 3, 4, 8, 12.
Магический квадрат с суммою 30 получается ряда ходов:
12, 8, 4, 3, 2, 6, 10, 9, 13, 15,
14, 12, 8, 4, 7, 10, 9, 14, 12, 8,
4, 7, 10, 9, 6, 2, 3, 10, 9, 6,
5, 1, 2, 3, 6, 5, 3, 2, 1, 13,
14, 3, 2, 1, 13, 14, 3, 12, 15, 3.
Приведем замечание немецкого математика Шуберта о числе возможных задач при «игре в 15».
«Сколько всего возможно задач; т. е. сколько различных расположений можно дать 15 шашкам, причем каждый раз пустое поле расположено справа внизу? Чтобы определить, сколько перестановок можно получить с помощью 15 предметов, начнем с 2-х предметов: а и b. Они могут дать лишь две перестановки, именно - ab и Ьа. При трех предметах имеется уже втрое больше перестановок, т. е. 6, так как предмет а может быть поставлен перед Ьс и перед cb, и кроме того, имеются еще две перестановки, начинающиеся с b, и две начинающиеся с с. Отсюда можно заключить, что четыре предмета а, b, с, d могут дать вчетверо большее число различных перестановок, т. е. 4x3x2 = 24 перестановки. Продолжая так, можно найти, что 15 шашек допускают всего
2x3x4x5x6x7x8x9x10x11x12x13x14x15
перестановок. Вычислив это произведение, мы найдем для числа задач игры внушительное число:
1 биллион 307674 миллиона 368000».
Из этого огромного числа задач ровно половина принадлежит к разрешимым и столько же - к неразрешимым. Заметим еще, что если бы возможно было ежесекундно давать шашкам новое положение, то чтобы перепробовать всевозможные расположения, потребовалось бы, при непрерывной работе круглые сутки, - свыше 40.000 лет.
Странная задача на премию
Проф. Г. Симона
Ряд лет тому назад в Берлине подвизался искусный счетчик, предлагавший публике такую задачу (переделываем ее на русский лад):
«Кто сможет уплатить 5 рублей, 3 рубля или 2 рубля полтинниками, двугривенными и пятаками, всего 20-ю монетами, - тому будет выдано наличными деньгами сто рублей».
Посетителям вручались необходимые монеты, - конечно, заимообразно. Но обещанная сотня рублей должна была остаться навсегда в руках счастливца, которому удалось бы решить задачу.
Разумеется, пол-Берлина потело над разрешением этой задачи (стояли как раз жаркие июльские дни), казавшейся не особенно трудной. Сто рублей хорошо пригодились бы всем, значит - стоит потрудиться. По мере того, как выяснялась бесполезность попыток, физиономии решавших вытягивались и розовые мечты о заманчивой награде испарялись. Надежды оказывались обманчивыми. Ловкий счетчик мог безбоязненно обещать в десять раз большую награду. Никто не в праве был бы на нее притязать, ибо задача требует невозможного.
Как в этом убедиться?
Нам не понадобится глубоко забираться в дебри алгебры, но все же не будем бояться х, у и z.
Рассмотрим сначала, можно ли уплатить требуемым образом пять рублей. Пусть для этого нужно х полтинников, у - двугривенных и z - пятаков. Сумма их должна составить 500 копеек, т. е.
50x + 20y + 5z = 500,
или, разделив на 5,
10x + 4y + z = 100.
Это легко осуществить на разные лады. Если, например, взять х = 8, то будем иметь
80 + 4y + z = 100,
или
4y + z = 20;
последнему уравнению можно удовлетворить, если принять z = 4, или 8, или 12, или 16 и, следовательно (при z = 4), 4у = 16, у = 4. Действительно, 8 полтинников, 4 двугривенных и 4 пятака составляют 500. Однако при этом не выполнено условие употребить в общей сложности 20 монет: мы употребили 8 + 4 + 4 = 16 монет. К нашему первому уравнению
10x + 4y + z = 100
необходимо, следовательно, присоединить второе
x + y + z = 20.
Соединяя их в одно, посредством вычитания второго из первого, мы освобождаемся от z и получаем
9х + 3у = 80;
теперь сразу становится очевидным, что не может быть таких целых чисел, которые удовлетворили бы этому уравнению. Потому что 9 раз х, каково бы ни было х, есть непременно число кратное 3; то же верно для числа 3у; следовательно, сумма 9х + 3у должна делиться без остатка на 3, то есть никак не может равняться 80.
Задача приводит к противоречивому требованию, и значит - ее решение невозможно.
Совершенно так же невозможно и составление требуемым образом сумм в 3 рубля и в 2 рубля. В первом случае, как каждый легко может убедиться, получается уравнение:
9х + 3у = 40;
во втором:
9x + 3y = 20.
Оба равенства невозможны, так как ни 40, ни 20 не делятся без остатка на 3.
Сказанным задача собственно исчерпывается. Но поучительно присоединить к ней рассмотрение вопроса, какие же суммы можно этими 20-ю монетами в самом деле уплатить, - разумеется так, чтобы получилось целое число рублей.
Если обозначим это число рублей через т, то у нас будет уравнение
50x + 20y + 5z = 100m,
или
10x + 4y + z = 20m,
при условии, что
x + y + z = 20,
откуда путем вычитания имеем:
9x + 3y = 20m-20 = 20 (m-1).
Так как 9х + 3у кратно 3, то и 20 (m-1) должно быть кратно 3.
Но 20 не делится на 3, так что кратным 3 должно быть только m-1.
Если m-1 равно 0, 3, 6, 9, 12 и т. д., то т должно быть на 1-цу больше, т. е. одно из чисел: 1, 4, 7, 10, 13 и т. д. Только такие суммы рублей могут быть уплачены нашими 20-ю монетами. Но очевидно, что 10 рублей - наибольшая сумма, так как 20 полтинников составляют уже 10 рублей. Принимая поэтому только четыре возможных суммы - в 1 р., в 4 р., в 7 р. и в 10 р., имеем четыре случая:
9х + 3у-20(m-1) = 0, или 60, или 120, или 180,
другими словами
3х + у = 0, или 20, или 40, или 60.
Только эти случаи и надо рассмотреть.
1) Один рубль. 3х + у = 0.
Это равенство возможно лишь тогда, когда и х, и у равны нулю, так как, приняв для них даже наименьшее целое число 1, получим 4, а не 0. Единственное решение для этого случая, следовательно, есть х = 0, у = 0, а потому z = 20, то есть один рубль можно уплатить, только употребив 20 пятаков.
Рассмотрим теперь другой крайний случай:
2) Десять рублей. 3х + у = 60.
Так как у должно быть кратно 3 (иначе сумма его с 3x не делилась бы без остатка на 3), то примем y = 0, 3, 6… Для случая у = 0 имеем х = 20 и z = 0. Это дает нам уже упомянутое решение: 20 пятаков. Но оно и единственное, потому что для у = 3 имеем х = 19, и х + у превышает высшую сумму 20.
3) Четыре рубля. 3х + у = 20.
Принимая
х = 0, 1, 2, 3, 4, 5, 6, 7, 8…,
получаем, что
y = 20-3x = 20, 17, 14, 11, 8, 5, 2, -1, -4…
Имеют смысл, очевидно, только первые семь значений. Им соответствуют
z = 0, 2, 4, 6, 8, 10, 12.
Четыре рубля можно, как видим, уплатить 7-ю различными способами, например: 6 полтинниками, 2 двугривенными и 12 пятаками.
4) Семь рублей. 3х + у = 40.
Здесь не приходится рассматривать значения для х от 0 до 9, так как при этом для у получаются числа от 40 до 13, и х + у составляет по меньшей мере 22, что нарушает требование. Остается рассмотреть поэтому лишь случаи:
x = 10, 11, 12, 13,
причем
у = 40-3х = 10, 7, 4, 1,
z = 0, 2, 4, 6.
Остальные случаи исключаются, так как ближайшее у уже отрицательное.
Этим вопрос исчерпывается полностью. Кто хотя немного имел дело с уравнениями, тот заметил, вероятно, что здесь не приходится оперировать так механически, как обычно. Это от того, что мы имеем в нашем случае больше неизвестных, нежели уравнений, а именно - 3 неизвестных при 2 уравнениях. Неизвестное z мы устранили и получили одно уравнение с двумя неизвестными х и у. Поэтому задача становится неопределенной; можно лишь установить взаимную обусловленность чисел х и у, так что для любого х можно найти соответствующее значение у. В сущности, имеется бесконечное множество пар решений задач такого рода. Но число их ограничивается требованием, вытекающим из сущности задачи, а именно: либо чтобы искомые числа были целые (как в нашей задаче, где речь идет о монетах), либо чтобы они не были отрицательные (наш случай), либо чтобы их сумма не превышала определенного числа (у нас - 20-ти), и т. п.
Итак, возвращаясь к первоначальной задаче, скажем: счетчик мог безопасно посулить сколь угодно большую награду - задача неразрешима. Для вас тем самым открывается легкая возможность предлагать своим друзьям крепкие головоломки. Можете обещать им величайшую награду - не попадетесь: как истые математики, вы можете быть твердо уверены в себе. А кто пожелал бы узнать подробнее об уравнениях в роде рассмотренных выше, - пусть спросит своего учителя математики о Диофанте Александрийском.
Примечание редактора
ДИОФАНТ АЛЕКСАНДРИЙСКИЙ
Упомянутый в конце очерка александрийский математик Диофант жил в III веке нашей эры. Им написана была «Арифметика», от которой до нас дошла только первая половина сочинения. В этом труде рассматриваются, между прочим, неопределенные уравнения, которые Диофантом и были впервые введены в математику; поэтому имя его осталось навсегда связанным с этими уравнениями.
О жизни Диофанта известно лишь то, что сообщается в надписи, сохранившейся на его могильном памятнике, - надписи, которая составлена в форме следующей задачи:
