Problem 086

[Francky]

EDIT : removed
No problem.

[hk]

I got a very simple proof to find the minimum between
...
I'll remove this if it's a spoiler. I don't know. Tell me, thanks.

This forum is:

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions.

Posted without any reference to a PE problem I wouldn't see a problem.
Posted with reference to this problem I think it is a hint.

Edit:

EDIT : removed
No problem.

Thanks

[ScoopyPuppy2]

There are two things that trouble me in the problem statement:

• "integer" is a noun, so I would say (I am not a native) that "shortest route is not always integer" should read "shortest route is not always an integer" or "shortest route is not always integral"
• why does it state that "there are up to three "shortest" path candidates for any given cuboid"? I would say there are six. Granted, they go by pairs, as the formula for the distance shows, still, I count six of them: the spider can choose any of the three faces that "touches" it, but for each of these faces, there are two edges on the other side that the spider can choose. In the case of a cube, those six paths are all "smallest".

Did I miss something? I guess I do, since the problem is old now

[thundre]

There are two things that trouble me in the problem statement:

• "integer" is a noun, so I would say (I am not a native) that "shortest route is not always integer" should read "shortest route is not always an integer" or "shortest route is not always integral"

I think that's right, from a grammatical standpoint. If the authors were English professors, I'd bother them until they changed it. But this very minor grammatical error doesn't seem to stop people from solving the problem.

• why does it state that "there are up to three "shortest" path candidates for any given cuboid"? I would say there are six. Granted, they go by pairs, as the formula for the distance shows, still, I count six of them: the spider can choose any of the three faces that "touches" it, but for each of these faces, there are two edges on the other side that the spider can choose. In the case of a cube, those six paths are all "smallest".

I think anybody who has a chance of solving this problem understands that cuboids are symmetric. Mathematically, there are at most 3 values to check. If you changed it to 6, you'd probably want to draw the other shortest path on the diagram, which would make it harder to visualize. I don't think it would help.

Good luck with your solution!

[ScoopyPuppy2]

Thanks for the reply!

• why does it state that "there are up to three "shortest" path candidates for any given cuboid"? I would say there are six. Granted, they go by pairs, as the formula for the distance shows, still, I count six of them: the spider can choose any of the three faces that "touches" it, but for each of these faces, there are two edges on the other side that the spider can choose. In the case of a cube, those six paths are all "smallest".

I think anybody who has a chance of solving this problem understands that cuboids are symmetric. Mathematically, there are at most 3 values to check. If you changed it to 6, you'd probably want to draw the other shortest path on the diagram, which would make it harder to visualize. I don't think it would help.

I agree. Yet the wording puzzled me. There are definitely up to six shortest path candidates! But since they go by pair, only three need to be checked.

Good luck with your solution!

I had solved it, thanks!

[hk]

There are two things that trouble me in the problem statement:

• "integer" is a noun, so I would say (I am not a native) that "shortest route is not always integer" should read "shortest route is not always an integer" or "shortest route is not always integral"

I think that's right, from a grammatical standpoint. If the authors were English professors, I'd bother them until they changed it. But this very minor grammatical error doesn't seem to stop people from solving the problem.

Always happy to learn something.
However, nitpickingwise, shouldn't we talk about the length of the shortest route then?
"A route that is integer" or "an integral route" seem rather pointless to me too.

[ScoopyPuppy2]

Hi hk,

However, nitpickingwise, shouldn't we talk about the length of the shortest route then?
"A route that is integer" or "an integral route" seem rather pointless to me too.

FWIW, I agree.

[frogjg2003]

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?

I'm getting 34 for 15, 66 for 20, and 111 for 25. Can I PM my code to someone so they can take a look at it?

[Marcus_Andrews]

Either way, right now it's grammatically incorrect. "...the shortest route is not always integer" should be changed to "...the shortest route is not always an integer" at the very least.

Regarding "integral": One person's pedantic distinction is another person's thorough accuracy. While "integral" is a valid adjective to use here, it's not as widely known as the other obvious definition of "integral," so sometimes it's best to avoid the confusion. While I think a case could be made for either term, I'd rather go with the definition that best renders the problem description as clear as possible for the greatest number of people -- so I think "an integer" is perfectly fine.

There are two things that trouble me in the problem statement:

• "integer" is a noun, so I would say (I am not a native) that "shortest route is not always integer" should read "shortest route is not always an integer" or "shortest route is not always integral"

I think that's right, from a grammatical standpoint. If the authors were English professors, I'd bother them until they changed it. But this very minor grammatical error doesn't seem to stop people from solving the problem.

Always happy to learn something.
However, nitpickingwise, shouldn't we talk about the length of the shortest route then?
"A route that is integer" or "an integral route" seem rather pointless to me too.

[thundre]

I'm getting 34 for 15, 66 for 20, and 111 for 25. Can I PM my code to someone so they can take a look at it?

Do your results up to M=9 match what DDgeva and Jaap posted above?

[hk]

Either way, right now it's grammatically incorrect. "...the shortest route is not always integer" should be changed to "...the shortest route is not always an integer" at the very least.

Regarding "integral": One person's pedantic distinction is another person's thorough accuracy. While "integral" is a valid adjective to use here, it's not as widely known as the other obvious definition of "integral," so sometimes it's best to avoid the confusion. While I think a case could be made for either term, I'd rather go with the definition that best renders the problem description as clear as possible for the greatest number of people -- so I think "an integer" is perfectly fine.

That's all very nice but in the next sentence, that is now three lines long already it reads:
"By considering all cuboid rooms with integer dimensions, "
So if we abolish "integral" we would have to write something like:
"By considering all cuboid rooms with dimensions that are integers,...."
or
"By considering all cuboid rooms with dimensions being integers,...."

which sounds pretty awkward to me and not very readable.
So why not let a possibly grammatically incorrect but perfectly clear description as it is?

[hk]

Actually if we insist that "integer" is a noun, I think this whole Wikipedia article should get a major rewrite:
http://en.wikipedia.org/wiki/Integer_triangle

To begin with the title: Integer triangle.
I can't grammatically make any chocolate of this if "integer" is considered a noun.
Even stronger with a sentence like:
"A Heronian triangle, also known as a Heron triangle or a Hero triangle, is a triangle with integer sides and integer area."
and more sentences like that in the same article.
Could it be that common usage has developed in the direction that "integer" can also be used in other ways than as a noun?

[Marcus_Andrews]

Either way, right now it's grammatically incorrect. "...the shortest route is not always integer" should be changed to "...the shortest route is not always an integer" at the very least.

Regarding "integral": One person's pedantic distinction is another person's thorough accuracy. While "integral" is a valid adjective to use here, it's not as widely known as the other obvious definition of "integral," so sometimes it's best to avoid the confusion. While I think a case could be made for either term, I'd rather go with the definition that best renders the problem description as clear as possible for the greatest number of people -- so I think "an integer" is perfectly fine.

That's all very nice but in the next sentence, that is now three lines long already it reads:
"By considering all cuboid rooms with integer dimensions, "
So if we abolish "integral" we would have to write something like:
"By considering all cuboid rooms with dimensions that are integers,...."
or
"By considering all cuboid rooms with dimensions being integers,...."

which sounds pretty awkward to me and not very readable.
So why not let a possibly grammatically incorrect but perfectly clear description as it is?

Because it's a slightly different usage.

"Integer" in itself is not technically an adjective but a noun. "Integral" is an adjective but usually confuses people, so "integer" tends to be used as a descriptive noun -- an "attributive noun" or "noun adjunct." See more here.

For instance, "School uniform" is fine but you wouldn't say "Consider all uniforms that are school(s)" in the same way I could reference "green apples" with "Consider all apples that are green."

To native English speakers, "By considering all cuboid rooms with integer dimensions" sounds completely fine because "integer" here is an attributive noun. But "...the shortest route is not always integer" sounds incorrect.

[hk]

Thanks for your explanation.
So I presume that:
"and the shortest route doesn't always have integer length." is correct?

[Marcus_Andrews]

Thanks for your explanation.
So I presume that:
"and the shortest route doesn't always have integer length." is correct?

I think this is OK to use.

[hk]

Changed it that way.

[hk]

Thanks.
I'm still a bit baffled why:
"there are exactly 2060 cuboids for which the shortest distance is integer when M=100," doesn't raise any thorn.

[Marcus_Andrews]

Thanks.
I'm still a bit baffled why:
"there are exactly 2060 cuboids for which the shortest distance is integer when M=100," doesn't raise any thorn.

That one falls victim to the same issue as the previous case, yes. If you wanted to keep the language consistent with the recent edit, you could use "...there are exactly 2060 cuboids for which the shortest distance has an integer length when M=100" or something to that effect.

[hk]

I made it:
"for which the shortest route has integer length when M=100", because I'm not that happy with a distance that has a length.

[Marcus_Andrews]

Sounds good -- thanks!