Hat Problems - Numberphile

Featuring Joe Buhler. See part 2 of this interview: • Stacks of Hats (extra)...
More links & stuff in full description below ↓↓↓
An Introduction to Infinite Hat Problems (paper): bit.ly/31OeWZK
See also Spheres and Code Words with James Grime: • Spheres and Code Words...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoun...
And support from Math For America - www.mathforame...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/...
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
Thanks to our Patrons, including: Ben Delo - Arjun Chakroborty - Jeff Straathof - Andy B - Yana Chernobilsky - Ken Baron - Jesús Saucedo Pérez - John Zelinka - Ubiquity Ventures - swiatek7 . - Garrett Smith - Ron Hochsprung - Jeremy Buchanan - Nat Tyce - Matthew Schuster - Mitch Harding - RAD Donato - Andrei M Burke - Ben White - Adam Savage - Christian Martel - Steve Crutchfield - James Bissonette - Jubal John - Susan Silver - Mirik Gogri - That Asymptote - Alex Khein - Kermit Norlund - Bodhisattva Debnath - Igor Sokolov - Jerome Froelich - Bernd Sing - Charles Southerland - Alfred Wallace - Valentin - Arnas - Tracy Parry - Ian George Walker

[@mebamme]

Those hats actually look great on him.

[@LeventK]

You can sense them and guess it's color

[@keetrandling4530]

∅i

[@keetrandling4530]

Jjjjjjjj

[@appleslover]

Daddy

[@NoriMori1992]

Agreed.

[@kaibroeking9968]

"Combining these 50/50s and coming up with certainty certainly sounds impossible." Nicely put. :-)

[@kaibroeking9968]

@Ron Maimon nevertheless, there is a certain linguistic elegance in the statement quoted above.

[@Triantalex]

false.

[@laurihei]

Standup Maths & 3b1b AND Numberphile all posting videos about error correction and higher dimensional cubes? *Cue the X-Files theme* Parabollati confirmed!

[@shambosaha9727]

Also related to prison. They are trying to tell us something.

[@ldx8492]

G 2 0 R 1 4 1 N X S Q U 4 R 1 S

[@LeoStaley]

Matt had a vee similar puzzle to the hat problem some time in the last few weeks too.

[@jbcoolestgamer9786]

Coincidence I THINK NOT

[@Danilego]

4:14 There's another crossover because Alice and Bob are always in 3B1B's videos and now they're here!

[@ayylmao3480]

I love that this is such a similar principle to the one in the 3b1b video from yesterday

[@thecuriousgorilla6005]

And Matt and James' anti-psychic video :)

[@sudheerthunga2155]

Ikr

[@msclrhd]

Representing the states on a cube also describes the puzzle where you need to get 3 animals (e.g. a goat, wolf, and rabbit) to the other side of a river with conditions on which animals can stay on a given side of the river (e.g. the wolf will eat the rabbit) -- you can represent each animal as one of the coordinates, and the solution becomes walking the vertices of the resulting square. IIRC, it is also related to the tower of hanoi, grey code, and serpinski triangle videos 3b1b did a while back.

[@sudheerthunga2155]

Coincidence you think? Maybe there are more people joining in!

[@Quwertyn007]

Spoilerssss I'm still thinking of a solution to that one

[@Archimedes115]

This is actually similar to a card trick Matt Parker and James Grime did some weeks ago

[@MrCheeze]

And the Matt Parker/3B1B crossover from yesterday!

[@MillerIndustriesInc]

@@MrCheeze not really

[@nitroh7745]

Just about to comment this

[@tristanridley1601]

@@MrCheeze It's from the same field of maths as those videos yesterday, but it seems to be the EXACT same maths as the card trick videos.

[@Triantalex]

??

[@coosoorlog]

charles looks like he was explained the strategy multiple times and he's still confused

[@akosbakonyi5749]

and Dave is angry that he always has to pass...

[@x_gosie]

Damn🤣😂👍

