Problem 086
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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 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.
Problem 086
Hello I am having trouble understanding what is required in problem 86.
What I mean is the following:
Consider the example cuboid with sides 6,5 and 3.
Now the first solutions is when all combinations are taken into account, having in mind that this is a pythagorean triple  6,8,10:
1 solution: 6,5,3 > 6*6 + (5+3)*(5+3) = 10*10
2 solution: 6,7,1 > 6*6 + (7+1)*(7+1) = 10*10
3 solution: 6,6,2 > 6*6 + (6+2)*(6+2) = 10*10
4 solution: 6,4,4 > 6*6 + (4+4)*(4+4) = 10*10
5 solution: 5,1,8 > (5+1)*(5+1) + 8*8 = 10*10
6 solution: 4,2,8 > (4+2)*(4+2) + 8*8 = 10*10
7 solution: 3,3,8 > (3+3)*(3+3) + 8*8 = 10*10
Thus there are 7 solutions for the shortest path (which is 10).
Which is correct?
These are solutions for the cuboid with sides 6,5,3?
Or the answer is the first 4 solutions where the initial length of 6 does not change?
What I mean is the following:
Consider the example cuboid with sides 6,5 and 3.
Now the first solutions is when all combinations are taken into account, having in mind that this is a pythagorean triple  6,8,10:
1 solution: 6,5,3 > 6*6 + (5+3)*(5+3) = 10*10
2 solution: 6,7,1 > 6*6 + (7+1)*(7+1) = 10*10
3 solution: 6,6,2 > 6*6 + (6+2)*(6+2) = 10*10
4 solution: 6,4,4 > 6*6 + (4+4)*(4+4) = 10*10
5 solution: 5,1,8 > (5+1)*(5+1) + 8*8 = 10*10
6 solution: 4,2,8 > (4+2)*(4+2) + 8*8 = 10*10
7 solution: 3,3,8 > (3+3)*(3+3) + 8*8 = 10*10
Thus there are 7 solutions for the shortest path (which is 10).
Which is correct?
These are solutions for the cuboid with sides 6,5,3?
Or the answer is the first 4 solutions where the initial length of 6 does not change?
Re: Problem86 please clarify
I also tried brute force:
E.g. the following all add up to integer solutions: Sqrt(a*a+(b+c)*(b+c)) = Integer
a  b  c
5  1  11
5  2  10
5  3  9
5  4  8
5  5  7
5  6  6
6  1  7
6  2  6
6  3  5
6  4  4
And there are 4411 solutions for M=100. Now I doubt that there is a mistake in Project Euler, so could somebody please clarify what is expected from the problem?!
E.g. the following all add up to integer solutions: Sqrt(a*a+(b+c)*(b+c)) = Integer
a  b  c
5  1  11
5  2  10
5  3  9
5  4  8
5  5  7
5  6  6
6  1  7
6  2  6
6  3  5
6  4  4
And there are 4411 solutions for M=100. Now I doubt that there is a mistake in Project Euler, so could somebody please clarify what is expected from the problem?!
Re: Problem 086
Rigel,
I think you are new here, but posts like this:
a) Belong in the forum Project Euler Clarifications
b) Should have as title "Problem xxx"
c) And no new topic should be created if a topic for that problem already exists.
I think you are new here, but posts like this:
a) Belong in the forum Project Euler Clarifications
b) Should have as title "Problem xxx"
c) And no new topic should be created if a topic for that problem already exists.
Re: Problem 086
I think there are more misunderstandings, but this is not the shortest route for this cuboid. There is one little shorter for this cuboid, but it is not integer length.rigel wrote:6,7,1 > 6*6 + (7+1)*(7+1) = 10*10
Re: Problem 086
The shortest path for the cuboid 6x5x3 is 10. The question is not asking you how many ways there are to achieve a shortest path on a given cuboid; it is asking you to count cuboids which have an integral shortest path. This cuboid does, so it counts as 1 of the 2060 solutions for M=100.
Re: Problem 086
Apologies kk for the new topic.
Concerning the problem, I mean the following:
The cuboid with sides 6,5,3 has a shortest path 10 and it counts as one.
A cuboid with sides 6,7,1 also has a shortest path of 10 and it is a different cuboid.
I have uploaded a file with cuboids that have different sides
E.g.
18  8  16
18  8  72
where a=18,b=8,c=16 for the first and a=18,b=8,c=72 for the second (a,b and c are the cuboid sides).
As you can see for the first (18*18)+(8+16)*(8+16)=900 > 30^2, for the second (18*18)+(8+72)*(8+72)=6724> 82^2 where the shortest path is sqrt (a^2 + (b+c)^2). These are all different cuboids (that is they have different a,b,c) and the total combinations for all that a,b,c <= 100 is 4411.
So if every cuboid with different sides that has an integer solution sqrt (a^2 + (b+c)^2) with sides a,b,c is in the file and the total count is not 2060 that I guess I am wrong, but I don`t see where since the number of different cuboids that I get is 4411 and all have integer length calculated by sqrt (a^2 + (b+c)^2) ?
Concerning the problem, I mean the following:
The cuboid with sides 6,5,3 has a shortest path 10 and it counts as one.
A cuboid with sides 6,7,1 also has a shortest path of 10 and it is a different cuboid.
I have uploaded a file with cuboids that have different sides
E.g.
18  8  16
18  8  72
where a=18,b=8,c=16 for the first and a=18,b=8,c=72 for the second (a,b and c are the cuboid sides).
As you can see for the first (18*18)+(8+16)*(8+16)=900 > 30^2, for the second (18*18)+(8+72)*(8+72)=6724> 82^2 where the shortest path is sqrt (a^2 + (b+c)^2). These are all different cuboids (that is they have different a,b,c) and the total combinations for all that a,b,c <= 100 is 4411.
So if every cuboid with different sides that has an integer solution sqrt (a^2 + (b+c)^2) with sides a,b,c is in the file and the total count is not 2060 that I guess I am wrong, but I don`t see where since the number of different cuboids that I get is 4411 and all have integer length calculated by sqrt (a^2 + (b+c)^2) ?
 Attachments

 results.rar
 Different cuboids
 (10.91 KiB) Downloaded 104 times
