Brain-Teaser 480: [Hymn numbers]
From The Sunday Times, 9th August 1970 [link]
The church hymn board shows the numbers of the four hymns chosen for the service. There are 800 hymns in the hymn book in use. The numbers are shown by slipping rectangular cards along the four grooved ledges.
Each card has a digit printed on each side of it, and there are no nines, inverted sixes being used instead.
What is the smallest number of cards which must be kept in stock so that the numbers of any four different hymns can be shown on the board?
This puzzle was originally published with no title.
[teaser480]
S2T2 
Jim Randell 8:09 am on 23 May 2019 Permalink |
(A similar puzzle is given in H E Dudeney’s 1917 book Amusements In Mathematics [ link ]. See: Puzzle 426: The Hymn-Board Poser).
I assumed the hymns are numbered from 1 to 800.
I think it is easier to work out the digits required on the back of an envelope, but here is a program that does it.
It examines the hymn numbers, and finds sequences of 4 hymns that use a maximal number of copies of each card, and then totals the numbers for each type of card. It runs in 80ms.
from enigma import (defaultdict, irange, arg, printf) # maximum hymn number (N), and number of hymns on the board (K) N = arg(800, 0, int) K = arg(4, 1, int) printf("[N={N} K={K}]") # record maximum numbers m = defaultdict(lambda: defaultdict(list)) # consider hymn numbers for n in irange(1, N): # displayed as cards with '9' replaced by '6' s = str(n).replace('9', '6') # record the hymn numbers by the number of each digit required for d in set(s): m[d][s.count(d)].append(n) # count maximum numbers of each digit for 4 hymns T = 0 for d in '012345678': # collect K numbers with a maximal count ks = sorted(m[d].keys()) ns = list() t = 0 while True: n = K - len(ns) if n == 0: break k = ks.pop() xs = m[d][k][:n] t += k * len(xs) ns.extend(xs) printf("digit {d} -> {ns}; requires {t} copies") T += t printf("total copies = {T}")The minimum number of digits required is 82, and we put 2 digits on each card, so…
Solution: The minimum number of cards required is 41.
Examples of maximal sequences for each digit are:
There is no point making a card with the same digit on both sides, so we can make C(9, 2) = 36 cards corresponding to all pairs of different digits. This uses each digit 8 times, so leaves us with: 1, 2, 3, 4, 5, 6, 6, 6, 6, 7. And we can pair these up as: (1, 6), (2, 6), (3, 6), (4, 6), (5, 7), making a full set of pairs of different digits, and 5 duplicates.
To show that these cards are sufficient to make all possible combinations is a bit trickier, and something I might revisit later. It might be interesting to determine the smallest number of different pairing types (along with necessary duplicates) required to make a working set.
LikeLike