(Original post by ukdragon37)
Problem 41***
A (countably) infinite class of Cambridge students who believe in the Axiom of Choice are taking their finals for the Mathematical Tripos. At the start of the exam, the examiner places either a white or a black hat on each student at random. There is only one question in the exam: "What colour is your hat?" If only a finite number of students answers incorrectly then everyone becomes a Wrangler (very good), otherwise the Wooden Spoon is given to the whole class (very bad). Everyone can see the hats of everyone else besides their own, and since it's exam conditions they are not allowed to communicate in any way.
What strategy could the students devise together so to avoid failure and the impending doom of unemployment? Being clever clogs from Cambridge, memorising infinitely large amounts of data is no problem to the students.
Note: A student suggested that each person just guess at random. However this has already been ruled out by the cleverer students who realised that if they were really unlucky, all of them could guess wrong.
x
Turn on thread page Beta

bananarama2
 Follow
 12 followers
 0 badges
 Send a private message to bananarama2
Offline0ReputationRep: Follow
 181
 12042013 13:06

 Follow
 182
 12042013 13:19
(Original post by bananarama2)
My ramblingsThis is dodgy ground for me, because there are an infinite number of students can it not be said that half have white and half have black. So, just my counting how many the others have, you can deduce the colour of your own? 
ukdragon37
 Follow
 25 followers
 13 badges
 Send a private message to ukdragon37
Offline13ReputationRep: Follow
 183
 12042013 13:20
(Original post by bananarama2)
My ramblingsThis is dodgy ground for me, because there are an infinite number of students can it not be said that half have white and half have black. So, just my counting how many the others have, you can deduce the colour of your own?Your ramblingsWhy must it be that half have white and half have black? It's possible that everyone has white. Also, what's half of infinity?
Last edited by ukdragon37; 12042013 at 13:23. 
 Follow
 184
 12042013 13:20
(Original post by ukdragon37)
Problem 41***
A (countably) infinite class of Cambridge students who believe in the Axiom of Choice are taking their finals for the Mathematical Tripos. At the start of the exam, the examiner places either a white or a black hat on each student at random. There is only one question in the exam: "What colour is your hat?" If only a finite number of students answers incorrectly then everyone becomes a Wrangler (very good), otherwise the Wooden Spoon is given to the whole class (very bad). Everyone can see the hats of everyone else besides their own, and since it's exam conditions they are not allowed to communicate in any way.
What strategy could the students devise together so to avoid failure and the impending doom of unemployment? Being clever clogs from Cambridge, memorising infinitely large amounts of data is no problem to the students.
Note: A student suggested that each person just guess at random. However this has already been ruled out by the cleverer students who realised that if they were really unlucky, all of them could guess wrong.
EDIT: @bananarama: what's half of infinityLast edited by shamika; 12042013 at 13:21. 
ukdragon37
 Follow
 25 followers
 13 badges
 Send a private message to ukdragon37
Offline13ReputationRep: Follow
 185
 12042013 13:28
(Original post by shamika)
I might be going mad from all the (lack of) revising for actuarial exams, but this really made me laugh! 
bananarama2
 Follow
 12 followers
 0 badges
 Send a private message to bananarama2
Offline0ReputationRep: Follow
 186
 12042013 13:30
(Original post by ukdragon37)
Your ramblingsWhy must it be that half have white and half have black? It's possible that everyone has white. Also, what's half of infinity?
(Original post by shamika)
I might be going mad from all the (lack of) revising for actuarial exams, but this really made me laugh!
EDIT: @bananarama: what's half of infinitySpoiler:ShowI'll explain in internal dialogue.
"Ahhhh random, so perhaps that means 50:50 chance. So for an infinite number of people, upon selecting one person you have a 50:50 chance. Continue ad infinitum and you remember counting half black and half white. So you can determine your own hat colour."
You Mathmos inventing nonsense
Yeh. I'll stick to the mechanics and calculus. 
bananarama2
 Follow
 12 followers
 0 badges
 Send a private message to bananarama2
Offline0ReputationRep: Follow
 187
 12042013 13:32
(Original post by joostan)
I thought that but there are an infinite number of white and black hats. . . 
 Follow
 188
 12042013 13:35
(Original post by bananarama2)
I think the solution will be out of my reach. 
ukdragon37
 Follow
 25 followers
 13 badges
 Send a private message to ukdragon37
Offline13ReputationRep: Follow
 189
 12042013 13:35
(Original post by bananarama2)
Spoiler:ShowI'll explain in internal dialogue.
"Ahhhh random, so perhaps that means 50:50 chance. So for an infinite number of people, upon selecting one person you have a 50:50 chance. Continue ad infinitum and you remember counting half black and half white. So you can determine your own hat colour."
You Mathmos inventing nonsense
Yeh. I'll stick to the mechanics and calculus.Spoiler:Show
An example demonstrates the futility of that method: suppose you see that the hats are arranged exactly 3 white, 1 black, 3 white, 1 black.... You'll always count more whites than black (and if you count infinitely there are infinite of each), but that doesn't tell you anything for certain about what colour you are.

