Магические квадраты

[MaximKat]

Aleks-Sid
Потому что $\Theta(n^2)$ растет быстрее, чем $\Theta(n)$

[Aleks-Sid]

MaximKat

Цитата:

Потому что $\Theta(n^2)$ растет быстрее, чем $\Theta(n)$

А разве не потому что деревья падают медленней?

[MaximKat]

Aleks-Sid писал(а):

А разве не потому что деревья падают медленней?

Ценю юмор.
Количество неизвестных в магическом квадрате пропорционально $n^2$. Количество уравнений пропрционально $n$. При достаточно больших $n$ первое больше второго и система разрешима. При $n=3$ система переопределена и решения нет.
Еще пояснения нужны?

[Aleks-Sid]

MaximKat

Непонятен только один момент (я слаб в математических абстракциях) - почему при n=4 система не переопределена? Где критерий переопределенности?
Я подсчитал - число уравнений для n=3 равно 16 . Это условия пандиагональности и ассоциативности. Количество неизвестных 9. Для n=4 соответственно имеем 25 уравнений и 16 неизвестных. То есть качественно все одно и то же!

[MaximKat]

Точный критерий дать нельзя в общем виде, потому что часть уравнений могут быть эквивалентными, а значит могут быть исключены из системы. Надо писать конкретную систему и смотреть.

[Aleks-Sid]

Вот я конкретно и рассмотрел. Все одинаково для двух случаев, но второй имеет решение, а первый почему-то должен артачиться.

P.S. В каждом из двух случаев эквивалентных уравнений не оказалось.

[MaximKat]

Aleks-Sid в сообщении #170582 писал(а):

P.S. В каждом из двух случаев эквивалентных уравнений не оказалось.

Предъявите 25 линейно независимых уравнений для n=4, пожалуйста

[Nataly-Mak]

Коллеги, я не понимаю, о чём спор.
Система линейных уравнений, описывающая идеальный магический квадрат 4-го порядка, приведена в моей статье “Ассоциативные магические квадраты”.
Эта система имеет решение только с повторяющимися числами. Так сказал Maple.
Система линейных уравнений, описывающая идеальный квадрат 3-го порядка, содержит всего 4 неизвестных и 4 уравнения (не забывайте, что квадрат у нас идеальный, а значит ассоциативный). Вот эти уравнения:
x1 + x2 + x3 = S x4 = S/3 2x1 – x2 – x3 = 0 2x3 – x1 – x2 = 0
(x1, x2, x3 – числа в первой строке квадрата, x4 – число в центральной ячейке этого квадрата).
Первые два уравнения – это условия ассоциативности, последние два уравнения – это условия пандиагональности. Если рассматривать только первые два уравнения, то будет бесконечно много решений (как с разными, так и с повторяющимися значениями неизвестных), так как ассоциативных (но не пандиагональных!) магических квадратов бесконечно много, традиционных – 8 вариантов, и бесконечно много нетрадиционных. Традиционные магические квадраты 3х3 (8 вариантов) всем известны. Вот пример решения для нетрадиционного квадрата:

10 17 27
35 18 1
9 19 26

Или вот ещё знаменитый квадрат Дьюдени, составленный из простых чисел:

67 1 43
13 37 61
31 73 7

(другие примеры нетрадиционных квадратов 3-го порядка вы можете посмотреть здесь или с успехом составить сами, руководствуясь первыми двумя уравнениями приведённой выше системы уравнений).
По этому пункту есть возражения?
Теперь рассматриваем систему в целом, то есть все 4 уравнения, а значит, требуем от квадрата пандиагональности. И вот тут система имеет… тоже бесконечно много решений, но во всех этих решениях все 4 неизвестных принимают одинаковые значения.
Найдите ошибку в моём доказательстве

[maxal]

Aleks-Sid в сообщении #170560 писал(а):

Я подсчитал - число уравнений для n=3 равно 16 . Это условия пандиагональности и ассоциативности. Количество неизвестных 9. Для n=4 соответственно имеем 25 уравнений и 16 неизвестных.

Более обще: для квадрата $n\times n$ имеем по $n$ уравнений для горизонталей и вертикалей, $\lceil n^2/2\rceil$ уравнений для ассоциативности и $2n$ уравнений для разломанных диагоналей. Суммарно $4n + \lceil n^2/2\rceil$ уравнений.

MaximKat в сообщении #170543 писал(а):

Количество неизвестных в магическом квадрате пропорционально $n^2$. Количество уравнений пропрционально $n$. При достаточно больших $n$ первое больше второго и система разрешима.

