Олимпийские хиты. Часть 3

        Когда я диктовал своей хорошей знакомой, учительнице высшей категории, заслуженной учительнице Кубани по телефону числа окончательного решения, то она лишь удивлённо восхищалась! Сам по себе набор цифр казалось, не вписывается ни в какую разумную логическую схему. Она тут же спросила:

- Ну и как ты это получил?

- А это уже, извини, не по телефону!

Речь шла об одной из олимпиадных заданий ВЗМШ МГУ 2006 г.

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

       Когда к тебе – простому частному преподавателю, обращаются столь уважаемые авторитеты современного образования, это, конечно, мгновенно окрыляет и придаёт уверенность и силы. Но когда задача не получается с лёту, когда просто сбиваешься на «тупой» перебор вариантов, не дающий ощутимых результатов, тогда легко впасть в отчаяние и уныние. Только позже осознаешь, что любой поиск, так, или иначе, пробивает шахту в подкорку. И только в награду за желание решить и за затраченные усилия Бог посылает тебе яркую, простую ключевую идею. А дальше – дело техники. Дальше ты уже можешь спокойно развивать эту идею, наслаждаясь  не блужданием в потёмках, а вполне осознанным, логичным, творческим поиском. Ловлю себя на мысли о том, как часто уже писал в предыдущих тетрадях, примерно  то же самое. Ничто не ново под Луной! И как же приятно спокойно, не торопясь записывать свои выстраданные, иногда просто вымученные решения! И не важно, что кто-нибудь над этими размышлениями просто посмеётся. Для кого-то эта задача будет не стоящим внимания пустяком. Важно, что сам ты о ней думаешь. И важно верить, что объяснение решения обязательно кому-нибудь пойдёт на пользу!

       Пора рассказать и о ключевой идее. Рассмотрим прямоугольную таблицу 4*3 (4 строки, 3 столбца). Выбор числа из каждой тройки будим обозначать цифрой 1 в соответствующей строке. Например:

Это означает, что из первой тройки выбрано первое число, из второй – второе, из третьей – третье, из четвёртой – второе. То есть в любой момент в каждой строке единицей занята лишь одна клетка. Зададим себе простой, детский вопрос: Сколько существует комбинаций таких наборов единиц? Каждую единицу, в каждой строке можно, независимо от других строк, выбрать тремя способами. Следовательно, число всех возможных комбинаций равно: 3*3*3*3 = 3⁴ = 81. Но ведь 81 – это и есть наибольшее число, которое нужно представить в виде суммы в данной задаче! Представление чисел в таблице и ответ на вопрос – это, в данном случае и есть основная, ключевая идея исследовательского поиска. Теперь самое главное –  найти способ последовательного перечисления каждой из 81 комбинаций. И когда такой способ нашёлся, то составление таблицы прошло просто, логично и убедительно. Как перечислить все комбинаций можно понять из следующей таблицы. Сначала передвигаем последовательно единицу в нижней строке. Как только она доходит до края, то на следующем шаге она возвращается в начало строки, а единица следующей, верхней строки перемещается на одну клетку вправо. После этого снова передвигается нижняя единица, пока не дойдет до края. И так далее, до перечисления всех комбинаций из 81. Числу 81 будет соответствовать заполненный единицами последний, третий столбик.

Начнём последовательное заполнение таблицы троек чисел. Число 1, естественно равно 1 + 0 + 0 + 0. Далее: 2 = 1 + 0 + 0 + 1; 3 = 1 + 0 + 0 + 2; 4 = 1 + 0 + 3 + 0. Тогда, первые несколько клеток таблицы заполняются следующим образом.

Эта таблица позволяет однозначно представить в виде суммы числа от 1 до 6. Причём 6 = 1 + 0 + 3 + 2. Тогда клетку третьей строки и третьего столбца или, коротко, клетку (3;3), надо заполнить так, чтобы получить представление числа 7. Мы этого добьёмся, поставив в клетку (3;3) число 6. Тогда 7 = 1 + 0 + 6 + 0; 8 = 1 + 0 + 6 + 1; 9 = 1 + 0 + 6 + 2. Теперь, чтобы получить представление в виде суммы числа 10, надо клетку (2;2) заполнить числом 9, тогда: 10 = 1 + 9 + 0 + 0. Легко убеждаемся в том, что следующее заполнение таблицы позволяет сделать однозначное  представление в виде суммы любого натурального числа от 1 до 18.

18 = 1 + 9 + 6 + 2. Пора заполнить клетку (2;3). Следующее число 19, поэтому в клетку (2;3) ставим 18, тогда 19 = 1 + 18 + 0 + 0.

Наибольшее число, которое можно представить в виде суммы с помощью заполненной на данный момент таблицы, равно: 1 + 18 + 6 + 2 =  27. Поэтому клетку (1;2) заполняем числом 28, тогда 28 = 28 + 0 + 0 + 0. В результате мы сможем однозначно представить в виде требуемой суммы уже любое натуральное число от 1 до 28 + 18 + 6 + 2 = 54. Поэтому в клетку (1;3) ставим число 55 и задача полностью решена! Окончательная таблица имеет следующий вид:

Но это ещё далеко не всё! Теперь, поумневшим усвоенными идеями читателям, надеюсь, не составит труда решить следующую задачу:

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

Кроме того, решение данного задания даёт отличный повод для знакомства с функцией «Сумма Произведений» из процессора EXCEL, играющая важную роль в решении  задач оптимизации.

Рис. 1. Интерактивная версия решения задачи. Фрагмент «Число по коду».

На рис. 1. показан фрагмент интерактивной версии решения данной задачи. Помещая в массив (E5:G8) коды чисел, в клетке D11 получаем значение числа от 1 до 81. Это число получается как сумма произведений соответствующих значений в массивах (A5:C8) и (E5:G8). На другом листе решается обратная задача – восстановление кода по данному числу. Для этого приходится воспользоваться операцией «Поиск решения» и, к сожалению, программа для некоторых чисел даёт отказ в поиске. Но это уже чисто технические детали.

Рис. 2. Интерактивная версия задачи. Фрагмент «Код по числу».