Brain-Teaser 462: [Crocodiles]
From The Sunday Times, 5th April 1970 [link]
A friend of mine, who is headmistress of a small school, sends her fifteen girls for a walk every day in a crocodile of threes. She told me that she had for long been trying, unsuccessfully, to arrange that no two girls ever walked together in a trio more than once during a whole week; and she added that, denoting the girls by the first fifteen letters of the alphabet, she wanted A to walk with B and C on Sunday, and with the consecutive pairs of letters for the rest of the week, finishing with N and O on Saturday.
“Well”, I replied, “if four more trios were specified, I could find a unique solution for your problem. But, if you want to work it out yourself, I shall help you by telling you B’s and C’s partners throughout the week:
Mon: BHJ, CMN
Tue: BIK, CLO
Wed: BLN, CEF
Thu: BMO, CDG
Fri: BDF, CIJ
Sat: BEG, CHKFurthermore, F, who is a bit of a snob as regards those lower in the alphabetical order, will be relieved to find that she does not have to walk with the two available furthest from herself in that order until Saturday.
Now, you should be able to tell me with whom D walks on Sunday and on Wednesday.”
This puzzle was originally published with no title.
[teaser462]
S2T2 
Jim Randell 9:31 am on 9 March 2019 Permalink |
I’ve marked this puzzle as flawed for two reasons. Firstly when the solution was published it was acknowledged that there was not a unique answer, and secondly I’m not really sure that the constraint about F makes sense.
My first thought was that it means that F partnered N and O (the two furthest along from F alphabetically) on Saturday, but N and O are already partnering A on Saturday. It does say the “two available furthest from herself”, so perhaps it means F partners L and M (the next furthest alphabetically), but L and M were partnering A on Friday, so can’t appear in a grouping on Saturday. In fact, according to the information we are given, the groups: ANO, BEG, CHK are already defined for Saturday, leaving DFIJLM, to be formed into viable groups. So maybe we are meant to partner F with J and M. This is the interpretation I ended up using, and it does generate the published answer(s). But I think there is still a problem (see below).
This Python 3 program solves the puzzle recursively in 865ms.
Run: [ @repl.it ]
from itertools import combinations from enigma import unpack, partitions, join, update, flatten, printf # check no pairs are repeated def pairs(ps, ts): ps = ps.copy() for t in ts: for p in combinations(t, 2): if p in ps: return None ps.add(p) return ps # complete the groups, with pairs ps already used def solve(groups, ps): # find days with missing groups gs = list((k, vs) for (k, vs) in groups.items() if len(vs) < 5) if not gs: yield groups else: # choose the day with the fewest missing groups (k, vs) = min(gs, key=unpack(lambda k, vs: 5 - len(vs))) # form the remaining kids into groups for ts in partitions(kids.difference(*vs), 3): ts = list(join(sorted(t)) for t in ts) ps2 = pairs(ps, ts) if ps2: yield from solve(update(groups, [(k, sorted(vs + ts))]), ps2) # the kids kids = set("ABCDEFGHIJKLMNO") # the groupings we are given groups = dict( Sun=["ABC"], Mon=["ADE", "BHJ", "CMN"], Tue=["AFG", "BIK", "CLO"], Wed=["AHI", "BLN", "CEF"], Thu=["AJK", "BMO", "CDG"], Fri=["ALM", "BDF", "CIJ"], Sat=["ANO", "BEG", "CHK", "FJM"], ) # check no pairing is duplicated among the given groups ps = pairs(set(), flatten(groups.values())) assert ps # solve for the remaining groups for gs in solve(groups, ps): # find the group on day d for child x get = lambda d, x: list(t for t in gs[d] if x in t)[0] # a measure for F's partners fn = lambda d: sum(int(x, 25) - 9 for x in get(d, 'F') if x != 'F') # output the groups for (k, vs) in gs.items(): printf("{k}: {vs} [{m}]", vs=join(vs, sep=" "), m=fn(k)) # D's groups on Sun and Wed printf("[D] Sun={S} Wed={W}", S=get("Sun", 'D'), W=get("Wed", 'D')) printf()Solution: There are two possible solutions: (1) D partners H and O on Sunday, and K and M on Wednesday; (2) D partners K and N on Sunday, and J and O on Wednesday.
The full groupings look like this:
And now we run into the problem with F, their “worst” day is suppose to be Saturday, when they partner J and M.
But in the first case, F partners K and N on Sunday, each of these is one step further along the alphabet than Saturday’s partners, so is surely a less desirable situation. If we just sum the positions in the alphabet of her partners to get a measure of “badness”, the partnering I and O on Monday is also less desirable than Saturday.
Using the same measure we find that in the second case, Sunday, Monday and Thursday all score as badly as Saturday for F.
And if we use other measures (e.g. looking for the “best” of the two partners, or the “worst”) we find that in neither of these scenarios does Saturday does provide F with their worst partnering of the week.
Further, if we consider all possible pairings for F on Saturday (and not a specific one) we find it is not possible to solve the puzzle so F has her worst day on Saturday.
So maybe it would have just been better to say: “F doesn’t get on with her sisters, J and M. So she will be relieved to find she does not have to walk with them until Saturday”. Or just come straight out with it: “F walked with J and M on Saturday”. But that still leaves the problem of the two answers. Although an extra condition disallowing one of the groupings in one of the answers would sort that out.
LikeLike