Mathematical Puzzle. 10pts, best answerrr?

Question

there are 10 lights. you turn them ON (0) and OFF (X) ten times. here's the thing, you turn each light by it's sequence of numbers. such as. 2,4,6 or 3,6,8. (ALL lights are off when you start, but you flight the light at 1 making the lights turn ON (0)
here's how i'd set it up
-1,2,3,4,5,6,7,8,9,10 (the lights)
1
2
3
4
5
6
7
8
9
10 (the number of times you flick the lights (vertically)
here's an example
-..1,2,3,4,5,6,7,8,9,10 (the lights)
1.0,0,0,0,0,0,0,0,0,,0
2..,X....X....X....X.....X
3......X.......0......X
4.........0.........0
5
6
7
8
9
10
and so on. 
WHAT LIGHTS REMAIN ON AT THE END?
WHAT IS AN EQUATION YOU MAY USE, TO FIND THIS?

tjnarciso · Accepted Answer

Observe the following:
    you flip light N an X number of times, where X is the number of factors of N. This is because, if Y is a factor of N, then on the Yth round of light-flipping, you flip light N.
    if you flip a light an even number of times, then that light is OFF, otherwise it's ON.

Thus, the lights that remain ON at the end, have to be perfect squares (see note below for reason)!
Thus, there are 3 lights on, namely 1, 4, and 9 at the end.

Reason why these are perfect squares:
Suppose a number N has prime factorization p1^q1 * p2^q2 * p3^q3 *... *pn^qn where p1, p2, p3,...,pn are primes and q1,q2,q3,...,qn are integers >0.
Then it has (q1 + 1)*(q2 + 1)*(q3 + 1)*...*(pn + 1) factors, since you can consider 0, 1, 2,...,qi-1, or qi instances of pi in a factor.
If N was a perfect square, each q1,q2,...,qn is even, and thus it has an odd number of factors.
Otherwise, there exists a qi that is odd, and thus it has an even number of factors.

Mathematical Puzzle. 10pts, best answerrr?

Related Questions

Trending Questions