Project Euler Forum

Hi,

Are there 1120 different rectangles that can be situated in a 5x7 grid?

Thanks!

I get 420 for a 5*7 grid, but I'm not so sure about my answer.

Oh, I mean vertical + horizontal + cross-hatched rectangles, but I've verified it using brute force.

Thanks for the time!

I'm trying to solve it but I haven't found any algorithm to find the number of cross hatched ones yet

Lol, try to see the cross-hatched grid as a normal matrix

Good luck!

axelbrz wrote:Are there 1120 different rectangles that can be situated in a 5x7 grid?

The question is a little ambiguous. Do you mean only in a strictly 5x7 grid or in that size grid and ALL smaller ones as required in the problem???

No, no, I was referring in a strictly 5x7 grid, but I've resolved the problem, I had a trivial mistake in the program when I asked that.

So, thanks too!

Hi,

Problem 147 (View Problem)
Can anyone confirm if these rectangles are correct. This is assuming just strictly that rectangle, so 3x2 is just 37.

3x3 = 87
3x4 = 56
3x5 = 209
4x4 = 264
4x5 = 395
2x12 = 343
2x13 = 392
1x20 = 229
10x9 = 7660
10x10 = 9502

Thanks for your help.

3x3 is correct, the rest is not.

lg5293 wrote:3x3 = 87
3x4 = 56

Here something is obviously wrong, as the latter contains at least all the rectangles of the former.

I hope it's not too much to emphasize that the result for a 5 by 7 grid is NOT 1120.

I have difficulty understanding the conditions in this question.

First when considering the second set of 35 rectangles contained within the horizontal-vertical rectangles, surely you are double counting, not only the smaller grids themselves, but also their contents, so they aren't different.

Also for example the 2x2 grid contains 4 1x1 horizontal-vertical rectangles as well as 2x1's and 1x2's which themselves can be re-cross-hatched and double counted as above to contain yet more rectangles. Where do you stop? Does the question imply a limit to the reduction of contained horizontal-vertical rectangles?

They are not sub-grids of each other. The question just asks you to examine one grid of each possible size up to some maximum size limit, and add their results together.

Not sub-grids, ok. I now realise how I misread the question. Thanks for the clarification.