Нека бъде светлина!

[ql^2/8]

Поздравявам ви с тая песен на Подуене-блус бенд:
http://vbox7.com/play:d15e9314

И една задачка в петък:
Лампа е свързана така, че да се захранва през 4 последователни ключа,
разположени в ъглите на въртяща се квадратна маса.
Всички трябва да са едновременно включени, за да светнем лампата.
Самите бутони при натискане сменят алтернативно включено/изключено,
но няма индикация за текущото положение.
Можем да превключим едновременно един, два, три, или и четирите
ключа, след което масата се завърта в тъмното (не можем да проследим
мястото на ключовете) и застава в ново положение.
Намерете стратегия за да има светлина.

* * *
О-о-о-обичам почивните дни! (ама това е друга песен)

[MitkoS]

Хе-хе, най-много 15 хода (завъртания) и лампата е запалена. Не знам дали може да се оптимизира към по-късо решение. Не съм и търсил оптимизация.

По-трудно е да се опише отколкото да се реши.
Работим в двоична бройна система. Ако ключа прекъсва веригата означаваме с 0, ако свързва означаваме с 1.
Имаме двоично число с четири позиции - демек десетично от 0 до 15.
Ако стигнем някак си до 15 (или 1111 двоично) в положението на ключовете, значи имаме светлина.

Разбиваме числата на множества,
0 = {0000 - двоично} = {0 - десетично}
A = {0001, 0010, 0100, 1000 - двоично} = {1, 2, 4, 8 - десетично}
B = {0011, 0110, 1100, 1001 - двоично} = {3, 6, 12, 9 - десетично}
C = {0101, 1010 - двоично} = {5, 10 - десетично}
D = {0111, 1011, 1101, 1110 - двоично} = {7, 11, 13, 14 - десетично}
L = {1111- двоично} = {15 - десетично} (означението L идва от LIGHT)

Както се вижда, тия множества обхващат всичките числа от 0 до 15, т.е. няма как някое състояние да "избяга" и да не попадне в някое от множествата.
Другото много важно нещо в разбивката на тия множества е, че ако въртим масата без да цъкаме, то все сме си в едно и също множество, без значение колко пъти подред ще завъртим и без значение на колко точно градуса въртим (0, 90, 180, 270).

И сега правим магическата функция:
Множество1 (Множество2)=Множество3

където:
1. Множество1 означава завареното състояние преди поредния ход
2. Множество2 означава "цъкането" на ключовете на конкретен ход. Една такава особеност има тук - "цъкането" е равносилно на число, защо говорим за множество ? Ами за по-лесни означения ужким. Значи тук означаваме с Множество2 това множество в което попада числото на цъкането.
3. Множество3 - това е резултата след всеки ход (включва цъкането и завъртането). И имаме същата особеност като в 2

(ДОБАВКА: В тая функция няма нищо магическо - тя просто отразява цъкането на ключовете, което е двоичен XOR. Единственото "магическо" е в записването - вместо числа са множества.)

И сега с малко хамалски проверки намираме всичките възможни "базови" стойности при магическата функция. Тия така наречени от мен базови стойности са общо 6x6 = 36

(ДОБАВКА: "Базовите" стойности ги нарекох базови щото Множество1 е множество от разбивката 0,A,B,C,D,L)

БАЗОВИ СТОЙНОСТИ:
01. 0(0) = 0
02. A(0) = A
03. B(0) = B
04. C(0) = C
05. D(0) = D
06. L(0) = L
07. 0(A) = A
08. A(A) = {0 или B или C} = {0,B,C}
ЗАБЕЛЕЖКА: За по-кратко надолу няма да пиша "или". T.e. множество с елементи множества ще означава множество от елементите на обединението на множествата.
09. B(A) = {A,D}
10. C(A) = {A,D}
11. D(A) = {B,C,L}
12. L(A) = {D}
13. 0(B) = {B}
14. A(B) = {A,D}
15. B(B) = {0,C,L}
16. C(B) = {B}
17. D(B) = {A,D}
18. L(B) = {B}
19. 0(C) = {C}
20. A(C) = {A,D}
21. B(C) = {B}
22. C(C) = {0,L}
23. D(C) = {A,D}
24. L(C) = {C}
25. 0(D) = {D}
26. A(D) = {B,C,L}
27. B(D) = {A,D}
28. C(D) = {A,D}
29. D(D) = {0,C,B}
30. L(D) = {A}
31. 0(L) = {L}
32. A(L) = {D}
33. B(L) = {B}
34. C(L) = {C}
35. D(L) = {A}
36. L(L) = {0}
Така написаните базови стойности на практика съм ги проверявал и изчислявал една по една (... въобще не е трудно).

