6502's cornerThe enlightened frogs [Solution]
2005-06-25
Index

Welcome!
Who am I
Demo
Documents
Small ones
Problems
Chess
Images
Music
My blog
Write me

Versione italiana 


The enlightened frogs [Solution]

From the definition it's clear that the n-th light will be on if n has an even number of divisors. For example the light with number 14 will be on because the divisors of 14 are 1, 2, 7 and 14; so the first, the second, the 7th and 14th frog will be the only ones to jump on the 14th light.

If we however consider all the divisors of a number n and we sort them in ascending order it's easy to note that the product of the first divisor with the last, the second with the second last, the third with the third to last and so on is always n. The mathematical explanation is that if x is an integer that exactly divides n then also y = n/x is an exact divisor and the product x*y is n.

So what does it mean if a number has an odd number of divisors ? If we call k the "central" divisor then we can conclude that n/k=k; the reason is that n/k must be a divisor but it can't be neither lower nor higher than k because divisors above and below k are already paired and k is the central remaining one. But this implies than n is a perfect square because from n/k=k it's easy to conclude n = k*k.

Of course even the reverse is true, i.e. if we consider a perfect square then number of its divisors will be necessarely odd because the square root of the number being an integer will also be a divisor, and it will be "paired" with itself and so it's the "central" divisor of the number.

So the final conclusion is that the n-th light will be off if and only if n is a perfect square.