1
$\begingroup$

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!

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

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Oh I see ! Thanks :) Nice sol :) $\endgroup$ Oct 5, 2020 at 2:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .