Re: a combinatorial problem

Hello, mgarson!

Quote:

We have twelve balls each marked with a distict number between 1 and 12.

In how many ways can we pick three balls from the twelve

so that the difference between the numbers written on them is at least 2?

For example: we are not allowed to pick {1, 2, 5} since 2 - 1 = 1,

. . but are allowed to choose {1, 5, 12}.

The answer should be 120, but why?

In desperation, I started a brute-force Listing of the possible triples,

. . then I discovered a pattern.

Suppose the smallest number is 1 and the next number is 3.

. . Then the largest number must be 5 or more: .8 choices.

Suppose the smallest number is 2 and the next number is 4.

. . Then the largest number must be 6 or more: .7 choices.

Suppose the smallest number is 3 and the next number is 5.

. . Then the largest number must be 7 or more: .6 choices.

. . . . . . . . $\displaystyle \vdots$

Suppose the smallest number is 1 and the next number is 10.

. . Then the largest number must be 12: .1 choice.

Hence, when the smallest number is 1,

. . there are: .$\displaystyle 1 + 2 + 3 + \hdots + 8 \:=\:36$ ways.

When the smallest number is 2, we find that the number of triples is:

.$\displaystyle 1 + 2 + 3 + \hdots + 7 \:=\:28$ ways.

When the smallest number is 3, we find the number of triples is:

. . $\displaystyle 1 + 2 + 3 + \hdots + 6 \:=\:21$ ways.

And so on . . .

We see that the total number of ways

. . is the sum of the first 8 Triangular Numbers.

This is a Tetrahedral Number: .$\displaystyle T(n) \:=\:\frac{n(n+1)(n+2)}{6}$

Therefore: .$\displaystyle T(8) \:=\:\frac{8\cdot9\cdot10}{6} \:=\:120$