Вы забываете, что нужно абы какое решение, а лишь такое, которое в точности состоит из чисел от 1 до $n^2$. А оно не факт, что существует, даже если система недоопределена.
И, кстати, в "лобовой" системе количество уравнений также пропорционально $n^2$ (см. выше), но вот если по ассоциативности исключить половину неизвестных, то в системе действительно останется $\lfloor n^2/2\rfloor$ неизвестных и лишь $4n$ уравнений.

[Aleks-Sid]

Коллеги! Вы все говорите вокруг да около. А мне важно знать одно: существует ли нетрадиционный идеальный МК 3х3? Пусть там хоть 7 чисел будут одинаковые! И если такого нет, то дать четкое объяснение, почему это невозможно. Только не так голословно, как это сделал MaximKat. Да еще вопрос задал:

Цитата:

Еще пояснения нужны?

MaximKat
Если быть точным, то для 4х4 всего 23 уравнения а не 25. Это досадная ночная опечатка. Но суть от этого не меняется. Вот они передо мной на листе написаны. Если у Вас сомнения, то сами составьте, и если я неправ, то скажите мне: какие из них эквивалентные. Заодно и сами для себя проясните задачу.
Nataly-Mak
По ссылкам прошелся, но идеального нетрадиционного 3х3 не обнаружил.
maxal
Число уравнений для пандиагонального квадрата 4n-1. Доказывать не буду, так как это элементарно. Число уравнений по критерию ассоциативности: n^2/2 для четных n, и n^2/2+1 - для нечетных (в центральной ячейке должно быть число, равное половине суммы 1+n^2)

[maxal]

Aleks-Sid в сообщении #170690 писал(а):

А мне важно знать одно: существует ли нетрадиционный идеальный МК 3х3? Пусть там хоть 7 чисел будут одинаковые! И если такого нет, то дать четкое объяснение, почему это невозможно.

Вам уже сказали, что нет. Так как соответствующая система уравнений имеет решением только наборы чисел, в которых все числа равны между собой.

Aleks-Sid в сообщении #170690 писал(а):

Число уравнений для пандиагонального квадрата 4n-1. Доказывать не буду, так как это элементарно.

Это зависит от того, как вы определяете уравнения. Некоторые из уравнений можно сразу исключить, так как они очевидным образом являются следствием остальных, тогда уравнений будет еще меньше уравнений. Но если не заниматься ручным исключением, то для пандиагонального квадрата количество уравнений равно $4n$.

Добавлено спустя 4 минуты 31 секунду:

Aleks-Sid в сообщении #170690 писал(а):

Доказывать не буду, так как это элементарно. Число уравнений по критерию ассоциативности: n^2/2 для четных n, и n^2/2+1 - для нечетных

Ну так это в точности и есть $\lceil n^2/2\rceil$, как у меня и написано выше.

[Aleks-Sid]

Итак, получается, что с точки зрения идеального магического квадрата, 3 х 3 эквивалентен 1 х 1 и не относится к группе n x n где n>3.
Почему такая особенность с точки зрения математической логики?

[maxal]

Ради интереса посчитал ранги систем уравнений (то есть, по сути максимальное количество линейно независимых уравнений в системе) описывающих нетрадиционные идеальные квадраты. Для $n$ от 1 до 10 они получились равны:
1, 4, 9, 14, 21, 28, 37, 46, 57, 68
В это же время число неизвестных (включая магическую константу) равно $n^2+1$:
2, 5, 10, 17, 26, 37, 50, 65, 82, 101

Нетрудно понять, что система уравнений в данном случае всегда имеет семейство решений (размерности 1), где все элементы квадрата равны между собой. Поэтому, если ранг системы лишь на единицу меньше числа неизвестных, то ее решение в точности состоит из этого тривиального семейства, и других решений нет. Эту ситуацию мы наблюдаем для $n=1, 2$ и $3$. Для больших значений $n$ разность между числом неизвестных и рангов превышает 1, и поэтому найдется по крайней мере нетрадиционный идеальный магический квадрат, в котором не все элементы равны между собой (другими словами, есть по крайней мере два неравных элемента).

[Aleks-Sid]

maxal

О! Вот это объяснение! Теперь все встало на свои места! Ваше имя навеки отпечатается в моей книге, как Евклид отпечатался в своих "Началах"

[maxal]

maxal в сообщении #170702 писал(а):

Ради интереса посчитал ранги систем уравнений (то есть, по сути максимальное количество линейно независимых уравнений в системе) описывающих нетрадиционные идеальные квадраты. Для $n$ от 1 до 10 они получились равны:
1, 4, 9, 14, 21, 28, 37, 46, 57, 68

Для рангов справедлива формула:

$$\left\lfloor\frac{n^2 + 4n - 3}{2}\right\rfloor$$