Sunday Times Teaser 2844 – Children’s Children

by Angela Newing

Published March 26 2017 (link)

The head teacher’s retirement celebration was attended by many former pupils. These included Adam, Brian, Colin and David, whose sons and grandsons had also attended the school — actually different numbers of grandsons for each of them, with Adam having the most. Their sons were Eric, Fred, George, Harry and Ivan, and the sons of the sons were John, Keith, Lawrence, Michael, Norman and Oliver.

Altogether Adam and Brian had sons Eric, Fred and one other; altogether Adam and Colin had sons George and one other; altogether Eric, George and Harry had sons Keith, Michael, Norman and one other; and altogether Harry and Ivan had sons Lawrence, Norman and one other.

The retirement gift was presented by the fathers of John’s and Oliver’s fathers: who were they?

3 Comments Leave one →

Brian Gladman permalink

Unfortunately this teaser is flawed as there are multiple solutions. This solution is a bit pedestrian and I might improve on it later but it is fast enough and completes in 9 milliseconds on my system.


from itertools import combinations, product

# create labels for the fathers, sons and grandsons
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O = range(15)

# lists of fathers, sons and grandsons
fathers = [A, B, C, D]
sons = [E, F, G, H, I]
grandsons = [J, K, L, M, N, O]

# find and store solutions for the sons of the fathers
f2sl = []
# choose the third son for the AB group (E, F, ?)
for s3 in (G, H, I):
  # the combined sons for the AB and CD groups 
  AB, CD = {E, F, s3}, {G, H, I}.difference([s3])
  # choose the number of sons for A
  for nA in range(4):
    # ... and who they are
    for c1 in combinations(AB, nA):
      sA, sB = set(c1), AB.difference(c1)
      # choose the number of sons for C
      for nC in range(3):
        # ... and who they are
        for c2 in combinations(CD, nC):
          sC, sD = set(c2), CD.difference(c2)
          # A and C combined have sons G and one other 
          AC = sA | sC
          if len(AC) == 2 and G in AC:
            # store this solution as a dictionary
            f2sl += [{A:sA, B:sB, C:sC, D:sD}]

# find and store solutions for the grandsons of the sons
s2gsl = []
# choose the fourth grandson for the EGH group
for g4 in (J, L, O):
  # the combined grandsons for the EGH and FI groups
  EGH, FI = {K, M, N, g4}, {J, L, O}.difference([g4]) 
  # choose the number of grandsons for E
  for nE in range(4):
    # ... and who they are
    for c1 in combinations(EGH, nE):
      gsE = set(c1)   
      # choose the number of grandsons for G
      for nG in range(5 - nE):
        # ... and who they are
        for c2 in combinations(EGH.difference(c1), nG):
          gsG = set(c2)     
          gsH = EGH - (gsE | gsG)
          # choose the number of grandsons for F
          for nF in range(3):
            # ... and who they are
            for c3 in combinations(FI, nF):
              gsF, gsI = set(c3), FI.difference(c3)
              # H and I combined have sons L, N and one other  
              HI = gsH | gsI
              if len(HI) == 3 and {L, N} < HI:
                # store this solution as a dictionary
                s2gsl += [{E:gsE, F:gsF, G:gsG, H:gsH, I:gsI}]
                
# convert numeric labels to letters 
z = lambda s: ''.join('ABCDEFGHIJKLMNO'[x] for x in sorted(s))

# save solutions
sol = []
# find all valid combinations of father -> son and son -> grandson
for f2s, s2gs in product(f2sl, s2gsl):
  # compile the results for father -> grandson
  f2gs = {f:set(sum((list(s2gs[s]) for s in sl), [])) for f, sl in f2s.items()}
  
  # all the fathers have different numbers of grandsons, A the most
  ngs = [len(f2gs[f]) for f in fathers]
  if len(set(ngs)) == 4 and ngs[A] == max(ngs):
    
    # J and O have different grandfathers
    if not any({J, O} <= x for x in f2gs.values()):
      # store the maps F->S, S->GS and F->GS (as lists in natural order)
      sol.append([[z(f2s[f]) for f in fathers],
                  [z(s2gs[s]) for s in sons], 
                  [z(f2gs[f]) for f in fathers]])

