2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Очень нетривиальная задача
Сообщение11.08.2012, 13:33 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Начну с критики.
В "шапке" раздела висит тема столетней давности "Al Zimmermann's Programming Contest".

Небось, тот конкурс давным-давно в лету канул :D

А между тем в данный момент проходит новый конкурс программистов, о котором моя тема в разделе "Свободный полёт". А почему она в этом флеймовом разделе? Да я уже боюсь открывать темы в тематических разделах: всё не так, всё не туда...
Ха! А нашёлся тут человек, который высказал мнение, что теме "Новый конкурс программистов" не место в "Свободном полёте". Опять не туда! :D

Ну, это так - вступление. На всех, понятно, не угодишь и "на каждый роток не накинешь платок".

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

Собственно, задача сформулирована здесь
Надо ли дублировать постановку задачи?
Я выложила эту задачу и на форуме конкурса для программистов всего мира. Там тишина пока.

Достаточно сказать, что задача сродни задаче о нахождении комплекта из трёх попарно орогональных латинских квадратов 10-го порядка, которую вот уже десятки лет решают все математики и программисты мира.
Есть даже проект распределённых вычислений (в теме о конкурсе есть ссылка на этот проект), предлагается предоставить свои вычислительные ресурсы для решения этой задачи.

Оротогональность прямоугольников определяется точно так же, как и ортгональность ЛК.
Если на пальцах: наложим один прямоугольник на другой; при этом в соответствующих ячейках образуются упорядоченные пары чисел. Так вот: в двух ортогональных прямоугольниках все эти пары различны.

Всё-таки комплект попарно ортогональных прямоугольников продублирую:

(Оффтоп)

Код:
1 10 10 10 10 10 10 10 10 2
2 2 2 2 2 2 2 2 3 3
3 3 3 3 3 3 3 4 4 4
4 4 4 4 4 4 5 5 5 5
5 5 5 5 5 6 6 6 6 6
6 6 6 6 7 7 7 7 7 7
7 7 7 8 8 8 8 8 8 8
8 8 9 9 9 9 9 9 9 9
9 1 10       

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

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

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

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

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

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

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

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

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

Ну и - гипотеза моя состоит в следующем: невозможно составить аналогичный комплект из 10 попарно ортогональных прямоугольников 9х10 (заполненных числами от 1 до 10), в которых в последней строке будет 4 элемента.

Гипотезу надо доказать или опровергнуть.
Ну, понятно, что опровергнуть просто: достаточно предоставить комплект из нужных 10 прямоугольников.
Но вот составить его не так просто. Тупой перебор вряд ли даст результат. Нужен перебор "идейный", а для такого перебора нужна эта самая идея.

Доказать, что гипотеза верна, тоже, наверное, непросто. Тут тоже нужна идея - строгая математическая.

 Профиль  
                  
 
 Re: Очень нетривиальная задача
Сообщение13.08.2012, 05:53 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Попытка найти нужный комплект из 10 прямоугольников 9х10:

(Оффтоп)

Код:
1 1 2 1 3 4 5 6 3 1
7 7 8 7 6 4 9 8 6 7
5 5 1 5 8 4 10 1 8 5
9 9 7 9 1 4 3 7 1 9
10 10 5 10 7 4 2 5 7 10
3 3 9 3 5 4 8 9 5 3
2 6 10 2 9 X 1 10 9 2
8 8 3 8 10 4 7 3 10 4
8 6 X 2     

1 6 1 3 4 5 6 3 1 7
7 8 7 6 4 9 8 2 7 5
5 1 5 8 4 10 1 8 5 9
9 7 9 1 4 3 7 1 9 10
10 5 10 7 4 2 5 7 10 3
3 9 3 5 4 8 9 5 3 6
6 10 6 9 4 1 10 9 6 8
8 3 8 10 4 7 3 10 8 4
1 X 6 X     

2 1 3 4 5 2 6 1 7 7
8 7 2 4 9 8 2 7 5 5
1 5 8 4 10 1 8 5 9 9
7 9 1 4 6 7 1 9 10 10
5 10 7 4 2 5 7 10 3 6
9 3 5 4 8 9 5 3 2 2
10 2 9 4 1 10 9 2 8 8
3 8 10 4 7 6 10 8 1 4
1 X 3 X     

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

