x Turn on thread page Beta
 You are Here: Home >< Maths

# The Proof is Trivial! watch

1. (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.
My ramblings
This 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?
2. (Original post by bananarama2)
My ramblings
This 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?
I thought that but there are an infinite number of white and black hats. . .
3. (Original post by bananarama2)
My ramblings
This 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?
Why must it be that half have white and half have black? It's possible that everyone has white. Also, what's half of infinity?
4. (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.
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 infinity
5. (Original post by shamika)
I might be going mad from all the (lack of) revising for actuarial exams, but this really made me laugh!
I was getting bored by all the numbers and integral signs hanging around here
6. (Original post by ukdragon37)
Why 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 infinity
Spoiler:
Show
I'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.
7. (Original post by joostan)
I thought that but there are an infinite number of white and black hats. . .
I think the solution will be out of my reach.
8. (Original post by bananarama2)
I think the solution will be out of my reach.
Same Unless of course there's a blindingly obvious solution we're missing
9. (Original post by bananarama2)
Spoiler:
Show
I'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.
10. (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:
Show
What do you count as being communication? Are the hats symmetrical?

Edit: I've just noticed the three stars.
11. (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.
So I'm going to assume the students have some sort of communication beforehand; or perhaps they are telepathic; or perhaps they all go along to the game theory socials. I can't see the answer otherwise.

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.
12. (Original post by bananarama2)
Spoiler:
Show
What do you count as being communication? Are the hats symmetrical?

Edit: I've just noticed the three stars.
Spoiler:
Show
Basically 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?
13. (Original post by ukdragon37)
Spoiler:
Show
Basically 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?
Nevermind The strategy I would adopt is befriend Llewellyn and hope he has a genius plan.
14. (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.
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)
15. 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)
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.

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).
16. 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 ?
17. (Original post by Llewellyn)
I probably should have known better than to attempt this
It's a good attempt, in fact you've got the right idea, but I'm just questioning whether you understand the details

(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.
Yes they can meet beforehand and agree on the possible equivalence classes and their representatives. However my point 1) was questioning about in the exam how do they know if they were using the same equivalence class since each student has (slightly) different information.

(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).
No, the axiom of choice only guarantees that it's possible to pick some representative for each equivalence class, not that there is only one choice for each class. It is able to guarantee this even if no obvious selection method (choice function) is available. However my point 2) asks why is the axiom of choice still necessary because there does seem to be an obvious selection method (pick the sequence in each equivalence class that has the finite portion being all black).

Don't worry, these are nasty nasty questions and you've got the right method already.

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 ?
e.g. the chain is strictly increasing but is infinite (although bounded, rather paradoxical but true). Even if you only consider finite-sized chains, there are still an infinite number of them - although the number of wrongs in each chain is finite, this does not mean overall it is finite.
18. Problem 42*/**

Show that

(angles measured in degrees)
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 ?
This solution is somewhat incomplete: what are your a and b? Elements of the ordinal alpha?

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
20. Well, my solution is incomplete, yet I am sure the -strategy works fine there. I shall write more rigorous proof.

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:
Updated: February 22, 2018
Today on TSR

### Four things top students are doing

Over the Easter break

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams