2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 89, 90, 91, 92, 93, 94, 95 ... 192  След.
 
 Re: Магические квадраты
Сообщение12.04.2010, 18:49 
Аватара пользователя


20/01/10
766
Нижний Новгород
Несколько слов о невозможности квадрата 5858

Если рассмотреть квадрат с магической суммой 5858 по модулю 9, воспользовавшись методом 12d3, можно увидеть распределение остатков:
0 - 7 шт.
3 - 1 шт.
4 - 37 шт.
6 - 16 шт.
8 - 3 шт.
В каждом ряду суммы этих остатков могут принимать значения 8, 17, 26, 35, 44, 53 .. (=8 (mod 9)). Оценим максимальную сумму, она меньше 8+8+8+6+6+6+6+6=54, но не может быть =53. Сумма остатков=271, т.е. мы можем написать:
$8x+17y+26z+35u+44t=271$,
где x,y,z,u,t - количества рядов с соответствующими суммами, $x+y+z+u+t=8$, исключив $u$ можно переписать:
$3x+2y+(z-t)=1$
при этом $u+y=8-x-z-t=1$, т.к. 3 всего одна, т.е. $t=7-x-z$, или
$2x+y+z=4$
Итого, 3 решения:
$1. x=2, z=0,  t=5$ примем y=0, u=1, другой вариант хуже
$2. x=1, z=2,  t=4$
$3. x=0, z=4,  t=3$
Но t не может быть больше 3, т.к. 8-ок всего 3, и при t=3 в каждую строку с суммой 44 может входить только одна 8 (и обязательно входит). С учетом этого максимальное число 4-ок в строках:
8 - 2 (0 0 0 0 0 0 4 4)
26 - 5 (0 0 4 4 4 4 4 6)
35 - 5 (3 4 4 4 4 4 6 6)
44 - 3 (4 4 4 6 6 6 6 8)
Для оставшегося решения максимальное число 4-ок:
3. 0*2+4*5+3*3+1*6=35
А у нас 37, т.е. решения нет.

Ниже приведены все возможные строки
Код:
0 0 0 0 0 0 0 8  ( 8)
0 0 0 0 0 0 4 4  ( 8)
0 0 0 0 0 3 6 8  (17)
0 0 0 0 3 4 4 6  (17)
0 0 0 4 4 4 6 8  (26)
0 0 0 4 4 6 6 6  (26)
0 0 3 4 4 8 8 8  (35)
0 0 3 4 6 6 8 8  (35)
0 0 3 6 6 6 6 8  (35)
0 0 4 4 4 4 4 6  (26)
0 3 4 4 4 4 8 8  (35)
0 3 4 4 4 6 6 8  (35)
0 3 4 4 6 6 6 6  (35)
0 4 4 6 6 8 8 8  (44)
0 4 6 6 6 6 8 8  (44)
0 6 6 6 6 6 6 8  (44)
3 4 4 4 4 4 4 8  (35)
3 4 4 4 4 4 6 6  (35)
4 4 4 4 4 8 8 8  (44)
4 4 4 4 6 6 8 8  (44)
4 4 4 6 6 6 6 8  (44)
4 4 6 6 6 6 6 6  (44)

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.04.2010, 11:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Итак, уважаемые коллеги, у нас остался один квадрат из последовательных смитов - 4-го порядка.

Я посоветовалась с ice00 в личной переписке, как нам приступить к решению этой задачи.

От ответил, что такие большие числа для него представляют сложность. Но если сделать ВСЕ потенциальные массивы в нормализованном виде (то есть вычесть из всех чисел массива минимальное число), тогда он сможет проверить такие потенциальные массивы на предмет составления их них магического квадрата, даже если таких массивов окажется очень много.

Это хорошая идея - сделать все потенциальные массивы в нормализованном виде.

Здесь уже был приведён maxal'ем ряд таких нормализованных потенциальных массивов, которые и я смогла проверить по своей программе (так как их было не очень много). Хорошая программа проверки есть и у svb (он мне её прислал).
Думаю, что и у 12d3 есть такая программа.

Какие будут предложения? Приступим? :wink:

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение16.04.2010, 17:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
А что обозначает абревиатура ПМК? Искать расшифровку на 92-х страницах обсуждения трудно.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение16.04.2010, 19:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #310320 писал(а):
А что обозначает абревиатура ПМК?

ПМК - полумагический квадрат.

Отредактировала статью "Наименьшие магические квадраты из последовательных чисел Смита" и статью "Наименьшие магические квадраты из чисел Смита" (соответствующая последовательность в OEIS A170928).
Написала статью "Магические квадраты четвёртого порядка из последовательных простых чисел" (это о последовательности A173981 в OEIS).

