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.
rigel
Posts: 4
Joined: Mon Dec 17, 2012 9:27 pm

Problem 086

Post by rigel »

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?

rigel
Posts: 4
Joined: Mon Dec 17, 2012 9:27 pm

Re: Problem86 please clarify

Post by rigel »

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

User avatar
hk
Administrator
Posts: 10875
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 086

Post by hk »

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

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 086

Post by TheEvil »

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

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 086

Post by TripleM »

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.

rigel
Posts: 4
Joined: Mon Dec 17, 2012 9:27 pm

Re: Problem 086

Post by rigel »

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) ?
Attachments
results.rar
Different cuboids
(10.91 KiB) Downloaded 104 times

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 086

Post by TripleM »

rigel wrote:A cuboid with sides 6,7,1 also has a shortest path of 10.
As TheEvil mentioned above - no, it does not.

rigel
Posts: 4
Joined: Mon Dec 17, 2012 9:27 pm

Re: Problem 086

Post by rigel »

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

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 086

Post by RishadanPort »

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
Image

Rishada is the gateway to free trade—but the key will cost you.

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 086

Post by RishadanPort »

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

Rishada is the gateway to free trade—but the key will cost you.

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 086

Post by RishadanPort »

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
Image

Rishada is the gateway to free trade—but the key will cost you.

User avatar
yourmaths
Posts: 29
Joined: Mon Aug 25, 2014 11:00 am

Re: Problem 86 clarification

Post by yourmaths »

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.)
level = lambda number_solved: number_solved // 25
Image

User avatar
euler
Administrator
Posts: 3313
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: Problem 086

Post by euler »

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)
Image
impudens simia et macrologus profundus fabulae

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 086

Post by TheEvil »

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

User avatar
euler
Administrator
Posts: 3313
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: Problem 086

Post by euler »

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.
Image
impudens simia et macrologus profundus fabulae

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 086

Post by TheEvil »

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

User avatar
yourmaths
Posts: 29
Joined: Mon Aug 25, 2014 11:00 am

Re: Problem 086

Post by yourmaths »

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.
level = lambda number_solved: number_solved // 25
Image

User avatar
euler
Administrator
Posts: 3313
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: Problem 086

Post by euler »

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.
Image
impudens simia et macrologus profundus fabulae

Post Reply