Дана головоломка-пазл "пятнашка", простоты ради из 9 клеток, разобранная максимально сложным способом. 1)Привести необходимые и достаточные условия такого разброса.(Видимо,через размещение диаметральных,"медианных", центральной костяшек и пустого деления друг относительно друга ) 2)Найти (и обосновать) минимальное количество перемещений, требуемое для выигрыша в этом случае.(Пока понимаю только, что не меньше 7) 3) Есть ли для 8 костяшек случай несобираемой расстановки? (слышал, что для 15 есть) п.с. Ответов ни на один вопрос не знаю, сам пока ломаю голову. Отвечать можно в любом порядке, с меня награда за ответ на любой вопрос.
Сообщение отредактировал erudite-man - Ср, 11.11.15, 14:20
1) Если для номера каждой клетки определить норму l1, то их сумма должна быть равна 21, при этом условии обязательно будет достигнута конфигурация максимальной сложности. норма l1 это расстояние, измеряемое в клетках, от текущего положения номера клетки до места базового положения данного номера.Конфигурацию считаем решённой, когда все номера находятся в базавом положении.
Сообщение отредактировал Kreativshik - Ср, 11.11.15, 01:54
а 21= (кол-во костяшек - 1)*3 (где 3 - минимальное кол-во перемещений составляющее цикл 1 хода определенной костяшки, или все таки размерность "матрицы")?
ЦитатаKreativshik ()
3) Да, их 181440
половина всех возможных размещений?
ЦитатаKreativshik ()
2) 31, меньше в этом случае не получится
Спасибо, теперь, пожалуй, попробую тоже найти решение.
Сообщение отредактировал никник - Ср, 11.11.15, 10:07
Я думаю так. Имеющийся квадрат 3х3, разбиваем на квадраты 2х2. Собственно это можно сделать всего 1 способом. Очевидно, что решение головоломки достигается правильной последовательностью вращения этих квадратов. На 1й взгляд мне кажется, что каждый квадрат 2х2 имеет всего 4 состояния, и таким образом "пробегает" их все за 3 хода. Но это не так, в силу того, что костяшки могут (и должны) мигрировать из квадрата в квадрат, а также того, что изначально возможность вращения есть только в одном квадрате.. %) подумаю об этом завтра)
Сообщение отредактировал никник - Ср, 11.11.15, 10:11
а 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- лебегово пространство с единичной нормой.
