2
$\begingroup$

Four numbers are chosen from 1 to 20. If $1\leq k \leq 17$, in how many ways is the difference between the smallest and the largest number equal to k?

My Working:

Case 1:
The greatest number is 20.

As $1\leq k \leq 17$, hence, the smallest number $\geq 3$.
If it is 3, the number of ways of choosing the other 2 numbers is $16\cdot 15$
Similarly, for smallest number $4, 5, 6,\cdots$ no. of possibilities are $15\cdot 14$, $14\cdot 13$, $13\cdot 12$,$\cdots$

Hence, total combinations$=\sum{n(n+1)}$ from $n=16$ to $n=1$

Case 2:
The greatest number is 19 and 18. We can proceed similarly to get the same result i.e. total combinations$=\sum{n(n+1)}$ from $n=16$ to $n=1$

Case 3:
The greatest number $\leq 17$.
Let us call it $l$. total combinations$=\sum{n(n+1)}$ from $n=l-2$ to $n=1$

Problem:
This solution is very long. Is there an easier way of solving it?

$\endgroup$
2
  • 1
    $\begingroup$ Can the numbers chosen repeat? Does order of selection of the numbers matter? In the case that numbers cannot repeat and order of selection doesn't matter, then you have a grave error in your calculation, you calculated as though the order of the middle two numbers did matter. In the case that order does matter, you again have a major error as you do not account for this for all four of the numbers, only the middle two. $\endgroup$
    – JMoravitz
    Jan 15, 2017 at 7:49
  • $\begingroup$ @JMoravitz Oh yeah, forgot to divide by '2!' $\endgroup$
    – oshhh
    Jan 16, 2017 at 2:17

1 Answer 1

2
$\begingroup$

I will assume that numbers may not be repeated and that order of selection of the numbers does not matter., i.e. we are counting how many subsets, $A$, of $\{1,2,\dots,20\}$ have the property that $max(A)-min(A)=k$

First, recognize that $max(A)-1\geq max(A)-min(A)=k$ implies $max(A)\geq k+1$, for example if the distance between max and min is six, you cannot have the largest number be $6$ or less, it must be at least $7$ or more.

Step 1: Pick the largest number.

We first need to count how many ways in which we may pick the largest number for our set for a specific $k$. As $20\geq max(A)\geq k+1$ there are $20-k$ different possibilities for $max(A)$.

(E.g. for $k=19$ our only choice is for $max(A)=20$ and $min(A)=1$ for a total of $20-19=1$ choices while for $k=17$ we could have $max(A)=18~min(A)=1,~~max(A)=19~min(A)=2,$ or $max(A)=20~min(A)=3$ for a total of $20-17=3$ choices)

In having picked the largest number, the smallest number is forced to ensure that the desired difference is achieved.

Step 2: Pick the locations of the remaining two numbers in relation to the smallest number.

There will be $k-1$ available numbers between $min(A)$ and $max(A)$ to choose from and we wish to select two of these without regard to their order. There are $\binom{k-1}{2}$ ways to accomplish this.

There are then $(20-k)\binom{k-1}{2}$ subsets of $\{1,2,\dots,20\}$ with the property that $max(A)-min(A)=k$

Note: for $k=1$ and $k=2$ the above formula correctly gives a total of zero possibilities without need to add a special case since $\binom{k-1}{2}=0$ in both of those cases.

$\endgroup$
8
  • $\begingroup$ Thank you :) If you want you could just add a step three giving a summation for all 'k's (although it's pretty obvious) $\endgroup$
    – oshhh
    Jan 16, 2017 at 2:34
  • 1
    $\begingroup$ @OsheenSachdev my understanding was that the question was being asked about a specific single arbitrary value of $k$ in that range., not asking the sum of the totals over all possible $k$ in the range. If you were to sum the totals for each possible value of $k$ over the range $\{3,4,\dots,19\}$ you will wind up with a final total of $\binom{20}{4}$ as it is just a more complicated and longer way of partitioning the set of four-element subsets (which yields a derivation of an interesting identity at least, but otherwise seems unuseful) $\endgroup$
    – JMoravitz
    Jan 16, 2017 at 2:50
  • $\begingroup$ "you will wind up with a final total of $\binom{20}{4}$ as it is just a more complicated and longer way of partitioning the set of four-element subsets" How? This seems interesting... $\endgroup$
    – oshhh
    Jan 16, 2017 at 2:53
  • $\begingroup$ I hope you have noticed that $k\leq 17$ $\endgroup$
    – oshhh
    Jan 16, 2017 at 2:57
  • $\begingroup$ @OsheenSachdev yes I did, which is why I specified in my aside comment that it was to do with if $k$ ranged all the way up to $19$ instead. Why they would be equal is because of the first principle of combinatorics, if two expressions correctly count the same scenario (albeit looking different and arrived at via different methods) then they must be equal. $\endgroup$
    – JMoravitz
    Jan 16, 2017 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.