**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]

### Like this:

Like Loading...

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 least5 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 theenigma.pylibrary) to count the letters shared between names.It runs in 177ms.

Run:[ @repl.it ]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: