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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

Problem 147

Post by axelbrz »

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

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

Re: Problem 147

Post by uws8505 »

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

Post by axelbrz »

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

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

Re: Problem 147

Post by uws8505 »

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

Post by axelbrz »

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

Image
User avatar
rayfil
Administrator
Posts: 1407
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 147

Post by rayfil »

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

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

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

Problem 147

Post by 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.
User avatar
jaap
Posts: 559
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 147

Post by jaap »

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

Post by Schu-ism »

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

Re: Problem 147

Post by 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?
User avatar
jaap
Posts: 559
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 147

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

Re: Problem 147

Post by rustleg »

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