Резултати от 1 до 7 от общо 7

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

Сподели във Facebook Сподели в Google Plus Сподели в Twitter Изпрати на Email Сподели в LinkedIn
  1. Member
    Тук е от
    Sep 2009
    Мнения
    699
    #1

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

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

  2.  
  3. Senior Member Аватара на Bibi
    Тук е от
    Nov 2004
    Мнения
    2,648
    #2

    Отговор: Фатална вечеря на свещи

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

    P.S.
    Уф, не е добра стратегията, трябва друга.
    Този пост е редактиран от Bibi; 30-09-17 в 11:21.

  4. Moderator Аватара на MitkoS
    Тук е от
    Mar 2005
    Мнения
    4,467
    #3

    Отговор: Фатална вечеря на свещи

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

    Ако решим задачата за конкретната обща бройка 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; 30-09-17 в 18:13.

  5. Moderator Аватара на MitkoS
    Тук е от
    Mar 2005
    Мнения
    4,467
    #4

    Отговор: Фатална вечеря на свещи

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

    Конкретно за 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 е сменила състоянието си.

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

  6. Member
    Тук е от
    Sep 2009
    Мнения
    699
    #5

    Отговор: Фатална вечеря на свещи

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


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


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

  7.  
  8. Member Аватара на kamenf
    Тук е от
    Feb 2005
    Мнения
    778
    #6

    Отговор: Фатална вечеря на свещи

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

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

  9. Novice
    Тук е от
    Jun 2017
    Мнения
    6
    #7

    Отговор: Фатална вечеря на свещи

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

Сподели във Facebook Сподели в Google Plus Сподели в Twitter Изпрати на Email Сподели в LinkedIn
SetCombG.com
SetCombG.com е портален сайт и Форум за битова техника, телевизори, климатици, лаптопи и смартфони, създаден през 1999 година.
Заедно сме над 15 години!
Този форум се задвижва, благодарение на Persy Сървър
Следвай ни
Горе