Алекс Чу не просто виграв Міжнародну математичну олімпіаду минулого місяця. Він побив усі рекорди. Британський учень, випускник 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. Такого правила немає.
Правило полягає у добутку чисел у рядках та стовпцях.
