• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 00:21
CEST 06:21
KST 13:21
  • 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
[ASL19] Finals Recap: Standing Tall9HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Flash Announces Hiatus From ASL60Weekly Cups (June 23-29): Reynor in world title form?13FEL Cracov 2025 (July 27) - $8000 live event19Esports World Cup 2025 - Final Player Roster16Weekly Cups (June 16-22): Clem strikes back1
StarCraft 2
General
Program: SC2 / XSplit / OBS Scene Switcher Statistics for vetoed/disliked maps The SCII GOAT: A statistical Evaluation Weekly Cups (June 23-29): Reynor in world title form? PiG Sty Festival #5: Playoffs Preview + Groups Recap
Tourneys
FEL Cracov 2025 (July 27) - $8000 live event RSL: Revival, a new crowdfunded tournament series Korean Starcraft League Week 77 Master Swan Open (Global Bronze-Master 2) [GSL 2025] Code S: Season 2 - Semi Finals & Finals
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma Mutation # 477 Slow and Steady
Brood War
General
Player “Jedi” cheat on CSL ASL20 Preliminary Maps SC uni coach streams logging into betting site Flash Announces Hiatus From ASL BGH Mineral Boosts Tutorial Video
Tourneys
[BSL20] Grand Finals - Sunday 20:00 CET [Megathread] Daily Proleagues Small VOD Thread 2.0 [BSL20] GosuLeague RO16 - Tue & Wed 20:00+CET
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile What do you want from future RTS games? Beyond All Reason
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread Trading/Investing Thread Things Aren’t Peaceful in Palestine The Games Industry And ATVI
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 508 users

Math Puzzle [num 19]

Blogs > evanthebouncy!
Post a Reply
evanthebouncy!
Profile Blog Joined June 2006
United States12796 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 States2801 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 States12796 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 States2801 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 States12796 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 States2801 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 States12796 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
Next event in 5h 39m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RuFF_SC2 208
ROOTCatZ 97
StarCraft: Brood War
Leta 885
Icarus 7
LuMiX 3
Dota 2
NeuroSwarm168
League of Legends
JimRising 882
Counter-Strike
tarik_tv5710
Heroes of the Storm
Khaldor153
Other Games
summit1g10232
WinterStarcraft350
ViBE195
ProTech47
SortOf7
Organizations
Other Games
BasetradeTV50
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 19 non-featured ]
StarCraft 2
• Berry_CruncH314
• Hupsaiya 75
• davetesta60
• practicex 24
• LaughNgamezSOOP
• sooper7s
• AfreecaTV YouTube
• intothetv
• Migwel
• Kozan
• IndyKCrew
StarCraft: Brood War
• Diggity3
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
League of Legends
• Lourlo1035
• masondota2813
• Stunt360
Other Games
• Scarra3089
Upcoming Events
RSL Revival
5h 39m
Clem vs Classic
SHIN vs Cure
FEL
7h 39m
WardiTV European League
7h 39m
BSL: ProLeague
13h 39m
Dewalt vs Bonyth
Replay Cast
1d 19h
Sparkling Tuna Cup
2 days
WardiTV European League
2 days
The PondCast
3 days
Replay Cast
3 days
RSL Revival
4 days
[ Show More ]
Replay Cast
4 days
RSL Revival
5 days
FEL
5 days
RSL Revival
6 days
FEL
6 days
FEL
6 days
Liquipedia Results

Completed

BSL 2v2 Season 3
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
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 © 2025 TLnet. All Rights Reserved.