Üljön $n$ ember az asztalnál.
Legyen $t$ az a ‐ csak $n$-től és $k$-tól függő ‐ legkisebb egész, ahányszor $k$-t kell lépni az asztal mentén ahhoz, hogy visszajussunk a kiindulási helyre. Egy ilyen körutazás során igazmondó után hazug, hazug után pedig igazmondó következik, így a kör hossza szükségképpen páros. (Egyébként volna két ,,$k$-szomszédos'' igazmondó vagy hazug.)
Megmutatjuk, hogy ha ‐ adott $n$-re és $k$-ra ‐ a $t$ páros, akkor lehetséges a megfelelő elrendezés. Címkézzük meg ugyanis ekkor az ülőhelyeket (illetve a megfelelő helyen ülő embereket) a következőképpen. Szemeljünk ki egyet, ő legyen I(gazmondó), a tőle $k$ hellyel jobbra ülő H(azug), az ettől $k$ hellyel jobbra lévő ismét I stb; $t$ lépésben jutunk vissza a kiindulási helyre, és az utolsó, $t$-edik címke H volt.
Ha van olyan hely/ember, amely/aki még nem kapott címkét, válasszunk ki egy ilyet, és tőle elindulva végezzünk el egy, az előbbihez hasonló címkézést. Ennek során nem juthatunk olyan helyre, ahol az előző szakaszban már jártunk, tehát újabb $t$ darab címke is kiosztható; és így tovább.
Hátravan még a $t$ meghatározása. Mivel $k$-asával lépve az $n$-személyes asztalt járjuk körbe-körbe ‐ éppen $t$-szer ‐ a $t$ azon egészek minimuma, amelyekre $n\mid t\cdot k$, azaz $\frac{n}{\left(n\mathrm{,}k\right)}|t\cdot \frac{k}{\left(n\mathrm{,}k\right)}$. Mivel pedig $\frac{n}{\left(n\mathrm{,}k\right)}$ és $\frac{k}{\left(n\mathrm{,}k\right)}$ egymáshoz relatív prímek, $\frac{n}{\left(n\mathrm{,}k\right)}|t$; a legkisebb ilyen $t$ maga $\frac{n}{\left(n\mathrm{,}k\right)}$.
A feladat megoldását tehát azok az $n$ értékek adják, amelyre $t=\frac{n}{\left(n\mathrm{,}k\right)}$ páros, azaz $n$ a 2-nek magasabb hatványával osztható, mint a $k$.