Brain-Teaser 443: Space ship
From The Sunday Times, 2nd November 1969 [link]
Says Bell at the pub:
I’ve been reading about a space ship. They fly the thing round playing the usual Cops and Robbers stuff, but the way they name the crew is interesting. Using A, B, C and so on right up to I, no gaps, they make, once only, every possible pair of different letters; so there’s no AA, BB and so on, and they take no notice of the order in a pair; s0 BC is the same as CB.
Four, including AD and BC, are on a list of officers and on that list no letter appears more than once. All the rest are just proles but do they have an A initial they call themselves A proles.
All proles work in shifts with the same number on each shift — not just two shifts; more than that — and at the end of a shift every prole hands over to another whose initials are each one farther on in the alphabet than his own, so AB would hand over to BC. Of course I is followed by A.
The shifts are picked so that when all shifts have been worked, every prole has been on duty once only.
Now you tell me who’s on the first shift. I want the biggest possible list. Easier than it looks. Usual prize. One pint.
Which A proles, if any, are on the first shift?
This puzzle is included in the book Sunday Times Brain Teasers (1974).
[teaser443]
GeoffR, 
Hugo, 
Frits, 
Ruud, 
Lise Andreasen are discussing. 
Pete Good and 
John Crabtree and 
S2T2 
Jim Randell 4:48 pm on 2 June 2024 Permalink |
A manual solution follows from a bit of analysis:
There are C(9, 2) = 36 names, and 4 officers, so there are 32 proles, which we must form into shifts, and we want the shifts to be as large as possible (and more than 2 of them).
So we are looking at:
If we start with a name we can consider the successor names until we get back to where we started, which forms the names into 4 groups:
Any officer (in bold) must be preceded by a member of the final shift and working backwards gives us members of previous shifts, giving a chain that is 8 long, which consists of 1 member for each of 8 shifts, or 2 members for each of 4 shifts.
Each officer must appear in a different group, and as we have used ABCD, we must choose 2 officers from EFGHI.
In the final group only EI is available to be an officer, so the remaining officer must be FH in the second group.
And so we can construct 4 shifts, each of 8 proles:
(And the two halves could be split to make 8 shifts, each of 4 proles = (1b, 2b, 3b, 4b, 1a, 2a, 3a, 4a)).
Solution: AE and AF are on the first shift.
Here is a program that performs the same steps:
It runs in 64ms. (Internal runtime is 351µs).
Run: [ @replit ]
from enigma import ( irange, subsets, diff, tuples, repeat, join, intersect, disjoint_union, cache, printf ) # letters letters = "ABCDEFGHI" # construct possible crew names names = list(x + y for (x, y) in subsets(letters, size=2)) # constrict successor names adj = dict(tuples(letters, 2, circular=1)) succ = cache(lambda xs: join((adj[x] for x in xs), sort=1)) # group names into successor chains def group(names): while names: # make the chain for the next name g = list(repeat(succ, names[0], 8)) yield g names = diff(names, g) # collect groups gs = list(group(names)) # choose an officer from each group def officers(gs, offs=[]): # are we done? if not gs: yield offs else: g = gs[0] # AD and BC are officers xs = intersect([{'AD', 'BC'}, g]) if not xs: # choose officers that don't include ABCD xs = list(x for x in g if not intersect(['ABCD', x])) # process the candidates for x in xs: offs_ = offs + [x] if disjoint_union(offs_): yield from officers(gs[1:], offs_) # choose the officers for offs in officers(gs): # find the first shift shift = set() for (g, off) in zip(gs, offs): j = g.index(off) shift.update(g[(j + i) % 9] for i in [-4, -8]) shift = sorted(shift) # output shifts 1-4 for k in irange(1, 4): printf("shift {k} = {shift}", shift=join(shift, sep=" ")) if k == 4: break # hand on to the next shift shift = list(succ(x) for x in shift)LikeLike