bananarama2
 Follow
 12 followers
 0 badges
 Send a private message to bananarama2
Offline0ReputationRep: Follow
 190
 12042013 13:38
(Original post by ukdragon37)
Spoiler:Show
An example demonstrates the futility of that method: suppose you see that the hats are arranged exactly 3 white, 1 black, 3 white, 1 black.... You'll always count more whites than black (and if you count infinitely there are infinite of each), but that doesn't tell you anything for certain about what colour you are.
Spoiler:ShowWhat do you count as being communication? Are the hats symmetrical?
Edit: I've just noticed the three stars.Last edited by bananarama2; 12042013 at 13:41. 
 Follow
 191
 12042013 13:48
(Original post by ukdragon37)
Problem 41***
A (countably) infinite class of Cambridge students who believe in the Axiom of Choice are taking their finals for the Mathematical Tripos. At the start of the exam, the examiner places either a white or a black hat on each student at random. There is only one question in the exam: "What colour is your hat?" If only a finite number of students answers incorrectly then everyone becomes a Wrangler (very good), otherwise the Wooden Spoon is given to the whole class (very bad). Everyone can see the hats of everyone else besides their own, and since it's exam conditions they are not allowed to communicate. Students may not remove their hats or try to look at it in any way.
What strategy could the students devise together so to avoid failure and the impending doom of unemployment? Being clever clogs from Cambridge, memorising infinitely large amounts of data is no problem to the students.
Note: A student suggested that each person just guess at random. However this has already been ruled out by the cleverer students who realised that if they were really unlucky, all of them could guess wrong.
The students could meet before the exam (or not if they are telepathic) and define an equivalence relation that states that two sequences are equivalent if they the same after a finite number of entries (so they can get a collection of equivalence classes). By the axiom of choice they are able to select and memorise a representative sequence from each equiv. class.
When the students are in the exam room, they innocently take a glance at the hats of everyone in the room before them (row and column) (they will have to predetermine how the sequence is to be read) and memorise it perfectly, then they can determine what equivalence class the actual sequence of hats on heads (be it row by row by row for example) and then they can "guess" their own hat colour by using the representative sequence from that particular equivalence class which they have previously decided.
Seeing as the actual sequence of hat colours and the representative sequence that is used are in the same equivalence class; they have the same entries after a finite number of students and so all the students after this point will guess correctly.
Alternatively, a finite number of students could invest in a piece of stationary with a partially reflective surface and so just look at the reflection.Last edited by Llewellyn; 12042013 at 13:49. Reason: keyboard acting up again 
ukdragon37
 Follow
 25 followers
 13 badges
 Send a private message to ukdragon37
Offline13ReputationRep: Follow
 192
 12042013 13:49
(Original post by bananarama2)
Spoiler:ShowWhat do you count as being communication? Are the hats symmetrical?
Edit: I've just noticed the three stars.Spoiler:ShowBasically in the exam the students are only allowed to know the colour of hat on each student but not their own. Communication counts as any way which allows a student to obtain more information than this (telling someone else their colour, holding up a mirror, removing their hat, knocking out the examiner etc.)
What do you mean by symmetrical?

bananarama2
 Follow
 12 followers
 0 badges
 Send a private message to bananarama2
Offline0ReputationRep: Follow
 193
 12042013 13:58
(Original post by ukdragon37)
Spoiler:ShowBasically in the exam the students are only allowed to know the colour of hat on each student but not their own. Communication counts as any way which allows a student to obtain more information than this (telling someone else their colour, holding up a mirror, removing their hat, knocking out the examiner etc.)
What do you mean by symmetrical?
Last edited by bananarama2; 12042013 at 13:59. 
ukdragon37
 Follow
 25 followers
 13 badges
 Send a private message to ukdragon37
Offline13ReputationRep: Follow
 194
 12042013 14:31
(Original post by Llewellyn)
The students could meet before the exam (or not if they are telepathic) and define an equivalence relation that states that two sequences are equivalent if they the same after a finite number of entries (so they can get a collection of equivalence classes). By the axiom of choice they are able to select and memorise a representative sequence from each equiv. class.
When the students are in the exam room, they innocently take a glance at the hats of everyone in the room before them (row and column) (they will have to predetermine how the sequence is to be read) and memorise it perfectly, then they can determine what equivalence class the actual sequence of hats on heads (be it row by row by row for example) and then they can "guess" their own hat colour by using the representative sequence from that particular equivalence class which they have previously decided.
Seeing as the actual sequence of hat colours and the representative sequence that is used are in the same equivalence class; they have the same entries after a finite number of students and so all the students after this point will guess correctly.
1) A student Y who's after student X cannot see his own hat but X can, and therefore they have differing information in determining the equivalence class. How can it be guaranteed that X is thinking of the same equivalence class as Y?
2) Since within each class the sequences only differ after a finite number of hats, why can't the students agree on a selection method for the representative independent of the axiom of choice? (e.g. pick the sequence in the class where the finite portion is all black) 
 Follow
 195
 12042013 14:53
