Balls In Boxes

New puzzle o'clock! I should probably be working instead of blogging, but blogging is so much more fun. Anyway, I found something of a neat puzzle on the Putnam 2010 exam. Usually those exams are just filled with semi-impossible math problems involving stupid functions, but there was one question on that exam I thought was pretty cool as a puzzle:

There are 1000 boxes, labelled 1 through 1000. There are 1000*N balls in the boxes, distributed randomly between the boxes. You will be playing a 1 player game, trying to average out the balls in the boxes, so that each box has exactly N balls in it.

The only legal move in the game is to select a number K and move exactly K balls from box K into any other box. So you could go to box 247 and move exactly 247 balls from that box into any other box. If box 247 has fewer than 247 balls in it, you cannot do this, so you don't get to move any of them. You are allowed to keep making legal moves as long as you like, and you win if every box has exactly N balls in it.

Given that in total there are 1000*N balls in the 1000 boxes, for what values of N is it always possible to win, regardless of the initial configuration of the balls?

Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.

Correlated Hats

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:

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

∫F(x) F(x) f(x) dx
=∫F(x)² 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)³-1, so then we have

x(F(x)³-1)+∫(1-F(x)³) 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:

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.

Splitting Up Numbers

Time to take a break from thesis writing to blog. I won't have much time to blog for the next little while, due to said thesis, but I found a new puzzle recently I really wanted to post. I still intend to post the follow-up to my post from last time about other solutions to the birds on a wire problem, but I don't have the time to give that a full write up right now. Anyway, this puzzle is really weird to word properly, so if you don't get it the first time read the example I give after and then try reading it again. I first learned this puzzle on the forums at xkcd.

There are 2 blackboards, and on the first one a natural number N>1 is written, the second board starts empty. You are going to do a calculation in a series of steps. A step is defined as follows:

If there are no numbers greater than 1 on the first blackboard, stop. Otherwise select one of the numbers greater than 1, call it k. Select two natural numbers i and j smaller than k such that i+j=k. Cross out k from the first black board, and write i and j on the first blackboard. On the second blackboard, write the product i*j. Then do another step.

When you are done doing steps (because all the numbers on the first blackboard are equal to 1), and add up the numbers on the second blackboard, call this sum M.

The puzzle is, given the initial value of N, what are the possible values of M?

Alright, so as example, let us assume N=8. Now, we select a number of the board (there is only 8, so we choose it) and select that i and j are 5 and 3. We cross out 8 and write 5 and 3 on the first blackboard, and write 15 on the second one.

Next step we select 3, crossing it out and writing 1 and 2 on the first blackboard, writing 2 on the second blackboard. On the first board there is now (1,2,5) and on the second one there is (15,2)

Next step we select 5 and cross it out and write 2 and 3 on board one, writing 6 on board two. Board one has (1,2,2,3) board two has (15,2,6)

Next step we select 2, writing 1 and 1 in its place, and write 1 on board two. The boards are (1,1,1,2,3) and (15,2,6,1)

Next select 2, write 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,3) and (15,2,6,1,1)

Next select 3, writing 2 and 1 in its place, writing 2 on board two. The boards are (1,1,1,1,1,1,2) and (15,2,6,1,1,2)

Next select 2, writing 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,1,1,1) and (15,2,6,1,1,2,1)

Finally we stop, board one has no numbers greater than 1. We calculate M by adding up the numbers on board two, se we see M=28.

So we see that when N=8, it is possible for M to be 28. The puzzle is asking what other values of M are possible for N=8? What about other values of starting N?

Birds On A Wire

Alright, time to post the solution to the dots on a line puzzle from last time. First I suppose I'll link directly the cut-the-knot page with the puzzle. He has a cool little applet thing there you can use to simulate the problem and try to guess the solution yourself, and he also has links to where people have written up derivations, one of which I will regurgitate on here later because I found it to be so interesting.

For today though, I am simply going to post the solution to the problem as Matt and I initially solved it. First, I must solve a very simple problem that gives us a technique that will be needed later. Consider the following problem:

N numbers between 0 and 1 are selected uniformly at random. On average what is the value of the smallest one?

First, let us try to solve this for N=2. We can see that we simply must solve the integral

∫ min(x,y) dxdy

integrated over [0,1]x[0,1], and min(,) is the minimum function. Clearly min(x,y)=min(y,x) so we can instead integrate over the "lower half triangle" and double our answer. So, instead integrate x in [0,1] and y in [0,x] in

2∫ y dxdy

the 2 is because we are only covering half the area we should be covering, and min(x,y) has been replaced by y, because x>y now. The integral is pretty simple to do, and gives the answer 1/3.

Now in the general N case we must consider we have a collection of N points {x[1],x[2],x[3]...,x[N]}, and integrate

∫ min(x[1],x[2],x[3]...,x[N]) dx[1]dx[2]dx[3]...dx[N]

As before, we order them x[1]>x[2]>x[3]...>x[N], so the min function always returns x[N], and we must integrate x[1] in [0,1], x[2] in [0,x[1]], x[3] in [0,x[2]] and so on. We must also find the prefactor, which is one over the area of the triangle we are integrating. Integrating the function 1 over the region of integration, we find the prefactor must be N!. So we must integrate

N!∫ x[N]dx[1]dx[2]dx[3]...dx[N]

over our triangular region. The final answer comes out to be 1/(N+1), sort of neat, but anyway I just wanted to demonstrate the technique so it is less confusing later.

Back to the problem at hand. We have N points {x[1],x[2],x[3]...,x[N]}, and we will order them as x[1]>x[2]>x[3]...>x[N]. Let us define

d[i]=x[i]-x[i+1]

so d[i] is the size of the i^th region, and this i runs from 1 to N-1.

Next, we will define S[i] to be equal to d[i] if the i^th region is shaded, and S[i] will be zero if it is not. The answer we seek is

S=N!∫ Σ S[j] dx[i]

Integrated over all the x[i] positions, and j summed from 1 to N-1 to add up all the shaded regions.

S[i] will be nonzero (and equal to d[i]) in one of two conditions:

1) x[i+1]-x[i+2] > x[i]-x[i+1]
2) x[i-1]-x[i] > x[i]-x[i+1]

That is, if d[i+1] is greater than d[i] or if d[i-1] is greater than d[i], d[i] will get shaded in.

With calculating probabilities, whenever you have to find the chance that A or B happens, it is often easier to find the chance that neither happened and take one minus that. Similarly here, rather than integrate whenever 1) or 2) happens, it is easier to find the situation of neither of them happening. Let is define q[i] as d[i]-S[i], so q[i] represents the unshaded regions, it is equal to d[i] when S[i]=0 and it is zero when S[i]=d[i]. Clearly then

S=N!∫ Σ S[j] dx[i]
=1 - N!∫ Σ q[j] dx[i]

We can of course move the sum outside of the integral, so we simply must calculate

∫ q[j] dx[i]

for an arbitrary j and then we can sum it up and multiply by N!.

The integration has x[1] running from 0 to 1 and x[i] running from 0 to x[i-1]. q[j] is zero in some of this region and nonzero is other parts, let us identify exactly where q[j] is nonzero. It is exactly the negation of conditions 1) and 2) earlier, that is

1) x[j+2] > 2x[j+1]-x[j]
2) x[j+1] < x[j-1]-2x[j]

This actually needs to break into a few cases, the first inequality is trivial if 2x[j+1] < x[j], since x[j+2] is always positive. The second case depends on whether x[j-1] is greater than or less than 3x[j] (because if x[j-1] is more than 3 times x[j] then the second inequality is made trivial by the fact that x[j+1] < x[j]).

So the integration region over dx[j-1] until dx[j+2] breaks up into many smaller pieces that one can cleanly write out with this information, but its fairly lengthy, so I'm not going to bother here. In this region, q[j]=d[j] so you simply integrate x[j]-x[j+1] in this region. This integral is most easily done in Maple (or whatever other math program you like) by first doing the integrals from dx[N] to dx[j+3] (the function is constant there and the integration region is simple) then doing the next four integrals carefully, then finishing it off integrating to x[1].

In the end, you get a somewhat awful function of N and j. You then sum j going from 1 to N-1 and multiply by N!. You will get something somewhat less awful, but a still terrible function of N. Finally, you must take the limit of N going to infinity (this step will be easy enough to do by hand, but by this point you already have Maple open anyway, and your spirit will have been far too crushed to do such a limit) and in then end you get 11/18. This was the unshaded region (the shaded region was 1-(the integral of q[j])) so the shaded region is given by 7/18.

Next time I'll go into a bit of the analysis by the other solutions found at the cut the knot page. One of them I found to be particularly interesting so I wanted to show it in detail, but I wanted to demonstrate my own horrible method first.

Also, I expect the date on this post will be confusing, I started writing it some time ago, but it took me more than a month to get around to finishing it.