elfjes en trollen

Opgave - VWO 2006 vraag 3

Aan een grote ronde tafel zitten 60 sprookjesfiguren: elfjes en trollen. De trollen in dit gezelschap liegen altijd, de elfjes spreken altijd de waarheid, tenzij ze zich vergissen. Iedereen beweert tussen een elfje en een trol te zitten, maar twee elfjes vergissen zich. Hoeveel trollen zitten er aan deze tafel?

Oplossing

Het antwoord is 20 trollen.
Noteer:
T voor een trol,
E voor een elfje dat zich niet vergist, en
E' voor een elfje dat zich wel vergist.

Twee trollen naast elkaar kan niet, want dan liegt de tweede en dan moet de derde figuur dus ook een trol zijn enzovoort, maar dan zou het hele gezelschap uit trollen bestaan. Deze mogelijkheid mogen we verwerpen omdat er sprake is van twee elfjes die zich vergissen.

Elke trol die zit, zit dus tussen twee elfjes.

Mogelijke patronen voor waarachtige elfjes E:
- drie naast elkaar kan niet, dus maximaal twee naast elkaar.
- één tussen twee trollen kan niet, dus minimaal twee naast elkaar.

Mochten er geen leugenachtige elfjes zijn, dan is het enige andere mogelijke patroon:
TEETEETEETEET... = $n$ x (TEE) met $n=20$.

Als we aan dit patroon één leugenachtig elfje toevoegen, dan moet dit
- ofwel tussen twee trollen, dan wordt het ... $p$ x (TEE) + TE' + $q$ x (TEE)...;
- ofwel tussen twee elfjes, dan wordt het ... $p$ x (TEE) + TEE'E + $q$ x (TEE)...;

Als we het tweede leugenachtig elfje toevoegen, dan zijn de enige mogelijke patronen:
- een aantal keer (TEE) en $2$ keer een keuze uit (TE') of (TEE'E) in eender welke volgorde;
- een aantal keer (TEE) en $1$ keer (TEE'E'E).

Om aan $60=3n$ figuren te komen is de enige manier: $(n-2)$ keer (TEE) en $1$ keer (TE') en $1$ keer (TEE'E) in eender welke volgorde.

Het aantal elfjes is dus $2n =40$, en het aantal trollen is $n =20$.