The whole numbers 1 to 2n are placed in order around a circle. For which n is it possible to draw n non-intersecting chords (one from each number) such that each of them joins two numbers whose sum is a perfect square?
What if we wish that the two numbers belonging to each chord add up to a prime number?
This is possible precisely for the
multiples of 4.
Proof:
Necessity:
First observe that any pair participating must consist of an odd and an even number because their connecting chord has to split the other numbers into two groups of even size each. All squares arising are therefore odd and it is well-known that odd squares are congruent 1 mod 8. For the pairs that means that a number with residue class k mod 8 must be paired with a number from class 1-k. In particular, the classes k and 1-k must occur the same number of times. Now count the number of residue classes mod 8 among the numbers 1,...,2n. Note that class 1 will occur the same number of times as class 0 if and only if n is a multiple of 4.
Sufficiency:
Assume to reach a contradiction that there are multiples of four not permitting a decomposition. Let n = 4k be the smallest such number. Note that there is guaranteed to be an odd square S between 2n and 4n. Form all pairs that sum to this square, i.e. (2n,S-2n),(2n-1,S-2n+1),... Observe that mod 8 this reduces to (0,1),(7,2),(6,3),(5,4),(4,5),(3,6),(2 7),(1,0),etc...., in particular the number of pairs formed is a multiple of 4 because the list can only terminate at one of the highlighted pairs. The remaining numbers are therefore of the form 1,...,2n' with n'<n divisible by 4. (We note that n'=0 is not possiblle since it would mean that we already have paired all numbers into squares.) By minimality assumption these remaining numbers can be paired into squares. Contradiction.
