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

Don't post any spoilers
petrw1
Posts: 7
Joined: Mon Jan 21, 2008 10:02 pm

### Problem 086

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?

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

### Re: Problem 86 clarification

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. Phibonacci
Posts: 10
Joined: Fri Nov 28, 2008 4:04 am
Location: Des Moines, IA
Contact:

### Re: Problem 086

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

The problem talks about counting cuboids, not paths.

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

### Re: Problem 086

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  Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

### Re: Problem 086

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 [edit: and again silly me: no need to filter doublets, just don't loop over them ] vasilyev
Posts: 4
Joined: Fri Dec 11, 2009 5:54 pm

### Re: Problem 086

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

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

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 [edit: and again silly me: no need to filter doublets, just don't loop over them ]
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?  jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 086

M=1: 1 cuboid,
M=2: 1+3 = 4 cuboids
M=3: 1+3+6 = 10 cuboids
...
Jaap's Puzzle Page MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

### Re: Problem 086

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

### Re: Problem 086

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.
Jaap's Puzzle Page MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

### Re: Problem 086

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   EnDorphin
Posts: 8
Joined: Wed Oct 13, 2010 3:23 pm

### Re: Problem 086

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.] DDgeva
Posts: 15
Joined: Mon Dec 29, 2008 12:47 pm

### Re: Problem 086

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?

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

### Re: Problem 086

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.
Jaap's Puzzle Page DDgeva
Posts: 15
Joined: Mon Dec 29, 2008 12:47 pm

### Re: Problem 086

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?

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

### Re: Problem 086

Those numbers are all correct.
Jaap's Puzzle Page DDgeva
Posts: 15
Joined: Mon Dec 29, 2008 12:47 pm

### Re: Problem 086

jaap wrote:Those numbers are all correct.
This problem is making me doubt both my computers functionality and the validity of mathematics in reality.. 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.

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

### Re: Problem 086

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.
Jaap's Puzzle Page 