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, they toggle every fourth locker. They toggle lockers 4,8,12, etc.
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?
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. 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:
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, is 1 x 12 or 2 x 6 or 3 x 4.
Since there are three ways of breaking it down into two factors, it has six factors in all. (1,2,3,4,6,12)
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 3x3. 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.
Microsoft's Cult Of The Puzzle
By William Poundstone
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, they toggle every fourth locker. They toggle lockers 4,8,12, etc.
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?
Solution:
The first thing to realize is that this puzzle almost has to be simpler than it looks. 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. 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:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| / | // | // | /// | // | //// | // | //// | /// | //// |
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, is 1 x 12 or 2 x 6 or 3 x 4.
Since there are three ways of breaking it down into two factors, it has six factors in all. (1,2,3,4,6,12)
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 3x3. 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.
Source:
By William Poundstone
No comments:
Post a Comment