All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Arrange 1 to N (Posted on 2024-05-17) Difficulty: 3 of 5
Arrange the integers from 1 to N in an order such that the sum of any two consecutive terms is a power of 2.

For what values of N do solutions exist?

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts I think ... | Comment 1 of 2
For 1 to N, we need N-1 pairs of integers chosen from {1,...,N} which sum to a power of two.  In addition, except for the first and last pair, each member of a pair must appear in two different pairs.  A computer search suggests that there are not enough pairs to make that happen, so I suspect such an arrangement is impossible.  But can this be proved?

Consider the special case where N = 2^p - 1 where p is a positive integer.
There are N choose 2 ways to pair up integers from 1 to N, but only p-1 powers of 2 which can be the sum of 2 adjacent numbers:   2, 3, ..., p.  The smallest pairing is (1,3) summing to 2^2.
For a particular "sum target" of 2^k, there are 2^(k-1) - 1 pairs which sum to that target

e.g. p=3, N=2^p - 1=7, target sums are 4 and 8, suitable pairs are (1,3); (1,7), (2,6), (3,5).
There are only 1 + 3 = 4 pairs but we need 6 pairs.

For N = 2^p - 1 for larger values of p, the number of pairs is:
1 + 3 + 7 + 15 + ... + 2^(p-1)-1  or 
The Sum as k goes from 2 to p of 2^(k-1)-1
This sum is equivalent to 2^p - p - 1  but we need at least N-1, or 2^p - 2 pairs.
There just are not enough pairs.

Now suppose we increment N by 1; now N = 2^p.  The largest pair (2^p-1, 2^p) will sum to 2^(p+1) - 1, so there will not be any more target sums, but we need one more.
e.g. N=7, p=3; incrementing N from 7 to 8, the largest pair sums to 15.

But incrementing N by 2 does result in another target.
e.g. N=9 results in 2^4 = 16 being a viable target, but we are not getting the full complement of 7 pairs we would have if N were as large as 15; with N=9, only 1 pair (7,9) sums to 16.
Incrementing N to 10 brings one more viable pair on board:  (6,10),(7,9).

So it appears that the number of pairs available for various N values is
 N       #pairs
2^p - 1    2^p - p - 1
2^p + a    2^p + a - p - 1  (where a is from 0 to 2^p)

I think this is enough for a proof.

  Posted by Larry on 2024-05-17 09:50:14
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information