• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 19:15
CET 01:15
KST 09:15
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #238[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over2Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
No more SC2 streamers on team liquid? Team Liquid Map Contest #23 Dark completes military service, returns to SC2 Weekly Cups (Nov 9-15): Clem and herO take over StarCraft open world shooter announced at BlizzCon
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22 Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
List of top players active on ShieldBattery BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion NaDa's Body Light introduces ShieldBattery on his YouTube
Tourneys
SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [Megathread] Daily Proleagues [BSL23] Ro16 Group D - Sunday 21:00 CET [BSL23] Ro16 Group B - Saturday 21:00 CET
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Warcraft III: The Frozen Throne Nintendo Switch Thread Stormgate/Frost Giant Megathread Free Space RTS Game, optimised f. Phone/Tablet etc List of Game Threads
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Trading/Investing Thread Artificial Intelligence Thread Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 17671 users

Math Puzzle [num 19]

Blogs > evanthebouncy!
Post a Reply
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
Last Edited: 2011-04-12 09:49:33
April 12 2011 09:43 GMT
#1
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.

*****
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
MisterD
Profile Blog Joined June 2010
Germany1338 Posts
April 12 2011 09:46 GMT
#2
does arbitrary configuration mean, they are arranged randomly on the wall, or that they are randomly switched on and off before you enter?
Gold isn't everything in life... you need wood, too!
Slithe
Profile Blog Joined February 2007
United States985 Posts
April 12 2011 09:53 GMT
#3
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.
iGrok
Profile Blog Joined October 2010
United States5142 Posts
April 12 2011 10:30 GMT
#4
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 :Þ
MOTM | Stim.tv | TL Mafia | Fantasy Fighting! | SNSD
incnone
Profile Joined July 2009
17 Posts
Last Edited: 2011-04-12 11:17:19
April 12 2011 11:00 GMT
#5
Good to see you back -- you always post good puzzles.
iGrok
Profile Blog Joined October 2010
United States5142 Posts
April 12 2011 11:02 GMT
#6
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
MOTM | Stim.tv | TL Mafia | Fantasy Fighting! | SNSD
MasterOfChaos
Profile Blog Joined April 2007
Germany2896 Posts
April 12 2011 11:14 GMT
#7
+ 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.
LiquipediaOne eye to kill. Two eyes to live.
Seth_
Profile Blog Joined July 2010
Belgium184 Posts
Last Edited: 2011-04-12 15:10:52
April 12 2011 14:09 GMT
#8
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)
iGrok
Profile Blog Joined October 2010
United States5142 Posts
Last Edited: 2011-04-12 14:36:01
April 12 2011 14:34 GMT
#9
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
MOTM | Stim.tv | TL Mafia | Fantasy Fighting! | SNSD
MasterOfChaos
Profile Blog Joined April 2007
Germany2896 Posts
April 12 2011 14:37 GMT
#10
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.
LiquipediaOne eye to kill. Two eyes to live.
iGrok
Profile Blog Joined October 2010
United States5142 Posts
April 12 2011 16:12 GMT
#11
theres also no solution for non-integer k :p
MOTM | Stim.tv | TL Mafia | Fantasy Fighting! | SNSD
EsX_Raptor
Profile Blog Joined February 2008
United States2802 Posts
Last Edited: 2011-04-12 19:08:15
April 12 2011 17:54 GMT
#12
+ Show Spoiler +
Hamming Code

Suppose n = 8 and the following is our random on/off (red/black) sequence:

[image loading]

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]

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?
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
April 12 2011 20:28 GMT
#13
On April 13 2011 02:54 EsX_Raptor wrote:
+ Show Spoiler +
Hamming Code

Suppose n = 8 and the following is our random on/off (red/black) sequence:

[image loading]

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]

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
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
EsX_Raptor
Profile Blog Joined February 2008
United States2802 Posts
Last Edited: 2011-04-12 20:51:39
April 12 2011 20:50 GMT
#14
Here's one thread:

http://www.teamliquid.net/blogs/viewblog.php?topic_id=206477

I also made a pretty drawing in there explaining in more detail how the...

+ Show Spoiler +
... Hamming Code...

... works.

^^
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
April 12 2011 20:56 GMT
#15
On April 13 2011 05:50 EsX_Raptor wrote:
Here's one thread:

http://www.teamliquid.net/blogs/viewblog.php?topic_id=206477

I also made a pretty drawing in there explaining in more detail how the...

+ Show Spoiler +
... Hamming Code...

... works.

^^


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.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
EsX_Raptor
Profile Blog Joined February 2008
United States2802 Posts
April 12 2011 21:03 GMT
#16
On April 13 2011 05:56 evanthebouncy! wrote:
Show nested quote +
On April 13 2011 05:50 EsX_Raptor wrote:
Here's one thread:

http://www.teamliquid.net/blogs/viewblog.php?topic_id=206477

I also made a pretty drawing in there explaining in more detail how the...

+ Show Spoiler +
... Hamming Code...

... works.

^^


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. ^^
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
April 13 2011 02:10 GMT
#17
On April 13 2011 06:03 EsX_Raptor wrote:
Show nested quote +
On April 13 2011 05:56 evanthebouncy! wrote:
On April 13 2011 05:50 EsX_Raptor wrote:
Here's one thread:

http://www.teamliquid.net/blogs/viewblog.php?topic_id=206477

I also made a pretty drawing in there explaining in more detail how the...

+ Show Spoiler +
... Hamming Code...

... works.

^^


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?
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
Please log in or register to reply.
Live Events Refresh
Replay Cast
08:00
SC2 Kevin Scrim
CranKy Ducklings72
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft: Brood War
Artosis 455
Bishop 54
LuMiX 5
Dota 2
Gorgc5089
monkeys_forever441
Counter-Strike
Fnx 1204
Super Smash Bros
AZ_Axe33
Heroes of the Storm
Trikslyr72
Other Games
summit1g12173
tarik_tv4834
shahzam467
PiGStarcraft239
C9.Mang0184
ToD86
ViBE72
Organizations
Other Games
gamesdonequick409
BasetradeTV120
[ Show 12 non-featured ]
StarCraft 2
• Hupsaiya 115
• musti20045 48
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• Azhi_Dahaki4
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Other Games
• Shiphtur894
Upcoming Events
Online Event
9h 46m
GSL
11h 16m
Maru vs Dark
Patches Events
13h 46m
OSC
15h 46m
Replay Cast
22h 46m
KCM Race Survival
1d 9h
Ultimate Battle
1d 11h
ZerO vs Bisu
RSL Revival
2 days
BSL
2 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
3 days
[ Show More ]
IPSL
3 days
Ret vs ggnore13
nOmaD vs Aether
BSL
3 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
3 days
WardiTV Weekly
4 days
Kung Fu Cup
5 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
6 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.