Problem 147

[axelbrz]

Hi,

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

Thanks!

[uws8505]

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

[axelbrz]

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

Thanks for the time!

[uws8505]

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

[axelbrz]

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

Good luck!

[rayfil]

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???

[axelbrz]

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!

[lg5293]

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.

[jaap]

3x3 is correct, the rest is not.

3x3 = 87
3x4 = 56

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

[Schu-ism]

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

[rustleg]

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?

[jaap]

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.

[rustleg]

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

[drassont]

Are the sides of the rectangles supposed to be either horizontal, vertical, or diagonal? I assume so, looking at this thread, but the problem is not clear on that.

In other words, does the number of rectangles in an n×n grid (not counting the number of rectangles in the subgrids) grow as n³ or as n⁴?

[pjt33]

In other words, does the number of rectangles in an n×n grid (not counting the number of rectangles in the subgrids) grow as n³ or as n⁴?

If I understand your definition of "in an n×n grid" correctly, surely it would grow as n? Each rectangle must touch the top edge, and each lattice point on the top edge would be a vertex of precisely one rectangle.

[drassont]

@pjt33, I'm not sure I understand: why must each rectangle touch the top edge? That's not the case in #85, nor in the picture given in #147.

Apparently in problem 85 the sides of the rectangle are restricted to be grid lines. So I guess I may have to assume that that's the case in this problem and see what happens. It's still strange to me that this isn't clarified in the problem text.

[drassont]

I solved the problem, so it must be the case that, as I'd guessed, the rectangles are restricted to those with horizontal/vertical or diagonal sides.

I still think that, to be candid, this fact could be made much clearer in the problem text. E.g. even if one made just the slight change of using a 3×3 rectangle instead of a 2×3 rectangle in the example, it would be unambiguous that rectangles whose sides are not on the grid lines are not being counted. But because a 2×3 rectangle isn't large enough for one to make such rectangles, I was unable to know for sure what the problem was asking.

[pjt33]

@pjt33, I'm not sure I understand: why must each rectangle touch the top edge?

Because otherwise it's a rectangle in a subgrid. But as I said, maybe I wasn't understanding your definition.