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?
ken
April 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.
jim
April 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
jim
April 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.
Administrator
April 27, 2009 at 16:35
Nice puzzle =)
Jax
August 26, 2010 at 16:28