Tuesday, May 15, 2007

Answer to POD #1

The answer is in white on white below, highlight to verify your answer. Surprisingly this didn't take me much time, so I'll continue with my questions tomorrow. I will have to qualify by stating that I may pose a problem that I don't know the answer to, and may pass on the problem until I can research it further. This is all but an experimental exercise. :)
Here's how you figure out the expected number of complete rows: there are five possibilities to consider, because you can leave anywhere from 0 to 4 complete rows. You cannot leave 3 or 4 complete rows because of pigeonhole principle: 4 is impossible after removing one, and 3 is impossible after removing 4 (because you can remove an entire row and have one more to remove, destroying another row). So, in all C(12,4) possibilities there are 3 outcomes: leaving 0 rows, leaving 1 row, and leaving 2 rows.

Case 1: leaving 0 rows... you can do this by choosing 1 from each row, or 3*3*3*3 of 81 possibilities.

Case 2: leaving 2 rows... you can do this by first choosing the rows that are complete ( C(4,2) ) then finishing by choosing what to take within the rows that aren't complete ( C(6,4) ) leaving C(4,2)*C(6,4)=6*15=90 possibilities

Case 3: leaving 1 row. First, choose the complete row C(4,1) then choose which 4 of the 9 remaining to remove. But, be careful: of those C(9,4) you must exclude the ones that leave a full row which is [choose first the row remaining then the 4 from the 6 remaining, or C(3,1)*C(6,4)=3*15 or 45] so C(4,1)*(C(9,4)-45)=4*81=324.

To confirm: 81+90+324=495=11*5*9=12*11*10*9/4*3*2*1=C(12,4)

So, now that we have all the possibilities, let's calculate the expected value E=(81*0+90*1+324*2)/495=738/495=1.49090909... so the expected number of rows is about 1 1/2 rows. More likely than not, you'll have 1 complete row remaining.

I had a really fun time tonight, scoring 46 points in the brainmaster's competition at Tigin. I must look up this website; it sounds like a lot of fun. But, it makes for a long night, and your dear author is too tired to continue. Will write again tomorrow.