Triangular Hypermarbles

Due to some discussion in the solution to the breaking marbles puzzle, I have decided to make a post of the extension problem. Now let us suppose we have K marbles and N floors, what is the minimum number of moves it takes to find the critical floor, assuming you are minimizing the worst case scenario.

For some definiteness, we will assume that if you eliminate all the floors but the end one, you must still check the end one. This is so that, say, in the 2 marble 3 floor case, you can do it in 2 steps optimally by checking floor 2, then checking floor 3 if it does not break, and checking floor 1 if it does (specifically you cannot just assume that if it didn't break on floor 2 it will then break on 3, and that if it broke on floor 2 it can't break on floor 1). The reason for this "handling of the endpoints" is so that in the two marble case, you cannot do better than Triangle(M) floors with M steps. Triangle(M), the M^th triangle number, will be denoted T_M, and is given by M(M+1)/2.

Now, lets try the 3 marble case. Let us suppose we have N floors, and we have a solution that works in never more than 5 steps (I'll generalize 5 to M later). Then with our first move, we might as well go to floor 11. If we go any higher, then if it breaks we cannot solve the remaining case with over 10 floors with only 2 marbles and 4 steps (2 marbles, 4 steps, 10 floors is optimal), and nothing is to be gained by going any lower. Next, we move 7 more floors, since if it breaks we can solve through the 6 we skipped with 2 marbles and 3 steps. Next, we will move up another 4 floors, so that if it breaks, there are 3 floors unchecked which we do can with the remaining 2 steps and 2 marbles. Next up 2 more floors, because we will only have 1 step left (now steps is more limiting than marbles, one gets the impression that when you have at least as many steps as you have marbles, binary search will be best). And finally we get 1 last step.

The result is 11+7+4+2+1=25 (looks like powers of 2 at the end, neat), this is better written as 10+1+6+1+3+1+1+1+0+1, that is T₄+1+T₃+1+T₂+1+T₁+1+T₀+1. Which is the same as P₄+4+1 (P_K is the K^th pyramidal number, the sum of the first K triangle numbers). The general statement, which is easy enough to verify by induction, is that with 3 marbles and M steps, you can do at most P_M-1+M floors. We will denote this as F(3,M), the maximum you can do with 3 marbles in M steps.

We already know that

F(1,M)=M
F(2,M)=T_M=M(M+1)/2

And now we know

F(3,M)=P_M-1+M
=(M-1)M(M+1)/6+M
=(M²+5)*M/6

The formula P_M=M*(M+1)*(M+2)/6 can be found either by induction or by realizing the connection between Pascal's triangle and the generalized triangle numbers (more on that in a moment).

Next we want to try 4 marbles. With M steps, we cannot go higher than F(3,M-1)+1 for our first step, and there is no sense in going lower. We then move up another F(3,M-2)+1 steps and so on until we are out of moves. The result is that

F(4,M)=Σ F(3,M-i)+M

The sum being i from 1 to M-1. This argument will hold quite generally, to get the result of

F(N,M)=Σ F(N-1,i)+M

i now being summed from 1 to M-1, or if we define F(N,0)=0 (the most number of floors you can do with N marbles and zero steps) we can start i from 0.

Before going further into F, I would like to consider another function. Let us define the "hypertriangular numbers" H(N,M) so that each one is the sum of the first M previous ones. Specifically,

H(0,M)=1
H(N,M)=Σ H(N-1,i)

i being summed from 0 to M-1. These generalize the triangle numbers cleanly, H(1,M)=M+1, H(2,M)=T_M+1, H(3,M)=P_M+1. One can easily confirm that

H(N,M)=H(N-1,M)+H(N,M-1)
H(N,0)=1
H(0,M)=1

So these numbers basically form up Pascal's triangle, so that

H(N,M)=(N+M)!/(N!M!)

Note that in the definition, N and M were not symmetric, but in the end they are.

I'll come back to that function later, but the connection between hypertriangle numbers and Pascal's triangle will be important in a bit. Recall F's recursion relation is:

F(0,M)=0
F(N,0)=0
F(N,M)=Σ F(N-1,i)+M

(i summed from 0 to M-1). One can start filling this in, its slightly illustrative to do this. Labeling x-axis as M value and y-axis as N value, we get (apologies for formatting issues):

0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 1 3 6 10 15
0 1 3 7 14 25
0 1 3 7 15 30
0 1 3 7 15
0 1 3 7
0 1 3 7

and so on. Each number is the sum of the numbers in the row above it from 0 to M-1 and then adds the number M. This results in the first non-zero row coming up just as M, the second row comes up as triangle numbers, but then the third row comes up funny. Note that when N gets bigger than M, the numbers just turn into 2^M-1, somewhat demonstrating the fact that having more marbles than steps means the marbles breaking isn't an issue, and then you get the result of a binary search.

One can construct Pascal's triangle in a similar way, starting with 1's and letting each element be the sum of the row above it, from that one can prove the relation H(N,M)=H(N-1,M)+H(N,M-1) (I'm going to start calling this the Pascal relation). In this case, one can find by inspection of the graph that F will obey a similar linear relation:

F(N,M)=F(N-1,M)+F(N,M-1)-F(N-2,M-1)

It isn't exactly clear to me how to prove this formally, but I am confident in it. You should confirm for yourself that it is true, it is somewhat pivotal. Anyway, we now have a semi-Pascal relation that F obeys, and now our relation is linear in F. At this point, I asked myself, "what would Matt do?" and got the only obvious answer, define the derivative function:

D(N,M)=F(N,M)-F(N-1,M)

I suppose its the derivative with respect to N, but its one nonetheless.

Using our semi-Pascal relation on F, we can find a similar one on D, rewrite the F one as:

F(N,M)-F(N-1,M)=F(N,M-1)-F(N-2,M-1)
=F(N,M-1)-F(N-1,M-1)+F(N-1,M-1)-F(N-2,M-1)
=> D(N,M)=D(N,M-1)+D(N-1,M-1)

This is almost a Pascal relation on D, but things are shifted over slightly, to fix this we will define a new function K according to

K(N,L)=D(N,N+L)
K(N,M-N)=D(N,M)

I'm really just defining L=M-N and considering a function of N,L rather than N,M (this is logical, since D sort of "breaks down" if N>M, thats were F stopped varying). Anyway, from D's relation, we can find that K obeys the relation:

K(N,M-N)=K(N,M-N-1)+K(N-1,M-N)
K(N,L)=K(N,L-1)+K(N-1,L)

Hurrah, K obeys the Pascal relation, now we need to find its boundary conditions. Trying to check K(0,L) immediately causes problems involving D(-1,L), so lets try K(1,L)

K(1,L)=D(1,L+1)=F(1,L+1)-F(0,L+1)
=L+1

Good, next lets check K(N,0)

K(N,0)=D(N,N)=F(N,N)-F(N-1,N)

Uh oh, this could put a stop to all of our fun right here. Fortunately, we can handle this, it turns out (one can inspect the chart) that F(N,N)-F(N-1,N)=1. We can prove this using the earlier recursion relation for F to show that

F(N,N)=F(N-1,N)+F(N,N-1)+F(N-2,N-1)
F(N,N)-F(N-1,N)=F(N,N-1)+F(N-2,N-1)

Next, we must handle F(N,N-1) by considering the "physics" of the problem. Consider F(N,M) when N>M, so you have more marbles than you have steps remaining. In this case, the extra marbles are irrelevant, so you can just ignore their existence, F(N,M)=F(M,M) when N>M. This is also present in the table of F. Thus we have F(N,N-1)=F(N-1,N-1), therefore

F(N,N)-F(N-1,N)=F(N-1,N-1)+F(N-2,N-1)

So apparently F(N,N)-F(N-1,N) is constant in N (shifting N by 1 has no effect, so shifting it by 100 won't either). Evaluating when N=1 gives us

F(N,N)-F(N-1,N)=F(1,1)-F(0,1)=1-0=1

Proving that K(N,0)=1.

Ok, current data on K:

K(N,L)=K(N,L-1)+K(N-1,L)
K(1,L)=L+1
K(N,0)=1

We can extend K to K(0,L) using its Pascal relation on N=1:

K(1,L)=K(1,L-1)+K(0,L)
L+1=L+K(0,L)

Demonstrating that it is consistent to take K(0,L)=1. so, K has the same initial conditions as H (the hypertriangle function) and the same Pascal relation, so K=H must be the case.

K(N,M)=(N+M)!/(N!M!)

Now we can find D as D(N,M)=K(N,M-N)

D(N,M)=M!(N!(M-N)!)

So it seems D is just M choose N, naturally if N>M then D(N,M)=0.

Finally we are ready to construct F. D was the "derivative" of F, so F is the "integral" of D. Specifically,

F(N,M)-F(0,M)=Σ D(i,M)

The sum running i from 1 to N. We know F(0,M)=0, and D(N,M) is zero if N>M, and so we have

F(N,M)=Σ M!/((M-i)! i!)

Summing i from 1 to min(N,M). Note that the summation starts at 1, where a typical summation over choose functions would start at 0.

So when N is less than M, F(N,M) is the sum of the first N elements in the M^th row of Pascal's triangle, minus 1. In words, one can consider a set of M elements and ask how many nonempty subsets with at most N elements are there. I'm not sure if there is a clean form for that.

Finally, if N>M, F(N,M)=F(M,M), the number of nonempty subsets of size at most M in the set of M elements. A set with M elements has 2^M subsets, and one of those is the empty set. So, F(M,M)=2^M-1, as one would expect from a binary search solution.

This completes the solution for how many floors you can cover with N marbles in M steps. If somebody asked your the reverse (and more standard) problem of solving K floors with N marbles, you simply look for the minimal value of M such that F(N,M)>K, and that gives you the worst case M.

Invisible Ants

Time for the solution to the ants on a line problem. The solution is actually stupidly simple, it really just is about one realization: Two pointlike ants bouncing off eachother is identical to two pointlike ants passing through eachother. At this point, you can easily see that there theoretical maximum is that you have an ant right on the left end initially walking to the right. No matter how the other ants are distributed, it will take exactly 100s for the last ant to fall off.

Pretty dumb puzzle, to be honest, but I thought it was a bit of a cute trick.

Ants On A Line

New puzzle time, though this one is a bit strange. I first heard it somewhere random on the blagosphere:

You have a one dimensional meterstick that you distribute 100 pointlike ants on, at random locations. Each ant will select randomly to begin walking right or left, and keep walking that direction at until it bumps into another ant. If two ants bump into eachother, they will each turn around and go the other direction. If an ant reaches the end of the meterstick, it will fall off. The ants have a constant speed of 1 cm/s. Given enough time, eventually all of the ants will fall off the stick, and for different initial distributions and choices of initial directions this will take a varying amount of time. What is the theoretical maximum length of time it will take for all the ants to fall of the stick?

So, find the distribution and set of left/right choices that maximizes the time the ants spend on the stick. Or the class of distributions, I suppose, no guarantee that it is unique.

Gambling Solution

Time to solve the gambling puzzle from last time. When I told this problem to Matt, his immediate reaction (which I found rather amusing) was to say "OK....hmm, what would Kory do?................. ah yes, consider a simpler case." That seems to be the right approach, so lets assume that the frungy tournament is best or 3, first team to 2 games wins.

We already know that we should not bet all $400 on Blue in the first game, because then Red might win the first game and suddenly we are out of money. Blue then might go on to win the tournament and we are in trouble. Taking the other extreme strategy of not betting on the first game at all, if Blue wins the game, we have no choice but to bet everything on Blue now (else if Blue wins again we are done). But now if Red wins we are out of money for the final game (which, if we are unlucky, Blue will win).

The next obvious thing is to take the middle ground and bet $200 on Blue in the first game. Now if Blue loses we have $200 left and Red is up 1-0. Since Red winning again is auto-victory for us anyway we might as well bet everything we have left on Blue. If Blue wins now we have $400 and they are tied 1-1. At this point it is simple. OK, instead suppose Blue wins the first game, now we have $600 and Blue is up 1-0. We need only bet $200 on Blue this next game, so that if they win we end with $800, so now if they lose we have $400 left and the teams are 1-1 again. Good, this is a full solution, it is also nice to see that it is 100%, rather than just a probabilistic solution.

A few things to notice about that solution. First of all, we never ended with any excess money, in all strategies we came out with exactly $800. Another thing is that the result was "path independent", that is, no matter if Blue won first or Red won first if the game got to being tied at 1-1 it did not matter how we got there, we had exactly $400. Both of these facts are general about the full solution (assuming it is a 100% solution, that is).

First of all, the "no excess money" result. Let us begin by supposing that we have a full strategy for how to bet in the games as the tournament progresses. Note that every game is a bet on a coin flip, therefore no matter what your planned strategy is you will have an expectation of $400 after each game. The side bet is an even chance split of $800 and $0, so it has an expectation of $400. Thus, at the end of the week, no matter your strategy, you have an expected final amount of money equal to $800. If there is any possible path through the game tree that ends with more than $800, there is also a path through the game tree with less than $800, so no solution that works 100% of the time can ever end with excess money.

Now for the "path independent" result. Suppose we have a betting strategy for the whole week. Further suppose there was a node in the game tree (for example, Red is up 3-1 on Blue) that depending on how you got there you will have different amounts of money (so for one path you have $x, and for the other you have $y). Assuming x>y then if we get there with $x, we can simply throw away $(x-y) to leave ourselves with $y and still have a planned out strategy for the rest of the game. This strategy will apparently have had excess money, which we know is impossible.

Alright, we are almost ready to make the full solution. The final step is that if your strategy knows how much money it has at each step, you know how much you need to bet. So if you know you have $400 now and if Blue wins you need to have $600, but if Red wins you need to have $200, the it is time to bet $200 on Blue. We will describe a strategy as a chart of the amount of money we need at each step in the game tree. Consider the tree for the three game case as follows (This is going to format like crap, but it will be readable):

AAA BBB
CCC DDD

OK, AAA represents the amount of money we start with (so, 400), BBB is the amount of money we have if Red is up 1-0, CCC is the amount of money we have if Blue is up 1-0 and DDD is the amount of money we have if the game is tied 1-1. So, my notation is that if Red wins we move a step right, if Blue wins we take a step down.

We know that if Blue wins two games we must have exactly 800, and if Red wins we must have exactly 0 (no excess money), so we can add those values in:

AAA BBB 0
CCC DDD 0
800 800

Now, we know that DDD must be exactly 400, there is no other amount of money it can be that will be consistent with this. But then we know that CCC is 600, and BBB is 200. Finally we get that AAA is 400, which is really just a consistency check.

You can now easily see the general answer, but lets just go through it anyway, for the full 7 game case we have:

AAA BBB CCC DDD 0
EEE FFF GGG HHH 0
KKK LLL NNN PPP 0
QQQ RRR SSS TTT 0
800 800 800 800

Great, we can now see that TTT is 400, PPP is 200, HHH is 100 and DDD is 50. Also we get that SSS is 600, RRR is 700 and QQQ is 750. Sort of a neat symmetry here:

AAA BBB CCC 050 0
EEE FFF GGG 100 0
KKK LLL NNN 200 0
750 700 600 400 0
800 800 800 800

Its simple enough to continue filling this all in now:

400 275 150 050 0
525 400 250 100 0
650 550 400 200 0
750 700 600 400 0
800 800 800 800

So, apparently the correct solution begins with placing a $125 bet on Blue in the first game.

Gambling Puzzle

I suppose I could have titled this one "gambling problem", but that carries all sorts of other implications that we won't bother with here. Anyway, this puzzle I first learned on the forums at xkcd:

Alex has decided to start a widget company with his $800 savings. He has put in an order for a widget machine that will be delivered next week and will cost him $800, to be paid on delivery. However, when he went back to check on his money he found out that last night, in a drunken stupor, he placed a $400 bet on Red in the upcoming Red vs. Blue Frungy tournament.

A Frungy tournament is a seven game tournament, one game played each day, and the first team to win 4 games wins the tournament. Red and Blue are equally skilled teams, and each game is 50-50 between them (and there are no ties in Frungy). Alex decided to go to the betting office to simply bet his remaining $400 on Blue so that they would cancel and he would be guaranteed to get back his $800 at the end of the week, but he has found out that that part of the betting is closed, now he can only bet on the individual games each morning.

Each morning, Alex may place as much money as he likes on an even bet for either Red or Blue. The bet is resolved that evening, and he will receive any winnings before the next day. Find a betting strategy that guarantees that Alex will end the week with at least $800 so he can make the payment for his widget machine.

Assuming that all made sense through the "theme", you basically have to guarantee that if Blue wins 4 games, you have made at least $800 from your bets. If Red wins 4 games, then your side bet kicks in and you are safe no matter what.

Alex would just like to bet all $400 on Blue in the first game, but Blue might lose the first game and then go on to win the tournament. Find a strategy that maximizes the probability of ending the week with at least $800.