[@mobius32]

I know these videos are edited but Joe Buhler's explanations are so clear it's like I'm watching someone make art in real time. Great video!

[@kalpanarms9597]

Hats off to that professor!

[@PeaceAndProgress1242]

Here..take my like

[@omninuel]

Clever word play, my friend. I see what you did there. I bestow my like unto you. *Take it*

[@Kevy_G]

bud dum tis

[@LeventK]

@@omninuel LOL!

[@SocksWithSandals]

🥁

[@ianoliver3879]

Thank you. So nice to see a YooToob thing that is so clean and tidy. Straight to the point, no idiot in a back-to-front hat screaming. "What's up?" at me, no two minutes worth of gabble before that "Let's get to it." Just clean tidy information and enough gentle humour to make it friendly. Thank you very much.

[@ilkero1067]

Prof. Joe Buhler, The way you are teaching is just perfect. Wish we can raise more educators like you.

[@davidgillies620]

The bit strings at the vertices of the cube (or hypercube) are Gray codes, which have the property that only one bit changes between adjacent code words. Since a Gray code of a given length can be ordered, this shows that a Gray code can be used to induce a Hamiltonian path an a hypercube, where in traversing the path, every vertex of the cube is visited exactly once.

[@sebastiannrregaard5849]

Love this guy

[@numberphile]

Joe’s a top person.

[@andrerenault]

Yeah, I wouldn't mind more of him in the future.

[@Nilguiri]

A fair-dinkum bonza bloke.

[@n0tthemessiah]

@@numberphile A top HAT person

[@Danilego]

Am I the only one who thinks he looks like Chris Hadfield?

[@punkkap]

0:04 Oh why, why doesn't the cube fall to a square, and the square to a line, and a line to a dot?

[@ivarkrabol]

12:11 This explanation reminds me of how gerrymandering works.

[@liborkundrat185]

Because it is gerrymandering, just more abstract. I mean, look at the solution with three players. These are all the options for red (R) and blue (B) hats: In BBR, BRB, BRR, RBB, RBR and RRB you have 1 correct, 2 neutral and 0 wrong guesses for each combination. It's like a 67-33 result in the election. In BBB and RRR you have 0 correct, 0 neutral and 3 wrong guesses for each combination. It's like a 0-100 result in the election. If you sum up all the combinations, you'll get 6 correct guesses, 12 neutral guesses and 6 wrong guesses, yet you can win 75% of the games. ... 67-33 and 0-100 results might sound extreme, but now apply them to only 20% of the voters and assume the other 80% of the voters vote evenly for the two parties regardless of gerrymandering. You'll suddenly get six 53-47 districts and two 40-60 districts. These numbers are much more real. (edited due to typos)

[@rosiefay7283]

And as chance would have it, today Tom Scott uploads a video giving a little of the history of how too few people once had too much political power.

[@notEphim]

I left a comment about it on Matt Parker's video, but this problem is my favourite for about 6 years already! Thank you

[@Axolotine]

This is the first time I've ever gotten the right answer on these types of problems!! Maybe this show is making me smarter...

[@aspermwhalespontaneouslyca8938]

We don't want to step on a landmine... so we predict we aren't on a landmine! I just love how mathematicians think.

[@oz_jones]

"Sir, we're on a minefield!" "Let's assume that we're not."

[@timg5011]

"Consider a spherical cow..."

[@thrilhousesf]

I heard this problem in 2008 and it took me until 2019 to solve the 2^n-1 case. One of my favorite problems ever.

[@jamesbentonticer4706]

Hats off to making this video.

[@ezanchi5422]

Actually, hats on!

[@jonlottgaming]

Oh Hey, Stand up Maths and 3 Blue 1 Brown did a collaboration on similar maths to this just recently.

[@WannesMalfait]

I think you're talking about the one with James Grime and Matt Parker (with the playing cards)

[@Ashbakhaaz]

