Puzzle 4

Find a permutation p of { 1, 2, ..., 567 } such that, for each i in the domain, i + p(i) is a power of 2.

You have 567 letters, numbered from 1 to 567; and 567 envelopes, also numbered from 1 to 567. How can you pair up the letters and the envelopes such the sum of the number on a letter and the number on its envelope is always a power of 2?

Answer

If you try this puzzle, you'll soon find that you're considering only permutations of order 2, consisting entirely of 2-cycles and 1-cycles. Indeed, all cycles must be of order 1 or 2.^*
You'll soon find that if you put letter p in envelope q, you'd better put letter q in envelope p.

Now we start with the biggest unpaired number, call it N. We know that N < N+f(N) ≤ 2N, and that there's exactly one power of 2 in that range. So we have exactly one option for f(N), and we form the pair ( N, f(N) ). Next we consider the biggest remaining unpaired number, and so on.

So, starting at 567, its partner must be 457. The complete permutation is

(567, 457)
(566, 458)
(565, 459)
  ...
(512)
(456, 56)
  ... 
(256)
(55, 9)
 ...
(32)
(8)
(7, 1)
(6, 2)
(5, 3)
(4)

* Proof
Suppose there is a cycle of length >2. Find a pair of consecutive terms, call them a and b, with the greatest sum. We now have a+b = 2ⁿ for some n. But a and b must each be less than 2^n-1.

This answers question 4 at A technique in solving puzzles.