## Square Rods

#### Problem

Using rods of fixed length 1, 2, 3, ..., `n`, the smallest value of `n` for which a square can be formed is `n` = 7.

Find the values of `n` for the next two solutions.

#### Solution

The next solution occurs when `n` = 8: the perimeter of the square will be, 1 + 2 + 3 + ... + 8 = 36. Therefore one side will be 36/4=9 units long.

It can be seen that 1 must be paired with 8, then 2 must be paired with 7, and so on. Hence we must use the following pairings: (1,8), (2,7), (3,6), (4,5).

In general, the perimeter, P = 1 + 2 + 3 + ... + `n`, must be divisible by 4.

We note that P, the sum of the first `n` positive integers, is given by `n`(`n`+1)/2. And as the product of two consecutive numbers, `n` and `n`+1, will contain one odd factor and one even factor, the even factor must be divisible by 8 in order to be divisible by 4 after being halfed. This explains why `n`=8 is a solution, and `n`=7 is a solution because `n`+1=8. In other words, it is necessary for `n` or `n`+1 to be divisible by 8.

Hence the next solution should occur when `n`=15, as `n`+1=16; that is, 1 + 2 + ... + 15 = 1516/2 = 158 = 120.

As the side of the square will be 120/4 = 30, we can form a square using the following sets: (15,14,1), (13,12,5), (11,10,9), and (8,7,6,4,3,2).

If `n` or `n`+1 is divisible by 8, will you always be able to form a square?