Page 1 of 5
Problem 086
Posted: Wed Aug 06, 2008 10:43 pm
by 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?
Re: Problem 86 clarification
Posted: Wed Aug 06, 2008 11:31 pm
by Tommy137
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.
Re: Problem 086
Posted: Wed Jan 14, 2009 5:07 pm
by 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.
Re: Problem 086
Posted: Wed Jan 14, 2009 6:26 pm
by Eigenray
The problem talks about counting cuboids, not paths.
Re: Problem 086
Posted: Tue Oct 27, 2009 8:32 pm
by 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
Re: Problem 086
Posted: Tue Oct 27, 2009 8:46 pm
by 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
]
Re: Problem 086
Posted: Fri Jan 22, 2010 6:48 pm
by 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.
Re: Problem 086
Posted: Fri Jan 22, 2010 7:20 pm
by harryh
Good spot ! Wording amended to:
By considering all cuboid rooms with integer dimensions, up to a maximum size ...
Re: Problem 086
Posted: Fri Aug 06, 2010 12:16 pm
by MaJJ
Jochen_P wrote: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?
Re: Problem 086
Posted: Fri Aug 06, 2010 1:15 pm
by jaap
M=1: 1 cuboid,
M=2: 1+3 = 4 cuboids
M=3: 1+3+6 = 10 cuboids
...
Re: Problem 086
Posted: Fri Aug 06, 2010 1:32 pm
by 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
Re: Problem 086
Posted: Fri Aug 06, 2010 4:03 pm
by jaap
MaJJ wrote: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.
Re: Problem 086
Posted: Fri Aug 06, 2010 6:03 pm
by MaJJ
jaap wrote:MaJJ wrote: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
Re: Problem 086
Posted: Wed Oct 13, 2010 3:38 pm
by EnDorphin
jaap wrote:MaJJ wrote: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.]
Re: Problem 086
Posted: Tue Mar 08, 2011 7:48 am
by 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?
Re: Problem 086
Posted: Tue Mar 08, 2011 8:14 am
by jaap
DDgeva wrote: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).
DDgeva wrote:for M=9 I'm getting the following 12 solutions:
You are missing some - 2 2 3 and 6 6 9.
Re: Problem 086
Posted: Tue Mar 08, 2011 9:23 am
by 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?
Re: Problem 086
Posted: Tue Mar 08, 2011 10:28 am
by jaap
Those numbers are all correct.
Re: Problem 086
Posted: Tue Mar 08, 2011 10:43 am
by DDgeva
jaap wrote: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.
Re: Problem 086
Posted: Tue Mar 08, 2011 12:07 pm
by jaap
DDgeva wrote: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.
DDgeva wrote: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.