Идеята на решението е, така да правим ходовете, че да контролираме резултатите и постепенно да изолираме(изхвърляме) множества от резултатите, докато накрая в резултата остане само L.

По-долу са 15-те хода, с които гарантирано се стига до резултат само L, като този резултат може да излезе и на междинен ход. Важното е, че на 15-тия ход това е единствения резултат.
И една друга особеност има в ходовете - ако в междиния резултат може да присъства 0, то на следващия ход непременно цъкаме и четирите ключа - по някаква случайност всичките нечетни ходове са такива.

Състоянието преди N-тото завъртане е означено с XN. А верноста на "равенствата" при ходовете следва от по-горните 36 на брой базови стойности на магическата функция, които съм оцветил в синьо.

X1 = {0,A,B,C,D} - това заварваме преди първото цъкане
1. X1(L) = X2 = {A,B,C,D,L}
2. X2(C) = X3 = {0,A,B,D,L}
3. X3(L) = X4 = {A,B,D,L}
4. X4(B) = X5 = {0,A,C,D,L}
5. X5(L) = X6 = {A,C,D,L}
6. X6(C) = X7 = {0,A,D,L}
7. X7(L) = X8 = (A,D,L}
8. X8(A) = X9 = {0,B,C,L}
9. X9(L) = X10 = {B,C,L}
10. X10(C) = X11 = {0,B,L}
11. X11(L) = X12 = {B,L}
12. X12(B) = X13 = {0,C,L}
13. X13(L) = X14 = {C,L}
14. X14(C) = X15 = {0,L}
15. X15(L) = X16 = {L}

или записано по друг начин, ходовете са
1. 1111 - това е от L,
2. 0101 - това е от C, може и 1010,
3. 1111 - това е от L
4. 0011 - това е от B, може и 0110, 1100, 1001
5. 1111 - това е от L
6. 0101 - това е от C
7. 1111 - това е от L
8. 0001 - това е от A, може и 0010, 0100, 1000
9. 1111 - това е от L
10. 0101 - това е от C
11. 1111 - това е от L
12. 0011 - това е от B
13. 1111 - това е от L
14. 0101 - това е от C
15. 1111 - това е L

Хи-хи, ако има нещо неясно - питайте !
И една такава молба - преди да питате, прочете поста ми открай-докрай ! Напълнил съм го с пояснения и може четейки пътьом да стигнете до извода че няма нужда от питане.

ПП.
Много ще се радвам, ако някой с актуални познания в програмирането направи/напише нужната програма, с която експериментално да потвърди (или отхвърли), че с тези 15 хода (че с тези конкретни 15 на брой числа) непременно палим лампата, независимо от първоначалното състояние и независимо на колко градуса е завъртяна масата (0,90,180,270).

[Yasen6275]

Незнам дали влияе на разсъжденията ти, но имам малко възражения по базовите стойности. Всички на които им прилагаш 0-ли или започват от L не са възможни по условие.
_________________________________________________[color=red]слети поредни публикации на: [time]1342940640[/time]_________________________________________________

