• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 00:43
CEST 06:43
KST 13:43
  • 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 - Finalists & Open Tournaments0[ASL20] Ro16 Preview Pt2: Turbulence5Classic Games #3: Rogue vs Serral at BlizzCon9[ASL20] Ro16 Preview Pt1: Ascent10Maestros of the Game: Week 1/Play-in Preview12
Community News
Weekly Cups (Sept 8-14): herO & MaxPax split cups3WardiTV TL Team Map Contest #5 Tournaments1SC4ALL $6,000 Open LAN in Philadelphia7Weekly Cups (Sept 1-7): MaxPax rebounds & Clem saga continues29LiuLi Cup - September 2025 Tournaments3
StarCraft 2
General
Team Liquid Map Contest #21 - Presented by Monster Energy #1: Maru - Greatest Players of All Time Weekly Cups (Sept 8-14): herO & MaxPax split cups SpeCial on The Tasteless Podcast Team TLMC #5 - Finalists & Open Tournaments
Tourneys
WardiTV TL Team Map Contest #5 Tournaments Maestros of The Game—$20k event w/ live finals in Paris RSL: Revival, a new crowdfunded tournament series Sparkling Tuna Cup - Weekly Open Tournament SC4ALL $6,000 Open LAN in Philadelphia
Strategy
Custom Maps
External Content
Mutation # 491 Night Drive Mutation # 490 Masters of Midnight Mutation # 489 Bannable Offense Mutation # 488 What Goes Around
Brood War
General
Diplomacy, Cosmonarchy Edition [ASL20] Ro16 Preview Pt2: Turbulence BW General Discussion BGH Auto Balance -> http://bghmmr.eu/ ASL20 General Discussion
Tourneys
[ASL20] Ro16 Group D [ASL20] Ro16 Group C [IPSL] ISPL Season 1 Winter Qualis and Info! Is there English video for group selection for ASL
Strategy
Simple Questions, Simple Answers Muta micro map competition Fighting Spirit mining rates [G] Mineral Boosting
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile General RTS Discussion Thread Nintendo Switch Thread Borderlands 3
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
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Things Aren’t Peaceful in Palestine Canadian Politics Mega-thread Russo-Ukrainian War Thread The Big Programming Thread
Fan Clubs
The Happy Fan Club!
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread
Sports
2024 - 2026 Football Thread Formula 1 Discussion MLB/Baseball 2023
World Cup 2022
Tech Support
Linksys AE2500 USB WIFI keeps disconnecting Computer Build, Upgrade & Buying Resource Thread High temperatures on bridge(s)
TL Community
BarCraft in Tokyo Japan for ASL Season5 Final The Automated Ban List
Blogs
The Personality of a Spender…
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
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1356 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 States24701 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 States24701 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
OSC
00:00
Mid Season Playoffs #2
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
ROOTCatZ 61
StarCraft: Brood War
soO 95
Noble 57
JulyZerg 34
ajuk12(nOOB) 23
sSak 19
Bale 11
Icarus 8
Dota 2
monkeys_forever414
NeuroSwarm128
League of Legends
JimRising 637
Counter-Strike
Stewie2K682
semphis_31
Other Games
summit1g5856
shahzam834
C9.Mang0355
Maynarde114
SortOf99
Trikslyr40
Organizations
Other Games
gamesdonequick874
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 14 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• Diggity5
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Rush1398
• Lourlo919
• Stunt288
Upcoming Events
Sparkling Tuna Cup
5h 17m
Afreeca Starleague
5h 17m
Light vs Speed
Larva vs Soma
2v2
6h 17m
OSC
8h 17m
PiGosaur Monday
19h 17m
LiuLi Cup
1d 6h
RSL Revival
2 days
Maru vs Reynor
Cure vs TriGGeR
The PondCast
2 days
RSL Revival
3 days
Zoun vs Classic
Korean StarCraft League
3 days
[ Show More ]
BSL Open LAN 2025 - War…
4 days
RSL Revival
4 days
BSL Open LAN 2025 - War…
5 days
RSL Revival
5 days
Online Event
5 days
Wardi Open
6 days
Liquipedia Results

Completed

Proleague 2025-09-10
Chzzk MurlocKing SC1 vs SC2 Cup #2
HCC Europe

Ongoing

BSL 20 Team Wars
KCM Race Survival 2025 Season 3
BSL 21 Points
ASL Season 20
CSL 2025 AUTUMN (S18)
LASL Season 20
RSL Revival: Season 2
Maestros of the Game
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

Upcoming

2025 Chongqing Offline CUP
BSL World Championship of Poland 2025
IPSL Winter 2025-26
BSL Season 21
SC4ALL: Brood War
BSL 21 Team A
Stellar Fest
SC4ALL: StarCraft II
EC S1
ESL Impact League Season 8
SL Budapest Major 2025
BLAST Rivals Fall 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
MESA Nomadic Masters Fall
Thunderpick World Champ.
CS Asia Championships 2025
ESL Pro League S22
StarSeries Fall 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.