Numbers which cannot be formed

Question

We are given two numbers $a,b$ such that $a<b$. Now we have a set $\{a,a+1,a+2,\ldots, b\}$ (all number between a and b including them). Then, we have to find how many numbers cannot be formed from the above set. The only operation allowed on the set elements is addition.

Note : We can add these number as many times we want. Only addition allowed on these numbers.

Eg : If numbers are 3 and 5, the set is $\{3,4,5\}$ using these we only cannot make $1,2$.

Can anyone help me with that?

I am not getting any idea. I tried the cases when $b-a = 1$.

Answer 1

If you start with $a\neq b$ (i.e. if your starting set contains more than one number) then the set of numbers that "can be formed" will always be cofinal in the natural numbers (i.e. there will always be a $n$ s.t. every $m>n$ could be obtained via additions).

To see this, assume you start from $\{n,n+1\}$. Notice that if you consider the possible results you can obtain by summing these two numbers $m$ times you obtain $m+3$ consecutive elements. Eg:

$$0:\quad \{n,n+1\} $$ $$1:\quad \{2n, 2n+1, 2n+2 \} $$ $$2:\quad \{3n, 3n+1, 3n+2, 3n+3 \} $$

and so on. This should come as no surprise as the number of $k$-combinations with repetition of $2$ elements is $$ \frac{(2+k-1)!}{(2-1)!k!} = \frac{(k+1)!}{k!}=k+1 $$

This implies that, after $m=n-1$ sums you have $$ \{mn, mn+1, mn+2, ... , mn+n \} $$ and last term is exactly $(m+1)n$.

Example:

start with $\{3,4\}$. Summing them once you get $\{6,7,8\}$. If you consider the possible results of summing $3$ elements drawn from $\{3,4\}$ you get $\{9, 10, 11, 12 \}$. But $12 = 3\cdot 4$, i.e. if you consider the possible sums of $4$ elements drawn from $\{3,4\}$ the smallest number you can get is exactly $12$. This means that, from now on, you will be able to obtain every other number. In this example the only ones you cannot get are $\{1,2,5\}$.

Answer 2

Let us consider the numbers that can be formed by $\alpha-1$ additions:

\begin{align} \alpha =1 \text{ gives }& \mathcal{A}_1 =\{a,a+1,\ldots, a+(b-a)\}\\ \alpha =2 \text{ gives } & \mathcal{A}_2 =\{2a,2a+1,\ldots, 2a+2(b-a)\}\\ \alpha =3 \text{ gives } & \mathcal{A}_3 =\{3a,3a+1,\ldots, 3a+3(b-a)\}\\ &\vdots\\ \text{In general, } \alpha \text{ gives } & \mathcal{A}_\alpha =\{\alpha a,\alpha a+1,\ldots, \alpha a +\alpha(b-a)\} \end{align} Note that $ \mathcal{A}_\alpha$ is a set of consecutive numbers, and the size of the set$| \mathcal{A}_\alpha|=\alpha(b-a)$ increases with $\alpha$.

Suppose for some $\alpha$, $\mathcal{A}_{\alpha+1}$ is the continuation of $\mathcal{A}_{\alpha}$, i.e., there is no gap between the two consecutive group of numbers that can be formed, then all numbers $\geq \alpha a$ can be formed.

Therefore, if the last element of $\mathcal{A}_{\alpha}$ is one less than $\mathcal{A}_{\alpha+1}, i.e., \alpha a +\alpha(b-a)+1= (\alpha+1) a\implies \alpha=\frac{a-1}{b-a}$, then all numbers $\geq \alpha a$ can be formed using the set. Thus, the gap between the consecutive groups of numbers that can be formed is the set of numbers that can not be formed:

$$\left\{\alpha b+1,\alpha b+2,\ldots,(\alpha+1)a-1, > \forall \; 0\leq \alpha < \frac{a-1}{b-a}\right\}$$ can not be formed using the given set.

For example, \begin{align} a=3,b=5\implies&\frac{a-1}{b-a}=1 \implies \alpha = 0\\ &\left\{\alpha b+1,\alpha b+2,\ldots,(\alpha+1)a-1, \forall \; 0\leq \alpha < \frac{a-1}{b-a}\right\}=\left\{1,2 \right\}\\ a=3,b=4\implies&\frac{a-1}{b-a}=2 \implies \alpha = 0,1\\ &\left\{\alpha b+1,\alpha b+2,\ldots,(\alpha+1)a-1, \forall \; 0\leq \alpha < \frac{a-1}{b-a}\right\}=\left\{1,2,5 \right\}. \end{align}