Archived

This topic is now archived and is closed to further replies.

Burning_Ice

Can this be solved?

Recommended Posts

well first i have to apologize since this isn''t really gamedev/programming related, but i figured since there are so many smart people here asking won''t hurt I have a little problem with a riddle, which i don''t think is possible to solve at all, but i don''t know for sure. The riddle goes something like this: there are 4 switches, aligned in a square. goal is to bring them all in the same position, but you never see them and don''t know their initial positions (on or off). You only have have 3 buttons: A will change the state of one randomly chosen switch, B will change the state of two randomly chosen switches (with both being in the same row or column), and C will change the state of two randomly chosen switches that are in a diagonal line. Now the riddle asks for the shortest code (series of A, B, C buttons to be pressed) that is guaranteed to bring all switches in the same position, no matter what their initial position was. Now i''m pretty sure this isn''t solvable, since you never know anything about the current state of the switches and its almost completely random which switches do change when you hit a button so you will never reach a position that is guaranteed to produce the desired goal in the next step, so already the first step when trying to solve this thing (or proof it''s solvability) with induction fails. I also wrote some piece of code that just tries one ''code'' after the other..it''s running since two hours now, currently at a codelength of 19, and still no goal. Well, i''m not asking for a solution to this problem, i just want to know if it is possible to solve at all( and if so, why?), or if it''s unsolvable and i can stop wasting time with it Thanks
Runicsoft -- latest attraction: obfuscated Brainfuck Interpreter in SML ( This post was made entirely from re-cycled electrons )

Share this post


Link to post
Share on other sites
I''m thinking the same thing. If you don''t know where you started, you can''t check in-between, and you don''t know when to stop, then it seems unlikely that you can come up with the magic sequence that always works. The other thing is that is randomly chooses a switch. If you were to solve this, you''d probably have to use probabilities and find the code that is simply most likely to cause all the switches to be the same.

It''s an interesting riddle thought, definitely worth the brain time.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
No sequence is more likely than the other. Given no information about the initial or current state, the probability is 1/16 regardless of what buttons you press.

Share this post


Link to post
Share on other sites
Where did you get this riddle anyway? Like AP implyed, it''s just whatever the chance is that they are all the same state at the beginning - the probability would be 1/8 though, 1 condition when they''re all on plus 1 condition when they''re all off, out of 16 configurations.

Share this post


Link to post
Share on other sites
Check out your library. You may be able to find a book on math tricks. I know that i''ve seen books before on problems like these.

On a side note... have you ever watched David Copperfield? And he has a trick for the viewers at home to participate in... those magic tricks play solely on math and due to the arrangements always end up in the same way. Its really fascinating. Good luck in trying to find out... I myself would start with a pen and paper... you only have 4 switches... so... actually testing out all there solutions can be done... Hell... Make a program to test probailities and solutions for ya. WOuldn''t be a hard console program to do. Good luck...

Sincerely,
Brent "DD"

Share this post


Link to post
Share on other sites
I think

CBCACBC

will do it: if you operate the buttons in the above sequence then I think one of the arrangements of lights will be all the same (not necessarily the final position, there''s no sequence that guarantees that). And I think this is shortest.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Very nice. The sequence seems to work and a shorter one is obviously not possible.

Share this post


Link to post
Share on other sites
thanks for all the answers, but i still think it''s not possible to solve
as i said, i already wrote a program, which i had test all sequences of upto length 20 without success so far. (would be a bit hard to do it by hand.. )
the CBCACBC unfortunately doesn''t help, since it doesn''t put all switches in the same position, and even if it would put them in the same arrangement all the time (which it doesn''t always do according to my tests) it would be no better then any random initial arrangment
but thanks anyway


Runicsoft -- latest attraction: obfuscated Brainfuck Interpreter in SML
( This post was made entirely from re-cycled electrons )

Share this post


Link to post
Share on other sites
> the CBCACBC unfortunately doesn''t help, since it doesn''t put
> all switches in the same position,

Hm, I think it does. Didn''t bother with a program just logic like so:

Initially either 4, 3 or 2 are the same
4: Already all the same, i.e. this sequnce does it after 0 buttons

2: then either:
* diagonal pairs the same, then all the same after C (done after 1 button)
* horizontally or vertically the same:
** after C have vertically or horizontally the same (swapped from above)
** after CB have either 4 the same (done after 2 buttons) or have diagonals the same, so CBC makes all 4 the same (done after 3 buttons)

3: after pressing CBC still odd number lit, i.e. still 3 the same. After CBCA even number the same so either 4 the same (done after 4 buttons), or 2 the same. If 2 then repeating CBC results in all the same after 5, 6 or 7 buttons.

If you object to it being solved after 0 then insert an extra button at the start, e.g.

ACBCACBC

Then it''s got to be the same after 1, 2, 3, 4, 5, 6, 7 or 8 button presses.

As noted earlier it''s only possible to solve this way. There''s no way you can produce a fixed sequence that always makes them all the same at the end: I think the ending arrangement is as random as the initial arrangement for a fixed sequence, so any sequence is as good or bad as any other at producing a correct pattern at the end.

Share this post


Link to post
Share on other sites