A
rectangular cuboid has edges of lengths x, y and z. It is divided into x*y*z cubes each having dimension 1x1x1 by planes parallel to its faces.
A diagonal joins a vertex of the cuboid to the vertex furthest away from it.
Determine the total number of cubes that this diagonal intersects.
Every time the line passes through a plane separating one sheet of cubes and the next, a new cube is entered. Sometimes, if this is on an edge of two cubes this counts only one new cube even though two such planes are crossed. Likewise if the line is passing through a vertex of cubes, it's one new cube instead of three for the three planes being passed through.
We apply the inclusion/exclusion principle:
x + y + z - gcd(x,y) - gcd(y,z) - gcd(x,z) + gcd(x,y,z)
The following table illustrates this formula for all x, y, z through 10, showing only ascending order.
As an illustration, verifying the accuracy of the formula anecdotally, let's take 6 x 9 x 10.
From the fact there are 6 layers in one direction, new cubes are entered the following fractions of the way:
1/6 2/6 3/6 4/6 5/6 or
1/6 1/3 1/2 2/3 5/6
this amounts to a total of 6 cubes if it were just for this dimension, as we need to count the initial (starting) cube.
Then for the dimension with 9 layers:
1/9 2/9 3/9 4/9 5/9 6/9 7/9 8/9 or
1/9 2/3 1/3 4/3 8/9 2/3 7/9 8/9
* * two repeated from first, and so don't count
totally 9 cubes counting the first, but two are discounted by already passing cube-to-cube at that point. But also remember the first cube was already counted also, so there are really only 6 new cubes to be counted.
and then for the 10 layers:
1/10 2/10 3/10 4/10 5/10 6/10 7/10 8/10 9/10 or
1/10 1/5 3/10 2/5 1/2 3/5 7/10 4/5 9/10
*
so 8 more cubes are counted, as the initial cube and the one starting at point 1/2 way along the path have already been counted.
That's 6 + 6 + 8 = 20, and the formula does give 20 as tabulated below.
Consider a set of dimensions where the line does go through a vertex point: 4 x 6 x 10:
1/4 1/2 3/4 for the 4
1/6 1/3 1/2 2/3 5/6 for the 6
1/10 1/5 3/10 2/5 1/2 3/5 7/10 4/5 9/10 for the 10
The 1/2 point is the start of a new cube according to all the planes and is therefore a vertex point. No edges were traversed. Count 3 + 4 + 8 + the initial 1 = 16 and indeed the formula gives 16.
dimensions cube count
1 x 1 x 1 1
1 x 1 x 2 2
1 x 1 x 3 3
1 x 1 x 4 4
1 x 1 x 5 5
1 x 1 x 6 6
1 x 1 x 7 7
1 x 1 x 8 8
1 x 1 x 9 9
1 x 1 x10 10
1 x 2 x 2 2
1 x 2 x 3 4
1 x 2 x 4 4
1 x 2 x 5 6
1 x 2 x 6 6
1 x 2 x 7 8
1 x 2 x 8 8
1 x 2 x 9 10
1 x 2 x10 10
1 x 3 x 3 3
1 x 3 x 4 6
1 x 3 x 5 7
1 x 3 x 6 6
1 x 3 x 7 9
1 x 3 x 8 10
1 x 3 x 9 9
1 x 3 x10 12
1 x 4 x 4 4
1 x 4 x 5 8
1 x 4 x 6 8
1 x 4 x 7 10
1 x 4 x 8 8
1 x 4 x 9 12
1 x 4 x10 12
1 x 5 x 5 5
1 x 5 x 6 10
1 x 5 x 7 11
1 x 5 x 8 12
1 x 5 x 9 13
1 x 5 x10 10
1 x 6 x 6 6
1 x 6 x 7 12
1 x 6 x 8 12
1 x 6 x 9 12
1 x 6 x10 14
1 x 7 x 7 7
1 x 7 x 8 14
1 x 7 x 9 15
1 x 7 x10 16
1 x 8 x 8 8
1 x 8 x 9 16
1 x 8 x10 16
1 x 9 x 9 9
1 x 9 x10 18
1 x10 x10 10
2 x 2 x 2 2
2 x 2 x 3 4
2 x 2 x 4 4
2 x 2 x 5 6
2 x 2 x 6 6
2 x 2 x 7 8
2 x 2 x 8 8
2 x 2 x 9 10
2 x 2 x10 10
2 x 3 x 3 4
2 x 3 x 4 6
2 x 3 x 5 8
2 x 3 x 6 6
2 x 3 x 7 10
2 x 3 x 8 10
2 x 3 x 9 10
2 x 3 x10 12
2 x 4 x 4 4
2 x 4 x 5 8
2 x 4 x 6 8
2 x 4 x 7 10
2 x 4 x 8 8
2 x 4 x 9 12
2 x 4 x10 12
2 x 5 x 5 6
2 x 5 x 6 10
2 x 5 x 7 12
2 x 5 x 8 12
2 x 5 x 9 14
2 x 5 x10 10
2 x 6 x 6 6
2 x 6 x 7 12
2 x 6 x 8 12
2 x 6 x 9 12
2 x 6 x10 14
2 x 7 x 7 8
2 x 7 x 8 14
2 x 7 x 9 16
2 x 7 x10 16
2 x 8 x 8 8
2 x 8 x 9 16
2 x 8 x10 16
2 x 9 x 9 10
2 x 9 x10 18
2 x10 x10 10
3 x 3 x 3 3
3 x 3 x 4 6
3 x 3 x 5 7
3 x 3 x 6 6
3 x 3 x 7 9
3 x 3 x 8 10
3 x 3 x 9 9
3 x 3 x10 12
3 x 4 x 4 6
3 x 4 x 5 10
3 x 4 x 6 8
3 x 4 x 7 12
3 x 4 x 8 10
3 x 4 x 9 12
3 x 4 x10 14
3 x 5 x 5 7
3 x 5 x 6 10
3 x 5 x 7 13
3 x 5 x 8 14
3 x 5 x 9 13
3 x 5 x10 12
3 x 6 x 6 6
3 x 6 x 7 12
3 x 6 x 8 12
3 x 6 x 9 12
3 x 6 x10 14
3 x 7 x 7 9
3 x 7 x 8 16
3 x 7 x 9 15
3 x 7 x10 18
3 x 8 x 8 10
3 x 8 x 9 16
3 x 8 x10 18
3 x 9 x 9 9
3 x 9 x10 18
3 x10 x10 12
4 x 4 x 4 4
4 x 4 x 5 8
4 x 4 x 6 8
4 x 4 x 7 10
4 x 4 x 8 8
4 x 4 x 9 12
4 x 4 x10 12
4 x 5 x 5 8
4 x 5 x 6 12
4 x 5 x 7 14
4 x 5 x 8 12
4 x 5 x 9 16
4 x 5 x10 12
4 x 6 x 6 8
4 x 6 x 7 14
4 x 6 x 8 12
4 x 6 x 9 14
4 x 6 x10 16
4 x 7 x 7 10
4 x 7 x 8 14
4 x 7 x 9 18
4 x 7 x10 18
4 x 8 x 8 8
4 x 8 x 9 16
4 x 8 x10 16
4 x 9 x 9 12
4 x 9 x10 20
4 x10 x10 12
5 x 5 x 5 5
5 x 5 x 6 10
5 x 5 x 7 11
5 x 5 x 8 12
5 x 5 x 9 13
5 x 5 x10 10
5 x 6 x 6 10
5 x 6 x 7 16
5 x 6 x 8 16
5 x 6 x 9 16
5 x 6 x10 14
5 x 7 x 7 11
5 x 7 x 8 18
5 x 7 x 9 19
5 x 7 x10 16
5 x 8 x 8 12
5 x 8 x 9 20
5 x 8 x10 16
5 x 9 x 9 13
5 x 9 x10 18
5 x10 x10 10
6 x 6 x 6 6
6 x 6 x 7 12
6 x 6 x 8 12
6 x 6 x 9 12
6 x 6 x10 14
6 x 7 x 7 12
6 x 7 x 8 18
6 x 7 x 9 18
6 x 7 x10 20
6 x 8 x 8 12
6 x 8 x 9 18
6 x 8 x10 20
6 x 9 x 9 12
6 x 9 x10 20
6 x10 x10 14
7 x 7 x 7 7
7 x 7 x 8 14
7 x 7 x 9 15
7 x 7 x10 16
7 x 8 x 8 14
7 x 8 x 9 22
7 x 8 x10 22
7 x 9 x 9 15
7 x 9 x10 24
7 x10 x10 16
8 x 8 x 8 8
8 x 8 x 9 16
8 x 8 x10 16
8 x 9 x 9 16
8 x 9 x10 24
8 x10 x10 16
9 x 9 x 9 9
9 x 9 x10 18
9 x10 x10 18
10 x10 x10 10
DefDbl A-Z
Dim crlf$
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For x = 1 To 10
For y = x To 10
For z = y To 10
Text1.Text = Text1.Text & mform(x, "#0") & " x" & mform(y, "#0") & " x" & mform(z, "#0") & " "
cubes = x + y + z - gcd(x, y) - gcd(y, z) - gcd(x, z) + gcd(gcd(x, y), z)
Text1.Text = Text1.Text & mform(cubes, "##0") & crlf
Next
Next
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Function gcd(a, b)
x = a: y = b
Do
q = Int(x / y)
z = x - q * y
x = y: y = z
Loop Until z = 0
gcd = x
End Function
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
|
|
Posted by Charlie
on 2016-07-13 12:55:10 |
solution
