Tessellate S.T.E.M.S. (2019) - Computer Science - School - Set 4 - Objective Problem 5

There are 1000 1000 doors in a corridor. There are 1000 1000 persons as well. Initially all the doors are closed. The first person goes and opens all the doors. The second person goes and closes all the even numbered doors. The third person goes and toggles the state of all the doors which are a multiple of 3 3 ( If it is open, the third person closes it and vice versa). Finally, The thousandth person goes and toggles the state of all the doors which are a multiple of 1000 1000 . Eventually how many doors will be open?


This problem is a part of Tessellate S.T.E.M.S (2019)

100 500 31 59

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.

2 solutions

Henry U
Dec 23, 2018

All doors will be opened and closed once for each of their number's divisors. Divisors usually come in pairs, so the door with number n = p q , p < q n = p \cdot q, p < q will be opened by tbe p p th person and closed again later by the q q th person. The only numbers whose divisors don't come in pairs are the square numbers, because person p = n N p = \sqrt{n} \in \mathbb{N} won't have a partner q q who closes the door again, because q = p q = p .

So, the question comes down to the number of perfect squares less than or equal to 1000, which is easy to compute as 1000 = 31 \lfloor \sqrt{1000} \rfloor = \boxed{31} .

Actually, why is this a computer science problem? Of course, an algorithm can solve it, but I think it's easier to do via number theory.

Henry U - 2 years, 5 months ago
V I S I O N .
Jan 16, 2019

Do for 10 numbers and you can see th pattern that only squares aare open

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...