### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

13 March 2017

Posted by on **From New Scientist #2280, 3rd March 2001** [link]

On each anniversary of its foundation my company asks a local artist to make a glass sculpture consisting of a three-by-three arrangement of squares of glass. On the first anniversary just one of the squares had to be red, the rest being blue. On the second anniversary two of the nine had to be red, the rest blue, etc. Before making the final work the artist produces scale models of all the possibilities so that we can choose the one we like best. For economy she does not make any two that look the same when rotated or turned over. So, for example, her first anniversary models were as illustrated, involving a total of just three red squares:

For our current anniversary she has again produced scale models of all the possibilities, and for these she has had to make more than one hundred small red squares of glass.

Which anniversary is it, and precisely how many small red squares does she need?

[enigma1124]

Advertisements

%d bloggers like this:

The grid is fairly small, so programatically we can just generate all possible colourings of the grid with

nred squares, and then combine colourings that are the same by rotation/reflection.This Python program examines the number of red and blue squares for anniversaries from 0 to 9. It runs in 57ms.

Solution:It is the fifth anniversary. 115 red squares are required.Of course the numbers of red and blue tiles required for anniversary

nare the same as the number of blue and red tiles required for anniversary9 – n.Here’s the output of the program, with the number of different grids and the number of red and blue tiles required for each anniversary:

On the first anniversary there are 9 configurations, including reflexions and/or rotations.

On the second, 36 which is the 8th triangular number = 8×9/2!.

On the third, 84 which is the 7th tetrahedral number = 7×8×9/3!.

On the fourth, 126 = 6×7×8×9/4!, which I suppose we can call the 6th four-dimensional tetrahedral number.

Continuing in like manner we find (not surprisingly) that the numbers continue 126, 84, 36, 9, 1.

The number of distinct ways of selecting M items in an N*N grid, unique up to rotation and reflection, is a well known problem.

This stackexchange question sketches the explanation of the solution, from which I have produced the code below, although I don’t claim to fully follow the derivation.

Of course, for this problem, the solutions for even values of N aren’t needed, but I have used the function in another program to verify that it correctly reproduces OEIS sequence A019318.

That’s neat. I ended up on that page on StackExchange yesterday, but got lost in all the talk of the Orbit-counting Lemma, the Cycle Index Theorem, and Pólya enumeration, and eventually decided that it was a bit of overkill for the 3×3 grid anyway.

But thanks for extracting the formulae. Here’s a version that uses the

Polynomialclass from theenigma.pylibrary, which saves having to pull inSymPy, so is a bit quicker.(I added the polynomial routines after the discussion on generating polynomials for

Pizza Puzzle).The size of grid

Ncan be specified on the command line (defaults to 3) and the number of different grids (patterns), red tiles and blue tiles are given for eachn = 0..N².The number of grids found corresponds with OEIS A054252.

For the

N=3case it runs in 42ms.