Логин:Пароль:
FAQ по форумуНовые сообщения на Форуме
  • Страница 1 из 1
  • 1
Форум Эрудитов » Логические задачи и головоломки » Скорая помощь » Решенные задачи » Пятнашка (sml[ok]праздные вопросы)
Пятнашка
никникДата: Вт, 10.11.15, 21:21 | Сообщение # 1
Гений
Сообщений: 2735
Награды: 404
Совы: 15
Дана головоломка-пазл "пятнашка", простоты ради из 9 клеток, разобранная максимально сложным способом.
1)Привести необходимые и достаточные условия такого разброса.(Видимо,через размещение диаметральных,"медианных", центральной костяшек и пустого деления друг относительно друга )
2)Найти (и обосновать) минимальное количество перемещений, требуемое для выигрыша в этом случае.(Пока понимаю только, что не меньше 7)
3) Есть ли для 8 костяшек случай несобираемой расстановки? (слышал, что для 15 есть)
п.с. Ответов ни на один вопрос не знаю, сам пока ломаю голову. Отвечать можно в любом порядке, с меня награда за ответ на любой вопрос.


Между своеобразной логикой и откровенной глупостью иногда очень тонкая грань.


Сообщение отредактировал erudite-man - Ср, 11.11.15, 14:20
 
KreativshikДата: Ср, 11.11.15, 00:52 | Сообщение # 2
Гений
Сообщений: 2472
Награды: 258
Совы: 113
2) 31, меньше в этом случае не получится
3) Да, их 181440


Жёлтый Зелёный Красный


Сообщение отредактировал Kreativshik - Ср, 11.11.15, 00:53
 
KreativshikДата: Ср, 11.11.15, 01:48 | Сообщение # 3
Гений
Сообщений: 2472
Награды: 258
Совы: 113
1) Если для номера каждой клетки определить норму l1, то их сумма должна быть равна 21, при этом условии обязательно будет достигнута конфигурация максимальной сложности.
норма l1 это расстояние, измеряемое в клетках, от текущего положения номера клетки до места базового положения данного номера.Конфигурацию считаем решённой, когда все номера находятся в базавом положении.


Жёлтый Зелёный Красный


Сообщение отредактировал Kreativshik - Ср, 11.11.15, 01:54
 
никникДата: Ср, 11.11.15, 09:49 | Сообщение # 4
Гений
Сообщений: 2735
Награды: 404
Совы: 15
Спасибо! bravo
Цитата Kreativshik ()
то их сумма должна быть равна 21

а 21= (кол-во костяшек - 1)*3 (где 3 - минимальное кол-во перемещений составляющее цикл 1 хода определенной костяшки, или все таки размерность "матрицы")?
Цитата Kreativshik ()
3) Да, их 181440

половина всех возможных размещений?
Цитата Kreativshik ()
2) 31, меньше в этом случае не получится

Спасибо, теперь, пожалуй, попробую тоже найти решение.


Между своеобразной логикой и откровенной глупостью иногда очень тонкая грань.


Сообщение отредактировал никник - Ср, 11.11.15, 10:07
 
никникДата: Ср, 11.11.15, 10:09 | Сообщение # 5
Гений
Сообщений: 2735
Награды: 404
Совы: 15
Я думаю так.
Имеющийся квадрат 3х3, разбиваем на квадраты 2х2. Собственно это можно сделать всего 1 способом.
Очевидно, что решение головоломки достигается правильной последовательностью вращения этих квадратов. На 1й взгляд мне кажется, что каждый квадрат 2х2 имеет всего 4 состояния, и таким образом "пробегает" их все за 3 хода. Но это не так, в силу того, что костяшки могут (и должны) мигрировать из квадрата в квадрат, а также того, что изначально возможность вращения есть только в одном квадрате..
%) подумаю об этом завтра)


Между своеобразной логикой и откровенной глупостью иногда очень тонкая грань.


Сообщение отредактировал никник - Ср, 11.11.15, 10:11
 
KreativshikДата: Сб, 14.11.15, 22:07 | Сообщение # 6
Гений
Сообщений: 2472
Награды: 258
Совы: 113
Цитата никник ()
а 21= (кол-во костяшек - 1)*3 (где 3 - минимальное кол-во перемещений составляющее цикл 1 хода определенной костяшки, или все таки размерность "матрицы")?

21 это сумма l1 норм для каждого числа.
Вот базавая позиция:

Рассмотрим следующую конфигурацию, которая требует минимум 31 ход, чтобы ее конвертировать в базавую.

Посчитаем для неё сумму l1норм (Σl1(n))
l1(1)=3 - расстояние в клетках от той ячейки где находится единица в представленной конфигурации до ячейки в которой единица находится в базовой позиции.
l1(2)=4
l1(3)=2
l1(4)=0
l1(5)=2
l1(6)=4
l1(7)=2
l1(8)=4
Итого Σl=3+4+2+0+2+4+2+4=21
См в вике статью l1 норма
P.S.l1- лебегово пространство с единичной нормой.
Прикрепления: 0345600.jpg (5.1 Kb) · 5523484.jpg (4.9 Kb)


Жёлтый Зелёный Красный


Сообщение отредактировал Kreativshik - Сб, 14.11.15, 22:19
 
KreativshikДата: Сб, 14.11.15, 22:38 | Сообщение # 7
Гений
Сообщений: 2472
Награды: 258
Совы: 113
Цитата никник ()

Спасибо, теперь, пожалуй, попробую тоже найти решение

Решение чего?


Жёлтый Зелёный Красный
 
Форум Эрудитов » Логические задачи и головоломки » Скорая помощь » Решенные задачи » Пятнашка (sml[ok]праздные вопросы)
  • Страница 1 из 1
  • 1
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Цифра)))2
2.Бессмысленное и загадочно...9
3.Помощь с решением задачи1
4.Помогите решить ребус1
5.О времена, о нравы ...10
6.Случайная хорда3
7.Лучше9
8.Акула12
9.6 ребусов3
10.Головоломка без ключа1
1.Rostislav5379
2.Lexx4728
3.nebo3636
4.Иван3061
5.никник2735
6.Kreativshik2472
7.Гретхен1807
8.Vita1488
9.erudite-man1378
10.Valet937
1.nebo123
2.Kreativshik113
3.sovetnik49
4.MrCredo38
5.IQFun30
6.Pro100_Artyom27
7.marutand20
8.хан20
9.никник15
10.Фигаро15

ГлавнаяГостевая книгаFAQОбратная связьКоллегиФорум Эрудитов