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 Mth triangle number, will be denoted TM, 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 T4+1+T3+1+T2+1+T1+1+T0+1. Which is the same as P4+4+1 (PK is the Kth 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 PM-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)=TM=M(M+1)/2
And now we know
F(3,M)=PM-1+M
=(M-1)M(M+1)/6+M
=(M2+5)*M/6
The formula PM=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)=TM+1, H(3,M)=PM+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 2M-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 Mth 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 2M subsets, and one of those is the empty set. So, F(M,M)=2M-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.
No comments:
Post a Comment