Project Euler Forum

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?

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?!

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.

rigel wrote:6,7,1 -> 6*6 + (7+1)*(7+1) = 10*10

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.

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.

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

rigel wrote:A cuboid with sides 6,7,1 also has a shortest path of 10.

As TheEvil mentioned above - no, it does not.

Aha, thanks.
So I understood the problem correctly, the calculations were wrongly assumed.

However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.

Isn't this incorrect, as actually there are six "shortest" path candidates for any given cuboid?

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

I believe I can answer my own question -- In assuming that the symmetry of a path,
is not considered as a unique path candidate.

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

Tommy137 wrote:

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.

Problem 86 is by far the most difficult problem to understand out of the first ~100 problems.

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

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

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.

to... ?

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

Problem 86 (View Problem)

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.

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.

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.

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:in the context of a room, up and down are fixed points of reference defined by gravity.

Yes, thank you, this is my point.

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.

yourmaths wrote:... this was the only problem in the first ~100 that I needed this forum to correctly interpret the problem.

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.

What happened to the diagram for problem 86?

It should be back again.
For some mysterious reason one of the characters in the file name was in uppercase while lowercase was expected.