0 = {0000 - двоично} = {0 - десетично}
A = {0001, 0010, 0100, 1000 - двоично} = {1, 2, 4, 8 - десетично}
B = {0011, 0110, 1100, 1001 - двоично} = {3, 6, 12, 9 - десетично}
C = {0101, 1010 - двоично} = {5, 10 - десетично}
D = {0111, 1011, 1101, 1110 - двоично} = {7, 11, 13, 14 - десетично}
L = {1111- двоично} = {15 - десетично} (означението L идва от LIGHT)
БАЗОВИ СТОЙНОСТИ:
01. 0(A) = A
02. A(A) ={0,B,C}
03. B(A) = {A,D}
04. C(A) = {A,D}
05. D(A) = {B,C,L}
06. 0(B) = {B}
07. A(B) = {A,D}
08. B(B) = {0,C,L}
09. C(B) = {B}
10. D(B) = {A,D}
11. 0(C) = {C}
12. A(C) = {A,D}
13. B(C) = {B}
14. C(C) = {0,L}
15. D(C) = {A,D}
16. 0(D) = {D}
17. A(D) = {B,C,L}
18. B(D) = {A,D}
19. C(D) = {A,D}
20. D(D) = {0,C,B}
21. 0(L) = {L}
22. A(L) = {D}
23. B(L) = {B}
24. C(L) = {C}
25. D(L) = {A}

Орязах излишъците, да видим дали няма да доведе до оптимизация.

[b]X1 = {0,A,B,C,D} - това заварваме преди първото цъкане
1. X1(L) = X2 = {A,B,C,D}
2. X2(C) = X3 = {0,A,B,D}
3. X3(L) = X4 = {A,B,D}
4. X4(B) = X5 = {0,A,C,D}
5. X5(L) = X6 = {A,C,D}
6. X6(C) = X7 = {0,A,D}
7. X7(L) = X8 = (A,D}
8. X8(A) = X9 = {0,B,C}
9. X9(L) = X10 = {B,C}
10. X10(C) = X11 = {0,B}
11. X11(L) = X12 = {B}
12. X12(B) = X13 = {0,C}
13. X13(L) = X14 = {C}
14. X14(C) = X15 = {0}
15. X15(L) = X16 = {L}

Ми аз не виждам оптимизации. Просто ше резюмирам схемата която си предложил.

1. Всеки нечетен ход се цъкат всички ключове.
2. При четните се редува - диагонал, съседни, диагонал, един, диагонал, съседни. диагонал

[MitkoS]

"Базовите" стойности ги нарекох базови щото Множество1 е множество от разбивката 0,A,B,C,D,L. Те са 36 на брой, но наистина за изчисляването на ходовете не се ползват всичките.

Това е все едно таблицата за умножение на числата от 1 до 10 - колко са там, ъъъ, ако не бъркам нещо, те са 55 на брой "базови" умножения, които сме научили наизуст в 1-ви клас.
(ДОБАВКА: Всъщност броя е 100=10x10. Но понеже a.b=b.a можем да помним само 55. Даже помним само 45 на брой, щото 1.а=а. Даже помним още по-малко, щото 0.а=0)

Но когато ползваме тази таблица за да умножин две конкретни големи числа, не ползваме непременно всичките редове от таблицата, а само тези от които имаме нужда при конкретното умножение на двете големи числа.

Съкращаването на "базовите" стойности не води до оптимизация. Но може и да може да се съкрати броя на ходовете, ака се приложат други в друга последователност.

А що се отнася за:
"2. При четните се редува - диагонал, съседни, диагонал, един, диагонал, съседни. диагонал"
въобще не съм гледал кое число на какво отговаря (диагонал или съседни). Така здраво съм потънал в модела с множествата, че всичко в главата ми е само двоични цифри и "базовите" операции, които са си най-обикновен XOR. Направо се изкефих, като разбрах как съм се откъснал от действителността.
Да, може да се каже "диагонал, съседни, диагонал, един, диагонал, съседни. диагонал", но все пак трябва и да се докаже защо върши работа, при каквото и да е първоначално състояние и при каквото и да е завъртане на всеки ход - нещо което считам че съм показал в предишния пост.

ПП.
На който му е трудно да вникне в решението, да се фокусира първо върху 13-ти, 14-ти и 15-ти ход.
12. ... X13 = {0,C,L}
13. X13(L) = X14 = {C,L}
14. X14(C) = X15 = {0,L}
15. X15(L) = X16 = {L}
При тия последни ходове резултатите вече са се опростили и е по-лесно да се разберат записванията и равенствата. След което и останалите ходове по-лесно се разбират.

