Математический форум Math Help Planet
http://mathhelpplanet.com/

Ортогональные латинские квадраты 10-го порядка
http://mathhelpplanet.com/viewtopic.php?f=57&t=46638
Страница 49 из 421

Автор:  Nataly-Mak [ 29 фев 2016, 10:38 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust
программа svb выложена здесь.
Скачайте, она махонькая. И сами два раза нажмите Enter :)
Программа выдаст вам все 4224 трансверсали.
Посмотрите на них, полюбуетесь. Потом прямо шарите по этому массиву и ищете непересекающиеся трансверсали :roll:

Автор:  bimol [ 29 фев 2016, 11:05 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

В русском переводе на 59 странице задачи 14а,б,г и в оригинальном стили задача 15 на 50 балов
Изображение

Квадраты 4и и 4д не признал, что за константы "закодированы"?

Автор:  Avgust [ 29 фев 2016, 11:34 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

bimol
так квадраты не диагональные.

Автор:  Nataly-Mak [ 29 фев 2016, 14:36 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Мне задача 15 понравилась.
Кнут за решение задачи века даёт 50 баллов :)

Avgust
Кнут не ставит задачу о диагональных ЛК, он любые рассматривает.

Автор:  bimol [ 29 фев 2016, 14:49 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Я забыл упомянуть. Кнут ОДЛК не рассматривал, просто ОЛК ( а может не дошел до той части кирпичей).
Но забавно. И его фишка [50].

Автор:  bimol [ 29 фев 2016, 14:51 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

За теорему Ферма тоже 50 давал. Сколько сейчас - 35 40?

Автор:  Nataly-Mak [ 29 фев 2016, 15:23 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Не, ну очень интересно.
Ввожу в программу svb ДЛК Брауна, задаю max=100 (найти 100 ортогональных соквадратов).
Легко! Три секунды.
Смотрю эти соквадраты, все они не диагональные. Вот 100-й соквадрат:

0 1 2 3 4 5 6 7 8 9
1 0 3 4 2 6 9 8 7 5
8 7 0 1 5 4 2 6 9 3
5 3 9 0 1 7 8 2 6 4
7 4 8 6 0 1 3 9 5 2
4 2 5 9 8 0 7 3 1 6
6 8 4 7 9 2 0 5 3 1
9 5 6 2 7 3 1 0 4 8
2 6 1 8 3 9 5 4 0 7
3 9 7 5 6 8 4 1 2 0

Проверяю по своей программе ортогональность этого ЛК и ДЛК Брауна; программа сообщает:
KVADRATY ORTOGONALNY!!!
0  11  22  33  44  55  66  77  88  99 
21 30 43 94 82 16 9 58 67 75
38 47 90 81 25 74 12 6 59 63
85 73 69 50 1 97 48 32 26 14
57 4 18 76 60 31 23 89 95 42
64 52 5 19 78 20 87 93 41 36
46 98 84 27 39 62 70 15 3 51
79 65 56 2 17 83 91 40 34 28
92 86 71 68 53 49 35 24 10 7
13 29 37 45 96 8 54 61 72 80

Замечательно! И сколько же всего ортогональных соквадратов у ДЛК Брауна? 500, 1000, 2000?
А вот диагональных из них должно быть всего 4, если верить ребятам с проекта SAT@home.

Значит, план такой: ищем все ортогональные соквадраты к ДЛК Брауна, потом из всех выбираем диагональные.
Надо написать программку для выбора диагональных ЛК.
Вот только не дай Бог всех ортогональных соквадратов окажется астрономическое количество. Ну и дела.

Сейчас проверю пару ОДЛК, найденную в проекте. Может, для неё поменьше будет ортогональных соквадратов.

Автор:  Nataly-Mak [ 29 фев 2016, 15:46 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Да, для этой пары ОДЛК все проще.

ДЛК №1

0 1 2 3 4 5 6 7 8 9
2 4 9 7 0 3 5 1 6 8
9 7 1 5 6 4 8 3 0 2
1 0 8 6 9 2 7 4 5 3
8 6 5 0 7 1 3 2 9 4
6 3 4 9 2 8 0 5 1 7
5 9 7 8 3 0 2 6 4 1
3 8 0 4 5 7 1 9 2 6
7 5 6 2 1 9 4 8 3 0
4 2 3 1 8 6 9 0 7 5

имеет двух ортогональных собратьев, один из них диагональный:

0 1 2 3 4 5 6 7 8 9
4 9 1 5 6 0 2 8 7 3
2 0 7 8 9 1 5 4 3 6
5 2 9 4 8 3 1 6 0 7
7 5 4 1 3 2 9 0 6 8
1 8 0 7 5 6 4 3 9 2
9 3 6 0 1 7 8 2 5 4
6 4 8 2 7 9 3 5 1 0
8 6 3 9 0 4 7 1 2 5
3 7 5 6 2 8 0 9 4 1

0 1 2 3 4 5 6 7 8 9
5 3 1 6 9 2 8 4 0 7
3 5 0 2 7 6 9 8 4 1
9 7 6 5 8 0 1 2 3 4
2 9 4 1 0 8 7 3 6 5
8 0 7 4 6 1 2 9 5 3
7 2 8 0 5 3 4 1 9 6
6 4 5 8 1 9 3 0 7 2
4 6 3 9 2 7 0 5 1 8
1 8 9 7 3 4 5 6 2 0

ДЛК №2

0 1 2 3 4 5 6 7 8 9
4 9 1 5 6 0 2 8 7 3
2 0 7 8 9 1 5 4 3 6
5 2 9 4 8 3 1 6 0 7
7 5 4 1 3 2 9 0 6 8
1 8 0 7 5 6 4 3 9 2
9 3 6 0 1 7 8 2 5 4
6 4 8 2 7 9 3 5 1 0
8 6 3 9 0 4 7 1 2 5
3 7 5 6 2 8 0 9 4 1

имеет всего одного ортогонального собрата - это ДЛК №1.

Ну и сочинил же квадратик Браун, чёрт знает сколько у него ортогональных соквадратов.
Сейчас проверю ДЛК Гергели, много ли у него ортогональных соквадратов. Форумчанин с boinc.ru написал, что диагональных соквадратов у него нет.

С квадратом Гергели тоже плохо - 100 ортогональных соквадратов находятся легко. Сколько всего - неизвестно.

Автор:  whitefox [ 29 фев 2016, 16:04 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Nataly-Mak писал(а):
Значит, план такой: ищем все ортогональные соквадраты к ДЛК Брауна, потом из всех выбираем диагональные.
Надо написать программку для выбора диагональных ЛК.
Вот только не дай Бог всех ортогональных соквадратов окажется астрономическое количество. Ну и дела.

Назовём трансверсаль диагональной если она проходит ровно через одну клетку главной диагонали и ровно через одну клетку побочной диагонали.

Утверждение. ЛК, ортогональный заданному ЛК, будет ДЛК тогда и только тогда, когда он построен из диагональных трансверсалей заданного ЛК.

Поэтому, план такой:
  1. находим все диагональные трансверсали заданного ЛК (или ДЛК);
  2. находим все 10-и элементные множестве непересекающихся диагональных трансверсалей.

Автор:  Nataly-Mak [ 29 фев 2016, 16:43 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Нашего полку прибыло :)

whitefox писал(а):
Поэтому, план такой:
  1. находим все диагональные трансверсали заданного ЛК (или ДЛК);
  2. находим все 10-и элементные множестве непересекающихся диагональных трансверсалей.

Э-э-э... я не умею искать трансверсали :(
А вот диагоальные ЛК в массиве всех ЛК найти смогу, наверное, если их, конечно, не миллион будет.

Сейчас загнала в программу ДЛК, созданный Avgust. Задала max=5000. Нашла программа 5000 ортогональных соквадратов. Это 5000-й ортогональный соквадрат

0 1 2 3 4 5 6 7 8 9
5 0 8 4 7 3 9 2 1 6
6 2 0 9 3 1 5 8 7 4
1 9 5 0 2 7 3 4 6 8
9 6 7 8 0 2 4 5 3 1
2 4 3 6 5 8 0 1 9 7
7 5 6 1 8 9 2 0 4 3
3 8 1 2 9 4 7 6 5 0
8 3 4 7 6 0 1 9 2 5
4 7 9 5 1 6 8 3 0 2

Начали появляться в главной диагонали другие циферки, а то одни нули были. Но до ДЛК, похоже, ещё не добралась программа. Ужас!

Страница 49 из 421 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/