Problem 086

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.
petrw1
Posts: 7
Joined: Mon Jan 21, 2008 10:02 pm

Problem 086

Post by petrw1 »

The example cuboid is 6 X 5 X 3.
Would a cuboid 6 X 3 X 5 OR 3 X 5 X 6 (and other permutations)
be considered the same cuboid or a different one?

User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: Problem 86 clarification

Post by Tommy137 »

petrw1 wrote:The example cuboid is 6 X 5 X 3.
Would a cuboid 6 X 3 X 5 OR 3 X 5 X 6 (and other permutations)
be considered the same cuboid or a different one?
It's considered the same cuboid.
Image

Phibonacci
Posts: 10
Joined: Fri Nov 28, 2008 4:04 am
Location: Des Moines, IA
Contact:

Re: Problem 086

Post by Phibonacci »

here is my problem, here is an example of a cuboid
x = 3
y = 3
z = 1

the three shortest paths are:
x*x + (y+z)*(y+z) = 25
y*y + (x+z)*(x+z) = 25
z*z + (x+y)*(x+y) = 37

notice that there are two shortest paths with integer lengths, namely sqrt(25) which is 5. Do we count these as two paths for the cuboid with the shortest length being integer, or just one path.
Phibonacci - A juxtaposition of Phi (The Golden Ratio) and Fibonacci (Leonardo of Pisa)

Eigenray
Posts: 62
Joined: Mon Jul 14, 2008 5:20 pm

Re: Problem 086

Post by Eigenray »

The problem talks about counting cuboids, not paths.

User avatar
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

Re: Problem 086

Post by Jochen_P »

for M=100 I count 338350 possible distinct cuboids, is this correct?
I only ask because I get nearly twice as much as 2060 cuboids for which the shortest path is int :?
Image

User avatar
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

Re: Problem 086

Post by Jochen_P »

Ooops,

of course there are only 171700 distinct cuboids for M=100. Silly me!
Even the amount of integer shortest path cuboids is correct now... It kinda slows the script tremendously to filter the doublets out, but at least I got the basics correct now :mrgreen:


