Problem of the Week 1217

Integer Pairs

True or False. For any positive integer n, it is possible to divide the integers 1, 2, ..., n into pairs (with one unpaired integer when n is odd) so that the sum of each pair is one less than a power of 2.

If one finds the unpaired integer inelegant, one can use the integers 0, 1, 2, ..., n when n is odd. The answer is the same in either case, as far as the problem posed. My view is that it is best to keep the base set unchanged as the parity changes and allows an unpaired number.

There are many variations obtained by using different target sets. Here are some examples. And one can treat the case of odd n in two ways (as noted above) by either including 0, or allowing one unpaired number. So the general problem has this form.

Variation 1. Call an integer n "pairable" with respect to property P if the set 1, 2, ..., n can be divided into pairs (with an unpaired number when n is odd) so that the sum of each pair has property P.

Variation 2. Call an integer n "pairable" with respect to property P if the the set 1, 2, ..., n (or 0, 1, 2, ..., n when n is odd) can be divided into pairs so that the sum of each pair has property P.

Which n are pairable (using either variation) for the squares? the primes? the Fibonacci numbers?

Source: G. Hamilton, K.S. Kedlaya, and H. Picciotto, Square-sum pair partitions, College Math. Journal 46 (Sept. 2015) 264-269.

[View the solution]