1-го января из сообщества Незадача дня я узнал про интересные равенства относительно числа 2025 и про задачу, которую на их основе можно сформулировать.

Равенства следующие:

Некоторые, возможно, ещё помнят, что в углублённой школьной (или вузовской) программе встречалось равенство . Собственно, оно тут и применяется. Кстати, согласно Википедии, это равенство называется тождеством Никомаха, древнегреческого математика (около 60-120 гг. н.э.).

На основе этих равенств можно сформулировать задачу:

Сколько существует способов расположить 1 квадратик со стороной 1, 2 квадратика со стороной 2, 3 квадратика со стороной 3, … , 8 квадратиков со стороной 8, 9 квадратиков со стороной 9 в квадрате со стороной 45, чтобы они не пересекались?

В продолжение части 1 привожу анализ заполнений квадрата со стороной 45 квадратиками размера от 1 до 9 (1x1 - 1 шт., 2x2 - 2 шт., 3x3 - 3 шт., ..., 9x9 - 9 шт.).

Начнём с простого. Несложно показать, что квадратик размера 1 не может стоять у границы и даже на расстоянии 1 от границы. Этот факт я учитывал при поиске вариантов, чтобы немного сократить перебор.

Если выстроить квадратики размера 9 вдоль двух соседних «стенок», то мы сведём задачу поиска заполнения к задаче для . Таким образом получается, что около 4% заполнений для получаются напрямую из заполнений для (у нас есть 4 способа выбрать 2 соседние «стенки»).