Re: Problem 086
As TheEvil mentioned above  no, it does not.rigel wrote:A cuboid with sides 6,7,1 also has a shortest path of 10.
Re: Problem 086
Aha, thanks.
So I understood the problem correctly, the calculations were wrongly assumed.
So I understood the problem correctly, the calculations were wrongly assumed.
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 086
Isn't this incorrect, as actually there are six "shortest" path candidates for any given cuboid?However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.
You can see this from a symmetry argument.
Even in the picture of the diagram shown, I can draw a symmetric path that duplicates the path shown.
 Thanks
Rishada is the gateway to free trade—but the key will cost you.
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 086
I believe I can answer my own question  In assuming that the symmetry of a path,
is not considered as a unique path candidate.
is not considered as a unique path candidate.
Rishada is the gateway to free trade—but the key will cost you.
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 086
I need a bit of help.
I appear to be under counting right now:
M = 99: 1544
M = 100: 1581
Can somebody give me the expected input when
M= 3, 4, 5, 6, 7, 8, 9, and 10?
I am getting: 2, 3, 3, 6, 6, 10, 14, 14
Thanks
<EDIT> I just looked at some parts of the forum and somebody said that at M=50 correct answer is 456, which is what I got.
So seems I am going astray after that.  Ill keep looking
 Okay had a small logical error  solved the problem. took a long time. I liked it
I appear to be under counting right now:
M = 99: 1544
M = 100: 1581
Can somebody give me the expected input when
M= 3, 4, 5, 6, 7, 8, 9, and 10?
I am getting: 2, 3, 3, 6, 6, 10, 14, 14
Thanks
<EDIT> I just looked at some parts of the forum and somebody said that at M=50 correct answer is 456, which is what I got.
So seems I am going astray after that.  Ill keep looking
 Okay had a small logical error  solved the problem. took a long time. I liked it
