I started tackling the puzzle by thinking about what happens to a specific locker, for example locker #1 or #1000, since I thought these numbers on the end are easier to figure out. I then realised that locker #1 is only going to have their state changed for once (by the first student), whereas locker #1000's state is probably going to be altered for many many times, including by the first and the second student.
I then tracked down the first few lockers, what happens to locker #2, #3 and #4. I realised that a locker's state will be altered when, and only when, the count of the student is a factor of the number of the locker. The first student were to alter all the locker's state, was because 1 is a factor of every integer from 1-1000.
Thus I could deduce that, by the end, a locker will be closed if it has odd number of factors (e.g. locker #1), and it will be opened, if it has even number of factors (e.g. locker #2).
To figure out which numbers have odd/even number of factors, I considered a few numbers, such as 8, 9, and 12. I found that the factors mostly comes in pairs, with the exception of squares, which introduce duplicated factors.
Thus, I could conclude that, from locker #1-1000, any lockers with a perfect square number will be closed by the end, that's #1, #4, #9, #16......, and will be opened otherwise.
With the aid of technology, I figured that the largest perfect square within a 1000 is 31^2 = 961. Hence there will be 31 lockers closed by the end.
-----
Overall I think my strategy was to start with considering specific examples, particularly the easier ones, to figure out the pattern.
No comments:
Post a Comment