• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 15:37
CEST 21:37
KST 04:37
  • 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 TLMC #5: Winners Announced!0[ASL20] Ro8 Preview Pt2: Holding On9Maestros of the Game: Live Finals Preview (RO4)5TL.net Map Contest #21 - Finalists4Team TLMC #5: Vote to Decide Ladder Maps!0
Community News
5.0.15 Patch Balance Hotfix (2025-10-8)3Weekly Cups (Sept 29-Oct 5): MaxPax triples up3PartinG joins SteamerZone, returns to SC2 competition245.0.15 Balance Patch Notes (Live version)118$2,500 WardiTV TL Map Contest Tournament 152
StarCraft 2
General
5.0.15 Balance Patch Notes (Live version) 5.0.15 Patch Balance Hotfix (2025-10-8) The New Patch Killed Mech! Weekly Cups (Sept 29-Oct 5): MaxPax triples up Team TLMC #5: Winners Announced!
Tourneys
Sea Duckling Open (Global, Bronze-Diamond) $2,500 WardiTV TL Map Contest Tournament 15 RSL Offline Finals Dates + Ticket Sales! Tenacious Turtle Tussle Stellar Fest
Strategy
Custom Maps
External Content
Mutation # 494 Unstable Environment Mutation # 493 Quick Killers Mutation # 492 Get Out More Mutation # 491 Night Drive
Brood War
General
ASL20 General Discussion BW General Discussion Question regarding recent ASL Bisu vs Larva game [BSL21] - How to Qualify to Each League ? RepMastered™: replay sharing and analyzer site
Tourneys
[ASL20] Ro8 Day 4 Small VOD Thread 2.0 [Megathread] Daily Proleagues [ASL20] Ro8 Day 3
Strategy
Current Meta TvZ Theorycraft - Improving on State of the Art Proposed Glossary of Strategic Uncertainty 9 hatch vs 10 hatch vs 12 hatch
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread ZeroSpace Megathread Dawn of War IV Path of Exile
Dota 2
Official 'what is Dota anymore' discussion LiquidDota to reintegrate into TL.net
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Deck construction bug Heroes of StarCraft mini-set
TL Mafia
SPIRED by.ASL Mafia {211640} TL Mafia Community Thread
Community
General
US Politics Mega-thread Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread UK Politics Mega-thread The Games Industry And ATVI
Fan Clubs
The herO Fan Club! The Happy Fan Club!
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
2024 - 2026 Football Thread Formula 1 Discussion MLB/Baseball 2023 NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
SC2 Client Relocalization [Change SC2 Language] Linksys AE2500 USB WIFI keeps disconnecting Computer Build, Upgrade & Buying Resource Thread
TL Community
Recent Gifted Posts The Automated Ban List BarCraft in Tokyo Japan for ASL Season5 Final
Blogs
What your "aura" says about…
Peanutsc
Mental Health In Esports: Wo…
TrAiDoS
Try to reverse getting fired …
Garnet
[ASL20] Players bad at pi…
pullarius1
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1626 users

[Math Puzzle] Day4

Blogs > evanthebouncy!
Post a Reply
Normal
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
Last Edited: 2009-04-30 11:13:25
April 30 2009 10:14 GMT
#1
So day 4!

Previous day's puzzle was first solved by Abydos1 or Hamster1800. Abydos1 has very good intuition but Hamster1800's answer is more precise.
+ Show Spoiler [solution] +

define a function f to be the difference in heights of 2 opposite points, x and x+pi. f(x) = height(x) - height(x+pi) where x is an angle, range from 0 to 2pi.

f(0) can either be >0, <0, or = 0.
If f(0)=0, then we're done.
The case of f(0)>0 and f(0)<0 is symmetrical, so we'll suppose f(0)>0.

f(0)>0 means height(0)-height(pi)>0.
However, since height(0)=height(2pi) because the track is continuous, we'll also have
height(2pi)-height(pi)>0 by substitution.
Rearranging we find that f(pi)=height(pi)-height(2pi)<0
Therefore we have a function f, moving from f(0)>0 to f(pi)<0, then at some point between 0 and pi, say c, f(c)=0.
That is to say, height(c)=height(c+pi), for some c, and that those 2 point are the opposite point with same height.


