The Namer-Claimer game

Consider the following game played on the integers from 1 to n.  In each round Namer names a forbidden distance d, then Claimer claims a subset of [n] that does not contain any two integers at distance d.  After finitely many rounds, Claimer will have claimed sets that cover the whole of [n], at which point the game ends.  How many rounds will there be with best play?

I’ve run this question out at a number of workshops and open problems sessions, and haven’t yet heard back about a success.  I’ll explain the known upper and lower bounds below the fold, but encourage you to spend a few minutes thinking about it before taking a look.

Continue reading “The Namer-Claimer game”