Using your Head is Permitted

August 2016 riddle

UPDATE (2 August): Anything with less than 2 people is not a party. All party acquaintance graphs must have n>1.

The following riddle comes from Dominic van der Zypen. (Thanks, Dominic!) It has two parts. Answer both for credit.

n people are at a party. Every pair of them has exactly k mutual acquaintances among the n. Acquaintance is a symmetric and anti-reflexive relation.

Part 1:

Describe an infinite family of party acquaintance graphs that satisfy the criteria above, all with k=1.

Part 2:

Describe at least two distinct party acquaintance graphs that satisfy the criteria above with k=2, or prove such do not exist.

List of solvers:

Jim Boyce (2 August 22:06)
Kuan Yang (2 August 22:33)
Lorenz Reichel (3 August 07:36)
Radu-Alexandru Todor (4 August 08:58)
Lin Jin (6 August 07:12)
Bart De Vylder (7 August 00:10)
JJ Rabeyrin (7 August 17:39)
Gaoyuan Chen (16 August 19:10)
Joseph DeVincentis (17 August 03:56)
Daniel Bitin (26 August 18:36)
Oscar Volpatti (31 August 03:45)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page