## Round 4: Problem 4

A square grid with 10 rows and 10 columns contains the numbers 1, 2,…, 100 in its squares, as shown to the right. The grid is to be divided into 50 rectangular pieces, each of which contains two squares. Each piece is given a value equal to the product of the numbers that are on it. What is the smallest possible sum of the values of the 50 pieces? (You should prove your answer is the minimum.)

very confusing.

at first, I was thinking 100*1+99*2…

but after I read the FAQ, seems like it needs to be 2 adjecent squares..

so I changed my mind to 100*90+99*89…

then I felt like this problem is impossible to be that easy…

can we have more hints?

kenApril 25, 2009 at 23:25

(a-b)^2 = a^2 + b^2 -2ab

so minimizing (or maximizing) the sum of ab is like doing so for the sum of (a-b)^2. (since the sum of the square of the individual entries is constant) So, to minimize, make a-b = 1 for each pair.

jimApril 27, 2009 at 07:45

That should have been, to maximize. To minimize you want the difference to be as large as possible, so (a-b)=10

jimApril 27, 2009 at 11:18

That’s right now, you had me a bit confused for a sec. You want to pair vertical entries, so the minimal sum ends up being 166675 I believe.

AdministratorApril 27, 2009 at 16:35

Nice puzzle =)

JaxAugust 26, 2010 at 16:28