Готовлю статью "Магические квадраты пятого порядка из последовательных простых чисел" и соответствующую последовательность в OEIS.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение19.04.2010, 13:15 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Написала статью "Магические квадраты пятого порядка из последовательных простых чисел".

Интересное получается чередование массивов, складывающихся и не складывающихся в магические квадраты. Я проверила 50 потенциальных массивов, только 32 дали магические квадраты.
Последовательность магических констант этой группы квадратов получилась такая:

Код:
313, 577, 703, 785, 865, 949, 1111, 1703, 2041, 2071, 2579, 2677, 2809, 3157, 3379, 3545, 4001, 4135, 4873, 5143, 5513, 5549, 5659,  5695, 5731, 5917, 6031, 6277, 6427, 6547, 7951, 8027

Думаю, что последовательность можно продолжить.
Готовлю статью для OEIS о данной последовательности.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 07:14 
Аватара пользователя


21/02/10
1594
Екатеринбург
Пусть у нас есть последовательность из 16 чисел: $0\leq x_1<x_2<...<x_{16}$ .
Тогда из 16! перестановок этих чисел, только 14 перестановок (с точностью до изоморфизма) могут подходить для построения нетрадиционного пандиагонального магического квадрата 4х4.

Изображение

В квадратах, на рисунке, это индексы переменных.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 07:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Может быть, я что-то не так поняла.
Взяла один из имеющихся у меня нетрадиционных пандиагональных квадратов 4-го порядка:

Код:
7 22 16 25
20 21 11 18
19 10 28 13
24 17 15 14

Ему соответствует такой квадрат из индексов элементов массива:

Код:
1 13 7 15
11 12 3 9
10 2 16 4
14 8 6 5

Такого вроде нет в приведённом вами наборе.

___
Написала статью "Магические квадраты шестого порядка из последовательных простых чисел".

Интересно, что из 100 проверенных потенциальных массивов, следующих подряд, магические квадраты построились из чисел всех массивов.
Будет ли разрыв в этой последовательности?

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 08:05 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #311592 писал(а):
Может быть, я что-то не так поняла.
Код:
1 13 7 15
11 12 3 9
10 2 16 4
14 8 6 5

Такого вроде нет в приведённом вами наборе.

этот квадрат изоморфен квадрату:
Код:
1 13 8 14
11 12 2 10
9 3 16 4
15 7 6 5


То есть если из конкретного набора удовлетворяющего условию: $0\leq x_1<x_2<...<x_{16}$ можно построить ваш пандиагональный квадрат , то второй квадрат будет тоже пандиагональным на этом наборе чисел. И наоборот.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 08:23 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Да, получается.
Но тогда надо определить, что вы понимаете под изоморфизмом пандиагональных квадратов 4-го порядка.
Я посмотрела на эти два пандиагональных квадрата, они не являются изоморфными в смысле определения изоморфных (эквивалентных) магических квадратов.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 08:26 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #311592 писал(а):
Код:
7 22 16 25
20 21 11 18
19 10 28 13
24 17 15 14



Код:
7   20   18   25
22   21   11   16
17   10   28   15
24   19   13   14


Второй квадрат тоже пандиагональный

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 08:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Да это я вижу :-)
Но эти два квадрата не изоморфны в смысле обычного определения изоморфности.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 08:38 
Аватара пользователя


21/02/10
1594
Екатеринбург
Пусть у нас есть произвольный набор чисел $0\leq x_1<x_2<...<x_{16}$ и две перестановки этих чисел A и B.
Определение. Перестановки A и B будем называть изоморфными если выполняется условие:
Для любого набора чисел удовлетворяющего условию $0\leq x_1<x_2<...<x_{16}$, перестановка A является пандиагональным квадратом <=> перестановка B является пандиагональным квадратом.

Мне казалось что такое определение изоморфизма естественно и интуитивно понятно.
Цитата:
они не являются изоморфными в смысле определения изоморфных (эквивалентных) магических квадратов

А какое определение используется для магических квадратов?

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 10:22 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Два магических квадрата называются изоморфными, если они получаются друг из друга с помощью основных преобразований (поворотов и отражений).
Каждый магический квадрат имеет точно 8 вариантов в данной группе эквивалентности, считая сам этот квадрат.

Некоторые исследователи (как пишет М. Гарднер) считают изоморфными магические квадраты, получающиеся друг из друга М-преобразованиями. Однако классическое количество магических квадратов 4-го порядка, данное Френиклем, равно 880, а это значит, что Френикль не считал изоморфными квадраты, получающиеся друг из друга М-преобразованиями. В противном случае квадратов было бы не 880, а 220. Следуя этому классическому примеру, я тоже не считаю М-преобразования изоморфизмом.

Что касается пандиагональных магических квадратов, то здесь изоморфными считаются ещё квадраты, получающиеся друг из друга параллельным переносом на торе.
Например, пандиагональных квадратов 4-го порядка 48 (с учётом поворотов и отражений), а с учётом параллельного переноса на торе их всего 3; точнее 3 базовых квадрата, каждый из которых порождает группу эквивалентности из 16 квадратов относительно переноса на торе.

Если следовать вашему определению... Ну, скажем, нашли мы некий пандиагональный квадрат, который соответствует перестановке А. Как найти все изоморфные ему квадраты в смысле вашего определения?

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 11:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот, например, запускаю я свою программу построения пандиагональных квадратов 4-го порядка из 16 заданных чисел (эта программа, кажется, здесь была выложена, и на сайте вроде выкладывала, точно не помню уже). В качестве исходного массива беру тот, из которого показан здесь пандиагональный квадрат.
Программа выдаёт 24 неизоморфных пандиагональных квадрата:

(Оффтоп)

1
7 20 21 22
24 19 10 17
14 13 28 15
25 18 11 16

2
7 20 21 22
25 18 11 16
14 13 28 15
24 19 10 17

3
7 20 19 24
22 21 10 17
16 11 28 15
25 18 13 14

4
7 20 19 24
25 18 13 14
16 11 28 15
22 21 10 17

5
7 20 18 25
22 21 11 16
17 10 28 15
24 19 13 14

6
7 20 18 25
24 19 13 14
17 10 28 15
22 21 11 16

7
7 22 21 20
24 17 10 19
14 15 28 13
25 16 11 18

8
7 22 21 20
25 16 11 18
14 15 28 13
24 17 10 19

9
7 22 17 24
20 21 10 19
18 11 28 13
25 16 15 14

10
7 22 17 24
25 16 15 14
18 11 28 13
20 21 10 19

11
7 22 16 25
20 21 11 18
19 10 28 13
24 17 15 14

12
7 22 16 25
24 17 15 14
19 10 28 13
20 21 11 18

13
7 24 19 20
22 17 10 21
16 15 28 11
25 14 13 18

14
7 24 19 20
25 14 13 18
16 15 28 11
22 17 10 21

15
7 24 17 22
20 19 10 21
18 13 28 11
25 14 15 16

16
7 24 17 22
25 14 15 16
18 13 28 11
20 19 10 21

17
7 24 14 25
20 19 13 18
21 10 28 11
22 17 15 16

18
7 24 14 25
22 17 15 16
21 10 28 11
20 19 13 18

19
7 25 18 20
22 16 11 21
17 15 28 10
24 14 13 19

20
7 25 18 20
24 14 13 19
17 15 28 10
22 16 11 21

21
7 25 16 22
20 18 11 21
19 13 28 10
24 14 15 17

22
7 25 16 22
24 14 15 17
19 13 28 10
20 18 11 21

23
7 25 14 24
20 18 13 19
21 11 28 10
22 16 15 17

24
7 25 14 24
22 16 15 17
21 11 28 10
20 18 13 19

Чтобы не занимали много места, спрятала их под тег оффтоп.

Вы можете получить по своим формулам такие же 24 квадрата?

-- Ср апр 21, 2010 13:22:48 --

Да, вспомнила...

Вопрос к svb:
вами получен наименьший магический квадрат 8-го порядка из произвольных смитов.
Надо бы внести этот результат в последовательность A170928.
Как вы смотрите на это?

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

Всё это я уже писала выше, но на это никто не обратил внимания.
Мне, как автору данной статьи, хочется, чтобы результаты были внесены. Но указанные результаты не мои, поэтому не берусь их вносить. К тому же, сама не умею вносить правки, мне помогает один товарищ по форуму.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение21.04.2010, 13:19 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #311662 писал(а):

Вы можете получить по своим формулам такие же 24 квадрата?


Где можно использовать опубликованные 14 перестановок? Скажем мы реашем задачу построения пандиагональных МК 4х4 из чисел специального вида. То есть у нас есть огромный файл с числами упорядоченными по возрастанию. И нам не нужно строить все МК, достаточно построить один.
Тогда алгоритм может быть примерно таким:
1) Формируем 16 чисел кандидатов.
2) Далее проверяем 14 перестановок, по общей формуле, можно ли из этих чисел построить пандиагональный МК.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 89, 90, 91, 92, 93, 94, 95 ... 192  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: tolstopuz


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group