How many solutions $\mid a - b \mid \le 5 $ for $a$, $b$ in $\{1, 2, ..., 50\}$?

51 Views Asked by At

I have begun reading Principles and Techniques in Combinatorics by Chong and Meng.

The very first exercise problem is like this:

Find the number of ways to choose a pair $\{a,b\}$ of distinct numbers from the set $\{1, 2, ..., 50\}$ such that

$$ \mid a - b \mid \le 5 $$

The answer in the back of the book is $235$, but I have arrived at a different answer and I believe it to be correct.

Let $$ a = k \in \{1,2,...,45\}$$

and $$ b \in \{k, k+1, ..., k+5\} $$

then certainly the following holds true

$$ \mid k - b\mid \le 5$$

so we have $$45 \times 6 = 270 $$

possible solutions. However, since

$$ \mid a - b \mid = \mid b - a \mid $$

There are really two sets of solutions, so shouldn't the answer be $540$ ?

Edit:

I have just realized I have double counted every instance of $(k,k)$.

1

There are 1 best solutions below

1
On BEST ANSWER

Since the answer they give is in the $200$ range, I assume that they want unordered pairs of numbers (also, in your question it is written as $\{a,b\}$ which indicates unordered pair). One other key in your question is that it asks for distinct pairs of numbers, so we must omit all $\{k,k\}$ choices. Finally, you should also need to include the cases of, for instance, $a=46$ and $b=47,48,49,50$ (in total there are $4+3+2+1$ of these types of cases).

Other than what I list above, your approach to the solution is valid (and good!). The corrections I list above yield $45\cdot 5=225$ pairs of the form $\{a,b\}$ with $a=k\in\{1,\ldots,45\}$ and $b\in\{k+1,\ldots,k+5\}$, and there are $4+3+2+1=10$ pairs with $a\in\{46,47,48,49\}$. This gives a total of $225+10=235$ possible pairs $\{a,b\}$.