I did Problem 85 during my pre-calculus Honors class, a very boring class, where I maintain above 100 average 99 average while slacking. [see why I'm not 100%]
Here is the question in case the official site is down(happens every 2 days)
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
Like the hint for problem 15, here we also start experimenting with small numbers and special cases.
Suppose there is a function, f(x,y), and it will show the amount of possible rectangles inside a x*y rectangle grid . Then:
f(x,y) = f(y,x), because nothing is changed if we just reflect the rectangles.
set up a special case, x=1, try some data and you would find f(1,y) = Ty, where Tn is the nth Triangular Number.(try yourself)
If x is something else, how would the formula change? well, because we know that f(x,y) = f(y,x), then there is something operation with commutative property applied to g(Ty) and g(Tx), where g(x) is a unknown function. to allow f(1,y) to be Ty,
g(1) [Insert a commutative operation here] g(Ty) = Ty. g(1) is a constant and g(x) should be a continuous function in the entire domain (no proof, just instinct), then we have the following induction, g(x) = x.
It's most likely f(x,y) = Tx * Ty, because f(x,y) is the 2D version of f(1,y). But it's only nice if we can prove it.
separate the rectangles into strips, size 1, 2, 3.... x, because this partition x into all possible values for the smaller rectangles
now apply f(1,y) to each strip.
f(x,1) = f(1,x), the numbers involve x below is exact same way the numbers involve y are formed.
1*1 (x*y times)+1*2(x*(y-1) times)+1*3(x*(y-2) times)+1*y(x*(y-y+1) times) = 1 * Ty
2*1 ((x-1)*y times), 2*2((x-1)*(y-1) times), 2*3((x-1)*(y-2) times)....2*y((x-1)*(y-y+1) times) = 2 * Ty
x*1 ((x-x+1)*y times), x*2((x-x+1)*(y-1) times), x*3((x-x+1)*(y-2) times)....x*y((x-x+1)*(y-y+1) times) = x*Ty
add them together.
because 1+2+3....+x = Tx
we have f(x,y) = Tx * Ty
Hint ends here.
You can figure out the rest of the problem with a little programming and under 100ms execution time :)
Bookmark/Search this post with:
There is a much nicer way to
There is a much nicer way to show this to be true.... (adds some mystery)
Post new comment