Wild About Math!

A hard but fascinating Math problem

I ran into the following problem in a contest problem book. I won’t reveal the source until later. I was not able to solve this problem and even though the solution is in the back of the book so I know how to solve it now, I’d like to see if anyone can solve this in an elegant and intuitive way and maybe even show how the author might have invented this problem.

There’s no prize for solving this, but I will publish all solutions and give link love to all solvers, and I will give special kudos to anyone who can help me to see why the interesting property shown in this problem is true.

Here’s the problem:

Express an arbitrary positive integer n, as ordered sums of positive integers in 2^(n-1) ways. For example, if n=5, the 16 ordered sums are listed in the left column below:

5 2(=2)
4+1 2×1(=2)
1+4 1×2(=2)
3+2 2×3(=6)
2+3 3×2(=6)
3+1+1 2×1x1(=2)
1+3+1 1×2x1(=2)
1+1+3 1×1x2(=2)
2+2+1 3×3x1(=9)
2+1+2 3×1x3(=9)
1+2+2 1×3x3(=9)
2+1+1+1 3×1x1×1(=3)
1+2+1+1 1×3x1×1(=3)
1+1+2+1 1×1x3×1(=3)
1+1+1+2 1×1x1×3(=3)
1+1+!+1+1 1×1x1×1x1(=1)

The entries in the right column are obtained from the corresponding entries in the left column by changing (a) additions to multiplications and (b) all the integers greater than or equal to 3 to 2, (c) 2 to 3, (d) 1 to 1 (i.e., keeping 1 unchanged).

Now add all the products in the right column. For n=5, we obtain

2+2+2+6+6+2+2+2+9+9+9+3+3+3+3+1=64=8^2

Prove or disprove: For every positive integer n, the sum of all the products in the right column is always a perfect square.

Send your solutions to sol dot lederman at gmail dot com.

If you enjoyed this post, make sure you subscribe to my RSS feed!