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:

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:

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 A_i and another list of mutually exclusive events B_i such that exactly one A_i and one B_i must occur. Of course, for particular i and j, we can read off Bayes' theorem as:

P(A_i|B_j)=P(B_j|A_i)P(A_i)/P(B_j)

and to find P(B_j) we can find P(B_j|A_k) for each k and then multiply by P(A_k) 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 A_i 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 A_i be 'Alice placed coins in exactly i envelopes', and the events B₀ and B₁ are 'Bob didn't find a coin' and 'Bob found a coin', respectively. So we have

P(A_i|B₁)=P(B₁|A_i)P(A_i)/P(B₁)

P(B₁|A_i) is easy, its i/N, and P(A_i) is just 1/(N+1). P(B₁), 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(A_i|B₁)=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/(N²(N+1))Σ (i²-i)

That sum evaluates to N³/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(A_i) 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(A_i), that is the only thing that matters. Alright, so we have already seen that

P(A_i|B₁)=P(B₁|A_i)P(A_i)/P(B₁)

P(B₁|A_i) is still i/N, but now P(A_i) is encapsulating Alices strategy. P(B₁) is still the sum of the numerator, that is

P(B₁)=Σ i/N P(A_i)

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(A_i|B₁)=i P(A_i)/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(A_i)/(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

K²=Σ (i-1) i P(A_i)
=Σ i² P(A_i) - Σ i P(A_i)

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=Σ i² P(A_i)-K²

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:

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.