Difficulty: Medium

There are 100 rooms in a row in a building and inside each room there is a lamp that is turned off. One person enters each room and switches the lamp inside. Then, a second person enters every second room (2, 4, 6, etc.) and switches the lamp inside. A third person switches the lamp in every third room and so on and so far, until person #100 switches the lamp in room 100. How many lamps are turned on at the end?

We can see that the only switches that have been switched an odd number of times are the ones in rooms with perfect square numbers.

Indeed, if person N has switched the switch in room M, then person M/N has done that as well. Since person N and M/N coincide only when M=N², the claim above follows.

We conclude that the number of lamps that are turned at the end is equal to the number of perfect squares less than or equal to 100; that is exactly 10 rooms.

Find a number containing every digit 0-9 exactly once, such that for every 1≤N≤10, the leftmost N digits comprise a number, divisible by N.

Let the number be ABCDEFGHIJ.

• The digit J must be 0, so that the number is divisible by 10.
• The digit E must be 5, so that the number comprised of the first 5 digits is divisible by 5.
• The digits B, D, F, H, J must be even, and therefore the digits A, C, E, G, I must be odd.
• The numbers CD and GH must be divisible by 4 and the number FGH must be divisible by 8. Since C and G are odd, D and H must be 2 and 6, or vice-versa.
• Since ABC, ABCDEF, and ABCDEFGHI are all divisible by 3, we see that A+B+C, D+E+F, and G+H+I are divisible by 3 as well. Therefore, D+F+5 is divisible by 3 and since D and F are even, we have either D=2, H=6, F=8, B=4 or D=6, H=2, F=4, B=8.
  • D=2, H=6, F=8, B=4. Since FGH is divisible by 8 and G is odd, we have G=1 or G=9. Also, G+I+6 is divisible by 3 and since I is odd, we have G=1, I=3. The only possibilities for ABCDEFG are 7492581630 and 9472581630, but they are not divisible by 7.
  • D=6, H=2, F=4, B=8. Since FGH is divisible by 8 and G is odd, we have G=3 or G=7. Also, G+I+2 is divisible by 3 and since I is odd, we have G=3, I=1 or G=3, I=7 or G=7, I=3 or G=7, I=9. The only possibilities for ABCDEFG are 9876543, 7896543, 1896543, 9816543, 1896547, 9816547, 1836547, 3816547. Out of these, only 3816547 is divisible by 7.

We conclude that the only solution is 3816547290.