I have an affinity for these. And since it's starting to be recruiting season for me, I think back to the interviews I had when I was a wee little undergrad. Trilogy Software in Austin asked me this one:
You have 100 people lined up in a row next to 100 closed lockers. The row of people will walk by all of the lockers. When they do, they behave like this:
Person 1 will toggle every locker ("toggle" means that if it is closed, she opens it, but if it is open, she closes it).
Person two will toggle every other locker.
Person three will toggle every third locker.
Person four will toggle every fourth locker.
Etc.
Question: when all 100 people have finished walking by all 100 lockers, how many lockers are open? Which ones are they?
joel
Subscribe to:
Post Comments (Atom)
3 comments:
10 - all the square numbers:
1,2,4,9,16,25,36,49,64,81
Good, though you missed one: 100.
Care to explain why for the throngs of readers? ;-)
joel
Each person #n visits lockers that are multiples of n. Therefore, each locker #n will be toggled only by people who are factors of n.
But if f is a factor of n, then f x z = n, where z is also a factor of n. So, for each factor f of n that changes the state of locker #n, factor z of n will change the state back, leaving the state of locker #n unchanged. Therefore these factor pairs can be ignored.
The exception is when f = z, i.e. n is a square number. In this case person #f will visit the locker once, changing its state once. So if all the lockers are closed to start, only those with square root integer will be opened. That is, all the square numbers.
Yes, you're right, I forgot that 10 x 10 = 100!
Post a Comment