Enigmatic Code

Programming Enigma Puzzles

Enigma 365: Men of letters

From New Scientist #1514, 26th June 1986 [link]

Six Professors, A, B, C, D, E and F, are the guest speakers at a philosophy conference at St Gadarene’s. So that they should not be confused with the audience they are given labels A, B, C, D, E and F by the organisers. Unfortunately, none of them ended up with the right label. On the way up to the podium, Professor A asks the man wearing the letter B: “Are you Professor C?”

“No. Why do you ask? You’re not wearing C. But Professor C ought to swap labels with Professor F, for then one of them would have the right label. And in case you were wondering, I’m not D either.”

“I’ve never seen such disarray. It would be quite impossible to choose a single pair from the six of us in such a way that one of the two might truthfully say to the other: ‘We two have each other’s labels’.”

“Well, it could be worse. At least the company can be divided into two groups, each of which would sport the same letters as the professors it contains. What’s more, each group would have a label with a vowel on it. Now please leave me alone, I’m a solipsist.”

By this time the applause had died down and it was decided that the professors should present their papers in the alphabetical order of the labels they each wore.

I wasn’t too happy with the paper about utilitarianism. I enjoyed “Why pragmatism doesn’t work”. But most of all I enjoyed deducing the names of the professors from their labels.

Can you list the names of the six professors in the order in which they presented their papers?

[enigma365]

Advertisements

2 responses to “Enigma 365: Men of letters

  1. Jim Randell 7 October 2016 at 7:31 am

    This Python code examines all possible assignments of labels to the professors. It runs in 39ms.

    from itertools import permutations
    from enigma import irange, join, printf
    
    # indices for the labels
    labels = (A, B, C, D, E, F) = irange(0, 5)
    
    # s is a sequence mapping professors to labels,
    # if X is the name of a professor then:
    # "X is wearing Y" -> m[X] == Y
    def check(m):
    
      # make the reverse map
      r = [None] * len(m)
      for (i, j) in enumerate(m):
        # ensure it is a derangement
        if i == j: return
        r[j] = i
    
      # "A asks the man wearing B: 'Are you C?'"...
      # so: A is not wearing B
      if m[A] == B: return
    
      # ..."No... You (A) are not wearing C" ...
      # so: man wearing B is not C
      if r[B] == C: return
      # and: A is not wearing C
      if m[A] == C: return
    
      # ... "if C swapped labels with F one of them would have the right label" ...
      # so: either C is wearing F, or F is wearing C
      if not((m[C] == F) ^ (m[F] == C)): return
    
      # ... "and I'm not D" ...
      # so: man wearing B is not D
      if r[B] == D: return
    
      # ... "no-one can say: 'we two have each other's labels'" ...
      # so: there are no 2-cycles
      if any(m[x] == i for (i, x) in enumerate(m)): return
    
      # but there are 2 3-cycles, one containing A, one containing E
      if not(m[m[m[A]]] == A and m[m[m[E]]] == E): return
      if len(set((A, m[A], m[m[A]], E, m[E], m[m[E]]))) != 6: return
    
      # return the reverse map
      return r
    
    # consider possible derangements
    for m in permutations(labels):
      r = check(m)
      if r is not None:
        n = 'ABCDEF'
        printf("p2n={m}, p2n={r}", m=join(n[x] for x in m), r=join(n[x] for x in r))
    

    Solution: The order in which the professors gave their papers is: C, E, F, B, D, A.

    Instead of considering all 720 permutations of A, B, C, D, E, F, in this particular case we are told that the derangement we are looking for consists of two 3-cycles with A and E in separate cycles. So we can just consider the 24 permutations of B, C, D, F instead.

    It doesn’t make a great deal of difference if we are looking at the problem programatically, but here is a solution that uses this refinement:

    from itertools import permutations
    from enigma import irange, join, printf
    
    # indices for the labels
    (A, B, C, D, E, F) = irange(0, 5)
    
    def output(s):
      return join('ABCDEF'[s[x]] for x in (A, B, C, D, E, F))
    
    # suppose the 3-cycles are (A p q) (E r s)
    # where p, q, r, s are B, C, D, F in some order
    for (p, q, r, s) in permutations((B, C, D, F)):
    
      # make the checks...
      if any((
    
        # "A is not wearing B"
        p == B,
    
        # "wearer of B is not C"
        p == C and q == B,
        r == C and s == B,
    
        # "A is not wearing C"
        p == C,
    
        # "C is wearing F, or F is wearing C"
        all((
          p != C or q != F,
          p != F or q != C,
          r != C or s != F,
          r != F or s != C,
        )),
    
        # "wearer of B is not D"
        p == D and q == B,
        r == D and s == B,
    
      )): continue
    
      # output the map and reverse map (solution)
      p2n = { A: p, p: q, q: A, E: r, r: s, s: E }
      n2p = dict((v, k) for (k, v) in p2n.items())
      printf("p2n={p2n}, n2p={n2p}", p2n=output(p2n), n2p=output(n2p))
    
  2. Brian Gladman 7 October 2016 at 4:11 pm
    from itertools import permutations
    
    # No Professor gets their correct label (i.e the permutation is a
    # derangement).  The permutation has  two cycles - with  these as 
    # (A, w, x) and (E, y, z),  where w, x, y and z are  permutations 
    # of B, C, D and F,  let each  Professor  have  the  label of the
    # Professor who follows them in these cycles.  (The cycles ensure
    # that no pair of Professors have each other's labels).
    
    for w, x, y, z in permutations('BCDF'):
      
      # map Professors to labels
      p2l = dict(zip(('A', w, x, 'E', y, z), (w, x, 'A', y, z, 'E')))
    
      # Professor A is not wearing labels B or C
      if not p2l['A'] in 'BC':
    
        # Professor C has label F or vice versa
        if (p2l['C'] == 'F') != (p2l['F'] == 'C'):
    
          # map labels to Professors
          l2p = dict(zip((w, x, 'A', y, z, 'E'), ('A', w, x, 'E', y, z)))   
    
          # label B is not on Professors C or D
          if not l2p['B'] in ('CD'):
            
            # output the Professors in label order
            print('Order:', *[l2p[k] for k in sorted(l2p)])
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: