Monday, August 16, 2010

The Last Picture Show

I just got done watching The Last Picture Show. It's pretty old... 1971. The film has a lot going on, and I enjoyed it. It's a movie about two young friends in a small Texas town as they make their transition into adulthood. Anyway, the story is decent so I never did get bored or anything. This movie is where Cybill Shepherd made her film debut, and there's also a couple other famous actors in it. There's Jeff Bridges and Randy Quaid, too.

But, why did I bother posting this? Because, while watching the movie I couldn't help but think that the young Cybill Shepherd looks like Reese Witherspoon. I don't know why I keep thinking everyone looks like someone else, but it is what it is. Anyway, go watch the movie if you haven't seen it before, it's worthwhile.

Sunday, August 15, 2010

1-4-24 Simulation

So, I've written some simple simulation code for the 1-4-24 game. If you're not familiar with it, see this old post: 1-4-24 Dice Game.

Edit: I found a bug in my code, so I've updated the simulation results.
Edit #2: I found another bug in my code, and so I've updated the results again. And, added ran a couple other strategies just to see results.

I ran an initial simulation with a simple default strategy as follows:

1) Always keep 1 and 4 if you don't already have them.
2) Always keep 6 if you already have both a 1 and a 4.
3) If you didn't keep anything in the current roll (1/4/6 as per Rules #1 and #2) , then keep a single die (the highest valued one).

Score Frequency PDF CDF
Not Qualified 4324214 (4.32%) (100.00%)
4 0 (0.00%) (95.68%)
5 11 (0.00%) (95.68%)
6 143 (0.00%) (95.68%)
7 1094 (0.00%) (95.68%)
8 5670 (0.01%) (95.67%)
9 21906 (0.02%) (95.67%)
10 75295 (0.08%) (95.65%)
11 222711 (0.22%) (95.57%)
12 562945 (0.56%) (95.35%)
13 1239852 (1.24%) (94.79%)
14 2489387 (2.49%) (93.55%)
15 4420645 (4.42%) (91.06%)
16 6855657 (6.86%) (86.64%)
17 9436721 (9.44%) (79.78%)
18 11863564 (11.86%) (70.34%)
19 14150677 (14.15%) (58.48%)
20 13048294 (13.05%) (44.33%)
21 11259056 (11.26%) (31.28%)
22 8955723 (8.96%) (20.02%)
23 6549697 (6.55%) (11.07%)
24 4516738 (4.52%) (4.52%)

Here are results for a different strategy. Based on these results, it seems superior in most cases -- one case where it would not be superior is if you need only to score 15 to win (the following strategy hits 15+ 85% of the time while the previously described default strategy gets you there 91% of the time).

Evaluate the dice in the following sorted order: (1+4), 6, 5, 3, 2

1) Always keep 1 and 4 if you don't already have them.
2) Always keep 6 if you already have both a 1 and a 4.
3) If you have 2 or fewer dice left to consider, then keep a 5.
4) If you have only one die left to consider, then keep a 4. (Basically, expected value of a single roll is 3.5. You are 50% to do worse than a 4, and only 33% to do better. So, keeping the 4 is best.)
5) If you didn't keep anything in the current roll (as per above rules) , then keep a single die (the highest valued one).

Score Frequency PDF CDF
Not Qualified
12031334 (12.03%) (100.00%)
4 0 (0.00%) (87.97%)
5 14 (0.00%) (87.97%)
6 106 (0.00%) (87.97%)
7 746 (0.00%) (87.97%)
8 3596 (0.00%) (87.97%)
9 14262 (0.01%) (87.96%)
10 49197 (0.05%) (87.95%)
11 147225 (0.15%) (87.90%)
12 372987 (0.37%) (87.75%)
13 821681 (0.82%) (87.38%)
14 1633170 (1.63%) (86.56%)
15 2888930 (2.89%) (84.93%)
16 4484273 (4.48%) (82.04%)
17 6258644 (6.26%) (77.55%)
18 9710872 (9.71%) (71.29%)
19 11806824 (11.81%) (61.58%)
20 11650430 (11.65%) (49.78%)
21 11174701 (11.17%) (38.13%)
22 12093475 (12.09%) (26.95%)
23 10505528 (10.51%) (14.86%)
24 4352005 (4.35%) (4.35%)

Here's the 'go for broke' strategy, where you are going for 24 only. This means that you are going to keep all 6's (up to 4) and keep 1 and 4 as they present themselves. This strategy is forced if someone before you had gotten 24, and so you need specifically 24 to tie.

Score Frequency PDF CDF
Not Qualified 14806947 (14.81%) (100.00%)
4 1 (0.00%) (85.19%)
5 9 (0.00%) (85.19%)
6 117 (0.00%) (85.19%)
7 728 (0.00%) (85.19%)
8 3590 (0.00%) (85.19%)
9 14230 (0.01%) (85.19%)
10 49667 (0.05%) (85.17%)
11 146853 (0.15%) (85.12%)
12 374034 (0.37%) (84.98%)
13 821225 (0.82%) (84.60%)
14 1625200 (1.63%) (83.78%)
15 2859193 (2.86%) (82.16%)
16 4400751 (4.40%) (79.30%)
17 6108761 (6.11%) (74.90%)
18 9339354 (9.34%) (68.79%)
19 11297706 (11.30%) (59.45%)
20 11116484 (11.12%) (48.15%)
21 10652890 (10.65%) (37.04%)
22 11547947 (11.55%) (26.38%)
23 10035266 (10.04%) (14.83%)
24 4799047 (4.80%) (4.80%)

Tuesday, August 10, 2010

Combinatorial Madness - The Final Post

This is a continuation from: Combinatorial Madness - Follow Up.

So, a colleague of mine was able to solve the original potions problem such that the solution was the double factorial and not the summation. Thus, he was able to kill two birds with one stone. His way of looking at the problem shows both that the solution of the problem is, in fact, the double factorial and that by doing so, produces a proof by combinatorial argument of the double factorial identity.

For those unfamiliar, a proof by combinatorial argument is basically where you show two different ways to count the same thing, each having its own expression. Thus, both expressions must be equal, since they both count the same thing.

I take no credit for the following... it was solely the work of my colleague. If I mangle his argument, I apologize. I'm sure that I could be clearer about some parts, but I do think that the reasoning is solid. Anyway, this is basically how it goes.

Say that we want to know the solution to the N potions problem. Suppose that the solution of the k potions problem is A(k). With (N-1) potions, the total number of final potion products is A(N-1). Now, in producing a single final product with (N-1) initial potions, we would have gone through (N-2) iterations where some potion was combined with another potion in each iteration.

So, we can view these (N-2) combination actions as C_1, C_2, C_3, ..., C_(N-2). Any one of these combinations can be expressed as X+Y, X and Y being available potions at that junction. In order to tackle the N potion problem, we would like to add a new potion (the Nth potion -- call it Z) to the total mix. The question now is how can we add it such that we don't end up with any overcounting, etc?

For any combination action, we can inject the newly introduced Nth potion (Z) into that particular iteration -- however, notice that there are two ways in which this injection can happen. We can replace the combination that we're focused on with one where we've injected Z as ((X + Z)+Y) or as (X + (Y+Z)). Since there are (N-2) combination actions where we can perform this injection, we have 2(N-2) possible injection points.

We're missing one more injection point. That is the case where we simply combine the newly introduced Nth potion at the very end after C_(N-2) has produced some final product. There is exactly one injection point at the very end of our chain of C_k's. That adds one, so that gives us (2(N-2) + 1) injection points, and it's clear that adding Z to each of these injection points creates a completely new final product given this particular chain of combination actions (C_k's).

Now, we also know that there are A(N-1) different chains of combination actions that produce unique final products. Thus, we have (2(N-2)+1) * A(N-1) total final products for the N potions case. This simplifies to (2N-3) * A(N-1), which is clearly equivalent to (2N-3)!!, especially given that we know A(2) = 1 (the trivial 2-potion problem) .

So, this is a direct explanation of why the N-potion problem solution is (2N-3)!!, and it gives us the combinatorial proof that (2N-3)!! is equal to our other expression (from the previous post):

I know the above wasn't explained previously. That was me being lazy. Anyway, the explanation of why the above summation counts the final products in the N-potion problem is as follows (this one I actually helped come up with).

We are essentially enumerating all possible 2-partitions of the N potions being combined. A(i) represents the total final product count of the first of two partitions where the Nth potion is not a member. The A(N-i) represents the total final product count of the second of the two partitions and it is where the Nth potion is a member. The product of the two final product counts (i.e. A(i) * A(N-i) will result in the total number of final products when all N potions (both partitions) are considered). We are allowed to do this since our construction ensures no overcounting.

To further clarify, our loop going from i=1 to (N-1) gives us all the possible cardinalities of our partitions. We must multiply by ((N-1) Choose i) in order to produce all the combinations possible that make up the partitions with those cardinalities. Again, since we cannot overcount due to our construction, we can now sum the final product counts for all the possible partitions, giving us A(N).

Hope that was clear enough. And, in a way it was nice that we did not initially come up with the solution that leads directly to the double factorial. Because of this, we now have a pretty nifty combinatorial identity relating the recursive summation described above to the double factorial.

Monday, August 09, 2010

Combinatorial Madness - Follow-Up

So, here's a follow-up to my previous post: Combinatorial Madness.
A follow-up to this follow-up post can be found here: Combinatorial Madness - Final Post.

After a fair bit more work at this and thinking about it (with a good deal of help from a few colleagues), here's where we have arrived. We basically have a good explanation of how we can formulate a recursive solution to the problem. And, it now comes to the point where we have to verify the following conjecture. We believe it holds true, but haven't yet proven it nor tried to prove it.

Assuming it's true, it is a pretty cool double factorial identity.