6 4 5 2 6 1 7 7 8 7
2 4 9 8 2 7 5 5 1 5
8 4 10 1 8 5 9 9 7 9
1 4 3 7 1 9 10 10 5 10
7 4 2 5 7 10 6 6 9 6
5 X 8 9 5 3 2 2 10 2
9 4 1 10 9 2 8 8 3 8
10 4 7 6 10 8 1 1 2 4
1 3 6 X     

4 5 2 3 1 7 7 8 7 2
4 9 8 2 7 5 5 1 5 8
4 10 1 8 5 9 9 7 9 1
4 3 7 1 9 10 10 5 10 7
4 2 5 7 10 3 3 9 3 5
6 8 9 5 3 2 2 10 2 9
4 1 10 9 2 8 8 3 8 10
4 7 3 10 8 1 1 2 1 4
3 4 X X     

5 2 3 6 7 7 8 7 2 4
1 8 2 7 5 5 6 5 8 4
10 6 8 5 9 9 7 9 6 4
3 7 6 1 10 10 5 10 7 4
2 5 7 10 3 3 9 3 5 4
8 9 5 3 2 2 10 2 9 4
6 10 9 2 8 8 3 8 10 4
7 3 10 8 6 6 2 6 3 4
4 9 X X     

2 3 1 7 7 8 7 2 4 9
8 2 7 5 5 1 5 8 4 10
6 8 5 9 9 7 9 6 4 3
7 1 9 10 10 5 10 7 4 2
5 7 10 3 3 9 3 5 4 8
9 X 3 2 2 10 2 9 4 1
10 9 2 8 8 3 8 10 4 7
3 10 8 1 6 2 1 3 4 4
5 1 6 X     

3 6 7 7 8 7 2 4 9 1
2 7 5 5 6 5 1 4 10 6
8 5 9 9 7 9 6 4 3 7
6 9 10 10 5 10 7 4 2 5
7 10 3 3 9 3 5 4 X 9
5 3 2 2 10 2 9 4 6 10
9 2 8 1 3 8 10 4 7 3
10 1 6 6 2 6 3 4 5 4
2 1 1 X     

1 7 7 8 7 2 4 9 8 2
7 5 5 1 5 8 4 10 1 8
5 6 6 7 9 1 4 3 7 1
9 10 10 5 10 7 4 2 5 7
10 3 3 9 3 5 4 8 X 5
3 2 2 10 2 9 4 1 10 9
2 8 8 3 8 X 4 7 3 10
8 1 1 2 1 3 4 5 2 4
3 6 X X

Прямоугольники хорошие, но... в них есть 20 пустых ячеек

[в пустых ячейках стоит символ Х; в прямоугольниках последняя строка неполная, но эти незаполненные ячейки не относятся к пустым ячейкам]

Если в эти пустые ячейки поставить любые числа больше 10, прямоугольники будут попарно ортогональны. А вот заполнить пустые ячейки числами от 1 до 10 с сохранением попарной ортогональности прямоугольников не удаётся :-(
При этом можно ведь как угодно изменять уже имеющиеся элементы прямоугольников, разумеется, только на числа от 1 до 10.

(Оффтоп)

Интересно, а почему все молчат?
Может быть, это очень даже тривиальная задача? :D
Просто я не вижу очевидного? Ну, так покажите мне это очевидное, пожалуйста :?

 Профиль  
                  
 
 Re: Очень нетривиальная задача
Сообщение13.08.2012, 09:21 
Аватара пользователя


31/10/08
1244
Nataly-Mak
Вы бы с начало условие опубликовали. А потом уж ваши мысли.

 Профиль  
                  
 
 Re: Очень нетривиальная задача
Сообщение13.08.2012, 09:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavia в сообщении #605567 писал(а):
Nataly-Mak
Вы бы с начало условие опубликовали. А потом уж ваши мысли.

"С начало" - это как? :D

Я условие опубликовала. Во-первых, дала ссылку на тему, где всё это очень подробно обсуждается.
Во-вторых, продублировала здесь комплект из 10 попарно ортогональных прямоугольников 9х10 с неполной последней строкой, заполненных числами от 1 до 10 (вы в тег off загляните, комплект там; под этим тегом на этом форуме прячут не только оффтоп, но и очень нужные вещи, которые громоздкие). Привела определение ортогональных прямоугльников, правда, слегка популярное - на пальцах, но сути это не меняет.

В-третьих, сформулировала свою гипотезу.

Какие вопросы по условию?

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:46 
Основатель
Аватара пользователя


11/05/05
4312
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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