Enigmatic Code

Programming Enigma Puzzles

Enigma 1262: Brickwork

From New Scientist #2418, 25th October 2003 [link]

George asked his son to imagine a 3 × 4 rectangle marked off in unit squares.

“Following the gridlines, how many rectangles (including squares) of all possible sizes, positions and orientations can you see?”

“Sixty.”

“Correct.  Now imagine a 2 × 3 × 4 brick marked off internally into unit cubes.  Following the grid markings, how many cuboids of all possible sizes, positions and orientations can you see?”

“One hundred and eighty!”

“Right again.  Now imagine I have a larger brick of integer dimensions for which the number of embedded cuboids is 105105.”

“Er, yes.”

“What are the dimensions of the brick?”

[enigma1262]

Advertisements

One response to “Enigma 1262: Brickwork

  1. Jim Randell 19 January 2015 at 8:17 am

    If we consider an n dimensional shape, that has s sub-shapes. If we then use it to generate an (n+1)-dimensional shape, we see that if the extra dimension is of size 1 then there are also s sub-shapes of the the (n+1)-dimensional shape. If the extra dimension is of size 2 then there are s sub-shapes with size 2 in the new dimension and 2s sub-shapes with size 1 in the new dimension, giving 3s sub-shapes overall. Following this reasoning we see that if we add a new dimension to the original shape with size k, then we end up with T(k)s sub-shapes of the (n+1) dimensional shape. (If maybe easier to see this if you consider going from 1-dimension to 2-dimensions, or 2-dimensions to 3-dimensions).

    So in general the number of sub-shapes of an n-dimensional shape is the product of the triangular numbers that measure each dimension, and in particular for 3-dimensional blocks with dimensions of x, y and z, the number of sub-blocks is:

    S(x, y, z) = T(x)T(y)T(z).

    And this fits with the examples given:

    S(3, 4) = T(3)×T(4) = 60
    S(2, 3, 4) = T(2)×T(3)×T(4) = 180.

    This Python program finds the x, y, z dimensions of a block consisting of 105105 sub-blocks in 33ms

    from itertools import count
    from enigma import is_triangular, T, printf
    
    N = 105105
    
    # assume x <= y <= z
    for x in count(1):
      Tx = T(x)
      (TyTz, r) = divmod(N, Tx)
      if TyTz < Tx: break
      if r > 0: continue
    
      for y in count(x):
        Ty = T(y)
        (Tz, r) = divmod(TyTz, Ty)
        if Tz < Ty: break
        if r > 0: continue
        z = is_triangular(Tz)
        if z is None: continue
    
        printf("x={x} y={y} z={z}")
    

    Solution: The dimensions of the block are 6 × 10 × 13.

    To solve the problem manually we see that we want:

    T(x) × T(y) × T(z) = x(x+1)/2 × y(y+1)/2 × z(z+1)/2 = 105105

    x(x+1) × y(y+1) × z(z+1) = 2×2×2×105105 = 2×2×2×3×5×7×7×11×13

    Re-writing the product as the product of thee adjacent pairs of integers:

    2×2×2×105105 = (6×7)×(10×11)×(13×14)

    hence: x=6, y=10, z=13.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: