As a computer scientist, I think the reason this makes me so uncomfortable is that the steps are presented as an algorithm, but each step involves a computation of infinite data that will take infinite time (uncountably infinite time to itemize all the equivalence classes beforehand, and then infinite counting to inspect all the hats and determine their class). Even in a theoretical land of pure math and infinite time, could the prisoners really distinguish between sets of numbers that differ in arbitrarily many ways, and are thereby equivalent, vs those that differ in truly infinite ways?
Haha, yes, this solution cannot be implemented in a Turing machine. Although being able to distinguish between elements from different equivalent classes is certainly not realistic, I think the most "uncomfortable" step here is the use of the axiom of choice, since that axiom is independent of the axiom of natural numbers. But being able to write down arbitrary real numbers (let alone the fact there are infinitely many people) isn't so realistic to begin with. :)
I don't think this solution works, but feel free to correct me. Because yes, each person agrees on the same equivalence class of sequences. But each person is also at a finite position when there's a countable number of people. So as you can imagine, there's no way the first 5 people gets the right number. But because this set of sequesnces is uncountable, this will be the case for every single person. Everyone is at a finite point, and part of "only the first n people" which will for sure get it wrong, and therefore everyone will get it wrong. Because the number of people is countable, the number of people who get it right is given by the limit of n -> infinity of how many get it right for the first n people, which is 0 for all n. So the answer is 0 people get it right. Where does my logic fail?
Here is a similar problem: There is a house with 100 rooms. Each room contains an infinite collection of boxes, indexed with the natural numbers. Each box contains a random real number, which is the same over all the rooms - that is, for every natural number n, box n contains the same real number in every room. In this house, 100 set theorists play a game. Each player goes into a unique room and opens as many boxes as they like (perhaps infinitely many) as long as they leave at least one box in their room unopened. Then, each player picks an unopened box in their room and guesses what real number is inside of it. In order to win the game, at least 99 players must guess correctly. The players can discuss a strategy beforehand, but after they go into their respective rooms, no more communication is allowed. Design a winning strategy.
An equivalence class is a subset (of natural numbers in this case). A subset with countably many members. Now look up cantor’s diagonal argument - it will clarify the rest.
Haha yes, the solution here is certainly not very realistic. We are essentially black-boxing the function from the set of real sequences to the set of equivalence classes in the video (more precisely, we assume each person can somehow quickly get the output from this function for any input). I don't think the fact that there are countably many people matters so much here, since this evaluation is performed individually and not collaboratively; what matters is that each person somehow has the magical power to do such a task.
Nah man. Long before you get to a hat with graham number on it, simply the information density of writing the number on the hat would collapse the prisoner into a black hole.
I have my doubts about determining uncountable amount of equivalence classes. For each prisoner we may get 1 class, so, at the end, we wont be able to cover all the classes. This problem would work for rational numbers though
Please show that there is some way that allows a prisoner to determine which equivalence class any observed sequence of numbers belongs to. (Seems like one would need some kind of axiom-of-choice-like assumption that I am not sure can be granted.)
I think there is a way to guarantee that at the most one will be incorrect as long as the prisoners know the order they will be picked. The way is for the first prisoner to use the function f(n) = 1 / (n^2 + |h(n)|) where n is the number of the prisoner and h(n) is the number on their hat on each of the prisoners, and then multiply the result by -1 if h(n) < 0, then sum up all of the results, I'm pretty sure that the sum will converge and now every prisoner will be able to calculate their hat number like the solution to the finite number of prisoners.
Note that in the video, all guesses are made at the same time, so such a strategy isn't viable. However, this is a really awesome idea! I agree it works and it's a cool extension of the usual finite number case.
wait this is genius bruh. Basically making the first person say a number that with the combination of every number other than yourself, let's you find your own number. Sadly as the channel guy said this doesn't work because they do it simultaneously but still
The neerest thing i got to a solution is this: Suppose that you only allow each prisoner to display a single bit of information, by either standing up or sitting down. Here's a procidure that allows them all to know their number: First, the prisoners agree to map all the real numbers to the interval (0,1) (by way of an s curve for example). They will later reverse the map when they make the guess. Let p(n) denote the bit displayed by prisoner n. The prisoners agree to the following: p(1)=1 ( or 0, does'nt matter) p(n)=(sum from i=1 to n-1 of the (n-i)th binary digit of prisoner i's hat) all mod 2 This way every prisoner can deduce every digit of their hat, by subtracting away the effect of all the prisoners with an index smaller than the priaoner holding the rellevant digit. They can do that because they can see all the other hats.
Does each person know whether they are person n? Or is their order randomized? Because if the order is randomized then I don’t think this solution works; as each person might try to fill in the role of the same swapped element of the sequence
Great point! I was assuming that there is an ordering that everyone agrees with, which is probably reasonable since they can decide on this ordering during their planning meeting.
Interesting! It's possible that this is just a decently well-known problem. I was curious about this, considering I heard this problem/solution from a graduate student some years ago (I don't think that student was the inventor, unless I'm really mistaken); either way, the problem likely is somewhat well-known, considering there is a wikipedia section on it (see the description).
Maybe you could reformulate the banach-tarski paradox in terms of the prisoner hat problem. Suppose each number on the prisoners hat were assigned acording to a uniform uncorralated distribution on the interval [0,1]. Since the numbers are uncorralated, any strategy based on the other hats will still have probability zero. Therefore the probability of all the prisoners guessing correctly in an arbitrary sequence of prisoners is 0×0×0×0...=0. The probability that any sequence containing all but a finite number is 0+0+0+0...=0. I think this argument fails because an arbitrary set of sequences of numbers [0,1] is not generally measurable.
Why? If you can enumerate you can count. Just start enumerating and assign consecutive numbers. Seems totally obvious, at least to someone with a computing background.
I understand what you are talking about. However, you did a poor job of explaining what numbers get assigned to each person. You made it sound like any random real number could be assigned in the beginning of the video. If that was the case, with countably infinite people, then the likely number of correct guesses will be 0. This is because every number comes from the uncountable infinite set of the Reals.
In this problem, the prisoners could be assigned a completely random sequence of real numbers. Even that sequence will still fit into one of the equivalence classes, so the prisoners would have no problem with it.
As the other commenter pointed out, there are no restrictions on the assignment of real numbers here (so it can be "random" as long as you make that term precise). Apologies if that was unclear. Note also that it does not make sense to analyze "the likely number of correct guesses" since the guesses are definitely *not* random and rather systematically chosen as explained in the video.
As a computer scientist, I think the reason this makes me so uncomfortable is that the steps are presented as an algorithm, but each step involves a computation of infinite data that will take infinite time (uncountably infinite time to itemize all the equivalence classes beforehand, and then infinite counting to inspect all the hats and determine their class).
Even in a theoretical land of pure math and infinite time, could the prisoners really distinguish between sets of numbers that differ in arbitrarily many ways, and are thereby equivalent, vs those that differ in truly infinite ways?
Haha, yes, this solution cannot be implemented in a Turing machine. Although being able to distinguish between elements from different equivalent classes is certainly not realistic, I think the most "uncomfortable" step here is the use of the axiom of choice, since that axiom is independent of the axiom of natural numbers. But being able to write down arbitrary real numbers (let alone the fact there are infinitely many people) isn't so realistic to begin with. :)
I don't think this solution works, but feel free to correct me. Because yes, each person agrees on the same equivalence class of sequences. But each person is also at a finite position when there's a countable number of people. So as you can imagine, there's no way the first 5 people gets the right number. But because this set of sequesnces is uncountable, this will be the case for every single person. Everyone is at a finite point, and part of "only the first n people" which will for sure get it wrong, and therefore everyone will get it wrong. Because the number of people is countable, the number of people who get it right is given by the limit of n -> infinity of how many get it right for the first n people, which is 0 for all n. So the answer is 0 people get it right. Where does my logic fail?
Here is a similar problem:
There is a house with 100 rooms. Each room contains an infinite collection of boxes, indexed with the natural numbers. Each box contains a random real number, which is the same over all the rooms - that is, for every natural number n, box n contains the same real number in every room.
In this house, 100 set theorists play a game. Each player goes into a unique room and opens as many boxes as they like (perhaps infinitely many) as long as they leave at least one box in their room unopened. Then, each player picks an unopened box in their room and guesses what real number is inside of it. In order to win the game, at least 99 players must guess correctly.
The players can discuss a strategy beforehand, but after they go into their respective rooms, no more communication is allowed. Design a winning strategy.
What is unclear to me is how a countable number of people can go through an uncountable number of equivalence classes in this solution you presented?
An equivalence class is a subset (of natural numbers in this case). A subset with countably many members. Now look up cantor’s diagonal argument - it will clarify the rest.
Haha yes, the solution here is certainly not very realistic. We are essentially black-boxing the function from the set of real sequences to the set of equivalence classes in the video (more precisely, we assume each person can somehow quickly get the output from this function for any input). I don't think the fact that there are countably many people matters so much here, since this evaluation is performed individually and not collaboratively; what matters is that each person somehow has the magical power to do such a task.
Nah man. Long before you get to a hat with graham number on it, simply the information density of writing the number on the hat would collapse the prisoner into a black hole.
I have my doubts about determining uncountable amount of equivalence classes. For each prisoner we may get 1 class, so, at the end, we wont be able to cover all the classes. This problem would work for rational numbers though
Please show that there is some way that allows a prisoner to determine which equivalence class any observed sequence of numbers belongs to.
(Seems like one would need some kind of axiom-of-choice-like assumption that I am not sure can be granted.)
I think there is a way to guarantee that at the most one will be incorrect as long as the prisoners know the order they will be picked. The way is for the first prisoner to use the function f(n) = 1 / (n^2 + |h(n)|) where n is the number of the prisoner and h(n) is the number on their hat on each of the prisoners, and then multiply the result by -1 if h(n) < 0, then sum up all of the results, I'm pretty sure that the sum will converge and now every prisoner will be able to calculate their hat number like the solution to the finite number of prisoners.
Note that in the video, all guesses are made at the same time, so such a strategy isn't viable. However, this is a really awesome idea! I agree it works and it's a cool extension of the usual finite number case.
wait this is genius bruh. Basically making the first person say a number that with the combination of every number other than yourself, let's you find your own number. Sadly as the channel guy said this doesn't work because they do it simultaneously but still
The neerest thing i got to a solution is this:
Suppose that you only allow each prisoner to display a single bit of information, by either standing up or sitting down.
Here's a procidure that allows them all to know their number:
First, the prisoners agree to map all the real numbers to the interval (0,1) (by way of an s curve for example). They will later reverse the map when they make the guess.
Let p(n) denote the bit displayed by prisoner n.
The prisoners agree to the following:
p(1)=1 ( or 0, does'nt matter)
p(n)=(sum from i=1 to n-1 of the (n-i)th binary digit of prisoner i's hat) all mod 2
This way every prisoner can deduce every digit of their hat, by subtracting away the effect of all the prisoners with an index smaller than the priaoner holding the rellevant digit. They can do that because they can see all the other hats.
Possibly the least convoluted example of the Axiom of Choice
Had some major alarm bells ringing at 7:04
Does each person know whether they are person n? Or is their order randomized? Because if the order is randomized then I don’t think this solution works; as each person might try to fill in the role of the same swapped element of the sequence
Great point! I was assuming that there is an ordering that everyone agrees with, which is probably reasonable since they can decide on this ordering during their planning meeting.
@@LetsSolveMathProblems true! Definitely a notable inclusion if you were to formalize this solution
They can decide ahead of time what order they want to go in.
This seems very similar to red-blue hat puzzle from coding theory!
Interesting! It's possible that this is just a decently well-known problem. I was curious about this, considering I heard this problem/solution from a graduate student some years ago (I don't think that student was the inventor, unless I'm really mistaken); either way, the problem likely is somewhat well-known, considering there is a wikipedia section on it (see the description).
Maybe you could reformulate the banach-tarski paradox in terms of the prisoner hat problem. Suppose each number on the prisoners hat were assigned acording to a uniform uncorralated distribution on the interval [0,1]. Since the numbers are uncorralated, any strategy based on the other hats will still have probability zero. Therefore the probability of all the prisoners guessing correctly in an arbitrary sequence of prisoners is 0×0×0×0...=0. The probability that any sequence containing all but a finite number is 0+0+0+0...=0. I think this argument fails because an arbitrary set of sequences of numbers [0,1] is not generally measurable.
Side comment: I always found the name "countable" so annoying. It should be called "enumerable".
Why? If you can enumerate you can count. Just start enumerating and assign consecutive numbers. Seems totally obvious, at least to someone with a computing background.
I understand what you are talking about. However, you did a poor job of explaining what numbers get assigned to each person. You made it sound like any random real number could be assigned in the beginning of the video. If that was the case, with countably infinite people, then the likely number of correct guesses will be 0. This is because every number comes from the uncountable infinite set of the Reals.
In this problem, the prisoners could be assigned a completely random sequence of real numbers. Even that sequence will still fit into one of the equivalence classes, so the prisoners would have no problem with it.
As the other commenter pointed out, there are no restrictions on the assignment of real numbers here (so it can be "random" as long as you make that term precise). Apologies if that was unclear. Note also that it does not make sense to analyze "the likely number of correct guesses" since the guesses are definitely *not* random and rather systematically chosen as explained in the video.
and still, the expectation value of the number of wrong guesses is infinity 😅 even though it is a finite number in every possible outcome.
🤯🤯🤯…
♾️