Problem 086

[petrw1]

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]

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]

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.

[Eigenray]

The problem talks about counting cuboids, not paths.

[Jochen_P]

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]

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]

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]

Good spot ! Wording amended to:

By considering all cuboid rooms with integer dimensions, up to a maximum size ...

[MaJJ]

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]

M=1: 1 cuboid,
M=2: 1+3 = 4 cuboids
M=3: 1+3+6 = 10 cuboids
...

[MaJJ]

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]

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.

[MaJJ]

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]

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]

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]

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

for M=9 I'm getting the following 12 solutions:

You are missing some - 2 2 3 and 6 6 9.

[DDgeva]

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]

Those numbers are all correct.

[DDgeva]

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]

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.

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.