Rishada is the gateway to free trade—but the key will cost you.
Re: Problem 86 clarification
Problem 86 is by far the most difficult problem to understand out of the first ~100 problems.Tommy137 wrote:It's considered the same cuboid.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?
Clearly a 6 X 3 X 5 cuboid is identical to a 3 X 5 X 6 cuboid if we allow rotations, but we are not normally able to rotate rooms!
Also the fact that the spider and fly are situtated in specific corners also suggests that rotations should be counted separately, but as stated here, rotations are considered identical when counting cuboids.
Can I humbly suggest that this part of the question be reworded, or the rotation issue specifically addressed in the problem description? (Reading the solution forum, others have suggested this change be made too.)
level = lambda number_solved: number_solved // 25
 euler
 Administrator
 Posts: 3313
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: Problem 086
I am sure that there is a deeper philosophical question in there somewhere: Are two rooms with identical dimensions the same?
But I take your point about the problem specifying "cuboid rooms" not cuboids, for which, arguably, the room measuring 6 x 5 x 3 (shown in the diagram) would appear quite different to a room measuring 6 x 3 x 5.
It doesn't seem easy to modify the wording without it becoming cumbersome, but how about changing the first part of
But I take your point about the problem specifying "cuboid rooms" not cuboids, for which, arguably, the room measuring 6 x 5 x 3 (shown in the diagram) would appear quite different to a room measuring 6 x 3 x 5.
It doesn't seem easy to modify the wording without it becoming cumbersome, but how about changing the first part of
to... ?By considering all cuboid rooms with integer dimensions, up to a maximum size of M by M by M, there are exactly 2060 cuboids for which the shortest route has integer length when M=100, and this is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions is 1975 when M=99.
Problem 86 (View Problem)We shall consider a cuboid with dimensions (A, B, C) to be congruent with (A, C, B), and all other permutation of A, B, and C.
It can be shown that there are exactly 2060 distinct cuboids with integer dimensions for which the shortest route is also integer, with A, B, C <= 100. For A, B, C <= M it turns out that M = 100 is the least value of M for which...
impudens simia et macrologus profundus fabulae
Re: Problem 086
I don't understand what was the problem with the former wording, but if after 6500 solvers you have to change the wording, I think you should use: [edited out by euler]. I'm not a native speaker, so I don't want to give you a whole sentence.
And technically a permutation must consist of different objects taken from a set. According to wiki "permutation of multisets" is the English name for permuting objects which can be identical.
Furthermore I think anyone who can understand permutations should not have a problem with understanding this question.
And technically a permutation must consist of different objects taken from a set. According to wiki "permutation of multisets" is the English name for permuting objects which can be identical.
Furthermore I think anyone who can understand permutations should not have a problem with understanding this question.
 euler
 Administrator
 Posts: 3313
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: Problem 086
I hope you don't mind, but I edited out the suggestion you made as I think it gives away too much about the best way to count the number of distinct arrangements.
The point being made, and I have I agree, was that a box measuring 30 cm by 10 cm by 8 cm is the same as a box measuring 30 cm by 8cm by 10cm; from any perspective it's the same box. But because the problem makes reference to "cuboid rooms" then the order of dimensions does matter; in the context of a room, up and down are fixed points of reference defined by gravity. That is why my alternative wording suggestion moves from the original context (which talks about a room) to the more abstract notion of a cuboid, where rearranging the order of the dimensions does not change it to a different box.
The point being made, and I have I agree, was that a box measuring 30 cm by 10 cm by 8 cm is the same as a box measuring 30 cm by 8cm by 10cm; from any perspective it's the same box. But because the problem makes reference to "cuboid rooms" then the order of dimensions does matter; in the context of a room, up and down are fixed points of reference defined by gravity. That is why my alternative wording suggestion moves from the original context (which talks about a room) to the more abstract notion of a cuboid, where rearranging the order of the dimensions does not change it to a different box.
impudens simia et macrologus profundus fabulae
Re: Problem 086
I'm sorry for that. It was years ago I solved this problem and forget it was probably part of the problem, as it is the most natural idea. I had a very nice idea for wording of this problem, but it would also give away too much, as you pointed it out.euler wrote:I hope you don't mind, but I edited out the suggestion you made as I think it gives away too much about the best way to count the number of distinct arrangements.
Re: Problem 086
Yes, thank you, this is my point.euler wrote:in the context of a room, up and down are fixed points of reference defined by gravity.
As it stands, the problem description gives no indication that we should consider cuboids with distinct dimensions only, and this was the only problem in the first ~100 that I needed this forum to correctly interpret the problem.
One other possibility could be:
"It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions..."
Kind Regards & Thanks.
level = lambda number_solved: number_solved // 25
 euler
 Administrator
 Posts: 3313
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: Problem 086
I'm glad that you brought it to our attention. I have modified the wording and I went with your more compact suggestion. Thank you, yourmaths.yourmaths wrote:... this was the only problem in the first ~100 that I needed this forum to correctly interpret the problem.
impudens simia et macrologus profundus fabulae