Today's puzzle is this:
You have n prisoners, and a warden who has a wardrobe. In this wardrobe there are hats of n colors, with many hats for each color(>n).
For example, if there are 3 prisoners, there will be 3 different colors of hats, say red hats, green hats, and blue hats, with more than 3 each, Say 10 red hats, 4 green hats, and 6 blue hats, for instance.

The game:
-Warden will put one hat(any color the warden wishes) on each of a prisoner's head, a prisoner cannot see the color of his own hat, but can see everyone else's hats.
-The prisoner cannot communicate to each other when the game starts.
-The prisoner will write down on a piece of paper what color hat he thinks he himself is wearing.
-If AT LEAST 1 prisoner guesses his own hat's color correctly, they all get to be free.

Your job:
Devise a strategy for the prisoners before the game starts, so at least 1 person would guess his own hat color correctly.

Extra information:
-Warden will also know the strategy as well, and he will try to put hats in a certain way if your strategy can fail.

Clarifications:
On April 30 2009 19:49 MasterReY wrote:
do prisoners know how many hats of a certain color are in the wardrobe before/after warden puts the hats on the prisoners?

No, but they do know it is greater than n, and they cannot see the wardrobe before/after.

On April 30 2009 20:03 Nytefish wrote:
Do they know what colours are possible?

On April 30 2009 20:03 Zona wrote:
Do the prisoners know before what the specific colors are?

-Yes. They will know the n possible colours beforehand.

Again, put answers in spoiler tags, and clarification will be given as needed.

GL HF!

*****
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!
Spenguin
Profile Blog Joined November 2007
Australia3316 Posts
April 30 2009 10:27 GMT
#2
+ Show Spoiler +
Don't break the law.
< TeamLiquid CJ Entusman #46 > I came for the Brood War, I stayed for the people.
freelander
Profile Blog Joined December 2004
Hungary4707 Posts
April 30 2009 10:46 GMT
#3
so anyone can get an any coloured hat, and they can't communicate in any way
This is HARD.
And all is illuminated.
MasterReY
Profile Blog Joined August 2007
Germany2708 Posts
April 30 2009 10:49 GMT
#4
do prisoners know how many hats of a certain color are in the wardrobe before/after warden puts the hats on the prisoners?
https://www.twitch.tv/MasterReY/ ~ Biggest Reach fan on TL.net (Don't even dare to mention LR now) ~ R.I.P Violet ~ Developer of SCRChart
TL+ Member
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
Last Edited: 2009-04-30 11:00:05
April 30 2009 10:58 GMT
#5
On April 30 2009 19:49 MasterReY wrote:
do prisoners know how many hats of a certain color are in the wardrobe before/after warden puts the hats on the prisoners?

No, but they do know it is greater than n, and they cannot see the wardrobe before/after.
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!
Nytefish
Profile Blog Joined December 2007
United Kingdom4282 Posts
April 30 2009 11:03 GMT
#6
Do they know what colours are possible?
No I'm never serious.
Zona
Profile Blog Joined May 2007
40426 Posts
April 30 2009 11:03 GMT
#7
Do the prisoners know before what the specific colors are?
"If you try responding to those absurd posts every day, you become more damaged. So I pay no attention to them at all." Jung Myung Hoon (aka Fantasy), as translated by Kimoleon
kOre
Profile Blog Joined April 2009
Canada3642 Posts
April 30 2009 11:07 GMT
#8
This is how they get released.
+ Show Spoiler +
All the prisoners take their pencil/pens and attack the warden all at once.

P.S. Saving this post for when I figure out the answer
http://www.starcraftmecca.net - Founder
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
April 30 2009 11:11 GMT
#9
On April 30 2009 20:03 Nytefish wrote:
Do they know what colours are possible?


On April 30 2009 20:03 Zona wrote:
Do the prisoners know before what the specific colors are?


