Поступить в 8й класс...

zykov · Сообщение **zykov** » 07 июл 2020, 23:43

Ещё для этого "магического квадрата" можно применить теорию Диофантовых уравнений, чтобы найти целые решения (потом ещё нужно выбрать только те, где значения неотрицательные).
На английской википедии нашел раздел про системы линейных Диофантовых уравнений (на русской странице этого нет).
Идея такая, что решаем матричное уравнение $AX = C$

в целых числах.
$X$

- столбец решений высоты 16 (например, если развернули наш квадрат по строкам).
$C$

- столбец высоты 10, который содержит десять пятёрок.
$A$

- матрица 10 на 16 с коэффициентами линейных ограничений (по 4 единицы в строке для тех элементов, которые суммируем).
Эта матрица $A$

приводится к Smith normal form. В Matlab есть такая встроенная функция. В моём Octave её нет, но с интернета скачал матлаб код такой функции.
Функция выдаёт две матрицы. Матрица $U$

имеетр размер 10 на 10. Матрица $V$

имеет размер 16 на 16. Обе матрицы целочисленные, имеют целочисленные обратные матрицы и имеют детерминант $\pm 1$ .
Пр этом матрица $UAV$

получается диагональной. В нашем случае на диагонали стоит 8 единиц, потом одна двойка, потом нуль.

Общее решение в целых числах получается как сумма одного квадрата и ещё 7 квадратов с целыми весами.

Код: Выбрать все

   0   0   5   0
  -5   5   0   5
   5   0   0   0
   5   0   0   0

Код: Выбрать все

   0  -1   1   0       0   1  -1   0       0   0   0   0      -1  -1   1   1
   1   0  -1   0       1  -1   0   0       1   0   0  -1       1   1  -1  -1
  -1   1   0   0      -1   0   1   0      -1   0   0   1       0   0   0   0
   0   0   0   0       0   0   0   0       0   0   0   0       0   0   0   0

   1   0  -1   0       1   1  -2   0       0   1  -1   0
   0  -1   1   0       0  -1   1   0       1  -1   1  -1
   0   0   0   0       0   0   0   0       0   0   0   0
  -1   1   0   0      -1   0   1   0      -1   0   0   1

Дело за малым. :roll:

Посчитать количество комбинаций из этих 7 весов, которые дают неотрицательные квадраты.

zykov · Сообщение **zykov** » 07 июл 2020, 23:57

Можно заметить, что 7 элементов квадрата равны ровно одному из семи весов:

Код: Выбрать все

   *   *   *   k4
   *   *   *   *
   *   k1  k2  k3
   *   k5  k6  k7

Значит сами веса могут принимать только значения от 0 до 5.

Другие 9 элементов дадут неравенства. Вобщем надо найти количество целых точек внутри 7-мерного многогранника, который получается пересечением гиперкуба (от 0 до 5) и этих 9 полупространств.
Задача должна быть подъёмная - нужно систематизировать грани, разбить многогранник на части, внутри которых количество точек легко ищется и просуммировать по этим частям.
В самом гиперкубе $6^7 = 279936$

точек.

Полупространства:

$k5+k6 \; \geq \; k4$
$k2+k6+k7 \; \geq \; k1+k4$
$5+k1+k4 \; \geq \; k2+k5+2 \cdot k6+k7$
$k1+k2+k3+k4+k7 \; \geq \; 5$
$5+k4 \; \geq \; k2+k5+k6+k7$
$k5+k6+k7 \; \geq \; k1+k4$
$5 \; \geq \; k3+k4+k7$
$5 \; \geq \; k1+k2+k3$
$5 \; \geq \; k5+k6+k7$

zykov · Сообщение **zykov** » 08 июл 2020, 22:11

Попробовал на компьютере сделать перебор по этим 279936 случаям.
Всё правильно. Тоже получается 1904 точки.

Если учесть только ограничения 7, 8, 9, то получается 11096 точек.
(Если учеть только одно из 7, 8, 9, то очевидно будет $56 \cdot 6^4 = 72576$ . Если учесть 8 и 9, то будет $56^2 \cdot 6 = 18816$ .)
Если учесть только ограничения 4, 7, 8, 9, то получается 8918 точек.

Портал Естественных Наук, версия 1.1