@@WannesMalfait Nope, they're not; they're refering to yesterday's video about the chessboard puzzle

[@WannesMalfait]

@@Ashbakhaaz I see, because it has to do with coding theory. I just thought they were talking about the other one because it was basically the first problem with the two hats.

[@baghead4548]

Shame about that audio quality!

[@Jaynat_SF]

@@WannesMalfait The trick Matt and James used with the cards video is the same trick used to win the 2 player, 1 must be correct game.

[@ubertoaster99]

I think you can intuitively understand the three player method by considering that everyone getting the same colour hat is unlikely (1/4). Therefore if you make a working strategy for every 'two and one' case you've got a 3/4 winning strategy.

[@Moohasha1]

"If it was the population of the planet the chance would be, I don't know, 4 billion let's say." This video was recorded in 1974.

[@txjoe]

The population of the planet has yet to exceed 2^32 (about 8 billion) so hasn't met the next breakpoint, so the chance would be about 1/2^31 (about 4 billion).

[@tristanridley1601]

4 billion and change is a commonly known power of 2, since that's the limit of a 4 byte decimal number. The next time the elegant solution will increase the probability is when the 8,589,934,592nd player joins. Since probabilities only increase slightly between these powers of 2, the probability of winning this game with 7 billion perfect players is somewhere in the 1 over 4 billions.

[@herrvorragend325]

@@tristanridley1601 7 billion perfect players...hah

[@gabrielwu5787]

With that many people and such a complicated strategy there's gotta be someone who messes everything up :P

[@tristanridley1601]

Definitely necessary to say we each have a perfect player robot stand in for us.

[@businessguide6219]

Your channel definitely deserves my subs!

[@Sakkura1]

So we can have a nice game when the world population hits 8.589.934.591 (2^33 - 1). Start preparing, everyone!

[@casfighter34]

prepare for the game or procreate as to hit that world population number in my lifetime?

[@Sakkura1]

@@casfighter34 We're forecast to hit that figure in about 10 years.

[@travissorenson9554]

@@Sakkura1 start figuring out the strategy to maximize our success....

[@ceruchi2084]

This is the kind of video that made me fall in love with Numberphile in the first place.

[@francescocostanzo8225]

I love this channel so much! Never stop being amazing!

[@AgentM124]

I have seen this similar problem on Matt Parker's channel. Really cool maths trick this is. And goes to show how weird and unintuitive such problems can feel, but when dissected make perfect sense.

[@roylim1169]

who is the guy who thought about having mathematicians as KZbinrs host and making them explain hard math problems and crazy phenomenons This is GENIUS!

[@AspieGamer13]

Only a couple minutes in and this seems like something I’ve seen both Matt Parker and James Grime do videos on but with playing cards and a different scenario and an opposite goal. This video obviously goes further than two persons.

[@Leander_]

That was really freaking cool. It's cool to see that these problems have such deep geometric interpretations.

[@johnn1199]

As well as being an interesting problem, the man really does rock that hat!

[@QuestionEverythingButWHY]

"An unsophisticated forecaster uses statistics as a drunken man uses lamp-posts - for support rather than for illumination. " --After Andrew Lang

[@alephnull4044]

Ha that's great!

[@theo7371]

This is also a similar kind of idea with many other combinatorics and probability problems. When you only care about maximizing the chance of winning in a game of chance, the optimal strategy is to make it so that when you lose, you lose big but when you win you barely win.

[@SonicGamesPlayer]

This was so nice to watch, would love to see more videos with Mr. Buhler :)

[@DeclanMBrennan]

I vaguely remember doing Hamming Codes in college. This was far more entertaining and easy to both understand and remember.

[@gregrishel4283]

WHAT AN EDUCATIONAL VIDEO , WE MUST KEEP OUR PRIORITIES

[@chinareds54]

One person guesses the same, one person guesses opposite. Matt Parker and James Grime did that trick with cards.

[@meditati-1524]

I love this videos so much!

[@gubblfisch350]

