Two Problems from RGP

As I sit down to write this article, I have been home for a week following five weeks in Australia. The five weeks in Oz kept me away from my usual connection to the computing world, but I did manage to spend an hour one day reading rec.gambling.poker (rgp). I happened to see two interesting questions whose solutions I'll present here. The two questions deal with keno, but the principle used to solve them has many applications to mathematical problems in poker.

When drawing the numbers in keno, we say the draw has a match if the i-th ball drawn has the number i on it for any of the 20 possible values of i. So, if the fourth number drawn is a four, or the twelfth number drawn is a twelve, and so on, we say the draw has a match.

The first question asks for the probability of having a keno draw with no matches. The answer is provided by a straightforward application of the principle of inclusion-exclusion. So let's get with it!

Since the order in which the balls are drawn is important in this problem, we are dealing with permutations. There are 80 possible choices for the first ball, 79 choices for the second ball, 78 choices for the third ball and so on. The total possible number of keno draws is then the product $80\cdot 79\cdots 62\cdot 61 = 80!/60!$ We shall denote the latter number by A(0). Now let A(1) denote the number of occurrences of draws with at least one match. There are 20 choices for a ball which matches and for the remaining 19 balls there are $79\cdot 78\cdots 61$ choices. Thus, $A(1) = 20\cdot 79\cdot 78\cdots 61$ .

In general, if we let A(i) denote the number of occurrences of draws with at least i matches, then there are C(20,i) choices for a set of i balls all of which match, and there are $(80 - i)(80 - i -1)\cdots 61$ choices for the remaining 20 - i balls. Then A(i) is the product of the two expressions.

I claim that the number of keno draws with no matches is given by the expression $A(0)-A(1)+A(2)-A(3)+\cdots -A(19)+A(20)$ . I will not give a proof of this fact, but let's consider an example.

Consider a keno draw with exactly three matches in it. Then it is counted once in A(0); three times in A(1), because it has one occurrence for each of the balls for which there is a match; three times in A(2); and once in A(3). Thus, these occurrences cancel each other in the above expression and such a draw is counted zero times. A similar cancellation takes place for any draw with at least one match and we are left with only the draws having no matches. Dividing by A(0) gives a probability of .77787317 that there is no match.

The second question posed on rgp queried the probability that every row and every column of the keno board has at least one cell lit after all 20 numbers are drawn. This is a problem involving combinations because we care only about which numbers are drawn, and not the order in which they are drawn. Solving this problem requires paying attention to how inclusion-exclusion works.

The total number of keno boards is C(80,20) because we choose 20 cells to be lit from 80. We denote this number by K(0,0). Now let K(i,j) be the number of occurrences of keno boards with no lit cells in some set of i rows and some set of j columns. Thus, K(1,2) is counting occurrences of keno boards with no lit cells in some row and some set of two columns. As in the previous problem, it is important to note that a keno board qualifying for K(1,2)also may have additional rows and columns in which it has no lit cells. This means it will be counted more than once in K(1,2).

When we are excluding lit cells from i rows and j columns, we are choosing i rows from eight rows, choosing j columns from 10, and we are prevented from using 10i+8j-ij cells. Thus, we must choose our 20 lit cells from the remaining cells implying that $K(i,j)={{8}\choose{i}} {{10}\choose{j}}{{80-10i-8j+ij}\choose{20}}$ .

Since we must have at least 20 cells available for balls to be drawn, the following numbers are valid:

K(1,0)	K(2,0)	K(3,0)	K(4,0)	K(5,0)	K(6,0)
K(0,1)	K(1,1)	K(2,1)	K(3,1)	K(4,1)	K(5,1)
K(0,2)	K(1,2)	K(2,2)	K(3,2)	K(4,2)	K(5,2)
K(0,3)	K(1,3)	K(2,3)	K(3,3)	K(4,3)	K(5,3)
K(0,4)	K(1,4)	K(2,4)	K(3,4)	K(4,4)	K(0,5)
K(1,5)	K(2,5)	K(3,5)	K(0,6)	K(1,6)	K(2,6)
K(0,7)	and	K(1,7).

In writing out the expression for the number of keno boards for which there is at least one cell from each row and column lit, +K(i,j) is included if i+j is even and -K(i,j) is included if i+j is odd. I would not have been surprised if the expression had been more complicated. So it begins K(0,0)-K(1,0)-K(0,1)+K(2,0)+K(1,1)+K(0,2)and so on. Performing the calculation and dividing by K(0,0), the total number of keno boards, we obtain a probability of .22063 that at least one cell from each row and each column is lit.

There is an interesting generalization of the latter result. The rows of the $8\times 10$ keno board partition the 80 cells into eight sets of 10 cells apiece, while the 10 columns partition the 80 cells into 10 sets of eight cells apiece. These two partitions are said to be orthogonal, because each set in the row partition intersects each set in the column partition in exactly one cell. The above calculations depend only on the fact that every row intersects every column in exactly one cell. Therefore, if we take any two orthogonal partitions of the cells of an $8\times 10$ keno board so that one partition has eight sets with 10 cells in each set and the other partition has 10 sets with eight cells in each set, then the probability of a keno board having at least one cell lit in each set of the partition sets is .22063.

For example, you could choose as one partition all of the $2\times 5$ blocks you get by taking adjacent rows in pairs and the first five columns, and adjacent rows in pairs and the last five columns. From each of these eight $2\times 5$ blocks, choose exactly one cell to form the sets of the other partition. The orthogonal partition just described is fairly regular looking, but you can take any old shapes for the two partitions, as long as they are orthogonal. The probability stays the same.