Uniquely Reachable Numbers

Let $n > 1$ be an integer. Given set $A_n = \{ 1, 1, \dots, 1, 2, 2, \dots, 2, \dots, n-2, n-2, n-1, n \}$ where there are:

$2^{n-1}$ number $1$

$2^{n-2}$ number $2$

$\dots$

$2^2$ number $n-2$

$2$ number $n-1$

$1$ number $n$

$1$ number $n+1$

(As you can see, there are a total of $2^n$ numbers in $A_n$). A positive integer is called "reachable" if it can be expressed as a sum of $2^{n-1}$ numbers in $A_n$. A reachable number is called "uniquely reachable" if that sum is unique (not counting permutations of the summands).

For example, for $n=3$, we have $A_3 = \{1,1,1,1,2,2,3,4\}$. The number 10 is uniquely reachable because it can be expressed as $10 = 1+2+3+4$ and this representation is unique (we consider $1+2+3+4$ and $3+4+2+1$ to be the same way). However, the number $6$ is not unique because $6 = 1+1+2+2 = 1+1+1+3$.

Find all the uniquely reachable numbers.

Solution

Answer: the only uniquely reachable numbers are $2^{n-1}, 2^{n-1}+1, 3.2^{n-1}-2,3.2^{n-1}-1$.

Proof:

We prove by induction. Now first note a few things:

The sum of all numbers in $A_n$ is $2^{n+1}-1$. So the number $k$ is reachable iff the number $2^{n+1}-1-k$ is reachable. Similarly, $k$ is uniquely reachable iff the number $2^{n+1}-1-k$ is uniquely reachable. We prove this by simply taking the complement of the numbers chosen to represent $k$. There are exactly half of the numbers in the set, so the sum of the numbers that are not chosen to represent $k$ will be $2^{n+1}-1-k$.

Also, the range of reachable numbers is from $2^{n-1}$ to $3.2^{n-1}-1$ (by taking the $2^{n-1}$ smallest numbers, that is all ones, all the way to the largest numbers, that is everything but ones). So any number outside of this interval is clearly not reachable by any choice of $2^{n-1}$ numbers in $A_n$.

We shall prove the following statements in tandem:

1. All numbers in the interval $[2^{n-1}, 3.2^{n-1}-1]$ are reachable

2. The uniquely reachable numbers are $2^{n-1}, 2^{n-1}+1, 3.2^{n-1}-2,3.2^{n-1}-1$.

These statements are easy to verify for $n=2$. Now suppose they all hold for $n-1$.

Claim 1: If $k$ is (uniquely) reachable in $A_{n-1}$ (it can be expressed as sums of $2^{n-2}$ numbers in $A_{n-1}$) then $k+2^{n-2}$ is (uniquely) reachable in $A_n$.

Proof: Take $k$ and its representation of $2^{n-2}$ summands, and add $2^{n-2}$ ones to it. This new representation is valid in $A_n$ because there are at most $2^{n-2}$ ones in $A_{n-1}$, and by adding $2^{n-2}$ more ones, we are using at most $2^{n-1}$ ones. The other numbers that are represented in $A_{n-1}$ are unchanged and still available to use in $A_n$. Each distinct representation of $k$ will yield a new representation of $k + 2^{n-2}$, so the uniqueness of reachability also transfers to the new representation.

Claim 2: If $k$ is (uniquely) reachable in $A_{n-1}$ then $k + 3.2^{n-2}$ is (uniquely) reachable in $A_n$.

Proof: If $k$ is (uniquely) reachable in $A_{n-1}$ then $2^n-1-k$ is (uniquely) reachable in $A_{n-1}$, then by claim 1, $2^n-1-k+2^{n-2}$ is (uniquely) reachable in $A_n$, therefore $2^{n+1}-1-(2^n-1-k+2^{n-2}) = k + 3.2^{n-2}$ is also (uniquely) reachable in $A_n$.

From the two claims above, because all numbers in the interval $[2^{n-2}, 3.2^{n-2}-1]$ are reachable in $A_n$, now we apply claim 1 to this interval. We have the interval $[2^{n-1}, 2^n-1]$ reachable in $A_n$. Similarly, we apply claim 2 to this interval, we have $[2^n, 3.2^{n-1}-1]$ reachable in $A_n$. By combining these two intervals, we have $[2^{n-1}, 3.2^{n-1}-1]$ reachable in $A_n$. Thus we have proven statement 1 of the induction hypothesis.

Now we prove uniqueness. By induction hypothesis, the numbers in the interval $[2^{n-2}+2, 3.2^{n-2}-3]$ are reachable but not uniquely in $A_{n-1}$. By claim 1, we can the interval $[2^{n-1}+2, 2^{n}-3]$ is reachable but not uniquely. Likewise, we can claim 2 to establish that the interval $[2^n+2, 3.2^{n-1}-3]$ is reachable but not uniquely. Then now we know that all numbers in the interval $[2^{n-1}+1, 3.2^{n-1}-3]$ are reachable but not uniquely, except of the following four numbers: $2^n-2, 2^n-1, 2^n, 2^n+1$. They are reachable but not yet proven as uniquely reachable.

Claim 3: If $k$ is (uniquely) reachable in $A_{n-1}$ then $k + 2^{n-1}$ is (uniquely) reachable in $A_n$.

Proof: First note that $A_n$ can be formed by adding one to each element of $A_{n-1}$ and then adding $2^{n-1}$ to it. Now, take any representation of $k$ in $A_{n-1}$. Add 1 to each summand, and then add $2^{n-2}$ ones to it. Now we have $2^{n-1}$ summands, and only $2^{n-2}$ are ones. The rest (the higher summands) are valid in $A_n$ because they were 1 more than the summands that were valid in $A_{n-1}$. The new sum is $k + 2^{n-2} + 2^{n-2} = k+2^{n-2}$. Distinct representations in $A_{n-1}$ would also result in distinct representations in $A_n$.

Because $n \geq 4$, we have $2^{n-2}+2 \geq 2^{n-1}-2$ and $2^{n-1} \leq 3.2^{n-1}-3$, so by induction hypothesis, $2^{n-1}-2$ and $2^{n-1}$ are non-uniquely reachable in $A_{n-1}$, then $2^n-2$ and $2^n$ are non-uniquely reachable in $A_n$. Then, their complements $2^n-1$ and $2^n+1$ are also non-uniquely reachable. This completes our proof of statement 2