Fictional Lockers

Two hundred students enter a hall filled with lockers numbered ( 1 , 2 , . . . . , 200 ) ({1,2,....,200}) . The first student opens all the lockers. The second operates lockers ( 2 , 4 , 6 , 8 , 10 , . . . . . . . . . , 200 ) (2, 4, 6,8,10,.........,200) . The third operates on ( 3 , 6 , 9 , 12 , . . . . . . . . . , 198 ) (3, 6,9,12,.........,198) and so on.

In short; if the locker was open then the student closes it and if it was closed then opens it.

Initially if all lockers were closed then at the end of these operations, how many lockers remain open?

This question belongs to the set Number theory best problems


The answer is 14.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

We will begin by observing the events.

  • After the first student operates, all lockers are opened.

  • After the second student operates, lockers with numbers 2 , 4 , 6 , 8 , . . . . . . . . . , 200 2,4,6,8,.........,200 are closed again.

  • After the third student operates, lockers with numbers 3 , 9 , 15 , 21 , . . . . . , 195 3,9,15,21,.....,195 are closed and lockers with numbers 6 , 12 , 18 , 24....... , 198 6,12,18,24.......,198 are opened again.

So we observe that the lockers with locker no.s having odd positive factors remain open, and those having even factors remain closed after all operations.

So we need to find no.s with odd factors.

If the no. k k can be represented as p 1 n 1 × p 2 n 2 × p 3 n 3 × . . . . . . . . . . . . . . . . . . . . . . . . p_{1}^{n_{1}}\times p_{2}^{n_{2}}\times p_{3}^{n_{3}}\times ........................

then the no. of factors is ( n 1 + 1 ) × ( n 2 + 1 ) × ( n 3 + 1 ) × . . . . . . . . . . . . . . . . . . . . . . . . (n_1+1)\times (n_2+1)\times(n_3+1)\times ........................ which will be odd when ( n 1 + 1 ) , ( n 2 + 1 ) , ( n 3 + 1 ) . . . . (n_1+1),(n_2+1),(n_3+1).... all are odd.

Thus n 1 , n 2 , n 3 . . . . . n_1,n_2,n_3..... all should be even.

If n 1 , n 2 , n 3 . . . . . n_1,n_2,n_3..... are all even then k k must be perfect square.

So, we conclude that all lockers with locker no.s a perfect squares are all open after all operation.

And there are 14 14 perfect squares till the no. 200 200 . So the answer is 14 \boxed {14}

Problem Credits : Titu Andreescu 104 Number Theory Problems (For the Training of the USA IMO Team).

Ayon Ghosh - 3 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...