Well, my thesis is essentially done, now its just time for the eternal editing of the damn thing (also, its only like 65 pages, somehow I had hoped for more). Anyway, time to post the solution the the hat problem from last time.
For the first part of the puzzle, consider that the logicians have some sort of strategy, which must be based on the hats of their fellow logicians and possibly some constant which varies for each individual logician and possibly some random variable. You get into the room ("you" being one of the logicians) and you check your strategy, and it says to say that your hat was white. OK, great, but since your strategy is independent of your own hat colour, your hat colour could randomize as we do this and your answer won't change. Thus you are 50% to be correct, no matter what. This is true for each and every logician. This means that no strategy can save more than 50% on average. In fact, no strategy can save less than 50% either. All strategies have an expectation value of saving 50 of the logicians.
You might think that is weird, since in so many other hat puzzles it has been that case that the logicians pull off something amazing with no information about their own hat colours. If you check carefully though, in all of those, when they were going to guess they were 50% chance to be correct, the most they ever pulled off was correlation with the other logicians being right.
Alright, now, is there a strategy that guarantees saving 50? Note that if the logicians knew if the total number of white hats was even, they could always guess their own hat, and similarly if they knew the total number of white hats was odd. So, the strategy is to have half of the logicians assume the total number of white hats is even, the other half assume that it is odd. Exactly one of those two groups will be right, and you will save 50 of them.
Finally, a strategy that saves all or none of them. This is simple given the last paragraph, simply have everybody assume the total number of white hats is even (or odd, if you prefer). They will either all be correct or all be wrong, with 50-50 chance.
Friendly Hats
Been some time since I have done an actual hat puzzle. There was one recently on Tanya Khovanova’s Math Blog that I had assumed I had done before, since it was so basic. Interestingly enough, I have never actually done this one, so I might as well put it up now:
Thats simple enough, there are a few follow up questions that Tanya also added though:
and,
Fairly simple if you have been following all the other hat posts, most of the basic results you need to solve this out have been proven somewhere or another on this blog.
There is a room of 100 logicians wearing hats. Each hat can be either black or white, and standard hat rules apply. The logicians must simultaneously guess what colour hat they have. Every logician who guesses right is released and every one that guesses wrong is killed.
Before the hats are assigned, they logicians may get together and plan. What strategy maximizes the number of logicians you can save on average?
Thats simple enough, there are a few follow up questions that Tanya also added though:
Suppose the maximum you can save on average is N, is there a strategy that guarantees that you will save N of them?
and,
Suppose the logicians are close friends, and they do not want to see their friends die, they would rather die with them. Is there a strategy that guarantees that they will all live together or die together?
Fairly simple if you have been following all the other hat posts, most of the basic results you need to solve this out have been proven somewhere or another on this blog.
Going In Circles
Alright, some time ago I promised to do more on the dots on a line puzzle, so I guess I'll do that now.
On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.
This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.
We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is
Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.
The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.
Moving on, the expected length of a large interval is given by
which we can integrate by parts. Let u=x and v=F(x)3-1, so then we have
v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.
One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).
To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).
Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.
A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.
So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.
When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?
This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral
over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.
Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.
On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.
This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.
We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is
∫F(x) F(x) f(x) dx
=∫F(x)2 dF
Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.
The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.
Moving on, the expected length of a large interval is given by
∫x F(x) F(x) f(x) dx
which we can integrate by parts. Let u=x and v=F(x)3-1, so then we have
x(F(x)3-1)+∫(1-F(x)3) dx
v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.
One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).
To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).
Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.
A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.
So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.
When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?
This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral
∫∫x dy dx
over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.
Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.
Shaking Hands
Alright, the thesis is currently sitting at 40 pages, so I'm happy enough with my progress that I deserve to take a break. Naturally a break comes in the from of posting solutions to logic puzzles, because I have no sense of fun. So, lets look at the solution to the crazy ass number problem from last time.
First of all, if you played around with it a bit, you probably determined that for any starting N, only one final M was ever possible. As far as I am concerned, that fact was in of itself neat enough to make this puzzle pretty cool, but lets look at it a bit more.
First, if you just split N into N-1 and 1, and then N-1 into N-2 and 1 and just keep splitting off 1 all the way down, then you end with having written N-1, N-2, N-3,..., 2, 1 on board two, so the total sum is N(N-1)/2. Thus, if for any N there is only one possible value of M, that value must be N(N-1)/2. Note a particular edge case, that of N is 1, we take the value of M to be zero, later we will see that this is important for consistency.
Alright, so let us conjecture the solution to the puzzle:
Initially I wanted to prove this by induction, and one almost can, but actually to do it properly you need to break out strong induction, which I will talk briefly about first.
Induction is used if you want to prove some statement S(n) for all natural numbers n (and for the purpose of this post, the naturals start at 1 (and it pains me to write that)). You prove the statement is true by first showing that S(1) is true, and then showing that S(k-1) implies S(k) for k>1, good stuff, and the intuition behind it is pretty obvious for anybody who would actually read this blog.
For strong induction, you instead prove S(n) by proving S(1) and then show that [S(j) for all j less than k] implies S(k) for k>1. Intuitively, its not really any different from regular induction, the assumption is technically a bit different, but it still works. Naturally, one can reformulate any induction proof as a strong induction proof, as the strong induction assumption of [S(j) for all j less than k] is a stronger assumption than S(k-1), but there are some strong induction proofs that cannot be recast as regular induction, since you needed the stronger assumption. Strong induction is also used for proving statements about the ordinals, since some of those are not successors to other ones.
Anyway, let us prove our earlier conjecture by strong induction. It is easy to see that it holds for small N (I'm not sure about proving it for N=1, but lets just start with 2 or something). Now, assume that it is true for all j less than k for some k. Lets say that k is written on the board and calculate the possible values of M. We break k into p and k-p, for some p less than k. We then write p(k-p) on board 2, and are left with p and k-p on board 1. Naturally breaking up p results in us writing numbers summing to p(p-1)/2 on board 2 (by strong induction assumption) and breaking up k-p results in us writing numbers summing up to (k-p)(k-p-1)/2 onto board 2. Note that if p=1 or p=k-1, then having a 1 on board one does not result in any additional numbers on board 2, good.
So, on board 2, we have p(k-p) and a bunch of other numbers that sum to p(p-1)/2 and (k-p)(k-p-1)/2. Adding those up, we get k(k-1)/2 for any choice of p, proving the conjecture.
On the xkcd forums, somebody posted a much simpler solution than mine, and its cool enough that I will give it here.
Consider that we have N people in a room, and breaking N up into p and N-p is splitting people up into smaller groups. Before we split people up, they all shake hands with the people in the other group and say goodbye. For example, when we split 8 into 5 and 3, the 5 people each shake hands with the 3 people, so there are 15 handshakes. Board 2 is just keeping track of handshakes. The steps halt when everybody has been fully divided up and everybody must have said goodbye to everybody else. How many handshakes were there? There must have been N choose 2 of them, which is N(N-1)/2.
First of all, if you played around with it a bit, you probably determined that for any starting N, only one final M was ever possible. As far as I am concerned, that fact was in of itself neat enough to make this puzzle pretty cool, but lets look at it a bit more.
First, if you just split N into N-1 and 1, and then N-1 into N-2 and 1 and just keep splitting off 1 all the way down, then you end with having written N-1, N-2, N-3,..., 2, 1 on board two, so the total sum is N(N-1)/2. Thus, if for any N there is only one possible value of M, that value must be N(N-1)/2. Note a particular edge case, that of N is 1, we take the value of M to be zero, later we will see that this is important for consistency.
Alright, so let us conjecture the solution to the puzzle:
When N is the starting value, then N(N-1)/2 is the unique final value of M.
Initially I wanted to prove this by induction, and one almost can, but actually to do it properly you need to break out strong induction, which I will talk briefly about first.
Induction is used if you want to prove some statement S(n) for all natural numbers n (and for the purpose of this post, the naturals start at 1 (and it pains me to write that)). You prove the statement is true by first showing that S(1) is true, and then showing that S(k-1) implies S(k) for k>1, good stuff, and the intuition behind it is pretty obvious for anybody who would actually read this blog.
For strong induction, you instead prove S(n) by proving S(1) and then show that [S(j) for all j less than k] implies S(k) for k>1. Intuitively, its not really any different from regular induction, the assumption is technically a bit different, but it still works. Naturally, one can reformulate any induction proof as a strong induction proof, as the strong induction assumption of [S(j) for all j less than k] is a stronger assumption than S(k-1), but there are some strong induction proofs that cannot be recast as regular induction, since you needed the stronger assumption. Strong induction is also used for proving statements about the ordinals, since some of those are not successors to other ones.
Anyway, let us prove our earlier conjecture by strong induction. It is easy to see that it holds for small N (I'm not sure about proving it for N=1, but lets just start with 2 or something). Now, assume that it is true for all j less than k for some k. Lets say that k is written on the board and calculate the possible values of M. We break k into p and k-p, for some p less than k. We then write p(k-p) on board 2, and are left with p and k-p on board 1. Naturally breaking up p results in us writing numbers summing to p(p-1)/2 on board 2 (by strong induction assumption) and breaking up k-p results in us writing numbers summing up to (k-p)(k-p-1)/2 onto board 2. Note that if p=1 or p=k-1, then having a 1 on board one does not result in any additional numbers on board 2, good.
So, on board 2, we have p(k-p) and a bunch of other numbers that sum to p(p-1)/2 and (k-p)(k-p-1)/2. Adding those up, we get k(k-1)/2 for any choice of p, proving the conjecture.
On the xkcd forums, somebody posted a much simpler solution than mine, and its cool enough that I will give it here.
Consider that we have N people in a room, and breaking N up into p and N-p is splitting people up into smaller groups. Before we split people up, they all shake hands with the people in the other group and say goodbye. For example, when we split 8 into 5 and 3, the 5 people each shake hands with the 3 people, so there are 15 handshakes. Board 2 is just keeping track of handshakes. The steps halt when everybody has been fully divided up and everybody must have said goodbye to everybody else. How many handshakes were there? There must have been N choose 2 of them, which is N(N-1)/2.
Subscribe to:
Posts (Atom)