Another strategy for 3 hats with 3/4 success rate is to let A guess anything if the hats of B and C are different and stay silent otherwise. If he stays silent, B knows he has the same hat color as C and can always say the right combination

[@praharmitra]

they all have to guess at the same time.

[@Maniclout]

2^6 likes and 2^0 dislikes. This is amazing.

[@renerpho]

Now show that exactly one of these tends to infinity :)

[@rogerkearns8094]

@@renerpho Neither does.

[@adarshmohapatra5058]

@@rogerkearns8094 The no. of likes tends to infinity :)

[@gavinmann4152]

who was the one dislike ;(

[@NoriMori1992]

Have we seen Joe Buhler before? I like him! He's one of those people who looks painfully serious at first glance, but can actually be as goofy as all the others! ❤️

[@JaniceinOR]

I liked him a lot when he was my instructor & advisor at Reed College (1987-1990). I think he was also one of many math professors who juggled.

[@jonathanchanms]

It is just like the cards video James Grime and Matt Parker did.

[@honigson8776]

cant imagine the expenses for these fency hats. :O they do everything to bring us the quality content we need

[@PowerfullPillow]

At this point I'm math channels are all controlled by a secret committee that decides the videos topic for each month

[@omikronweapon]

more likely there's some paper or publication come out and several mathematicians found one bit in it particularly interesting to share

[@KalOrtPor]

43 comments when the video hasn't even been posted long enough to view it in its entirety, goodness

[@ambidexter2017]

I dunno why, but for some reason this strategy was obvious to me. Just as I saw the 3 hat problem, my first thought was "you have to call the opposite color if you see two hats of the same color and pass otherwise, this way you'll only fail if all three hats are the same color which is like 2 out of 8 chance". Somehow it's the first thing that comes to mind.

[@ravikantsammi2783]

For the infinite hats part, I think I found a method that gives *5/8* (62.5%)chance of winning!! I may very well be wrong (and most probably am) but here is my method: Both look for any random row of two Blue hats (it does not have to be strictly two, if there is a row of, say, 5 Blue hats then you pick a pair of any two). Then, they will decide beforehand, and one would choose the top one from his pair and the second would then choose the bottom one from his pair. Now there are 4 cases:- Both of the pairs overlap (25%) •• •• One of them coincides (25%) • •• • One of them coincides, 2nd way (25%) ..mirror of the second case.. DO NOT coincide..(25%) Now the first 2 case will always give the correct match, and the other two each,themselves , have a 25% chance of succes so... (1/4)*1 + (1/4)*1 + (1/4)*(1/4) + (1/4)*(1/4) WHICH gives 62.5% succes rate (I know this is most probably wrong so pls tell where)

[@blackkhawkk]

So great to see Walter White in a red hat

[@yoloc4th]

ah yes the worlds first prison escape themed hat simulator

[@GenericInternetter]

You don't know blue and red hat problems until you've played Team Fortress 2.

[@nebelung1]

Excellent video! Joe is great at explaining this!

[@jimbysmamples9119]

Couldn’t stop thinking of the song “More Than One Hat” by Curtis Plum.

[@hitchano]

I believe I misunderstood the rules but I took it as only one player has to be correct. My first guess would be with Alice Bob and Charles (in that order) have one chose to be a disagreeable party. If, in this situation say to have Charles elect to be an agreeable party. In this case if it is BBR: Lose; BRB: Win; RBB: Win; BBB: Win; BRR: Win; RBR: Win RR,B: Win RRR: Lose. This still has a 3/4 chance of winning the game. Also if all three were a disagreeable party it would be the same BBB: Lose BBR: Win; BRB: Win; RBB: Win; RRR: Lose; RRB: Win; RBR: Win BRR: Win. Same as the end result but still interesting. When looking at 4 players, the optimal path would be for each player, if there is 2 or 3 of the same to choose the opposite. There are 16 possible outcomes but 14 of them would be a 'win' for at least 1 player. The bread down would be (in binary because it is easier) 0000=L 0001=W 0010=W 0011=W 0100=W 0101=W 0110=W 0111=W 1000=W 1001=W 1010=W 1011=W 1100=W 1101=W 1110=W 1111=L. As you can see, only in the end cases do you lose (87.5% win rate).

[@martincattell6820]

Vital to these scenarios is that the people can communicate before-hand.

[@brantnuttall]

Hats off to you Sir!

[@karenliu529]

World in the eyes of physicists: all spherical cows. World in the eyes of mathematicians: all colorful cubes lol

[@anjuranjan6701]

You know you are lucky if Numberphile and 3blue1brown post new videos in a span of two days😉 #mathslove

[@HardRockRock12345]

The 3 hat game, since you are allowed to come up with a strategy beforehand. The ones who see different colors always pass and will go first. Then the last one guesses the opposite color. If no one is passing for 10 seconds (or whatever), they can guess the same color.

[@deyesed]

With the 3 hat problem, Bob should immediately know he has a blue hat once Alice says red and Charlie has a blue hat. You always win.

[@ceruchi2084]

They all guess simultaneously.

[@raindropdreams8]

Love this stuff! Seems almost exactly like the game "Hanabi"

[@ruchirkadam8510]

A guy in my math class asked this question once :D

[@martysuwito]

Something we never ask, but something we need in the current quarantine.

[@catalyst217]

Nice work!

[@Cr42yguy]

Parker and Grime recently did something about guessing each other's cards where one of them is always right and one of them is always wrong.

[@PaulSmith-gi5bf]

Would be interesting to see the implementation of the problem too. I imagine it's got to do with networking and packet errors

[@BlueRaja]

100 people are wearing red or blue hats and placed in a line. Each person can see the hat-colors of the people in front of them in line, but not their own or of the people behind them. Starting from the back, each person guesses their own hat color in turn, loud enough for everyone else to hear. Find a strategy so that at MOST one person guesses incorrectly. With the axiom of choice, the problem can be extended to "there are infinite people, find a strategy so that only finitely-many guess incorrectly".

[@andrewkelley7062]

Hmm self generating sequences. With random overlaps. Maybe. I'm willing to bet there would still be a duality problem somewhere in all of that to. Still might go exponential with enough error as well. Then you would have error creep as well. In some cases. Might be able to correct with a monotone signal running through it. Not sure, or I could have missed something.

[@Rubrickety]

Seems to be the week for puzzles involving coloring cubes and binary! (See the recent Matt Parker / Grant Sanderson collab.)

[@brutalkangaroo30]

I was proud of my self for figuring this out lol and then so many hats

[@MyAce8]

as a comp sci major familiar with error detection/correction algorithms in interesting to see another way of view the underlying math.

[@yoyosheat]

About the 2nd game, if all the players could know if others answered already the probability to win would be 100%. You just need to change the strategy by a bit. You say : If no one "pass" that means we all have the same color.

[@cheaterman49]

That reminds me of what Matt Parker did with the cards? Is that the same thing?

[@drpkmath12345]

This one looks so real! Good job!

[@Ricocossa1]

This ties in well with 3b1b's most recent video and his collab with standup maths!

[@jenniferh3039]

I suddenly have a desire to rewatch "Cube" (1997). That 4D cube and "...n=2-1.." is tickling some brain cells.

[@Bleepbleepblorbus]

On one episode of Futurama the characters could switch minds but not back the creators of the show came up with a equation to see how many swaps it'd take to for each character to get back in there original bodies it's called:The Futurama Therom.

[@alexpotts6520]

I'm a couple of days late on this but I've just heard of the passing of Ron Graham, of Graham's Number fame. RIP.

[@Danilego]

This guy looks like Chris Hadfield, if Chris Hadfield stayed on earth and played with hats

[@davecrupel2817]

Glad to see Paul Newman took up teaching.

[@nicnakpattywhack5784]

similar to that card puzzle with matt parker and that other guy

[@johnnicholson8811]

At 1:45 did the ref practice flipping the coin? I ask because the physics says you can.

[@conchaelizabeth]

Hey uhm just letting you know your video still has 301 views and I am still shooketh by that

[@Myndale]

I'd love to see a Numberphile video on 100 Prisoners and a Light Bulb.

[@republicofmk5388]

The problems with hats is that it covers my hair

[@markpurslow7446]

would there be an advantage to training a neural network to try and do better?

[@MushookieMan]

What's the connection with error correcting codes, explicitly?

[@SimonBuchanNz]

An error for ECC is a transition along one if those hypercube edges, when a bit gets flipped during transmission. ECCs are designed so the valid positions in the hypercube are all at least 2N+1 edges apart, so they can handle up to N bits getting flipped simply by going to the nearest valid vertex. Does that help?

[@MushookieMan]

@@SimonBuchanNz There doesn't seem to be a close connection, except that they take place in the space of bit-strings.

[@SimonBuchanNz]

@@MushookieMan it's in the logic of possible transitions on bitstrings. For example, when you're designing ECCs traditionally, it's done by coloring the vertices, like the hats here. The last videos from stand-up maths and three blue one brown both cover another very similar situation that's essentially designing an anti-error correcting code, where you can get from any encoded value to any other with a single bit flip, that might make things clearer.

[@jamesl8640]

Is the power of two -1 happening because there's only two colours of hats or is there another reason? If so does that mean that if it were 3 colours of hats then it'd be the same, but with 3^x -1 where the probability of winning are nice.

[@diegofernandez8981]

For the three hat problem, i think they might be able to get 100 if you are supposed to pass, but are the last one to guess so you guess the same color

[@fakexzvo9479]

9:32 How can you even draw a cube like that....

[@fakexzvo9479]

I draw it with two overlapping squares😄

[@marcoskunrath5914]

@@fakexzvo9479 you can draw with a hexagon and a Y inside.

[@NoriMori1992]

What do you mean?

[@marcoskunrath5914]

​@@NoriMori1992​ / \ / \ | | -> | \ / | \ / \ | / ah... sorry, i think you were talking to FakeXZVO

[@NoriMori1992]

@@marcoskunrath5914 Yes, I was. And I still don't know what they mean XD

[@kn0bhe4d]

On a different note, if you want a perfectly fitting hat, measure your head, and divide the number by pi. That is the measurement of the hat you need for it to perfectly fit on your head.

[@PabloSanchez-qu6ib]

Yeah, but too much pi and your trousers won't fit.

[@mikaeleriksson1720]

This video reminded me of gerrymandering. Especially with the hats being red and blue.

[@robo3007]

Couldn't the first person say pass in either high pitch tone or a low pitch tone to denote whether everyone else is wearing an odd or even number of red hats, and and then the rest of them could check the number of red hats they see to check if their hat has to be red or blue for that number to match?

[@AsukaYaoi]

It was actually really cool

[@amoonlenka2872]

How many here, I forget anything and everything said in this video... I need to watch this for 3moretimes I think

[@d0pomein]

If you're allowed one wrong everyone else can be correct. The one wrong tells everyone else if there's an even or odd number of a pre decided color of hat then everyone else just counts and if it's not what the wrong said then you know your hat is that color. Bonus the first guy can also be correct 50/50

[@mujtabaalam5907]

6:35 I came up with this strategy: if you see two different colors, pass. If you see two of the same color, guess that your hat is the opposite of the ones that you see. This seems like it would work 75% of the time (you lose when all here hats are the same color). Am I missing something? Edit: nom lol

[@grzegorzcichosz8240]

those drawn hats are damn lit

[@SaveSoilSaveSoil]

How do we know whether a certain strategy is "the best"?

[@frozenmoon998]

Nobody: Numberphile: Hat Problems

[@TheMebKohu]

I got the three hat strategy before it was said!