# 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]

### 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.