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


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


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


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


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


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


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

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

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

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


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


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


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


Сообщение отредактировал никник - Среда, 11.11.2015, 10:11
 
KreativshikДата: Суббота, 14.11.2015, 22:07 | Сообщение # 6
Гений
Сообщений: 2357
Награды: 247
Совы: 112
Цитата никник ()
а 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(5Kb) · 5523484.jpg(5Kb)


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


Сообщение отредактировал Kreativshik - Суббота, 14.11.2015, 22:19
 
KreativshikДата: Суббота, 14.11.2015, 22:38 | Сообщение # 7
Гений
Сообщений: 2357
Награды: 247
Совы: 112
Цитата никник ()

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

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


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

Интересная информация
Обновленные задачи
Рейтинг сообщений Совиный рейтинг
1.Последовательность2
2.Чудо-Юдо и три головы7
3.Добрый тролль4
4.Каково соотношение площад...0
5.Математическое равенство7
6.Еще одна задача на постро...0
7.Построим касательные.4
8.Любви Вам9
9.Как заморозить воду ?3
10.Четырехугольник0
1.Lexx4728
2.Rostislav4638
3.nebo3394
4.Иван3061
5.Kreativshik2357
6.никник1944
7.Гретхен1802
8.erudite-man1289
9.Valet937
10.goliv772
1.Kreativshik112
2.nebo110
3.sovetnik49
4.IQFun28
5.Pro100_Artyom27
6.marutand20
7.хан20
8.MrCredo13
9.slltllnll12
10.Ленка11


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