Пятнашки

[Sirion]

Полагаю, всем знакома эта замечательная головоломка. Также, я надеюсь, все имеют представление о том, ка её собирать, и знают, что ровно половину позиций собрать невозможно (можно привести лишь к состоянию, когда на своих местах находятся все костяшки, кроме 15 и 14).



Эту головоломку можно усложнить, добавив между некоторыми полями перегородки. Например, если поставить перегородку между костяшками 10 и 8 на рисунке, головоломку по-прежнему можно будет собрать (хотя это и станет несколько труднее). В то же время, если поставить перегородку между 3 и 11, сборка окажется невозможной.

А теперь задача: какое максимальное количество перегородок можно поставить так, чтобы любая позиция, которую можно было собрать в нормальных пятнашках, была собирабельна и в усложнённой версии?

[семеныч]

 

[Booka1a]

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

[Sirion]

мало)

[Booka1a]

шесть
слева от 6, слева и над 10, справа от 8, справа и под 7, правда это уже копец по-моему

даже 7
три стороны центрального квадрата и одна перемычка, примыкающая к краю, например, если стороны центрального квадрата верх(2), лево(2), право(2) , то седьмая между 15 и 12

[Sirion]

достаточно) а слабо обосновать, что:

а) мы действительно сможем собрать такую пятнашку;

б) восемь стенок не поставить ну никак?

[Booka1a]

достаточно) а слабо обосновать, что:

а) мы действительно сможем собрать такую пятнашку;

б) восемь стенок не поставить ну никак?

ну первое кое-как обосную: если мы сможем провести одну змейку через все 16 полей, значит сможем на любое из них поставить любую цифру
а имея при этом один участок 2х2, мы можем еще и менять порядок цифр в змейке, периодически что-то вытаскивая в карман и вставляя обратно в другом месте, значит сможем полностью перебрать змейку в нужном порядке.
а второе думается мне вот как:
всего перегородок 24, а клеток 16
что бы можно было протащить змейку, нужно что бы отсутсвовали перегородки между каждой парой, т.е. 2 клетки = -1 перегородка, 3 клетки = -2... 16=-15, еще одна перегородка что бы замкнуть 1-ю и 16-ю клетки (т.е. если среди 16-ти клеток будут отсутствовать 15 перегородок, то получится разомкнутая линия, нужно убрать еще одну перегородку что бы линию замкнуть) и еще одну перегородку надо убрать что бы сделать дополнительное внутреннее кольцо (которым будем изменять порядок фишек в змейке)... всего -17 перегородок
24-17=7 = это наш максимум

[☭-Изделие 20Д]

16 - по периметру
21- оставив незакрытыми только места 1-2-3-4, 6-7 - по крайней мере останется играбельной

[Booka1a]

16 - по периметру
21- оставив незакрытыми только места 1-2-3-4, 6-7 - по крайней мере останется играбельной

не понял. можно поподробнее?

[☭-Изделие 20Д]

 
Типа такого 123467 с одной дыркой по своим местам расставить будет возможно

ну а периметр вообще ни на что не влияет, но стенки присутствуют 
PS и вообще насколько я помню игру "15" наверное можно отгородить весь центр т.е 6,7,8,10 с рисунка или по крайней мере 3 любые из них оставив только квадрат для маневра в углу и этого хватит чтобы оставшиеся можно было расставить по своим местам.

[Booka1a]

тоесть мы плюем на 9 фишек, которые вообще не двигаются и выстраиваем только 6?