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?
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 |