## Problem 147

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

### Problem 147

Hi,

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

Thanks!
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

### Re: Problem 147

I get 420 for a 5*7 grid, but I'm not so sure about my answer.
Math and Programming are complements
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

### Re: Problem 147

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

Thanks for the time!
Last edited by axelbrz on Mon Nov 10, 2008 8:14 am, edited 1 time in total.
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

### Re: Problem 147

I'm trying to solve it but I haven't found any algorithm to find the number of cross hatched ones yet
Math and Programming are complements
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

### Re: Problem 147

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

Good luck!
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

rayfil
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Contact:

### Re: Problem 147

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???
When you assume something, you risk being wrong half the time.
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

### Re: Problem 147

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!
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

lg5293
Posts: 3
Joined: Mon Sep 27, 2010 9:49 pm

### Problem 147

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

jaap
Posts: 559
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 147

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.
Schu-ism
Posts: 3
Joined: Tue Jun 20, 2017 11:56 pm

### Re: Problem 147

I hope it's not too much to emphasize that the result for a 5 by 7 grid is NOT 1120.
rustleg
Posts: 2
Joined: Fri Mar 19, 2021 11:03 am

### Re: Problem 147

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
Posts: 559
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 147

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
Posts: 2
Joined: Fri Mar 19, 2021 11:03 am

### Re: Problem 147

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