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

Home > Shapes
Cube Count Calculation (Posted on 2016-07-13) Difficulty: 3 of 5
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 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$

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information