The Student Room Group

The Proof is Trivial!

Scroll to see replies

Original post by ukdragon37
:colone:

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

Reply 181
Original post by bananarama2

My ramblings



I thought that but there are an infinite number of white and black hats. . . :s-smilie:
Original post by bananarama2

My ramblings



Your ramblings

(edited 10 years ago)
Reply 183
Original post by ukdragon37
:colone:

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 :tongue:
(edited 10 years ago)
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 :colone:
Original post by ukdragon37

Your ramblings




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 :tongue:


Spoiler



You Mathmos inventing nonsense :tongue:

Yeh. I'll stick to the mechanics and calculus.
Original post by joostan
I thought that but there are an infinite number of white and black hats. . . :s-smilie:


I think the solution will be out of my reach.
Reply 187
Original post by bananarama2
I think the solution will be out of my reach.


Same :redface: Unless of course there's a blindingly obvious solution we're missing :smile:
Original post by bananarama2

Spoiler



You Mathmos inventing nonsense :tongue:

Yeh. I'll stick to the mechanics and calculus.


Spoiler

Original post by ukdragon37

Spoiler



Spoiler



Edit: I've just noticed the three stars.
(edited 10 years ago)
Original post by ukdragon37
:colone:

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.
(edited 10 years ago)
Original post by bananarama2

Spoiler



Edit: I've just noticed the three stars.


Spoiler

Original post by ukdragon37

Spoiler



Nevermind :tongue: The strategy I would adopt is befriend Llewellyn and hope he has a genius plan.
(edited 10 years ago)
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)
I probably should have known better than to attempt this :colondollar:
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).
Reply 195
Solution 41

Let SS be the set of all the students. Denote its cardinality by α\alpha, where α\alpha is an arbitrary ordinal number. Define aba \triangleleft b if and only if a<ba < b.
To each student assign an element, say aia_{i}, of the ordinal α\alpha. Let FF be a good scenario. Then the student aia_{i} answers by guessing that the good scenario is f(ai)f(a_{i}). Let T={aiSf(ai)F}T=\{a_{i} \in S | f(a_{i})\not=F\}. Obviously, TT is the set of those students, who guess their hats incorrectly.
Since (S,)(S,\triangleleft) is a strictly increasing order without infinite chains, we know that TT 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 card(S)card(R)card(S) \ge card(\mathbb{R})?
(edited 10 years ago)
Original post by Llewellyn
I probably should have known better than to attempt this :colondollar:


It's a good attempt, in fact you've got the right idea, but I'm just questioning whether you understand the details :tongue:

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. :tongue:

Original post by Mladenov
Solution 41

Let SS be the set of all the students. Denote its cardinality by α\alpha, where α\alpha is an arbitrary ordinal number. Define aba \triangleleft b if and only if a<ba < b.
To each student assign an element, say aia_{i}, of the ordinal α\alpha. Let FF be a good scenario. Then the student aia_{i} answers by guessing that the good scenario is f(ai)f(a_{i}). Let T={aiSf(ai)F}T=\{a_{i} \in S | f(a_{i})\not=F\}. Obviously, TT is the set of those students, who guess their hats incorrectly.
Since (S,)(S,\triangleleft) is a strictly increasing order without infinite chains, we know that TT 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 card(S)card(R)card(S) \ge card(\mathbb{R})?


:confused: e.g. the chain 1,2,,ω1, 2, \dots, \omega 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.
(edited 10 years ago)
Problem 42*/**

Show that r=0881cosrcos(r+1)=cos1sin21\displaystyle\sum_{r=0}^{88} \dfrac{1}{\cos r \cdot \cos (r+1)} = \dfrac{\cos 1}{\sin^{2} 1}

(angles measured in degrees)
Reply 198
Original post by Mladenov
Solution 41

Let SS be the set of all the students. Denote its cardinality by α\alpha, where α\alpha is an arbitrary ordinal number. Define aba \triangleleft b if and only if a<ba < b.
To each student assign an element, say aia_{i}, of the ordinal α\alpha. Let FF be a good scenario. Then the student aia_{i} answers by guessing that the good scenario is f(ai)f(a_{i}). Let T={aiSf(ai)F}T=\{a_{i} \in S | f(a_{i})\not=F\}. Obviously, TT is the set of those students, who guess their hats incorrectly.
Since (S,)(S,\triangleleft) is a strictly increasing order without infinite chains, we know that TT 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 card(S)card(R)card(S) \ge card(\mathbb{R})?


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

Quick Reply

Latest