Yes. They will know the n possible colours beforehand.
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!
kOre
Profile Blog Joined April 2009
Canada3642 Posts
Last Edited: 2009-04-30 11:13:46
April 30 2009 11:13 GMT
#10
http://www.starcraftmecca.net - Founder
peanutter
Profile Joined February 2009
Australia165 Posts
April 30 2009 11:18 GMT
#11
i've solved this kind of problem twice before already and still forget how to do it
Malongo
Profile Blog Joined November 2005
Chile3472 Posts
April 30 2009 11:19 GMT
#12
+ Show Spoiler +
Help me! im still improving my English. An eye for an eye makes the whole world blind. M. G.
raiame
Profile Joined December 2007
United States421 Posts
April 30 2009 11:23 GMT
#13
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.
datscilly
Profile Blog Joined November 2007
United States529 Posts
April 30 2009 11:23 GMT
#14
+ Show Spoiler +
There are n colors. Assign a different number from 1 to n for each of the colors. Take the sum of all the hats (numbers) on all of the n prisoners, and mod n this sum. This sum mod n is a number from 0 to n-1.
Each prison cannot see their own hat, of course, so they do not know what the sum mod n is. However, if each prison guesses a different answer for the sum mod n, one of them will be correct. And if you have the correct sum mod n then it is possible to figure out your own hat color.
kOre
Profile Blog Joined April 2009
Canada3642 Posts
April 30 2009 11:25 GMT
#15
But you only know the colour of the hats, not how many of each you have.
http://www.starcraftmecca.net - Founder
Loanshark
Profile Blog Joined December 2008
China3094 Posts
April 30 2009 11:34 GMT
#16
One guy writes YOUR HAT IS N COLOR on his paper and shows it to the prisoner he just wrote about.
No dough, no go. And no mercy.
freelander
Profile Blog Joined December 2004
Hungary4707 Posts
April 30 2009 11:35 GMT
#17
On April 30 2009 20:23 raiame wrote:
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.


but they can't communicate at all
And all is illuminated.
Rhaegar99
Profile Blog Joined September 2008
Australia1190 Posts
Last Edited: 2009-04-30 11:52:09
April 30 2009 11:50 GMT
#18
+ Show Spoiler +
Each colour will be assigned a number from 1 to n. Every prisioner will write whatever colour onto the paper except for the two who are chosen last. The second last person will take 5X seconds to write down on his piece of paper, where X is the number that was assigned to the colour on the last prisioner's hat. The last prisioner will count how long the second person takes, and will then know which colour hat he is wearing.
stet_tcl
Profile Blog Joined May 2008
Greece319 Posts
Last Edited: 2009-04-30 12:13:40
April 30 2009 12:12 GMT
#19
On April 30 2009 20:35 freelander wrote:
Show nested quote +
On April 30 2009 20:23 raiame wrote:
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.


but they can't communicate at all


If I'm not mistaken they can communicate before the game starts.

Also
On April 30 2009 20:50 Rhaegar99 wrote:
+ Show Spoiler +
Each colour will be assigned a number from 1 to n. Every prisioner will write whatever colour onto the paper except for the two who are chosen last. The second last person will take 5X seconds to write down on his piece of paper, where X is the number that was assigned to the colour on the last prisioner's hat. The last prisioner will count how long the second person takes, and will then know which colour hat he is wearing.

LOL
stenole
Profile Blog Joined April 2004
Norway868 Posts
April 30 2009 12:13 GMT
#20
On April 30 2009 20:23 raiame wrote:
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.


I bet the warden didn't see that one coming. Sounds like you've been in this situation before prisoner raiame.
Nytefish
Profile Blog Joined December 2007
United Kingdom4282 Posts
April 30 2009 13:01 GMT
#21
On April 30 2009 20:35 freelander wrote:
Show nested quote +
On April 30 2009 20:23 raiame wrote:
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.


but they can't communicate at all


I think when he said "say" he meant "write".
No I'm never serious.
raiame
Profile Joined December 2007
United States421 Posts
April 30 2009 14:46 GMT
#22
On April 30 2009 21:13 stenole wrote:
Show nested quote +
On April 30 2009 20:23 raiame wrote:
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.


I bet the warden didn't see that one coming. Sounds like you've been in this situation before prisoner raiame.

I have! Except we didn't have the wonderful hats last time.
Also, the last time I was the one who correctly guessed my own. I hope to do so again.
Bebop Berserker
Profile Joined April 2009
United States246 Posts
Last Edited: 2009-04-30 17:13:51
April 30 2009 17:11 GMT
#23
+ Show Spoiler +

On April 30 2009 20:23 raiame wrote:
Why am I still up...
+ Show Spoiler +
n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.



+ Show Spoiler +

Maybe I don't understand but that's isn't right at all. Example: there are three hats red blue and white(1 2 and 3 respectively.) There are three prisoners(1 2 and 3.) 1 is wearing white 2 is wearing white and 3 is wearing blue. Now your theory states I should take 3 -5 % n. so, prisoner 1 is blue prisoner 2 is red and prisoner 3 is white. Therefore they all die.




+ Show Spoiler +

Rhaegar99 is who i agree with. Everyone chooses a different color beforehand and everyone memorizes everyone's color. Then they pick an interval(10 or 15 seconds is more realistic) Then we warden says go they wait 10 seconds everyone who doesn't see their color writes down their color. Everyone who does see their color waits 10x seconds were x is the the number of hats their color. Now out of the people who are left they have to watch to make sure everyone remaining doesn't write down at the same time(i.e. the warden doesn't put one of every color hat on the persons head who doesn't have that color.(there are more examples.) If he sees everyone writing down at the same time he can see tell what color hat he has on and he writes that down.(for example there are 4 prisoners and two have blue and two have red. the blue and red would wait thirty seconds and then write down both their colors. since the other two wrote down their colrs at ten seconds they know their are no other colors. they then know there are 2 red and 2 blue. so they write down the color they see only one of.)
Whatever happens, happens.
Nytefish
Profile Blog Joined December 2007
United Kingdom4282 Posts
Last Edited: 2009-04-30 17:45:47
April 30 2009 17:42 GMT
#24
Doesn't waiting to see when people start writing count as communicating though?

And to above poster, + Show Spoiler +
It's n - 5 (mod 3) so I think person 2 writes the correct colour.
No I'm never serious.
Normal
Please log in or register to reply.
Live Events Refresh
OSC
16:00
Mid Season Playoffs
TriGGeR vs MindelVKLIVE!
Lemon vs TBD
YoungYakov vs PAPI
ArT vs sebesdes
SteadfastSC258
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
SteadfastSC 258
PiGStarcraft156
BRAT_OK 95
ProTech81
Livibee 74
MindelVK 21
StarCraft: Brood War
Britney 27222
hero 223
Hm[arnc] 12
Dota 2
LuMiX1
Counter-Strike
pashabiceps651
Foxcn628
Stewie2K234
PGG 59
Heroes of the Storm
Liquid`Hasu481
Other Games
Grubby2421
FrodaN2101
fl0m1538
B2W.Neo551
ceh9486
RotterdaM213
ToD186
mouzStarbuck170
KnowMe159
Sick138
C9.Mang096
QueenE68
Dewaltoss51
UpATreeSC47
Trikslyr44
ZombieGrub29
JuggernautJason11
OptimusSC23
Organizations
Other Games
BasetradeTV17
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 19 non-featured ]
StarCraft 2
• Reevou 4
• intothetv
• sooper7s
• Migwel
• AfreecaTV YouTube
• LaughNgamezSOOP
• IndyKCrew
• Kozan
StarCraft: Brood War
• FirePhoenix17
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• C_a_k_e 3803
• WagamamaTV674
• lizZardDota253
League of Legends
• Nemesis5555
• TFBlade744
Other Games
• imaqtpie1722
• Shiphtur231
Upcoming Events
Tenacious Turtle Tussle
3h 23m
The PondCast
14h 23m
Map Test Tournament
15h 23m
OSC
20h 23m
Map Test Tournament
1d 15h
OSC
1d 17h
Korean StarCraft League
2 days
CranKy Ducklings
2 days
Map Test Tournament
2 days
OSC
2 days
[ Show More ]
[BSL 2025] Weekly
2 days
Safe House 2
2 days
Sparkling Tuna Cup
3 days
Map Test Tournament
3 days
OSC
3 days
IPSL
3 days
Bonyth vs Art_Of_Turtle
Razz vs rasowy
Liquipedia Results

Completed

Acropolis #4 - TS2
Maestros of the Game
HCC Europe

Ongoing

BSL 21 Points
ASL Season 20
CSL 2025 AUTUMN (S18)
C-Race Season 1
IPSL Winter 2025-26
WardiTV TLMC #15
EC S1
ESL Pro League S22
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

Upcoming

SC4ALL: Brood War
BSL Season 21
BSL 21 Team A
RSL Offline Finals
RSL Revival: Season 3
Stellar Fest
SC4ALL: StarCraft II
eXTREMESLAND 2025
ESL Impact League Season 8
SL Budapest Major 2025
BLAST Rivals Fall 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
Thunderpick World Champ.
CS Asia Championships 2025
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.