There are 16 overlapping circles in a plane with the following proerties:By "overlapping circles" I really mean that circle N can share some interior points with circle N+1, it just helps to say it that way to imagine the setup. If you have forgotten your grade school geometry you may want to look up what a chord of a circle is on wikipedia or something.
Circle 1 has radius 1
The diameter of circle 2 is a chord of circle 1
The diameter of circle 3 is a chord of circle 2
...
The diameter of circle 16 is a chord of circle 15
What is the maximum distance from a point in circle 16 to the center of circle 1?
Circles On Circles
New puzzle time? I guess it must be, its certainly not new solution time. Though I think I still have left that cats and dogs game hanging, one day I'll have to revisit that. Anyway, I found this puzzle on the xkcd forums, but its initially from the cofoundry:
True And False
I suppose the True or False puzzle from last time has been up long enough, so I should probably get around to the solution. Like I said, my solution will basically be following the derivation that Tanya Khovanova did on her blog, because she did a better job of it than I expect to be able to anyway.
Alright, remember last time I said it is important to solve the simpler case of 5 questions with 4 attempts, so lets assume that we already have the ability to do that (I will show how later) and then use that to solve the problem of 30 questions. Without any loss of generality, we might as well have Victor answer "true" to all the questions first, to establish a base case. Next, we can submit the first 5 as "false" and the other 25 as "true" to get a base case for the first 5 questions (which we can then solve independently in 4 attempts), next we do the next batch of 5 as "false" with the rest "true" to get a base case for the next 5 and solve those in 4 more attempts. When we get to the last batch of 5, we don't need to do a final base case for those ones, as we already had our initial base case to tell us how many true answers are on the test in total, and we knew how many true were in each other block of 5, so we have already found our base for the last 5 questions. This argument shows quite generally that if you can do Q questions in N attempts then you can do MQ questions in MN attempts (for our case Q=5, N=4, M=6).
Now, how do we do 5 questions in 4 attempts? First we spend one attempt on our base case to see how many answers are "true", so we submit TTTTT. For the other 3 attempts, we will switch some of the answers to "false". There is no need to switch 3 of them to "false", as you get the same information by taking the compliment and switching the other 2 of them to "false". Similarly switching 4 or 5 to "false" is also meaningless, so we need only worry about 1 or 2. If we use FTTTT for our second attempt, we will get the answer to the first question and have 2 more attempts to solve out the remaining 4 questions, seems sort of hard (is in fact impossible, but I'm not going to prove that), so for our second attempt we must flip two answers to "false". Thus we can use FFTTT as our second test.
For our third test, we can basically choose between TTFFT ad FTFTT, depending on if we want our third attempt to have any overlap with our second attempt. But TTFFT is the same information as FFTTF which along with our second attempt gives the same information as TTTTF with only one "false" is probably a bad idea. Thus for our third attempt we should use FTFTT. By a similar logic we can use FTTFT for our fourth attempt.
So our exams are TTTTT, FFTTT, FTFTT, FTTFT. The first one give us the number of "true" answers. Adding up the second, third, and fourth mod 2, we can determine the answer to question 5 (as a "true" in one of the first four question contributes 0 mod 2, while a "false" contributes 1 mod 2). Next, going from TTTTT to FFTTT you either gained 2 points, lost 2 points, or stayed the same If you gained or last 2, you know the answers to the first two questions and finishing things off is easy, if you stayed the same then exactly one of the first two questions is true while the other is false. Similarly, TTTTT and FTFTT tells you if questions 1 and 3 are both true or false (easy to solve) or 1 of each. And same for questions 1 and 4. The only hard case is if your score never went up or down, but in that case exactly one of 1 and 2 is true, exactly one of 1 and 3 is true, and exactly one of 1 and 4 is true, thus the only cases are TFFF or FTTT and our base case will distinguish those.
This completes the proof that you can do 30 questions in 24 attempts. Note that this strategy was non-adaptive, in the sense that I never used the information gained from submitting one exam to decide my questions for the next exam. I could have just submitted my 24 exams in any order and then studied them to get my answers. One can in theory make more powerful strategies by using adaptive strategies, by using information you gain along the way to adjust what you are doing, but then the strategy tree is way harder to figure out, because it in theoretically very large.
Alright, remember last time I said it is important to solve the simpler case of 5 questions with 4 attempts, so lets assume that we already have the ability to do that (I will show how later) and then use that to solve the problem of 30 questions. Without any loss of generality, we might as well have Victor answer "true" to all the questions first, to establish a base case. Next, we can submit the first 5 as "false" and the other 25 as "true" to get a base case for the first 5 questions (which we can then solve independently in 4 attempts), next we do the next batch of 5 as "false" with the rest "true" to get a base case for the next 5 and solve those in 4 more attempts. When we get to the last batch of 5, we don't need to do a final base case for those ones, as we already had our initial base case to tell us how many true answers are on the test in total, and we knew how many true were in each other block of 5, so we have already found our base for the last 5 questions. This argument shows quite generally that if you can do Q questions in N attempts then you can do MQ questions in MN attempts (for our case Q=5, N=4, M=6).
Now, how do we do 5 questions in 4 attempts? First we spend one attempt on our base case to see how many answers are "true", so we submit TTTTT. For the other 3 attempts, we will switch some of the answers to "false". There is no need to switch 3 of them to "false", as you get the same information by taking the compliment and switching the other 2 of them to "false". Similarly switching 4 or 5 to "false" is also meaningless, so we need only worry about 1 or 2. If we use FTTTT for our second attempt, we will get the answer to the first question and have 2 more attempts to solve out the remaining 4 questions, seems sort of hard (is in fact impossible, but I'm not going to prove that), so for our second attempt we must flip two answers to "false". Thus we can use FFTTT as our second test.
For our third test, we can basically choose between TTFFT ad FTFTT, depending on if we want our third attempt to have any overlap with our second attempt. But TTFFT is the same information as FFTTF which along with our second attempt gives the same information as TTTTF with only one "false" is probably a bad idea. Thus for our third attempt we should use FTFTT. By a similar logic we can use FTTFT for our fourth attempt.
So our exams are TTTTT, FFTTT, FTFTT, FTTFT. The first one give us the number of "true" answers. Adding up the second, third, and fourth mod 2, we can determine the answer to question 5 (as a "true" in one of the first four question contributes 0 mod 2, while a "false" contributes 1 mod 2). Next, going from TTTTT to FFTTT you either gained 2 points, lost 2 points, or stayed the same If you gained or last 2, you know the answers to the first two questions and finishing things off is easy, if you stayed the same then exactly one of the first two questions is true while the other is false. Similarly, TTTTT and FTFTT tells you if questions 1 and 3 are both true or false (easy to solve) or 1 of each. And same for questions 1 and 4. The only hard case is if your score never went up or down, but in that case exactly one of 1 and 2 is true, exactly one of 1 and 3 is true, and exactly one of 1 and 4 is true, thus the only cases are TFFF or FTTT and our base case will distinguish those.
This completes the proof that you can do 30 questions in 24 attempts. Note that this strategy was non-adaptive, in the sense that I never used the information gained from submitting one exam to decide my questions for the next exam. I could have just submitted my 24 exams in any order and then studied them to get my answers. One can in theory make more powerful strategies by using adaptive strategies, by using information you gain along the way to adjust what you are doing, but then the strategy tree is way harder to figure out, because it in theoretically very large.
Bulls And Cows
I suspect that there might be only finitely many logic puzzles in the universe that I find interesting, because they seem to be running out at an alarming rate. Anyway, Tanya Khovanova had an interesting one a few weeks back that I might as well put here:
Naturally one can generalize this puzzle to Q questions and N attempts at the test. This game is actually just mastermind with two colours. One important simpler case is 5 questions, 4 attempts, I say that case is important because you can use it to solve this one of Q=30, N=24.
Tanya actually did a very nice explanation of the answer and some side calculations, when I post my answer I will basically just be copying what she wrote, but I like having an archive of stuff I find interesting, so I want this puzzle to be posted here.
A test consists of 30 true or false questions. Victor will take the test but starts off having no idea what any answers are. After taking the test, Victor gets his score: the number of correct answers. He is allowed to re-take the same test several times. Can Victor work out a strategy that guarantees that he can figure out all the answers after the 24th attempt?Note that Victor does not need to get everything right on the 24th attempt, just that he needs to know all the correct answers (so that on a 25th take, he would get them all right).
Naturally one can generalize this puzzle to Q questions and N attempts at the test. This game is actually just mastermind with two colours. One important simpler case is 5 questions, 4 attempts, I say that case is important because you can use it to solve this one of Q=30, N=24.
Tanya actually did a very nice explanation of the answer and some side calculations, when I post my answer I will basically just be copying what she wrote, but I like having an archive of stuff I find interesting, so I want this puzzle to be posted here.
Same As Before
Ok, time to solve out the weighing medals problem from last time.
First, its easy to see that the gold medal will never be on the scale, there is nothing to balance it against, so we might as well throw it away and if we can't find the fake in the others then the fake was the gold medal. Next, note that we can't leave all the silvers off the first weighing, because then they must all go on the second weighing (since the gold is never being weighed, we must weigh everything else at least once or we can't find the fake) and there is no way to divide up the 3 silvers into two piles. Similarly, we must put at least one bronze on the first weighing.
It makes the most sense to weigh 2 bronze and 1 silver against 2 bronze and 1 silver for our first one, this way, if one side is heavy we have immediately identified 2 bronze and 1 silver as the "suspect group". We can use our second measurement to weigh the two suspect bronze against eachother and figure our which of the three medals is the fake.
If our first measurement comes out balanced, we have the gold, 1 bronze, and 1 silver as our suspect group. We put the suspect bronze with a genuine silver on the left against the suspect silver and a genuine bronze. Now 'left heavy' 'right heavy' and 'balanced' all point to a unique medal.
This solves the problem, and as stated isn't very difficult. What I found sort of cool was if you reconsider that solution without the different types of medals. It is just the 9 coins and 2 weighings problem and you start by weighing 3 vs 3 to get a suspect group of size 3. Of course, if the solution to the different medals problem is to work for arbitrary values of masses of genuine medals mbronze, msilver, mgold, then it must work in the particular case where all those m's are equal (I suppose this isn't true if your solution divided by mbronze-msilver or something, but we aren't doing that).
Anyway, thats all I got.
First, its easy to see that the gold medal will never be on the scale, there is nothing to balance it against, so we might as well throw it away and if we can't find the fake in the others then the fake was the gold medal. Next, note that we can't leave all the silvers off the first weighing, because then they must all go on the second weighing (since the gold is never being weighed, we must weigh everything else at least once or we can't find the fake) and there is no way to divide up the 3 silvers into two piles. Similarly, we must put at least one bronze on the first weighing.
It makes the most sense to weigh 2 bronze and 1 silver against 2 bronze and 1 silver for our first one, this way, if one side is heavy we have immediately identified 2 bronze and 1 silver as the "suspect group". We can use our second measurement to weigh the two suspect bronze against eachother and figure our which of the three medals is the fake.
If our first measurement comes out balanced, we have the gold, 1 bronze, and 1 silver as our suspect group. We put the suspect bronze with a genuine silver on the left against the suspect silver and a genuine bronze. Now 'left heavy' 'right heavy' and 'balanced' all point to a unique medal.
This solves the problem, and as stated isn't very difficult. What I found sort of cool was if you reconsider that solution without the different types of medals. It is just the 9 coins and 2 weighings problem and you start by weighing 3 vs 3 to get a suspect group of size 3. Of course, if the solution to the different medals problem is to work for arbitrary values of masses of genuine medals mbronze, msilver, mgold, then it must work in the particular case where all those m's are equal (I suppose this isn't true if your solution divided by mbronze-msilver or something, but we aren't doing that).
Anyway, thats all I got.
Weighing Medals
Almost a new year already, apparently I didn't do quite as much blogging this year, as I usually get about 40 posts a year and this year I only have about 30. I choose to blame it on my thesis rather than on my general laziness.
Anyway, I found a new puzzle over at Tanya Khovanovas Math Blog that I thought was sort of neat:
Standard balance scale rules, of course. The balance scale can be envisioned as having two places to put stuff, and then you push a button and it will tell you either "left side heavy", "right side heavy", or "balanced". The button will only work two times and then the scale will break.
Its actually a pretty simple puzzle if you have done the other balance scale problems, it only took me a few minutes to get it, but I somehow was very satisfied with the answer.
Anyway, I found a new puzzle over at Tanya Khovanovas Math Blog that I thought was sort of neat:
There is a collection of medals and one of them is known to be fake. There is 1 gold medal, 3 silver medals, and 5 bronze medals. A fake medal weighs slightly less than the corresponding real medal. All real medals of the same type weigh the same amount, but medals of differing types might not weigh the same amount. Using a balance scale and two weighings, find a strategy that is guaranteed to identify the fake medal.
Standard balance scale rules, of course. The balance scale can be envisioned as having two places to put stuff, and then you push a button and it will tell you either "left side heavy", "right side heavy", or "balanced". The button will only work two times and then the scale will break.
Its actually a pretty simple puzzle if you have done the other balance scale problems, it only took me a few minutes to get it, but I somehow was very satisfied with the answer.
Finding Coins
Alright, time to finish off the envelope puzzle from last time. This post is going to wind up getting into Bayes' theorem, which has never come up before in my blogging, to my surprise. I suppose I might as well also give a little proof and statment of Bayes' theorem while I'm at it, since its sort of cool.
First though, I want to explicitly demonstrate the solution to the follow-up problem of last time, then I will give a more general derivation using Bayes' theorem. The first thing to remember here, and the general theme of this post actually, is that Bob gained information when he selected a random envelope and found a coin. The explicit two envelope solution of last time served as a good example of this, but it is important enough that I want it stated explicitly. When Bob found a coin in a random envelope, he has to reevaluate his stance on how Alice put coins in envelopes. At first he thought it was 50-50 of zero or two coins, but after finding one, he knew there were two and not zero.
So, I'm going to just give the answer to the follow-up puzzle and then show that it is, in fact, an answer (I will later show that it is 'the' answer). It is for N=4 the scenario is consistent. Before opening an envelope, the cases k=0,1,2,3,4 are all equally likely, and so the expectation of a random envelope is 1/5(0/4)+1/5(1/4)+1/5(2/4)+1/5(3/4)+1/5(4/4)=1/2. A random envelope is worth $1/2, not very surprising. Next, when Bob finds a coin, he knows that k=0 is impossible, and if k had been 1 there would have been only a 1/4 chance of finding a coin, while if k was 4 he was certian, thus it is 4 times more likely that k=4 than k=1. Thus, Bob thinks the values k=0,1,2,3,4 have the relative likleyhoods of 0:1:2:3:4, meaning k=0 has probablity 0, k=1 probablity 1/10, k=2 probability 2/10, k=3 probability 3/10 and k=4 probability 4/10. for a given k, now that a coin has been removed, the expectation value of an envelope is (k-1)/4, so a random envelope now has expectation value 0/4(1/10)+1/4(2/10)+2/4(3/10)+3/4(4/10)=1/2. So we can see N=4 is a solution.
To prove N=4 is the only solution, and to sort of derive it in the first place, we need Bayes' theorem. Suppose we have some an experiment that we are doing, and there are events that can occur, call the events A,B,C... and so on. Now, We can talk about the probabilty of an event A, we call that P(A), and we can talk about the probabilty of an event A given that some other event B has occured, we call that P(A|B). We can of course talk about the probablity that both A and B occur, P(A and B) and such things. It can be seen that the probabilty that both A and B occur is equal to the probabilty that A occurs times the probabilty that B occurs given that A already occured, so we can say:
Of course I could switch A and B in that statement to get:
Giving us that
This last line is the statement of Bayes' Theorem.
So, this theorem can be used to tell us how likely is was that 'Alice put k coins in the envelopes' given that 'Bob found one at random' as long as we can calculate the chance that 'Bob found one at random' given that 'Alice put k coins in the envelopes'. That second one sounds pretty easy to calculate. This is the use of Bayes' theorem, it allows us to switch the order of conditionals which can often make it easier to calculate.
In most practical cases, we have a list of mutually exclusive events Ai and another list of mutually exclusive events Bi such that exactly one Ai and one Bi must occur. Of course, for particular i and j, we can read off Bayes' theorem as:
and to find P(Bj) we can find P(Bj|Ak) for each k and then multiply by P(Ak) and sum over k. Essentially we can see that in this case the denominator is serving as a normalizing constant (constant for each choice of j, that is) and that summing both sides of that last equation with resepct to i will give 1 (since exactly one of the Ai must happen).
Now lets try to use Bayes' theorem to solve the follow-up problem. Alice has N envelopes, placed coins in k of them, Bob found a coin. So for our purposes let the event Ai be 'Alice placed coins in exactly i envelopes', and the events B0 and B1 are 'Bob didn't find a coin' and 'Bob found a coin', respectively. So we have
P(B1|Ai) is easy, its i/N, and P(Ai) is just 1/(N+1). P(B1), the chance Bob found a coin, is the numerator summed over i, it is Σ i/(N(N+1)), which is just 1/2. So we have
Now, what is the expectation value of an envelope given that Bob found and then removed a coin? It is
Which is the chance of finding one of the remaining i-1 coins time the chance there were i coins (given that Bob found one) summed over i. We can rewrite this as
That sum evaluates to N3/3-N/3, so we now have
as the expectation value of a random envelope given that Bob has found a coin. If we set this to 1/2 we get N=4. Somewhat interesting is that in the limit of large N this tends to 2/3, so which is the statement that Bob pushes his expectation of a random envelope upward quite a bit if he found a coin, when N is large the act of removing one is pretty harmless, he probably won't pick that envelope again anyway.
Alright, that was fun, and in my mind was the end of the puzzle, however, in the comments of the initial post somebody showed me that you can classify all the solutions to the puzzle, so lets do that now (because its actually really cool).
First, note that the list of probabilites P(Ai) completely specifies Alices strategy. Once she has placed coins in the envelopes and shuffles them, the only information that matters is how many envelopes have coins in them. She can use whatever method she wants to place coins, but she might as well just whisper to Bob the list P(Ai), that is the only thing that matters. Alright, so we have already seen that
P(B1|Ai) is still i/N, but now P(Ai) is encapsulating Alices strategy. P(B1) is still the sum of the numerator, that is
Actually, thats the average value of the number of envelopes that Alice put coins in divided by N (sort of obviously), we will call this K/N.
So we have
Alright, after having found a coin, the expectation value of a random envelope is now (i-1)/N times the chance there are i coins, summed over i, so that is
If we want this to be equal to the expectation of an envelope before Bob selected one the first time, we must set this equal to K/N, meaning we now have
That second term on the right is just K and the first term on the right is the expectation of the number of coins in envelopes, squared. Some rearranging gives us
The right side is the expectation of coins squared minus the expectation of coins, squared. This is the standard deviation of Alices strategy squared. So a strategy for Alice is a solution to this puzzle if and only if: the expectation value of the number of coins Alice places in envelopes is equal to the standard deviation squared of the number of coins Alice places in envelopes. Neat.
You can confirm explicitly that the 50-50, 0,2 strategy and the 0,1,2,3,4 strategy both have this feature. Anyway, thats basically it for this.
First though, I want to explicitly demonstrate the solution to the follow-up problem of last time, then I will give a more general derivation using Bayes' theorem. The first thing to remember here, and the general theme of this post actually, is that Bob gained information when he selected a random envelope and found a coin. The explicit two envelope solution of last time served as a good example of this, but it is important enough that I want it stated explicitly. When Bob found a coin in a random envelope, he has to reevaluate his stance on how Alice put coins in envelopes. At first he thought it was 50-50 of zero or two coins, but after finding one, he knew there were two and not zero.
So, I'm going to just give the answer to the follow-up puzzle and then show that it is, in fact, an answer (I will later show that it is 'the' answer). It is for N=4 the scenario is consistent. Before opening an envelope, the cases k=0,1,2,3,4 are all equally likely, and so the expectation of a random envelope is 1/5(0/4)+1/5(1/4)+1/5(2/4)+1/5(3/4)+1/5(4/4)=1/2. A random envelope is worth $1/2, not very surprising. Next, when Bob finds a coin, he knows that k=0 is impossible, and if k had been 1 there would have been only a 1/4 chance of finding a coin, while if k was 4 he was certian, thus it is 4 times more likely that k=4 than k=1. Thus, Bob thinks the values k=0,1,2,3,4 have the relative likleyhoods of 0:1:2:3:4, meaning k=0 has probablity 0, k=1 probablity 1/10, k=2 probability 2/10, k=3 probability 3/10 and k=4 probability 4/10. for a given k, now that a coin has been removed, the expectation value of an envelope is (k-1)/4, so a random envelope now has expectation value 0/4(1/10)+1/4(2/10)+2/4(3/10)+3/4(4/10)=1/2. So we can see N=4 is a solution.
To prove N=4 is the only solution, and to sort of derive it in the first place, we need Bayes' theorem. Suppose we have some an experiment that we are doing, and there are events that can occur, call the events A,B,C... and so on. Now, We can talk about the probabilty of an event A, we call that P(A), and we can talk about the probabilty of an event A given that some other event B has occured, we call that P(A|B). We can of course talk about the probablity that both A and B occur, P(A and B) and such things. It can be seen that the probabilty that both A and B occur is equal to the probabilty that A occurs times the probabilty that B occurs given that A already occured, so we can say:
P(A and B)=P(A)P(B|A)
Of course I could switch A and B in that statement to get:
P(A and B)=P(B)P(A|B)
Giving us that
P(A|B)P(B)=P(B|A)P(A)
P(A|B)=P(B|A)P(A)/P(B)
This last line is the statement of Bayes' Theorem.
So, this theorem can be used to tell us how likely is was that 'Alice put k coins in the envelopes' given that 'Bob found one at random' as long as we can calculate the chance that 'Bob found one at random' given that 'Alice put k coins in the envelopes'. That second one sounds pretty easy to calculate. This is the use of Bayes' theorem, it allows us to switch the order of conditionals which can often make it easier to calculate.
In most practical cases, we have a list of mutually exclusive events Ai and another list of mutually exclusive events Bi such that exactly one Ai and one Bi must occur. Of course, for particular i and j, we can read off Bayes' theorem as:
P(Ai|Bj)=P(Bj|Ai)P(Ai)/P(Bj)
and to find P(Bj) we can find P(Bj|Ak) for each k and then multiply by P(Ak) and sum over k. Essentially we can see that in this case the denominator is serving as a normalizing constant (constant for each choice of j, that is) and that summing both sides of that last equation with resepct to i will give 1 (since exactly one of the Ai must happen).
Now lets try to use Bayes' theorem to solve the follow-up problem. Alice has N envelopes, placed coins in k of them, Bob found a coin. So for our purposes let the event Ai be 'Alice placed coins in exactly i envelopes', and the events B0 and B1 are 'Bob didn't find a coin' and 'Bob found a coin', respectively. So we have
P(Ai|B1)=P(B1|Ai)P(Ai)/P(B1)
P(B1|Ai) is easy, its i/N, and P(Ai) is just 1/(N+1). P(B1), the chance Bob found a coin, is the numerator summed over i, it is Σ i/(N(N+1)), which is just 1/2. So we have
P(Ai|B1)=2i/(N(N+1))
Now, what is the expectation value of an envelope given that Bob found and then removed a coin? It is
Σ (i-1)/N 2i/(N(N+1))
Which is the chance of finding one of the remaining i-1 coins time the chance there were i coins (given that Bob found one) summed over i. We can rewrite this as
2/(N2(N+1))Σ (i2-i)
That sum evaluates to N3/3-N/3, so we now have
2(N-1)/3N
as the expectation value of a random envelope given that Bob has found a coin. If we set this to 1/2 we get N=4. Somewhat interesting is that in the limit of large N this tends to 2/3, so which is the statement that Bob pushes his expectation of a random envelope upward quite a bit if he found a coin, when N is large the act of removing one is pretty harmless, he probably won't pick that envelope again anyway.
Alright, that was fun, and in my mind was the end of the puzzle, however, in the comments of the initial post somebody showed me that you can classify all the solutions to the puzzle, so lets do that now (because its actually really cool).
First, note that the list of probabilites P(Ai) completely specifies Alices strategy. Once she has placed coins in the envelopes and shuffles them, the only information that matters is how many envelopes have coins in them. She can use whatever method she wants to place coins, but she might as well just whisper to Bob the list P(Ai), that is the only thing that matters. Alright, so we have already seen that
P(Ai|B1)=P(B1|Ai)P(Ai)/P(B1)
P(B1|Ai) is still i/N, but now P(Ai) is encapsulating Alices strategy. P(B1) is still the sum of the numerator, that is
P(B1)=Σ i/N P(Ai)
Actually, thats the average value of the number of envelopes that Alice put coins in divided by N (sort of obviously), we will call this K/N.
So we have
P(Ai|B1)=i P(Ai)/K
Alright, after having found a coin, the expectation value of a random envelope is now (i-1)/N times the chance there are i coins, summed over i, so that is
Σ (i-1) i P(Ai)/(K N)
If we want this to be equal to the expectation of an envelope before Bob selected one the first time, we must set this equal to K/N, meaning we now have
K2=Σ (i-1) i P(Ai)
=Σ i2 P(Ai) - Σ i P(Ai)
That second term on the right is just K and the first term on the right is the expectation of the number of coins in envelopes, squared. Some rearranging gives us
K=Σ i2 P(Ai)-K2
The right side is the expectation of coins squared minus the expectation of coins, squared. This is the standard deviation of Alices strategy squared. So a strategy for Alice is a solution to this puzzle if and only if: the expectation value of the number of coins Alice places in envelopes is equal to the standard deviation squared of the number of coins Alice places in envelopes. Neat.
You can confirm explicitly that the 50-50, 0,2 strategy and the 0,1,2,3,4 strategy both have this feature. Anyway, thats basically it for this.
Half And Half
So, I wasn't sure if I should put up a complete solution to the envelope puzzle from last time or just post a partial solution and have follow-up questions, but I have since decided on the latter.
Anyway, a solution to the puzzle (which was also given in the comments, but was my "intended easy solution") is: Alice has two envelopes and flips a coin, filling both envelopes with coins on heads and neither of them on tails. With this, the expected value of a random envelope is $1/2. After Bob finds a removes a coin he knows for a fact the other envelope has a coin, so the expected value of an envelope is again $1/2.
Next a follow-up problem:
Anyway, a solution to the puzzle (which was also given in the comments, but was my "intended easy solution") is: Alice has two envelopes and flips a coin, filling both envelopes with coins on heads and neither of them on tails. With this, the expected value of a random envelope is $1/2. After Bob finds a removes a coin he knows for a fact the other envelope has a coin, so the expected value of an envelope is again $1/2.
Next a follow-up problem:
Suppose instead of Alice whispering her strategy, you overheard her say "I selected an integer k from 0 to N uniformly at random and placed coins in k of the envelopes." What is the value of N so that the scenario is possible?Its funny how our brains can work, I was again convinced that this was just impossible, even after knowing the earlier answer, but there is a way to solve this. It even has a unique answer.
Subscribe to:
Posts (Atom)
