Partition the numbers into disjoint pairs , and the replace each pair with it's non negative difference .

The numbers $$1,2, \cdots, 2^n$$ , $$n>2$$ is a natural number are written on a board . The following procedure is performed n times: partition the numbers into disjoint pairs , and the replace each pair with it's non negative difference . Determine all possible values of the final number.

My progress: I think the answer is $$0, 2^{k-1} ; k\in {2,\cdots,n}$$.

We will use induction. Note that by case works $$0, 2^k ; k\in {1,\cdots,n}$$ works for $$n=2$$. Hence the statement is true for $$n=l$$ , now we will show that $$0, 2^k ; k\in {1,\cdots,n}$$ for $$n=l$$ can be possible solutions .

• $$2^{l-1}$$ : group $$1,2,\cdots ,2^l$$ as

$$(2^l,1),(2^l-1,2), \cdots (2^{l-1}+1,2^{l-1}-1) \implies 2^l-2 , 2^l-4, \cdots 2$$

Similarly now, grouping the largest and smallest numbers and continuing the step we get ..

$$2^l-2 , 2^l-4, \cdots 2 \implies 2^l-2^2 , 2^l-8, \cdots 4 \implies \dots \implies 2^l-2^{l-2} , 2^{l-2} \implies 2^{l-1}$$

• $$2^i , i\ne l-1$$ : now grouping $$2^l \cdots 2^{l-1}+1$$ as $${ 2^l,2^l-1},{ 2^l-2,2^l-3} , \cdots {2^{l-1}+2,2^{l-1}+1}$$ . Note that in the next step the differences will be $$1$$ and as we continue we will get $$0$$ . So the final numbers's value is determined on how we "pair" numbers from $$1,2,\cdots 2^{l-1}$$ and hence by induction, we see that $$2^k ; k\in {1,\cdots ,l-1}$$ works .

• $$0$$ : Group $$1,2,\cdots ,2^l$$ as $${ 2^l,2^l-1},{ 2^l-2,2^l-3} , \cdots {2,1}$$

Now, I just want to show that other numbers aren't possible .

Claim: Odd numbers can't be the final numbers

Proof: Notice that after one "procedure" , the sum of the differences will be even as there are even number of odds between $$1,\cdots 2^l$$. Therefore this set of differences will contain even numbers of odd numbers. Similarly for other steps also . And hence the final number will be odd .

And after this I am not able to get any nice result .

• $n=3$, 4-2=2. 2-1=1. 8-1=7. Why odd not possible? Oct 5, 2020 at 2:15
• @cosmo5 For $n=3$ the numbers to partition into disjoint pairs is $1,2,3,4,5,6,7,8$. Oct 5, 2020 at 2:19
• Haha, I thought only powers of 2 given. I see now! Oct 5, 2020 at 2:23

Any even number under $$2^n$$ can be made. Here's how:
Let $$2k$$ be the desired number. Then pair:
$$(1,2k+2),(2,3),(4,5),\dots,(2k,2k+1),(2k+3,2k+4),\dots,(2^n-1,2^n)$$
The differences are $$2k+1$$ and $$(2^{n-1}-1)$$ ones.
The next differences are $$2k$$ and $$(2^{n-2}-1)$$ zeroes.