[edit: and again silly me: no need to filter doublets, just don't loop over them :oops: ]
Image

vasilyev
Posts: 4
Joined: Fri Dec 11, 2009 5:54 pm

Re: Problem 086

Post by vasilyev »

Hello,

In the problem statement it is not mentioned anywhere that the sides of the cuboid are integers. Therefore, the true correct answer to the problem 86 is infinity!

Example:
sides of the cuboid:
a1 = 2;
a2 = sqrt(12) - alpha;
a3 = alpha.

For alpha values between 1.5 and 2 there is a continuum of cuboids with shortest path being sqrt(a1^2 + (a2 + a3)^2) = sqrt(16) = 4.

Please correct the discrepancy or show me where I am wrong.

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 086

Post by harryh »

Good spot ! Wording amended to:
By considering all cuboid rooms with integer dimensions, up to a maximum size ...

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 086

Post by MaJJ »

Jochen_P wrote:Ooops,

of course there are only 171700 distinct cuboids for M=100. Silly me!
Even the amount of integer shortest path cuboids is correct now... It kinda slows the script tremendously to filter the doublets out, but at least I got the basics correct now :mrgreen:


[edit: and again silly me: no need to filter doublets, just don't loop over them :oops: ]
I don't understand ... This is how I thought:

Code: Select all

M = 1: 1 cuboid
1,1,1

M = 2: 3 cuboids
2,1,1
2,2,1
2,2,2

M = 3: 6 cuboids
3,1,1
3,2,1
3,2,2
3,3,1
3,3,2
3,3,3
etc. - for M there are M*(M+1)/2 cuboids ...
So for M=100 there would be 5050 cuboids.
Can somebody explain where to get the number 171700?
Image
Image

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 086

Post by jaap »

M=1: 1 cuboid,
M=2: 1+3 = 4 cuboids
M=3: 1+3+6 = 10 cuboids
...

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 086

Post by MaJJ »

Thanks. But when I change my code according to this, I see "least value of M for which the number of solutions first exceeds two thousand" as 70, not as 100 stated in the problem description.

For Ms from 1 to 9 I see 20 solutions (they are below). Is that number right?

Code: Select all

3 2 2
3 3 1
4 2 1
6 4 4
6 5 3
6 6 2
6 6 5
7 5 5
7 6 1
8 3 3
8 4 2
8 5 1
8 5 4
8 8 7
9 5 3
9 6 6
9 7 5
9 8 4
9 8 6
9 9 3
Image
Image

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 086

Post by jaap »

MaJJ wrote:For Ms from 1 to 9 I see 20 solutions (they are below). Is that number right?
No. Think about 6x6x5 for example, and reread the problem statement carefully.

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 086

Post by MaJJ »

jaap wrote:
MaJJ wrote:For Ms from 1 to 9 I see 20 solutions (they are below). Is that number right?
No. Think about 6x6x5 for example, and reread the problem statement carefully.
Of course ... Thanks a lot! Now I've got it right :)
Image
Image

EnDorphin
Posts: 8
Joined: Wed Oct 13, 2010 3:23 pm

Re: Problem 086

Post by EnDorphin »

jaap wrote:
MaJJ wrote:For Ms from 1 to 9 I see 20 solutions (they are below). Is that number right?
No. Think about 6x6x5 for example, and reread the problem statement carefully.
I don't get it...
I get the same result as MaJJ.
Is the example of 6x6x5 suppose to give a logical reason on why it doesn't work?

[EDIT: Oh!! I got it. As said, I read the question carefully. Thanks.]
Image

DDgeva
Posts: 15
Joined: Mon Dec 29, 2008 12:47 pm

Re: Problem 086

Post by DDgeva »

I can't manage to figure out what/ I'm missing in this one.
I do get that there are 171700 distinct cuboids for M=100, but I'm getting only 2002 cuboids with integer shortest paths.
I also don't get what's the issue with a (5,6,6) cuboid. According to my calculations, all 3 possible shortest paths for a (5,6,6) cuboid are not integer.

for M=9 I'm getting the following 12 solutions:

Code: Select all

1 2 4
1 3 3
1 5 8
2 4 8
2 6 6
3 3 8
3 5 6
3 9 9
4 4 6
4 8 9
5 7 9
7 8 8
Can anyone offer some assistance?

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 086

Post by jaap »

DDgeva wrote:I also don't get what's the issue with a (5,6,6) cuboid. According to my calculations, all 3 possible shortest paths for a (5,6,6) cuboid are not integer.
There is a path of length 13 (13^2=12^2+5^2).
DDgeva wrote:for M=9 I'm getting the following 12 solutions:
You are missing some - 2 2 3 and 6 6 9.

DDgeva
Posts: 15
Joined: Mon Dec 29, 2008 12:47 pm

Re: Problem 086

Post by DDgeva »

Thanks jaap, you are absolutely right. I hate Java's integer division.
But I'm still getting an incorrect answer for M=100: 2036.
Also for M=99 I'm getting 1955 instead of 1975.

Can you please verify that there are 35 solutions for M=15 and 67 solutions for M=20?
If these are correct, are there 113 solutions for M=25?

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 086

Post by jaap »

Those numbers are all correct.

DDgeva
Posts: 15
Joined: Mon Dec 29, 2008 12:47 pm

Re: Problem 086

Post by DDgeva »

jaap wrote:Those numbers are all correct.
This problem is making me doubt both my computers functionality and the validity of mathematics in reality.. :shock:

Just to be sure, when they say "up to a maximum size of M by M by M", it means that all sides of that cuboid have length not greater than M, right?

Could you send me (possibly privately) a sorted list of solutions for M=100? I'm really wondering which ones I'm missing.
For M=50 I get 453 solutions. If this is also incorrect than a list for M=50 will suffice.

This is, of course, only if it isn't considered violation of the forum rules. I don't think so though because it's mentioned in the problem statement that there are 2060 solution for M=100, so this isn't really giving too much away.

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 086

Post by jaap »

DDgeva wrote:Just to be sure, when they say "up to a maximum size of M by M by M", it means that all sides of that cuboid have length not greater than M, right?
Of course, or you wouldn't have the correct answers for up to M=25.
DDgeva wrote:Could you send me (possibly privately) a sorted list of solutions for M=100? I'm really wondering which ones I'm missing.
For M=50 I get 453 solutions. If this is also incorrect than a list for M=50 will suffice.
That should be 456.
Since you get 81 new solutions going from M=99 to M=100, when you should get 85, why not examine only those? You'll find there are two types, and you should have 37 of one type, 48 of the other.

Post Reply