• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 04:49
CEST 10:49
KST 17:49
  • 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 Tall6HomeStory 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 ASL41Weekly Cups (June 23-29): Reynor in world title form?12FEL Cracov 2025 (July 27) - $8000 live event16Esports World Cup 2025 - Final Player Roster16Weekly Cups (June 16-22): Clem strikes back1
StarCraft 2
General
Statistics for vetoed/disliked maps Esports World Cup 2025 - Final Player Roster The SCII GOAT: A statistical Evaluation How does the number of casters affect your enjoyment of esports? Weekly Cups (June 23-29): Reynor in world title form?
Tourneys
RSL: Revival, a new crowdfunded tournament series [GSL 2025] Code S: Season 2 - Semi Finals & Finals $5,100+ SEL Season 2 Championship (SC: Evo) FEL Cracov 2025 (July 27) - $8000 live event HomeStory Cup 27 (June 27-29)
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
Help: rep cant save Player “Jedi” cheat on CSL Flash Announces Hiatus From ASL [ASL19] Finals Recap: Standing Tall BGH Auto Balance -> http://bghmmr.eu/
Tourneys
[Megathread] Daily Proleagues [BSL20] GosuLeague RO16 - Tue & Wed 20:00+CET The Casual Games of the Week Thread [BSL20] ProLeague LB Final - Saturday 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
Russo-Ukrainian War Thread US Politics Mega-thread Things Aren’t Peaceful in Palestine Trading/Investing Thread 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 NBA General Discussion Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
Game Sound vs. Music: The Im…
TrAiDoS
StarCraft improvement
iopq
Heero Yuy & the Tax…
KrillinFromwales
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 580 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 1h 11m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 134
StarCraft: Brood War
Sea 3001
ToSsGirL 736
BeSt 612
actioN 313
Killer 200
GoRush 193
Nal_rA 106
Shinee 60
JulyZerg 56
Mong 46
[ Show more ]
Sharp 27
Noble 21
Sacsri 17
sSak 13
Bale 8
Dota 2
BananaSlamJamma405
XcaliburYe290
League of Legends
JimRising 533
Counter-Strike
Stewie2K895
shoxiejesuss854
Super Smash Bros
Mew2King229
Heroes of the Storm
Khaldor130
Other Games
shahzam1103
ceh9668
Happy317
rGuardiaN47
SortOf29
DeMusliM26
crisheroes24
Organizations
Other Games
gamesdonequick846
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 15 non-featured ]
StarCraft 2
• Berry_CruncH344
• LUISG 17
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2100
League of Legends
• Stunt766
• HappyZerGling78
Upcoming Events
The PondCast
1h 11m
RSL Revival
1h 11m
ByuN vs Classic
Clem vs Cham
WardiTV European League
7h 11m
ByuN vs NightPhoenix
HeRoMaRinE vs HiGhDrA
Krystianer vs sebesdes
MaxPax vs Babymarine
SKillous vs Mixu
ShoWTimE vs MaNa
Replay Cast
15h 11m
RSL Revival
1d 1h
herO vs SHIN
Reynor vs Cure
WardiTV European League
1d 7h
Scarlett vs Percival
Jumy vs ArT
YoungYakov vs Shameless
uThermal vs Fjant
Nicoract vs goblin
Harstem vs Gerald
FEL
1d 7h
Korean StarCraft League
1d 18h
CranKy Ducklings
2 days
RSL Revival
2 days
[ Show More ]
FEL
2 days
Sparkling Tuna Cup
3 days
RSL Revival
3 days
FEL
3 days
BSL: ProLeague
3 days
Dewalt vs Bonyth
Replay Cast
4 days
Replay Cast
5 days
The PondCast
6 days
Replay Cast
6 days
Liquipedia Results

Completed

Proleague 2025-06-28
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
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
YaLLa Compass Qatar 2025

Upcoming

CSLPRO Last Chance 2025
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.