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 .
Thanks in advance!
