3
$\begingroup$

If $n>1$ is a positive integer Let $A_n =\{a_1,a_2,\ldots,a_n\}$ be a finite set of consecutive integers.

How many distinct sums of the form $a_j+a_k$ where $j \neq k$ are there?

Surely there are ${n \choose 2}$ entries to select from $A_n$. So a naive answer would be that there are $1,3,6,10,\ldots$ possible sums for $n$ equal to $1,2,3,4,\ldots$ respectively. But that is wrong since the set $\{9,10,11,12\}$ has distinct sums: $9+10,9+11,9+12,10+12,11+12$ noting that $10+11=9+12$. So we have $5$ distinct sums and not ${4 \choose 2}=6$.

Here is my work and my approach so far:

If $a_j$ is any element in $A_n$ other than $a_1$ then $a_j=-1+j+a_1$. To see a working example of this just consider an $A_4=\{123,124,125,126\}$, then $a(3) = -1+3+123=-1+126=125$. I construct the following sets $S_{a_{j}}=\{a_j+a_k\text{ }|\text{ } j\neq k\}$. We need to compute $$\bigg|\bigcap_{j=1}^n S_{a_{j}}\bigg|$$ Surely $|S_{a_{1}}|=n-1$. I would like to use some type of inclusion-exclusion process to get rid of the sums that occur more than once.

$\endgroup$

1 Answer 1

4
$\begingroup$

You can solve this simply by looking at the smallest number you can form and the largest number you can form. Let's say $\{a_1, a_2, ..., a_n\}$ is ascending. Then let $x = a_1 + a_2$ be the smallest number you can form. Let $y = a_{n-1} + a_n$ be the largest number you can form. Then you can see that you can form every number in between $x$ and $y$ (Hint: You can shift the sequence $\{a_1, a_2, ..., a_n\}$ so that it looks like $\{1, 2, ..., n\}$). Therefore, you can create $y - x + 1$ distinct numbers. Looking at our shifted values, we can create $(2n-1)-(3)+1=2n-3$ distinct numbers.

$\endgroup$
5
  • $\begingroup$ @user825632 this looks nice but I do not understand how this approach eliminates "overcounting". It does seems correct though. $\endgroup$ Sep 8, 2016 at 19:04
  • 1
    $\begingroup$ We are saying that we can create all numbers between x and y (including x and y) and we cannot create any other numbers. Not being able to create any other numbers makes sense - we cannot make anything smaller than x and anything larger than y. To see that we can create all numbers between x and y, we look at the shift to {1,2,...,n} and see that we can create all numbers from 3 to (2n-1) somehow. We are counting the numbers that can be created exactly once - not the ways used to create them (e.g. we count "5" once, even if we can create 5 as 1+4 or 2+3). Therefore, we are not overcounting. $\endgroup$ Sep 8, 2016 at 19:12
  • $\begingroup$ As a follow up question and not worthy of another posts - is it possible to count the multiples of any sum? For instance in the set $\{1,2,3,4,5,6,7\}$ the sum $a_j+a_k=6$ occurs twice as $1+5$ and again as $2+4$. So it has "multiplicity", $2$. On the other hand the sum equal to $7$ can be formed in $3$ different ways namely $1+6$, $2+5$ and $3+4$. $\endgroup$ Sep 8, 2016 at 19:19
  • 1
    $\begingroup$ Yes - with a set {1,2..n}, we can form 3 in one way, 4 in one way, 5 in two ways, 6 in two ways, 7 in three ways, 8 in three ways, etc. (see the pattern?) We find that we can create (n+1) in floor(n/2) ways (which is the max), and after (n+1), the number of ways will decrease symmetrically (e.g. n and (n+2) will have the same number of sums, (n-1) and (n+3) will have the same number of sums, etc). $\endgroup$ Sep 8, 2016 at 19:33
  • 1
    $\begingroup$ @user2825632 The idea behind your argument is just what kids do when they figure out what numbers can be rolled with a pair of dice, if doubles don't count. They figure out why 7 is most likely by counting with multiplicities, just as you suggest in the comment to your answer. $\endgroup$ Sep 8, 2016 at 23:46

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.