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.)
Solution Solution and extension Comment 2 of 2 |
For any N there exists a largest power of 2 in the interval of 1 to N, call that number P.  P will necessarily obey the inequality P<=N<2P.

The smallest positive integer that we can add to P and get another power of 2 is a copy of P; P+P=2P is the next higher power of 2.  But we don't have another P since we are arranging the distinct members of a set.
Then the second smallest number we could try is 3P; P+3P=4P which is the second higher power of 2.  But 3P is outside the interval 1 to N, since we know that N<2P.

So P is a member of the set with zero possible neighbors, which makes finding an arrangement using all members of the set impossible.

This is enough to prove there are no solutions, with possible exception of the degenerate case when N=1 and there are no pairs at all.

I did explore some more avenues to show just how badly restrictive the conditions are.

I looked at the entire subset of members P+1 to N and found all those members have exactly one other number they can be adjacent to.  This is a pretty big problem as we can have at most 2 numbers like that in a solution.

I also looked at partitioning the set into subsets such that each subset has members with the same highest power of 2 dividing them.  For example, the N=7 case would be split up into {1,3,5,7}, {2,6}, and {4}.  For any sum of two elements to add up to a power of 2 then they must come from the same subset.  There is no way to string all these subsets together into a single unified arrangement.

This last observation suggests a followup question: If we restrict ourselves to the ODD integers 1 to 2N+1, for what N can we satisfy the conditions of the problem?  
Then an example with N=3 will give us 1,3,5,7 as the set of integers to work with.  This has a valid arrangement as 7,1,3,5 whose adjacent pair sums are 8, 4, and 8.

  Posted by Brian Smith on 2024-05-17 10:19:41
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
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