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

Computer Science Level 2

There are $1000$ doors in a corridor. There are $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$ ( 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$ . Eventually how many doors will be open?

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

100 500 31 59

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 \cdot q, p < q$ will be opened by tbe $p$ th person and closed again later by the $q$ th person. The only numbers whose divisors don't come in pairs are the square numbers, because person $p = \sqrt{n} \in \mathbb{N}$ won't have a partner $q$ who closes the door again, because $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 $\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

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

2 solutions

0 pending reports