Enigmatic Code

Programming Enigma Puzzles

Enigma 515: Foreign ties

From New Scientist #1667, 3rd June 1989 [link]

The Anglo-Slovak club had its meeting last week. Those present were Tom, Vyctur, Ted, Tago, Ray, Min, Wex, Olav, Russ and Cy.

Some of the members stood up and took part in an old Slovakian dance, rather like a Morris dance. The dancers stood around the floor with no three in a straight line and between each pair a taut piece of ribbon was stretched across the floor. Some ribbons were pink and the rest were blue. I noticed that there was a pink ribbon between two of them precisely when their Christian names had an odd number of letters in common. (So, for example, had a Jane, David and Victor been dancing, there would have been a pink ribbon from Jane to David, a blue from David to Victor, and a blue from Jane to Victor).

As soon as I saw how many dancers there were I realised that two of the ribbons would have to cross. But they had arranged themselves in such a way that there was no pink triangle and no blue triangle of ribbons.

Who was dancing?

[enigma515]

One response to “Enigma 515: Foreign ties

  1. Jim Randell 2 September 2019 at 8:32 am

    We have encountered a puzzle very similar to this one in Enigma 216 (also set by Susan Denham).

    So we see that there must be at least 5 dancers, for the ribbons to have to cross.

    And as they had arranged themselves in such a way that no three of the dancers that were interconnected by ribbons of the same colour, there must have been fewer than 6 dancers. (By Ramsey’s Theorem [ @Wikipedia ] it is not possible to colour a graph will 6 or more elements without creating a 3-set interconnected by the same colour).

    There is essentially only one way to construct the graph. So we need to find a 5-set of dancers, such that each dancer has an odd number of letters in common with exactly two of his fellow dancers.

    This Python program uses the [[ multiset() ]] class (recently added to the enigma.py library) to count the letters shared between names.

    It runs in 177ms.

    Run: [ @repl.it ]

    from enigma import subsets, multiset, join, printf
    
    # names
    names = "TOM VYCTUR TED TAGO RAY MIN WEX OLAV RUSS CY".split()
    
    # colour the edge between x and y
    def colour(x, y):
      return len(multiset(x).intersection(y)) % 2
    
    # count the colourings of edges between n and ns
    def count(n, ns):
      r = [0, 0]
      for x in ns:
        if x == n: continue
        r[colour(n, x)] += 1
      return tuple(r)
    
    # choose a 5-set of names
    for ns in subsets(names, size=5):
      # check each member has 2 ends of each of the 2 colours
      if all(count(n, ns) == (2, 2) for n in ns):
        printf("{ns}", ns=join(ns, sep=" "))
    

    Solution: The dancers were: Tom, Ted, Tago, Ray, Olav.

    We can draw an arrangement like this, where no set of three dancers is interconnected by three ribbons of the same colour:

    But we can also draw an arrangement like this, where none of the triangles formed in the diagram have three sides the same colour:

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: