All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Cube Count Calculation (Posted on 2016-07-13)
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.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution Comment 1 of 1
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\$

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

 Search: Search body:
Forums (0)