Problem: arrange integers 1 to 15 in a line, so that every two adjacent numbers sum up to a perfect square.

Solution: all perfect squares in question would be 4,9,16, and 25. For each number, find all other numbers that add up to one of those 4 squres. This form a graph. Start from one vertex, find a Hamilton path. Since 8 and 9 each is connected to one edge, they must be the two ends of the path. Start from either of them. The answer is 8,1,15,10,6,3,13,12,4,5,11,14,2,7,9 or the other way round.

(more…)