Hint for Problem 85

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 :)

There is a much nicer way to

Simon's picture

There is a much nicer way to show this to be true.... (adds some mystery)

Post new comment

The content of this field is kept private and will not be shown publicly.
If you have a Gravatar account, used to display your avatar. If you have a Gravatar account, used to display your avatar.
  • Allowed HTML tags: <img> <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <span> <fn>
  • Lines and paragraphs break automatically.
  • Textual smileys will be replaced with graphical ones.
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>. Beside the tag style "<foo>" it is also possible to use "[foo]".
  • Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.

More information about formatting options

What is 30 + 34?
To combat spam, please solve the math question above.
Honey Pot that kill bots