# output solutions
for f2s, s2gs, f2gs in sol:
  print(f'F->S: {f2s}, S->GS: {s2gs}, F->GS: {f2gs}')

from itertools import combinations, product

# create labels for the fathers, sons and grandsons

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O = range(15)

# lists of fathers, sons and grandsons

fathers = [A, B, C, D]

sons = [E, F, G, H, I]

grandsons = [J, K, L, M, N, O]

# find and store solutions for the sons of the fathers

f2sl = []

# choose the third son for the AB group (E, F, ?)

for s3 in (G, H, I):

# the combined sons for the AB and CD groups

AB, CD = {E, F, s3}, {G, H, I}.difference([s3])

# choose the number of sons for A

for nA in range(4):

# ... and who they are

for c1 in combinations(AB, nA):

sA, sB = set(c1), AB.difference(c1)

# choose the number of sons for C

for nC in range(3):

# ... and who they are

for c2 in combinations(CD, nC):

sC, sD = set(c2), CD.difference(c2)

# A and C combined have sons G and one other

AC = sA | sC

if len(AC) == 2 and G in AC:

# store this solution as a dictionary

f2sl += [{A:sA, B:sB, C:sC, D:sD}]

# find and store solutions for the grandsons of the sons

s2gsl = []

# choose the fourth grandson for the EGH group

for g4 in (J, L, O):

# the combined grandsons for the EGH and FI groups

EGH, FI = {K, M, N, g4}, {J, L, O}.difference([g4])

# choose the number of grandsons for E

for nE in range(4):

# ... and who they are

for c1 in combinations(EGH, nE):

gsE = set(c1)

# choose the number of grandsons for G

for nG in range(5 - nE):

# ... and who they are

for c2 in combinations(EGH.difference(c1), nG):

gsG = set(c2)

gsH = EGH - (gsE | gsG)

# choose the number of grandsons for F

for nF in range(3):

# ... and who they are

for c3 in combinations(FI, nF):

gsF, gsI = set(c3), FI.difference(c3)

# H and I combined have sons L, N and one other

HI = gsH | gsI

if len(HI) == 3 and {L, N} < HI:

# store this solution as a dictionary

s2gsl += [{E:gsE, F:gsF, G:gsG, H:gsH, I:gsI}]

# convert numeric labels to letters

z = lambda s: ''.join('ABCDEFGHIJKLMNO'[x] for x in sorted(s))

# save solutions

sol = []

# find all valid combinations of father -> son and son -> grandson

for f2s, s2gs in product(f2sl, s2gsl):

# compile the results for father -> grandson

f2gs = {f:set(sum((list(s2gs[s]) for s in sl), [])) for f, sl in f2s.items()}

# all the fathers have different numbers of grandsons, A the most

ngs = [len(f2gs[f]) for f in fathers]

if len(set(ngs)) == 4 and ngs[A] == max(ngs):

# J and O have different grandfathers

if not any({J, O} <= x for x in f2gs.values()):

# store the maps F->S, S->GS and F->GS (as lists in natural order)

sol.append([[z(f2s[f]) for f in fathers],

[z(s2gs[s]) for s in sons],

[z(f2gs[f]) for f in fathers]])

# output solutions

for f2s, s2gs, f2gs in sol:

print(f'F->S: {f2s}, S->GS: {s2gs}, F->GS: {f2gs}')

Tony Smith permalink

Brian
If ABCD had daughters some of the 6 grandsons could have 2 of ABCD as grandfather.
This would presumably need a more complex program (I have not tried very hard on pen and paper).

Reply
- Brian Gladman permalink
  
  Yes, your are right Tony, I don’t take that possibility into account. But I doubt that this is an intended feature of the teaser.
  
  Reply

Sunday Times Teaser 2844 – Children’s Children

by Angela Newing

Published March 26 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta