Á fundi í Karphúsinu sátu $29$ menn saman í kringum hringborð. Allir þessir menn voru með þeim ósköpum fæddir að annaðhvort sögðu þeir aldrei satt orð eða hvert einasta orð sem þeir sögðu var satt. Og þar sem þeir sitja þarna í kringum borðið segja þeir allir í kór „Næst mér á báðar hendur sitja lygarar“. Sýnið að í það minnsta $10$ af mönnunum segja alltaf satt. Er mögulegt að nákvæmlega $10$ af þeim séu sannsöglir?
Lausn
(1) Um þá sem alltaf segja sannleikann gildir að næst þeim á báðar hendur
sitja einstaklingar sem alltaf segja ósatt.
(2) Um þá sem alltaf segja ósatt gildir að næst þeim á báðar hendur
situr a.m.k.\ einn einstaklingur sem alltaf segir satt.
Af (1) leiðir að aldrei mega tveir sannsöglir menn sitja hlið við hlið,
því annars væri annar þeirra að ljúga. Af (2) leiðir að aldrei mega
þrír lygarar sitja í röð, því að þá væri sá í miðjunni að segja satt. Á
milli hverra tveggja sannsögla mann er annað hvort einn eða tveir
lygarar, aldrei fleiri og aldrei færri.
Á hægri hönd hvers sannsöguls manns situr því að minnsta kosti einn
lygari svo lygararnir eru fleiri en þeir sem segja satt. En það eru í
mesta lagi tveir lygarar á hægri hönd hvers sannsöguls manns svo
lygararnir eru ekki fleiri en tvöfalt fleiri en þeir sannsöglu. Höfum
því að
$$1\leq \frac{\text{fjöldi lygarar}}{\text{fjöldi sannsögla}}\leq 2.$$
Öfugt ef þessi ójafna er uppfyllt, þá getum við skipt mönnunum þannig í
hópa að í hverjum er nákvæmlega einn sannsögull maður og annaðhvort einn
eða tveir lygarar. Ef hóparnir sitja svo saman við borðið þannig að
þegar farið er réttsælis þá sitji fyrst sá sannsögli og svo einn eða
tveir lygarar, þá er augljóst að allir við borðið geta sagt: „Næst mér
á báðar hendur sitja lygara“.
Nú sitja 29 manns við hringinn. Táknum með $s$ fjölda sannsögla
mann. Þá er fjöldi lygara jafn $29-s$. Höfum þá að
$$1\leq \frac{29-s}{s}\leq 2$$
og þegar þessi ójafna er leyst fæst að $9\frac{2}{3}\leq s\leq
14\frac{1}{2}$. Því er $s$ ein af tölunum $10$, $11$, $12$, $13$, $14$. Þeirra á
meðal er $10$ svo það er mögulegt að nákvæmlega $10$ fundarmanna séu sannsöglir.