ПП2.
Сега на 20-то четене, виждам, че това с магическата функция може да се запише по-ясно (уж) така:
- всички знаем какво е операцията XOR между две двоични числа
- можем да я разширим и върху две множества като дефинираме, че резултата е множество от всички възможни състояния - точно това е магическата функция по-горе
И сега означенията стават:
12. ... X13 = {0,C,L}
13. X13 XOR L = X14 = {C,L}
14. X14 XOR C = X15 = {0,L}
15. X15 XOR L = X16 = {L}

ПП3.
"...X1 = {0,A,B,C,D} - това заварваме преди първото цъкане..."
Така както е записано, означава, че X1 е елемент на обединението на 0, A, B, C и D, т.е. може да е каквото и да е от 0 до 14 (десетично).
Гледайки алгоритъма от 15-те хода, (а също и базовите стойности) може да се каже още, че:
- ако X1 е от 0, то лампата ще светне още на първия ход
- ако X1 е от C, то лампата ще светне на втория или третия ход
- ако X1 е от B, то лампата ще светне на четвъртия или петия или шестия или седмия ход
- ако X1 е от A или D, то лампата ще светне от осмия ход нататък
т.е. ако началното състояние на ключовете е:
- всички ключове са "изключено" ==> ламата светва още на първия ход
- по единия диагонал са включени, по другия изключени ==> лампата светвa на втория или третия ход
- два съседни са включени, другите два изключени ==> лампата светва от четвъртия до седмия ход
- или един или три ключа са включени ==> лампата светва от осмия до петнадесетия ход

[ql^2/8]

Страхотно!
Изобщо не предполагах, че мога да дам толкова сложна задача! ,
Всъщност отговорът е верен, но ми трябваха няколко дни да го
прочета докрая. Добре, че Yasen6275 ми помогна!

А дали ако масата не се върти има по-кратко решение?

[MitkoS]

Ако масата не се върти, доколкото виждам има и поне едно друго решение пак от 15 хода -
числата от 1 до 15 са решение (от 1 до 15, не от 0 до 15) при това може и да са в разбъркан ред.

Май няма как да стане с по-малко ходове, заради следните съобръжения, които не са стриктно доказателство:1. На всяка стъпка правим XOR между две числа (четирибитови),
2. Ако X, Y, Z са такива четирибитови числа и ако X е различно от Y, то (X XOR Z) е различно от (Y XOR Z) за всяко Z.
3. За операцията XOR имаме (A XOR B) XOR C = A XOR (B XOR C) (забравил съм точната думичка за това свойство (срам, срам), но пък току що го проверих свойството, вярно е)
4. И тъй като имаме 15 възможни различни първоначални стойности и всяка една от тях се трансформира до 1111 чрез уникална поредица от XOR-операции (виж 2. и 3.) то няма как броя на ходовете да са по-малко от броя на първоначалните стойности. Ако допуснем че са по-малко, то ще стигнем до противоречие с 2. и 3. (така на око ако искаме да е стриктно, противоречието ще го получим с индукция)

И едно очевидно обобщение за невъртяща се маса:
При N на брой ключове, с 2^N на брой ходове палим лампата
Ако масата се върти, не знам за обощението, може и да го има но не го виждам ... няма и да го търся.

[tonych]

и аз умувах малко по задачата не можах да я направя с по-малко ходове, ето моя вариант:
първоначално положение на ключовете
a)----
b)--++
c)-+-+
d)-+++
e)---+
действия които можем да извършим:
1. да натиснем един ключ
2а. да натиснем два съседни ключа
2б. да натиснем два несъседни (през един) ключа
3.три ключа
4. четири ключа
стратегия
1.4 действие изключваме а)
2.2б най-лесно се проверява с)
3.4 ако не светне значи е b)
4.2а
5.4 ако не светне се е превърнало пак в с)
6.2б
7.4 d) и e) при тези действия не се променят (най-много да преминат едно в друго)така, че ако не сме успели продължаваме нататък
8.1 превръщаме d) и e) в b) или с)
9.4
10.2б
11.4
12.2а
13.4
14.2б
15.4 нека бъде светлина

разбира се както каза МиткоС може да светне и далеч по-рано от последния ход

[Yasen6275]

А дали ако масата не се върти има по-кратко решение?

Поне с тази логика не мисля че има по-кратък.