Фатална вечеря на свещи

[ql^2/8]

Задача:
Имаме вълшебен свещник с 13 свещи, разположени в кръг.
Някои от тях са запалени, други не. Магията се състои в това, че
ако запалим или угасим една свещ, съседните на нея свещи също сменят
своето състояние - угасените се запалват, запалените угасват.
Можем ли независимо от началното състояние, да запалим всички свещи?

[Bibi]

Тъй като 13 е просто число, смятам, че може. Но детайлно доказателство още нямам.
Стратегията ми е да се движим само в една посока и да сменяме свещта, която е след първата угасена, ако все още има угасени.

P.S.
Уф, не е добра стратегията, трябва друга.

[MitkoS]

Без значение броя на лампите, лесно се стига до състояние при което
или всички светят, или само една не свети.

Ако решим задачата за конкретната обща бройка 13 при която само една не свети, то сме решили и основната задача

--------------------------------------------------
Как се стига до състояние при което всички светят без една, когато броя е N:
За момент си представяме, че вместо в кръг са наредени в редица и сме ги номерирали от 1 до N
Гледаме първата - ако свети то преминаваме на втората, а ако не свети, то цъкаме втората и първата светва, т.е. палим първата чрез втората.
Правим същото за втората, като ако не свети я палим чрез третата
и т.н.
гледаме n-тата, където n < N - 3
ако n-тата свети, подминаваме я, ако не свети, то палима я чрез (n+1)-вата
И така гарантирано успяваме за запалим първите N - 3
остават последните 3 в тази редица, чието състояние може да бъде
000, 001, 010, 011, 100, 101, 110, 111 (0 означава "не свети", 1 означава "свети")

ако е 000 то палим средната и става на 111 - т.е. всичките N светят
ако е 111 нищо не правим и пак всичките N светят

ако е 001, или 101, или 110 то значи, че N-1 светят, а една единствена не свети

ако е 001, или 010, или 100, палим средната от тия три и отиваме в горния случай при който една единствена не свети от всичките N

Т.е., при N на брой лампи стигаме до състояние при което или всички светят или само една не свети.

-----------------------------------------------------------------------------------

ПП
Мноо съм прост !
Същото което съм написал горе става и за следното твърдение
"При N на брой лампи можем да стигнем до състояние при което само една лампа свети"
Т.е., прилагаме горния алгоритъм, като последователно гасим n-тата лампа използвайки при необходимост (n+1)-вата.
Т.е. при общ брой 13 лампи, имаме 12 изгасени и една светеща.
И сега несветещите 12 ги разделяме на четири тройки (една тройка се състои от три поредни лампи) и палим всяка една от тройките, като цъкаме тая по средата.

-----------------------------------------------------------------------------------
ПП2
Как се прави за 14 ?
Правим първо 13 изгасени и светеща последна
После палим предпоследната - и като резултат имаме две съседни светещи и всичките останали 12 несветещи.
Тук важното е, че светещите са съседни, което ни позволява останалите 12 несветещи пак да ги разделим на четири тройки, които да светнем всичките.

----------------------------------------------------------------------------------
ПП3
Лесно се обобщава, че:
"ако общия брой на лампите не се дели на три, то можем да ги светнем всичките, без значение какво е първоначалното им състояние"

А също и
"ако общия брой на лампите не се дели на три, то можем да ги изгасим всичките, без значение какво е първоначалното им състояние"

---------------------------------------------------------------------------------
ПП4
Изпуснал съм един случай и той засега остава нерешен - това е ситуацията при която сме изгасили първите N-3 лампи, а оставащите последни три също са изгасени, т.е. стигнали сме до състояние при което всички лампи са изгаснали.

---------------------------------------------------------------------------------
ПП5
Намерих решение и за този случай, но е свързан нови допълнителни 9 превключвания (9 превключвания при 13 лампи)
Девет в случая е "магическа" бройка защото:
Девет превключвания сменят общо 27 състояния на лампите.
Тези 27 смени на състоянията могат да бъдат разпределени така (лесно се вижда как става)
12 лампи сменят състоянието си два пъти
13-сетата сменя състоянието си три пъти
(27=12*2+1*3)
което означава, че след тези девет превключвания първите 12 са се върнали в изходно положение (четен брой пъти си сменят състоянието), а само последната си е променила състоянието след тези девет превключвания.
Т.е., при 13 лампи имаме алгоритъм от девет превключвания, при който алгоритъм накрая сменяме състоянието само на една лампа.
Който пък алгоритъм можем да го приложим поотделно за всички първоначално несветещи лампи и с него да светнем всичките 13 лампи прилагайки алгоритъма най-много 13 пъти.

--------------------------------------------
ПП6
Лампи или свещи - все тая ... не ми се смейте много

[MitkoS]

В предишния пост обобщенията са неверни, защото е изпуснат случай.

Конкретно за 13 на брой може да се използва следния алгоритъм при който
с 9 на брой превключвания сменяме състоянието само на една свещ/лампа

Номерираме лампите Л1, Л2, Л3, ..., Л13
Първо превключваме следните четири тройки
(Л1, Л2, Л3)
(Л4, Л5, Л6)
(Л7, Л8, Л9)
(Л10, Л11, Л12),
Л13
После превклюваме следните четири тройки
(Л13,Л1, Л2,)
(Л3, Л4, Л5)
(Л6, Л7, Л8)
(Л9, Л10, Л11),
Л12
И накрая правим деветото превключване
(Л12, Л13, Л1)
При тези девет превключвания Л1 е била цъкната три пъти, а всички останали от Л2 до Л13 са цъкнати точно два пъти.
Което значи, че само Л1 е сменила състоянието си.

Посочения алгоритъм можем да го приложим за всички първоначално изгасени лампи и накрая като резултат всички ще светят.

[ql^2/8]

Да обобщя дотук има за сравнение две стратегии от Митко:


1. Първа
- запалваме всички лампи (нищо, че са свещи)без една в 12 хода;
ако случайно се запалят всички - задачата пак е решена
- палим едната (ако е останала) в 9 хода


2. Втора стратегия
- гасим всички без една в 12 хода; ако случайно угасим всички - палим
една в 9 хода
- в 4 хода запалваме останалите 12 свещи (или пък лампи)

[kamenf]

Май вече се отговаря на въпроса "каква е оптималната стратегия?" щото на въпроса "може ли да се запалят" Митко вече показа, че да, може.

Аз бих казал, че очакваният максимален брой превключвания е около 13. Бих разглеждал все пак свещите в кръг и бих гледал поредиците от запалени/загасени свещи, като бих се "движил" и в двете посоки около дългите поредици, а не механично една по една. Така с около 4-5 превключвания от всяко начално състояние би се стигнало до поредица от 10 запалени, а останалите 3 във варианта две запалени могат да се гледат като вече направена първата от 9-те стъпки на Митко за палене на 1.

[vesivanova]

Малко наивно.
Ако се завъртя в кръг и духна всички запалени.
А после запаля само една?