Thread: a combinatorial problem

Ok, so we've got twelve balls all marked with a distict number between 1 and 12.
( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) (10) (11) (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?

Hello, mgarson!

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.

. . . . . . . .

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: . ways.



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

When the smallest number is 3, we find the number of triples is:
. . 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: .

Therefore: .