The Hat Problem - SLU Mathematics and Computer Science

1 The HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionThe Hat ProblemBrody Dylan JohnsonSaint Louis UniversityBrody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusion1 Introduction2 Three Prisoners3 More than Three Prisoners4 Help from Linear Algebra5 Optimal Strategies via Hamming Codes6 ConclusionBrody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionThe Hat Problem1A group of prisoners is allowed to play a game fortheir freedom.

2 The prisoners are donned with either ablack hat or a white hat and, while they cannot seetheir own hat, they can see the remaining hats . Thetwo colors are equally likely. The prisoners play as ateam and win when at least one prisoner guesses thecolor of his or her own hat without any incorrectguesses being made. The prisoners may strategizebefore the game, but cannot communicate in anyfashion once the game Ebert, University of California, Santa Barbara (1998).Brody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionImportant Aspects of the GameThings to keep in mind.

3 Hat colors are independent (White) =P(Black) =12 IdentifyBlack= 0 andWhite= acceptable strategy must always result in at least oneprisoner making a prisonerswinwhen at least one correct guess is madeand no incorrect guesses are prisoner sees all of the hats ,excepthis or her communication is allowed between prisoners, includingwhether or not others have elected Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionImportant Aspects of the GameThings to keep in mind:Hat colors are independent (White) =P(Black) =12 IdentifyBlack= 0 andWhite= acceptable strategy must always result in at least oneprisoner making a prisonerswinwhen at least one correct guess is madeand no incorrect guesses are prisoner sees all of the hats ,excepthis or her communication is allowed between prisoners, includingwhether or not others have elected Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionImportant Aspects of the GameThings to keep in mind.

4 Hat colors are independent (White) =P(Black) =12 IdentifyBlack= 0 andWhite= acceptable strategy must always result in at least oneprisoner making a prisonerswinwhen at least one correct guess is madeand no incorrect guesses are prisoner sees all of the hats ,excepthis or her communication is allowed between prisoners, includingwhether or not others have elected Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionImportant Aspects of the GameThings to keep in mind:Hat colors are independent (White) =P(Black) =12 IdentifyBlack= 0 andWhite= acceptable strategy must always result in at least oneprisoner making a prisonerswinwhen at least one correct guess is madeand no incorrect guesses are prisoner sees all of the hats ,excepthis or her communication is allowed between prisoners, includingwhether or not others have elected Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionImportant Aspects of the GameThings to keep in mind.

5 Hat colors are independent (White) =P(Black) =12 IdentifyBlack= 0 andWhite= acceptable strategy must always result in at least oneprisoner making a prisonerswinwhen at least one correct guess is madeand no incorrect guesses are prisoner sees all of the hats ,excepthis or her communication is allowed between prisoners, includingwhether or not others have elected Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionImportant Aspects of the GameThings to keep in mind:Hat colors are independent (White) =P(Black) =12 IdentifyBlack= 0 andWhite= acceptable strategy must always result in at least oneprisoner making a prisonerswinwhen at least one correct guess is madeand no incorrect guesses are prisoner sees all of the hats ,excepthis or her communication is allowed between prisoners, includingwhether or not others have elected Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionBasic ObservationsWhat strategy maximizes the chance of winning?

6 What effectdoes the number of prisoners have on the game?One prisoner: The prisoner is forced to guess and, thus,the probability of winning is prisoners: One can articulate a lot of strategies, but50-50 is the best one can both prisoners guess randomly their chance of winning single prisoner guessing leads to a12probability it clear that this is the optimal strategy forn= 2?Brody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionBasic ObservationsWhat strategy maximizes the chance of winning?

7 What effectdoes the number of prisoners have on the game?One prisoner: The prisoner is forced to guess and, thus,the probability of winning is prisoners: One can articulate a lot of strategies, but50-50 is the best one can both prisoners guess randomly their chance of winning single prisoner guessing leads to a12probability it clear that this is the optimal strategy forn= 2?Brody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionBasic ObservationsWhat strategy maximizes the chance of winning?

8 What effectdoes the number of prisoners have on the game?One prisoner: The prisoner is forced to guess and, thus,the probability of winning is prisoners: One can articulate a lot of strategies, but50-50 is the best one can both prisoners guess randomly their chance of winning single prisoner guessing leads to a12probability it clear that this is the optimal strategy forn= 2?Brody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionBasic ObservationsWhat strategy maximizes the chance of winning?

9 What effectdoes the number of prisoners have on the game?One prisoner: The prisoner is forced to guess and, thus,the probability of winning is prisoners: One can articulate a lot of strategies, but50-50 is the best one can both prisoners guess randomly their chance of winning single prisoner guessing leads to a12probability it clear that this is the optimal strategy forn= 2?Brody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionBasic ObservationsWhat strategy maximizes the chance of winning?

10 What effectdoes the number of prisoners have on the game?One prisoner: The prisoner is forced to guess and, thus,the probability of winning is prisoners: One can articulate a lot of strategies, but50-50 is the best one can both prisoners guess randomly their chance of winning single prisoner guessing leads to a12probability it clear that this is the optimal strategy forn= 2?Brody Dylan Johnson Saint Louis UniversityThe Hat ProblemThe HatProblemBrody DylanJohnsonSaint LouisUniversityIntroductionThreePrisoner sMore thanThreePrisonersHelp fromLinearAlgebraOptimalStrategies viaHammingCodesConclusionBasic ObservationsWhat strategy maximizes the chance of winning?