Problem

Source:

Tags: Comc, 2017 COMC



Source: 2017 Canadian Open Math Challenge, Problem C4 Let n be a positive integer and $S_n = \{1, 2, . . . , 2n - 1, 2n\}$. A perfect pairing of $S_n$ is defined to be a partitioning of the $2n$ numbers into $n$ pairs, such that the sum of the two numbers in each pair is a perfect square. For example, if $n = 4$, then a perfect pairing of $S_4$ is $(1, 8),(2, 7),(3, 6),(4, 5)$. It is not necessary for each pair to sum to the same perfect square. (a) Show that $S_8$ has at least one perfect pairing. (b) Show that $S_5$ does not have any perfect pairings. (c) Prove or disprove: there exists a positive integer $n$ for which $S_n$ has at least $2017$ different perfect pairings. (Two pairings that are comprised of the same pairs written in a different order are considered the same pairing.)