2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 задача по мотивам кубика Рубика
Сообщение19.04.2008, 04:55 


19/04/06
17
Такая игра: игровое поле это квадрат 3х3, в клетках записаны числа 1-9. Допускаются следующие преобразования: циклический сдвиг в любой строчке или любой вертикали.

1) Можно ли любую позицию перевести в любую?

2) Какого число преобразований достаточно, чтобы перевести случайную позицию в упорядоченную (1 2 3 / 4 5 6/ 7 8 9) ?

3) Есть ли какой простой алгоритм, который позволяет любую случайную позицию упорядочить за число ходов, близкое к оптимальному?

Можно, конечно, эти преобразования записать как перестановки на 9 элементах, и наперемножать чего там в группе есть, но может у кого есть менее тупые идеи?

 Профиль  
                  
 
 
Сообщение19.04.2008, 05:00 
Модератор
Аватара пользователя


11/01/06
5702
Возьмите GAP и проанализируйте группу таких сдвигов по аналогии с группой вращения кубика Рубика. Я думаю, и на вопросы 2,3) GAP сможет легко ответить в данном случае (в частности, найдет диаметр группы).

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

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



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

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


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

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