**From New Scientist #1417, 16th August 1984** [link]

Picnicaria’s independence is to be celebrated by a triumph of technological virtuosity, a Cubic stamp-sheet, which you are asked to design. Let me explain. The “sheet” will look like a cubic die, with a square postage-stamp forming each of the six faces, and with perforations along each of the 12 edges. The whole object of the exercise is to enable the customer to stamp a letter or parcel with a postage of any whole number pence from 1 up to *N* by tearing along suitable perforations and thus getting a *connected* set of one or more stamps which add up to exactly the right amount. *N* is to be made as large as possible.

How large can *N* be? And what values have the stamps on the various faces?

(The easiest way to specify a layout is to give the values of opposite faces: e.g. a layout like that of an ordinary die is “1/6, 2/5, 3/4”, giving *N*=21).

[enigma270]

### Like this:

Like Loading...

Of the 63 possible non-empty subsets of the stamps the only non-connected ones are the 3 sets of opposite faces. So that leaves 60 connected subsets. So the maximum possible values for N is 60 (when each subset has a different value).

This Python 3 program works down from stamps with a total value of 60. It runs in 5.9s

Solution:The largest value for N is 53. The four possible cubes are 1/2 + 3/7 + 13/27; 1/6 + 2/4 + 13/27; 1/26 + 2/4 + 6/14; 1/26 + 2/12 + 4/8.For a total value of stamps t > 60 (actually t ≥ 56) the best we can manage is subsets with values from 1 to 27 using an arrangement of 4/8 + 2/12 + 1/(t-27).

I had abandoned my attempt at a recursive solution because it got too complicated, and was too slow. But inspired by Brian’s approach I’ve resurrected it. My recursive step is somewhat more complicated than Brian’s, but the code in

update()to filter out non-canonical orderings brings it back to running in 5.5s – slightly faster than my code that works by considering possible totals (and you don’t have to worry about the case where t>N).After an Easter break, how about 55 with 1/2, 3/7 and 14/28?

Unfortunately it’s not possible to make 42 from a connected subset of 1/2 + 3/7 + 14/28, so this arrangement corresponds to N=41.

Yes Jim, thanks – I realised that too but too late!

As a matter of interest, the maximum for 6 stamps also corresponds to the maximum you can score with 3 darts with a choice of 6 numbers with these 2 sets.

1, 3, 7, 9, 19, 24 and 1, 4, 6, 14, 17, 29