Determine the number of ways to choose 5 numbers from the first 18 natural numbers such thatany two chosen numbers differ by at least 2.

Question

Please I need a method. Thanks.

Answer 1

One method of solution uses Exhaustive Enumeration (consider all possible combinations and determining whether the criteria is met for each).

Here is a computer program that does this:

LET Count = 0

FOR A = 1 TO 18

  FOR B = 1 TO 18

    IF ((B<>A) AND (ABS(B-A)>=2)) THEN

      FOR C = 1 TO 18

        IF ((C<>B) AND (ABS(C-B)>=2) AND (C<>A) AND (ABS(C-A)>=2)) THEN

          FOR D = 1 TO 18

            IF ((D<>C) AND (ABS(D-C)>=2) AND (D<>B) AND (ABS(D-B)>=2)  AND (D<>A) AND (ABS(D-A)>=2)) THEN

              FOR E = 1 TO 18

                IF ((E<>D) AND (ABS(E-D)>=2) AND (E<>C) AND (ABS(E-C)>=2) AND (E<>B) AND (ABS(E-B)>=2) AND (E<>A) AND (ABS(E-A)>=2)) THEN

                  LET Count = Count + 1

              NEXT E

          NEXT D

      NEXT C

  NEXT B

NEXT A

OUTPUT (Count)

END

 

Count is 240240.

 

Note: This method counts both (18,16,14,12,10) and (18,16,14,10,12) as different solutions, for example.

Answer 2

*UPDATED*

OK, I think I found a way to do it analytically...

 

Out of the 18 numbers we are going to choose 5 of them,

  N1  N2  N3  N4  N5

Let's assume they are in order N1 < N2 < N3 etc.

 

Now to meet the "differ by at least 2" requirement, that means that there are

5-1 = 4 numbers that we cannot choose, one each between the 

chosen ones, shown here as Ex(cluded number)'s:

 

   N1  Ex  N2  Ex N3  Ex     N4  Ex    N5

 

If we had just the numbers 1 ... 9 then there is only one solution.

But we have extra numbers: There are 18 - ( 5 + (5-1) ) = 9 numbers that are not indicated in the list above.

These can be put in anywhere in the gaps between our selected numbers (ading to the required one excluded number), or even before/after the lowest/highest selcted numbers.

This can be indicated by:

 

 G1  N1  Ex+G2  N2  Ex+G3  N3  Ex+G4   N4  Ex+G5  N5   G6

 

where the G1, G2 represent 0 or more numbers included in the sequence.

 

So there are 5+1 = 6 "gaps" where the extra 9 numbers can be put.

For each arrangement of these 9 gap numbers we have a different solution.

For example, if G1=3, G2=3 and G4=3 we'd have the solution:

- - - 4 - - - - 9 - 11 - - - - 16 - 18

 

It turns out there is a formula for putting N indistinguishable balls into K distinguishable bins allowing 0 balls in a bin

(see Wikipedia article "Stars and bars (combinatorics)", Theorem 2) :

 

  =  (N + K - 1 ) !  / (  N !   (K-1) ! )    

 

For this problem N = 9 extra numbers into K = 6 gaps between numbers:

 

  = 14! /(9! 5!) = 14 13 12 11 10 / (5 4 3 2 1)  = 7 13 1 11 2 = 2002 .

 

This is the number of distinct sets of 5 numbers, the order does not matter.

 

To count re-orderings as well we can multiply by the number of permuations

of 5 numbers = 5! = 5 4 3 2 1 = 120.

So the total number of ways counting different orderings is

  2002 * 120 = 240240  

in agreement with David W's Exhaustive Enumeration result.