|
Friends it's been a while!! Here goes!
==THE PROBLEM==
There is a room with n lightbulbs, n is a power of 2, i.e. n = 2^k. These n lightbulbs are arranged in a straight line.
You and your friend Bob are allowed to discuss a strategy, after the discussion, you and bob will be seperated.
You will receive a piece of paper, and on that piece of paper, there will be a number, which is selected from {1,2,...,n}.
You will then enter a room of the lightbulbs. The initial configurations of the lightbulbs are arbitrary, i.e. some might be on, some might be off. you must flip one and only one light switch and then exit the room.
Bob will then enter the room, and depending on what he sees, he will be able to answer correctly what was the number you were given on that piece of paper.
Describe the strategy.
Again, put answers in spoilers, put discussion NOT in spoilers, have fun. Generate some discussions, etc 
Oh yeah it's not a trick question where bob will feel the temperature or anything like that...
mini-sub-problems:
Can you do it for n = 2?
Can you do it for n = 4?
Solving specialized instances of this problem is quite rewarding as well 
QnA(hopefully not too many T_T)
On April 12 2011 18:46 MisterD wrote:
does arbitrary configuration mean, they are arranged randomly on the wall, or that they are randomly switched on and off before you enter?
The latter, they are in a straight line and the on/off is arbitrary.
|
does arbitrary configuration mean, they are arranged randomly on the wall, or that they are randomly switched on and off before you enter?
|
United States985 Posts
I believe this problem is very similar to one that I posted a couple years back in my blog. I will refrain from participating in this one, as it will be interesting to see how people approach this problem.
|
Solution for n=2
+ Show Spoiler +
o = on
x = off
Bold is flip
j = number on paper
Tell Bob:
xx = j=1
ox = j=2
xo = j=1
oo = j=2
Starting possibilities:
j=1
xx
ox
xo
oo
j=2
xx
ox
xo
oo
I know that this is terribly done, but it 5:30 in the morning and I've been up all night lol.
My first suggestion was to break bulb #j, but apparently thats cheating :Þ
|
Good to see you back -- you always post good puzzles.
|
Solution for n=4
+ Show Spoiler +
j is number you are told
If single light on or off, n=j
If all same: x=1
If 2 same: position of second of type in col.1
Proof:
Start__ j=1 _ j=2 __ j=3 _ j=4
xxxx | oxxx xoxx xxox xxxo
oxxx | xxxx ooxx oxox oxxo
xoxx | xxxx ooxx xoxo xoox
xxox | xxxx xxoo oxox xoox
xxxo | xxxx xxoo xoxo oxxo
ooxx | oxxx xoxx ooxo ooox
xoox | xooo xoxx xxox ooox
xxoo | xooo oxoo xxox xxxo
ooox | oooo ooxx oxox xoox
xooo | oooo xxoo xoxo xoox
oooo | xooo oxoo ooxo ooox
oxoo | oooo xxoo oxox oxxo
ooxo | oooo ooxx xoxo oxxo
ooox | oooo ooxx oxox xoox
oxxo | oxxx oxoo ooxo xxxo
ooxx | oxxx xoxx ooxo ooox
oxxx | xxxx ooxx oxox oxxo
again, i'm kind of tired so I can't think of the full proof for n=n lol. Perhaps tomorrow I will
|
Germany2896 Posts
+ Show Spoiler +Call the number of the piece of paper x
I give each lightbulb a unique name from 0 to n-1.
Then I calculate m=binary xor of the names of all light bulbs which are on.
now I calculate s=m xor (x-1) and switch the bulb with that name.
Bob calculates m'=binary xor of the names of all light bulbs which are on and then adds 1 to obtain x.
Originally I tried a similar scheme with addition modulo n, but that didn't work out because I needed switching on->off and off->on have the same effect on m. The xor scheme only works on powers of two, but the question kindly restricted it to that.
|
n=2 solution (probably the same as iGrok but it's explained better)
+ Show Spoiler +I'm counting from 0..n-1 since I'm a computer science student with off=0, on=1.
If the number is 0, you turn the first light off (if it's already off, just flip the second light)
If the number is 1, you turn the first light on (if it's already on, just flip the second light)
|
On April 12 2011 23:09 Seth_ wrote:btw There's no solution for n=1 although it's a power of 2. You probably mean 2^k for k>0 n=2 solution (probably the same as iGrok but it's explained better) + Show Spoiler +I'm counting from 0..n-1 since I'm a computer science student with off=0, on=1.
If the number is 0, you turn the first light off (if it's already off, just flip the second light)
If the number is 1, you turn the first light on (if it's already on, just flip the second light)
EDIT: I suppose this works. I dislike it though :p
|
Germany2896 Posts
On April 12 2011 23:09 Seth_ wrote:
btw There's no solution for n=1 although it's a power of 2. You probably mean 2^k for k>0
The solution is trivial for n=1. The number on the piece of paper is always "1", so bob just needs to say "1" and he is done.
|
theres also no solution for non-integer k :p
|
+ Show Spoiler +Hamming CodeSuppose n = 8 and the following is our random on/off (red/black) sequence: ![[image loading]](http://i52.tinypic.com/ixfp1w.jpg) By applying Hamming Code, we can represent every number in the range of 1 to 8 by making use of the first, second and fourth lightbulbs as parity checkers: ![[image loading]](http://i54.tinypic.com/2zflboy.jpg) Not long ago, a TL user posted a question that could be resolved using Hamming Code as well. Is this a new trend or something?
|
On April 13 2011 02:54 EsX_Raptor wrote:+ Show Spoiler +Hamming CodeSuppose n = 8 and the following is our random on/off (red/black) sequence: By applying Hamming Code, we can represent every number in the range of 1 to 8 by making use of the first, second and fourth lightbulbs as parity checkers: Not long ago, a TL user posted a question that could be resolved using Hamming Code as well. Is this a new trend or something?
I actually don't know... can you link me? :p
|
|
|
Ah but that one is exactly the same as 1000 jars of millk 1 poisoned or what not and you have 10 slaves etc. I don't think you need hamming code to do that one since I did it w/o any knowledge of it. However I was having lots of trouble doing this one w/o hamming code. Maybe the two are really similar, it's just the process is reversed: One is you have something wrong, how to detect it, one is if you detect, what is wrong.
|
On April 13 2011 05:56 evanthebouncy! wrote:Ah but that one is exactly the same as 1000 jars of millk 1 poisoned or what not and you have 10 slaves etc. I don't think you need hamming code to do that one since I did it w/o any knowledge of it. However I was having lots of trouble doing this one w/o hamming code. Maybe the two are really similar, it's just the process is reversed: One is you have something wrong, how to detect it, one is if you detect, what is wrong.
I agree.
Also, you know there are many ways to kill the tiger. What I like the most is seeing how users with different professions/backgrounds/interests tackle the same problem in their own way. ^^
|
On April 13 2011 06:03 EsX_Raptor wrote:Show nested quote +On April 13 2011 05:56 evanthebouncy! wrote:Ah but that one is exactly the same as 1000 jars of millk 1 poisoned or what not and you have 10 slaves etc. I don't think you need hamming code to do that one since I did it w/o any knowledge of it. However I was having lots of trouble doing this one w/o hamming code. Maybe the two are really similar, it's just the process is reversed: One is you have something wrong, how to detect it, one is if you detect, what is wrong. I agree. Also, you know there are many ways to kill the tiger. What I like the most is seeing how users with different professions/backgrounds/interests tackle the same problem in their own way. ^^
mind if I ask what is your background?
|
|
|
|
|
|
EPT
