♦ ♦ ♦ ♦

Een zeer groot apenverblijf waarin duizend apen leven is verlicht door duizend lampjes. Onder ieder lampje bevindt zich een bijbehorende aan/uit schakelaar. De schakelaars zijn genummerd van 1 tot en met 1000. Op een gegeven moment zijn alle lampjes uit, maar omdat het donker wordt willen de apen de verlichting aanzetten. Dat doen ze op de volgende manier

Aap nr. 1 drukt op alle schakelaars die in de tafel van 1 zitten.
Aap nr. 2 drukt op alle schakelaars die in de tafel van 2 zitten.
Aap nr. 3 drukt op alle schakelaars die in de tafel van 3 zitten.
Aap nr. 4 drukt op alle schakelaars die in de tafel van 4 zitten.
Etc., etc.

Hoeveel lampjes staan er aan nadat de laatste aap geweest is? En nog een vraag: Welke lampjes zijn dat precies?

Antwoord (CTRL+A):

Als de eerste aap geweest is staan lamp 1, 2, 3, ... en 1000 aan.
Als de tweede aap geweest is staan lamp 1, 3, 5, ... en 999 aan.
enz.

Laten we nu eens gaan bekijken of bijvoorbeeld lampje 10 uit is nadat alle apen zijn geweest. 10 = 2 * 5, 10 = 5 * 2, 10 = 10 * 1 en 10 = 1 * 10. Dus 10 komt voor in de tafel van 1, 2, 5 en 10. Dus aap 1, aap 2, aap 5 en aap 10 drukken op schakelaar 10. Dat betekent dat lampje 10 uit is als alle apen langs zijn geweest.

Neem nu een willekeurig lampje x. Natuurlijk geldt dat x = 1 * x en x = x * 1. x zit dus altijd in de tafel van 1 en van x. Als x een priemgetal is dan zijn er geen andere mogelijkheden meer en staat lampje x uit als alle apen langs zijn geweest. Als x geen priemgetal is dan kunnen we op minstens 1 manier x schrijven als x = n * m, waarbij n en m gehele getallen zijn. x zit dus in de tafel van n en van m. Als x geen kwadraat is, dan zit x dus daarom in een even aantal verschillende tafels. In dat geval zal lampje x dus uit staan. Maar als x een kwadraat is, dat wil zeggen, x = n * n, oftwel x = 1, 4, 9, ... dan zit x in een oneven aantal tafels. Dat betekent dat als x een kwadraat is lampje x uiteindelijk aanstaat.

Omdat 31*31=961 en 32*32 = 1024 zijn er 31 verschillende kwadraten onder de 1000. Er staan dus 31 lampjes aan, dit zijn dus 1, 4, 9, 16, 25, ... en 961.
Bron: http://www.rdzl.nl