I probably should have known better than to attempt this
(Original post by ukdragon37)
You are nearly there, just a slight correction: the students should look at the people after them not before to determine the equivalence class, since the classes are defined to be sequences that have the same infinite tail after a finite differing head. But then I'd like you to elaborate two points:
1) A student Y who's after student X cannot see his own hat but X can, and therefore they have differing information in determining the equivalence class. How can it be guaranteed that X is thinking of the same equivalence class as Y?
2) Since within each class the sequences only differ after a finite number of hats, why can't the students agree on a selection method for the representative independent of the axiom of choice? (e.g. pick the sequence in the class where the finite portion is all black)
So suppose the actual sequence is black, black, black, .... and every student picks a sequence with white as their hat colour and black for every other hat colour; then they would fail. However if the representative sequence is 'universal' then there can only be a finite number of differences between the representative sequence and the actual sequence, and therefore only a finite number of wrong answers; which is a direct consequence of the axiom of choice (only one sequence can be chosen from a set of all possible sequences). 
 Follow
 196
 12042013 14:55
Solution 41
Let be the set of all the students. Denote its cardinality by , where is an arbitrary ordinal number. Define if and only if .
To each student assign an element, say , of the ordinal . Let be a good scenario. Then the student answers by guessing that the good scenario is . Let . Obviously, is the set of those students, who guess their hats incorrectly.
Since is a strictly increasing order without infinite chains, we know that is finite.
Hence the number of students who guess incorrectly will be finite.
Remarks:
We can consider any finite set of colors.
Also, what can we say in the case when ?Last edited by Mladenov; 12042013 at 15:11. 
ukdragon37
 Follow
 25 followers
 13 badges
 Send a private message to ukdragon37
Offline13ReputationRep: Follow
 197
 12042013 15:23
(Original post by Llewellyn)
I probably should have known better than to attempt this
(Original post by Llewellyn)
You are right  if each student picks his/her own representative of the equivalence class (of the actual observed sequence) then guesses their hat colour in accordance, it is possible for every single student to guess wrong. That is why they need to meet beforehand and agree on only one representative for every single equivalence class and use only that. That is the only way to guarantee that only a finite number of them can be wrong instead of some amount.
(Original post by Llewellyn)
So suppose the actual sequence is black, black, black, .... and every student picks a sequence with white as their hat colour and black for every other hat colour; then they would fail. However if the representative sequence is 'universal' then there can only be a finite number of differences between the representative sequence and the actual sequence, and therefore only a finite number of wrong answers; which is a direct consequence of the axiom of choice (only one sequence can be chosen from a set of all possible sequences).
Don't worry, these are nasty nasty questions and you've got the right method already.
(Original post by Mladenov)
Solution 41
Let be the set of all the students. Denote its cardinality by , where is an arbitrary ordinal number. Define if and only if .
To each student assign an element, say , of the ordinal . Let be a good scenario. Then the student answers by guessing that the good scenario is . Let . Obviously, is the set of those students, who guess their hats incorrectly.
Since is a strictly increasing order without infinite chains, we know that is finite.
Hence the number of students who guess incorrectly will be finite.
Remarks:
We can consider any finite set of colors.
Also, what can we say in the case when ?Last edited by ukdragon37; 12042013 at 15:35. 
Felix Felicis
 Follow
 31 followers
 13 badges
 Send a private message to Felix Felicis
Offline13ReputationRep: Follow
 198
 12042013 15:31

 Follow
 199
 12042013 15:36
(Original post by Mladenov)
Solution 41
Let be the set of all the students. Denote its cardinality by , where is an arbitrary ordinal number. Define if and only if .
To each student assign an element, say , of the ordinal . Let be a good scenario. Then the student answers by guessing that the good scenario is . Let . Obviously, is the set of those students, who guess their hats incorrectly.
Since is a strictly increasing order without infinite chains, we know that is finite.
Hence the number of students who guess incorrectly will be finite.
Remarks:
We can consider any finite set of colors.
Also, what can we say in the case when ?
We're told that there are countably infinite students, so alpha is just omega here...
you haven't defined what f is for a start.
also, the countable chain condition doesn't really come into it 
 Follow
 200
 12042013 15:45
Well, my solution is incomplete, yet I am sure the strategy works fine there. I shall write more rigorous proof.
Reply
Submit reply
Turn on thread page Beta
Related discussions:
 The Proof is 'notso' Trivial  Physics Edition
 Matrices: detA=0 > there exists a nontrivial solution to Ax=0 ...
 Stuck on a proof!
 Slight ambiguity in STEP question
 Extremely difficult lower triangular matrices question proof ...
 Proof by Induction ( Algebra Year 1 Uni)
 Is there a bottom line to what should be proven?
 Recursive unprovability
 Algebraic proof help! Maths GCSE
 Preparing for proofbased mathematics at university
TSR Support Team
We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.
This forum is supported by:
 SherlockHolmes
 Notnek
 charco
 Mr M
 TSR Moderator
 Nirgilis
 usycool1
 Changing Skies
 James A
 rayquaza17
 RDKGames
 randdom
 davros
 Gingerbread101
 Kvothe the Arcane
 TeeEff
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Labrador99
 EmilySarah00
Updated: February 22, 2018
Share this discussion:
Tweet