Locker

Question:

A high school has this ritual on the last day of school: The Students go into the hall and stand by their closed lockers. At the first blow of a whistle, the students open every locker. At the second whistle, the students close every second locker (lockers 2,4,6, etc., are slammed shut). At the third whistle, the students toggle every third locker. To”toggle” means to close it if it’s open, and to open it if it’s closed. They toggle lockers 3,6,9, etc At whistle four, the toggle every fourth locker. At whistle five, they toggle every fifth locker, and so on.Let’s make things easy and say it’s a small school with only 100 lockers. At the one hundredth whistle, the student standing next to locker 100 (and only that student) toggles his locker. How Many lockers are then open?

Answer: A high school has this ritual on the last day of school…The first thing to realize is that this puzzle almost has to be simpler than it looks. Your interviewer is too busy to sit there while you run through all 100 steps. There must be a simplifying trick, and the answer must be relatively uncomplicated. Either all 100 lockers are open — or none are— or there’s some high-concept pattern that makes it easy to figure out how many are open.

Your fidgety interviewer will sit still for a quick whiteboard trial with the numbers 1 through 10. Write out the first ten numbers and make a tally of how many times each is toggled. For instance, on the very first run, all 100 lockers are toggled open. You put a mark beneath all the locker numbers.

For the second toggle, you add a mark beneath the even numbers 2,4,6,8, and 10. Continue on, all the way up to the tenth toggle, where you add a mark under 10 (you would add marks for 20, 30, 40, and so on, were you making a full chart). By this point, the tally looks like this:

Image

Further toggles will not affect the first ten lockers at all. The eleventh toggle affects only lockers 11, 22, 33… The above tallies are final and complete for the first ten lockers. Since the lockers started out closed, any locker toggled once is open. Any locker toggled an odd number of times is open. A locker toggled an even number of times is closed. This means that lockers 1, 4, and 9 above are open, while all the others above are closed. One, 4, and 9 are perfect squares. Each is a number multiplied by itself (1 = 1 x 1; 4 = 2 x 2; 9 = 3 x 3). That’s a pretty good pattern.

Do you see why the perfect square-numbered lockers are open? You toggle each locker once for every factor its number has. Factors come in pairs. Twelve, for instance, is1x12 or 2×6 or 3 x 4. Since there are three ways of breaking it down into two factors, it has six factors in all. That means locker 12 is toggled six times. The only way a number can avoid having an even number of factors is when two of its factors are identical. Nine is 1 x 9 and also 3×3. That gives it just three distinct factors (1, 3, and 9). Only the perfect square — numbered lockers are toggled an odd number of times, and only they are left open. The perfect squares up to 100 are 1,4,9,16,25, 36,49,64,81, and 100. The answer is that ten lockers are open.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s