• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 05:13
CEST 11:13
KST 18:13
  • 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
Maestros of the Game: Week 1/Play-in Preview12[ASL20] Ro24 Preview Pt2: Take-Off7[ASL20] Ro24 Preview Pt1: Runway132v2 & SC: Evo Complete: Weekend Double Feature4Team Liquid Map Contest #21 - Presented by Monster Energy15
Community News
LiuLi Cup - September 2025 Tournaments2Weekly Cups (August 25-31): Clem's Last Straw?39Weekly Cups (Aug 18-24): herO dethrones MaxPax6Maestros of The Game—$20k event w/ live finals in Paris54Weekly Cups (Aug 11-17): MaxPax triples again!15
StarCraft 2
General
Team Liquid Map Contest #21 - Presented by Monster Energy #1: Maru - Greatest Players of All Time Production Quality - Maestros of the Game Vs RSL 2 Geoff 'iNcontroL' Robinson has passed away Heaven's Balance Suggestions (roast me)
Tourneys
Maestros of The Game—$20k event w/ live finals in Paris RSL: Revival, a new crowdfunded tournament series Chzzk MurlocKing SC1 vs SC2 Cup Sea Duckling Open (Global, Bronze-Diamond) LiuLi Cup - September 2025 Tournaments
Strategy
Custom Maps
External Content
Mutation # 489 Bannable Offense Mutation # 488 What Goes Around Mutation # 487 Think Fast Mutation # 486 Watch the Skies
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ The Korean Terminology Thread Pros React To: herO's Baffling Game ASL20 General Discussion BW General Discussion
Tourneys
[Megathread] Daily Proleagues [IPSL] ISPL Season 1 Winter Qualis and Info! Is there English video for group selection for ASL Small VOD Thread 2.0
Strategy
Simple Questions, Simple Answers Muta micro map competition Fighting Spirit mining rates [G] Mineral Boosting
Other Games
General Games
General RTS Discussion Thread Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile Warcraft III: The Frozen Throne
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
The Games Industry And ATVI Things Aren’t Peaceful in Palestine US Politics Mega-thread Russo-Ukrainian War Thread Canadian Politics Mega-thread
Fan Clubs
The Happy Fan Club!
Media & Entertainment
[Manga] One Piece Anime Discussion Thread Movie Discussion! [\m/] Heavy Metal Thread
Sports
MLB/Baseball 2023 2024 - 2026 Football Thread Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread High temperatures on bridge(s)
TL Community
The Automated Ban List TeamLiquid Team Shirt On Sale
Blogs
Collective Intelligence: Tea…
TrAiDoS
A very expensive lesson on ma…
Garnet
hello world
radishsoup
Lemme tell you a thing o…
JoinTheRain
RTS Design in Hypercoven
a11
Evil Gacha Games and the…
ffswowsucks
INDEPENDIENTE LA CTM
XenOsky
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1039 users

really hard puzzle

Blogs > drift0ut
Post a Reply
1 2 3 Next All
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
Last Edited: 2009-05-10 01:44:18
May 10 2009 01:30 GMT
#1
This is probably the hardest puzzle that i've solved myself:

An infinite number of ppl are given either a black or a white hat. They can't see what colour hat they have on but they can see everyone elses. They cannot communicate with each other in anyway once they've been given the hats but they can devise a strategy before the game starts. Then, at a predetermined time, they all have to shout out the colour hat they think they have on [at the same time]. They win if only finitely many get it wrong.


There are no pissy tricks like "looking in a mirror" or sneaking round the "no communication" rule and we assume they can see all the the other ppl at once and perform any computations they might need to instantly.

