Алекс Чу не просто выиграл Международную математическую олимпиаду в прошлом месяце. Он побил все рекорды. Британский ученик, выпускник 13-го класса школы Тонбридж в Кенте, набрал идеальный результат. Это 100%. Это обеспечило ему золотую медаль и увеличило общее количество его наград до семи, причем пять из них — золотые.
Это историческое достижение. Ни один участник за долгую историю МО с 1959 года не получал медаль семь лет подряд. Олимпиама собирает талантливых школьников более чем из ста стран. Обычно поддерживать такой уровень точности почти десять лет невозможно. Чу изменил правила игры в Шанхае.
Но математика не ограничивается медалями. Я спросил Чу, какая головоломка ему понравилась больше всего. Он не назвал задачу из своего экзамена. Вместо этого он предложил эту.
Вызов со сеткой 3×3
Вот условие задачи. Необходимо заполнить сетку размером 3×3.
Ячейки должны содержать положительные целые числа.
Существует ограничение: произведение чисел в каждой строке должно быть равно 30.
Произведение чисел в каждом столбце также должно равняться 30.
Просто? Нет. Если пытаться перебрать все варианты методом грубой силы, вы быстро запутаетесь. Существует более 200 допустимых способов заполнить эту сетку. Метод проб и ошибок — это ловушка. Числа не обязаны быть разными. Повторы допускаются.
Ответ кроется не в угадывании, а в разложении числа 30 на его простые множители.
Итак, как решить эту задачу, не утонув в 200 вариантах? Нужно посмотреть на множители.
Простая факторизация — ключ к решению
30 — небольшое число, но оно состоит из определенных «строительных блоков».
30 = 2 × 3 × 5
Это простые числа. Никакие другие целочисленные множители здесь не имеют значения. Любое число, помещаемое в сетку, должно быть образовано комбинациями этих трех простых чисел. Поскольку произведение трех чисел в строке равно 30, каждая строка должна содержать эти простые множители.
Давайте посмотрим на диагональ. Или просто на первую строку.
Умножая три числа в одной строке, мы получаем результат 2 × 3 × 5.
Это означает, что каждая строка содержит простые множители 2, 3 и 5, распределенные по трем ячейкам. В некоторых ячейках может находиться просто 1 (это не 2, не 3 и не 5). В других может быть составное число, например, 6 (2×3), 10 (2×5) или 15 (3×5). Но общее количество двоек, троек и пятерок в строке должно соответствовать целевому значению.
Разрушение симметрии
Здесь становится интересно.
Рассмотрим диагональ от верхнего левого угла к нижнему правому. Пусть сетка обозначается как $G$.
$G_{11} \times G_{22} \times G_{33} = \text{что-то?}$ Не обязательно 30. Такого правила нет.
Правило заключается в произведении чисел в строках и столбцах.
