My approach to solving the locker problem started by looking at a subset of lockers to see if there were any recognizable trends. I chose 10, given that it was a small factor of 1000. I looked at the subset in the same way I would have had I been programming the problem by walking through an array and toggling the state of the lockers on and off. Even after just looking at 10 lockers, the perfect squares popped out. I couldn’t really gather why, so I decided to look at 16. It became clear that the lockers that were turned on had an odd number of visits. Why? It took me longer than it should have to recognize that visits corresponded to divisors :-) In hindsight, I think my approach allowed me to quickly gather the patterns of the solution. Still, I think I would have been quicker to the divisor recognition if I had focused on which numbers were actually the visitors for each locker.
UPDATED Sept 16th to support the comment from Malihe:
I wish I could see more pictures or visual representations of your process—it would be great to visualize how you worked through the problem step by step!
ReplyDeleteHey Malhie! Thanks for your comment. I guess I should have provided more explanation. In my depiction, 0 corresponds to a closed locker and 1 and open locker. When student 1 passes through, they close all the open lockers toggling the locker states from 0 to 1s. This student visits every locker so, below the array there is a 1 recorded for each visit. Student 2 then visits every second locker, so the state below the array has an entry of 0 below, every second record. I guess my depiction was unclear because I was collapsing the visits for different rows. For instance, for student 3, the third locker is toggled to 0, the sixth locker is toggled to 1 and the 9th locker is toggle to 0. I was basically collapsing this logic into the rows instead of spelling out what each visitor (divisor) was doing in it's own row. In hindsight, that's probably why I was slow to the divisor recognition. I'm attaching a new image below the post to spell this out. Thanks for the discussion.
ReplyDelete