Here it is.

Note that A(k) is the solution for the potion problem where N=k.

So, any takers? We haven't tried to prove the above, but basically, if you can prove that then that basically proves that the solution to the original potions problem follows the double factorial.

Friday, August 06, 2010

Combinatorial Madness

A Follow-Up Post can be found here: Combinatorial Madness Follow-Up.

I've gone mad. Here I am on a Friday night, absolutely consumed by a combinatorial problem that I came up with to challenge myself a while back. Only tonight have I begun thinking about it more seriously. And, either it's quite difficult or I'm just not getting it. If anyone wants to give it a go, please do, then teach me how you were able solve it if you figure it out. Because, I think I'm kind of stuck.

This is long, but if you like numbers, you may enjoy this.

Here's the problem.

There are N potions. Combining any two potions will form a completely new potion. Thus, (A+B)+C does not equal A+(B+C), as A+B forms something completely new, call it E, and B+C forms something completely new, call it F. So the former is E+C which is completely different than A+F.

In a single iteration, two potions are combined. After N-1 iterations, there is a single final potion. The question is, how many different final products can be created starting with the N potions?

This is much more difficult than the trivial question, which is how many possible paths are there from N potions down to a final product. The total number of possible paths is clearly (N choose 2)*(N-1 choose 2)*(N-2 choose 2)*...*(2 choose 2). The total possible paths will overcount the total number of possible final products, as some paths will lead to the exact same potion.

Here's what my friend Duke and I have come up with...

N=2, clearly it's 1 possible final product.
N=3, clearly there are 3 possible final products.

For N=4, it starts getting a bit more interesting. Here's a way I came up with that helps us count the number of final products possible. If you think about it some, you will realize that with N=4, there are only 2 possible forms in which a final product can be created.

Here they are:

Form 1 = ((A+B)+C)+D
Form 2 = (A+B)+(C+D)

It should be clear that (A+(B+C))+D is an isomorphism, and doesn't give us a new final product.

Now, there are 4! ways in which we can arrange A, B, C, and D. But, we also notice that the order of A and B does not matter. Thus, we overcount by a factor of two. So, there are actually 4!/2 = 12 final products of Form 1.

For Form 2, we notice that we overcount by a factor of 2 three times (once for A/B, once for C/D, and once for AB/CD). So, we have 4!/(2^3) = 3 final products of Form 2.

So, for N=4, we have a total of 12+3 = 15 possible final products.

Following the same counting strategy for N=5, here are the possible forms.

Form 1: (((A+B)+C)+D)+E
Form 2: ((A+B)+C)+(D+E)
Form 3: ((A+B)+(C+D))+E

For Form 1, again we have overcounting by a factor of 2, so we get 5!/2 = 60 for N=5.
For Form 2, we overcount by a factor of 2 twice (2^2). So, this gives us 5!/4 = 30. Note that the order of (A+B) and (D+E) does matter, which is why we only overcount for (A,B) and (D,E) and not for (AB,DE).
For Form 3, we notice that (A+B) and (C+D) order does not matter, so we have an additional factor of 2 overcounting compared with Form 2. This gives us 5!/8 = 15.

So, for N=5, there are a total of 105 possible final products.

Since, I'm a real glutton for punishment, here's my attempt at N=6. I came up with 6 possible forms, hopefully I'm not missing any.

Here are the six forms I came up with for N=6:

(((A+B)+(C+D))+(E+F)) – I think this overcounts by factor of 2^3 (A/B, C/D, AB/CD) [Note: This is incorrect -- see the Edit at bottom.]
(((((A+B)+C)+D)+E)+F) – overcounts by factor of 2 (A/B)
((((A+B)+C)+(D+E))+F) – overcounts by factor of 2^2 (A/B, D/E)
((((A+B)+C)+D)+(E+F)) – overcounts by factor of 2^2 (A/B, E/F)
((((A+B)+(C+D))+E)+F) – overcounts by factor of 2^3 (A/B, C/D, AB/CD)
(((A+B)+C)+((D+E)+F)) – overcounts by factor of 2^3 (A/B, D/E, ABC/DEF)

This gives us 6!/2 = 360, 6!/4 = 180 (twice), 6!/8 = 90 (three times), which is 990 total possible final products.

I was really hoping that I would have come up with 945 total possible final products, but I just don't see where I've gone wrong above. Maybe I did, so if you spot a mistake, please let me know.

If it had been 945, then we have a double factorial pattern for odd values... 1*3*5*7*...*(2n-1). 1, 3, 15, 105, 945, 10395, etc.

But, since I can't convince myself that it's 945, I am officially stuck.



(((A+B)+(C+D))+(E+F)) – I think this overcounts by factor of 2^3 (A/B, C/D, AB/CD) -- I neglected the E/F. This makes the overcounting factor 2^4, and that brings us to 945 possible final products for N=6. So, the solution is pretty much double factorial, but I do not have an actual proof. Will think about it, but maybe leave it to others, hehe.