right so if you don't know/believe the axiom of choice you'll have to come up with a solution i haven't thought of yet. You might have come across the axiom in one of it's many forms (Zorn's lemma, Well-ordering principle) at some point in a maths degree but otherwise, even if you look it up on wiki, you'll struggle to know how to use it. It (roughly) says that if you have any collection of sets, you can pick an element in each of them, equivalently it says you can "well order" any set (ie you can say x<y or y<x for any x not equal to y).

I was told this puzzle a while ago, but it's solution actually came up the other day in some proper maths i was doing in a really natural way. One thing that's pretty weird is that i don't think it's possible to come up with a strategy that works if we replace "only finitely many" with "less than n" for an arbitrarily large n

*****
Avidkeystamper
Profile Blog Joined June 2008
United States8552 Posts
May 10 2009 01:31 GMT
#2
People don't have to shout out their hat color at the same time, right?
Jaedong
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
Last Edited: 2009-05-10 01:33:19
May 10 2009 01:32 GMT
#3
yes they do [have to shout at the same time]
il0seonpurpose
Profile Blog Joined January 2007
Korea (South)5638 Posts
May 10 2009 01:54 GMT
#4
How about everybody yells one color
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
May 10 2009 01:58 GMT
#5
what if i handed out the hats black white black white ... all the way up? then which ever you shout you're wrong. In fact what if you all shout one colour and i handed out all of them the other colour?

oh and you need a plan that works all the time, not just one that gives you a good chance of winning
aznmathfreak
Profile Joined March 2009
United States148 Posts
May 10 2009 02:08 GMT
#6
I think what I'm proposing might count as a method of communication, but here's my first idea.

Arrange all the people in a line in any arbitrary order. First two people stand out in a separate line. The next person will look at the first two, and if there is a change of color in the line, he will stand right in between the two colors. If there is not, he will stand at the end of the line. In either case, the line will now be split between black and white, or is all of one color.

IE

If the line is WW, the guy will stand at the end, so the line is now WWB or WWW

If the line is WB, the guy will stand in between, so the line is now WWB or WBB.

Therefore there is always a clear division between the black hats and white hats.

Once the infinitely many people have gone into place (plausible because they can compute instantly?). Then the last person to go into the line will define the division between the two colors, and everyone else can just look at the other side of that division to find out what color their side is.
The only person that would not know what color his hat is would be the last guy.
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
Last Edited: 2009-05-10 02:20:11
May 10 2009 02:14 GMT
#7
this is what i said the first time i saw the puzzle but this comes under the (rather too vague) heading of not communicating at all.


imagine everyone's in a prison cell and all they can see is one little light for every person apart from you which is either on or off depending on the colour hat they have on.

by the well ordering principle you can assign everyone a number (or element of an indexing set if you want to go cardinals on it, the solution i know works for any cardinal)
Muirhead
Profile Blog Joined October 2007
United States556 Posts
Last Edited: 2009-05-10 02:27:08
May 10 2009 02:25 GMT
#8
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.

This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.

QED ^^
starleague.mit.edu
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
Last Edited: 2009-05-10 02:30:12
May 10 2009 02:28 GMT
#9
well done, i'd hoped it'd take longer than that


places you might have seen it: a basis of any infinite dim'l vector space
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
May 10 2009 02:33 GMT
#10
Muirhead: i don't suppose you'd know any places i could read up on the algebraic geometry approach to ramification do you? all i can find is number theory books
Muirhead
Profile Blog Joined October 2007
United States556 Posts
May 10 2009 02:41 GMT
#11
Hm... I don't know quite what level of book you want. You might check out some sections of Liu's book on Algebraic Geometry and Arithmetic Curves as a start?
starleague.mit.edu
drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
May 10 2009 02:48 GMT
#12
so it's for a postgrad reading group on galois thy that's sort of branched out a bit. That book looks pretty good. i don't really know a lot of alge geo but when ever i talk to my supervisor about what's going on in these rings i'm looking at he always starts drawing pictures and makes me feel i should get on it.
micronesia
Profile Blog Joined July 2006
United States24700 Posts
May 10 2009 03:29 GMT
#13
On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.

This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.

QED ^^

Can you explain what that means.
ModeratorThere are animal crackers for people and there are people crackers for animals.
mdainoob
Profile Joined June 2007
United States51 Posts
May 10 2009 03:38 GMT
#14
http://en.wikipedia.org/wiki/Axiom_of_choice

drift0ut
Profile Blog Joined June 2004
United Kingdom691 Posts
May 10 2009 03:50 GMT
#15
for convenience label each of the ppl 1,2,3,... Now let a(i) be a sequence of 0's and 1's and we'll say that a(i)=0 if person i's hat is white, a(i)=1 if the persons hat is black.

For example a(i) is one way of giving out the hats a(1)=1 a(2)=0 a(3)=0 would be BWW

Let b(i) be the same as a(i) for a different way of handing out hats, so b(1)=1 b(2)=1 b(3)=1 would be BBB.

then we say a(i) "=" b(i) if and only if only finitely many of the ( a(i) - b(i) ) are not equal to 0.
(the collection of the x(i) which are "=" are the equivalence classes)

Now pick a list a(i), b(i), c(i),... so that a(i) is not "=" to b(i) or c(i) or d(i) etc and b(i) is not "=" to c(i) or ...
(forgive me for the implied countableness, (countable is a technical maths term))

now how ever i hand out the hats there will be a x(i) in the list such that x(i) is "=" to the way i hand out the hats. everybody shouts out the colour of hat they should have in x(i), and only finitly many will be wrong
micronesia
Profile Blog Joined July 2006
United States24700 Posts
May 10 2009 03:53 GMT
#16
Forgive me for pointing out how inaccessible that explanation was, but I have no idea how that jargon results in people knowing what color to yell out.
ModeratorThere are animal crackers for people and there are people crackers for animals.
igotmyown
Profile Blog Joined April 2009
United States4291 Posts
Last Edited: 2009-05-10 04:28:48
May 10 2009 03:54 GMT
#17
On May 10 2009 12:29 micronesia wrote:
Show nested quote +
On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.

This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.

QED ^^

Can you explain what that means.


Think of the people with white hats as a subset of the people. If two subsets only differ by finitely many elements, then we group those two sets together (into a set of subsets of the people). This is our equivalence relation. There's some conditions you have to prove about equivalence classes, but in this case it's easy enough not to be worth mentioning.

In algebra, you can reduce a group with an equivalence class to the unique equivalence classes, for example, the integers by 0 mod p, 1 mod p, ..., p-1 mod p (or odds or evens if that's simpler) into p elements, hence the OP's solution motivated by n-dimensional vector spaces (where dividing the space by the equivalence class of lines is common).

edit: oops solution is simpler than i thought.

anyway, you have your equivalence classes of subsets. There are infinitely many, but that doesn't matter, and from each equivalence class, you choose one element, that is, one specific way of handing out hats. Since you've covered every equivalence class, any subset of the people will match to all but finitely many of one of the chosen elements.

When the hats are handed out, you can see everybody else's hat, and your own hat can only increase the number of possible wrong matches by 1, so you know equivalence class that particular hat distribution is in. Everyone now votes their according to what their representative element would have as a hat.
DeathSpank
Profile Blog Joined February 2009
United States1029 Posts
May 10 2009 04:09 GMT
#18
I'm not understanding this...if you hand out the hats to an infinite number of people... then the number wrong will be infinite... simply because the whole set is infinite. You would also never reach the time when everyone would call out what color they think there hat is...because you'd still be handing out hats..
and even if you did...even if you came up with a plan before hand that weeded out 99% of errors 1% of infinite is well infinite.... the continuum hypothesis be damned.
yes.
odave
Profile Joined December 2008
United Kingdom4 Posts
May 10 2009 04:34 GMT
#19
(Disclaimer: I'm not a mathematician)

I don't buy the equivalence relation thing. If we're allowed to apply "a = b if a(i) != b(i) for only a finite # of i" an infinite number of times (why not? everything else in this problem seems to be infinite ), then everything breaks.

Also, if we just coin-flip for each hat, 50% of the guesses are going to be wrong no matter how they were derived?
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2009-05-10 07:25:08
May 10 2009 04:37 GMT
#20
i think I know how to do it by moving into lines going right or left based on the 2 hats in front of u

but it's too hard to explain lol and i can't put it into math terms cuz i dont know how
1 2 3 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 48m
[ Submit Event ]
Live Streams
Refresh
StarCraft: Brood War
GuemChi 2597
Shuttle 2156
Larva 620
firebathero 419
JulyZerg 392
Zeus 142
Pusan 99
ToSsGirL 97
Backho 85
Mini 68
[ Show more ]
Soma 48
Aegong 45
sSak 33
NaDa 19
Shine 4
Dota 2
The International57180
Gorgc11362
Fuzer 240
XcaliburYe201
League of Legends
febbydoto10
Super Smash Bros
Mew2King69
Westballz8
Heroes of the Storm
Khaldor145
Other Games
summit1g6294
singsing936
JimRising 479
Happy273
OptimusSC27
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 13 non-featured ]
StarCraft 2
• Adnapsc2 1
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Jankos976
Other Games
• WagamamaTV201
Upcoming Events
RSL Revival
48m
Cure vs Bunny
Creator vs Zoun
Maestros of the Game
7h 48m
Maru vs Lambo
herO vs ShoWTimE
BSL Team Wars
9h 48m
Team Hawk vs Team Sziky
Sparkling Tuna Cup
1d
Monday Night Weeklies
1d 6h
The PondCast
4 days
Online Event
5 days
BSL Team Wars
5 days
Team Bonyth vs Team Dewalt
BSL Team Wars
5 days
Maestros of the Game
6 days
[ Show More ]
Cosmonarchy
6 days
Bonyth vs Dewalt
[BSL 2025] Weekly
6 days
Liquipedia Results

Completed

Proleague 2025-09-02
SEL Season 2 Championship
HCC Europe

Ongoing

Copa Latinoamericana 4
BSL 20 Team Wars
KCM Race Survival 2025 Season 3
BSL 21: BSL Points
ASL Season 20
CSL 2025 AUTUMN (S18)
LASL Season 20
RSL Revival: Season 2
Maestros of the Game
Chzzk MurlocKing SC1 vs SC2 Cup #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

Upcoming

2025 Chongqing Offline CUP
BSL Polish World Championship 2025
BSL Season 21
BSL 21 Team A
EC S1
BLAST Rivals Fall 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
Thunderpick World Champ.
MESA Nomadic Masters Fall
CS Asia Championships 2025
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
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.