I have not kept the square, but that to come
Shall all be done by the rule.
--- William Shakespeare, Antony and Cleopatra
What mighty contests rise from trivial things.
--- Alexander Pope, The Rape of the Locker
Last month, we were inspired by elementary school. This
month we'll take you to middle school or junior high, depending
on your local school district.
Leaving elementary school brings many changes. The one
that our daughters seem to attach the most importance to is ...
lockers!
Here's a problem that a middle-school math teacher gave
us over late-night coffee:
Imagine all the students lined up in front of their lockers
in a long line -- Student One in front of locker #1, Student
Two in front of locker #2, and so on. All the lockers are
closed.
Now we start, by having Student One open locker #1,
then open locker #2, then locker #3, locker #4, and so
forth, down the line. When he opens the last locker, he
returns to his own locker and stands in front of it.
Next, Student Two closes locker #2, then locker #4,
locker #6, and every other locker down to the end, and
returns to her place.
Now it's Student Three's turn. Student Three
closes locker #3, opens locker #6 (which was opened by
Student One and then closed again by Student Two) closes
locker #9, and so on, fiddling with the door of every third
locker.
If we continue this process through to the last
student, which lockers are opened, which are closed, and
why?
Before you go further, what's your answer?
What?
Our answers were both, ``Um ... prime-numbered lockers
are open?'' (Two great minds in one great rut.)
Wrong.
If this was your answer too, don't feel bad. We've
given several of our friends this same problem, and a lot of them
gave us this same wrong answer, Another frequent off-the-cuff
wrong guess is the Fibonacci series. Michael, who works behind
the counter in our neighborhood coffee-house, guessed factorials.
That's wrong too.
Instead of guessing, perhaps you tried using paper, a
pencil, and an eraser. We, of course, wrote a little program.
1 #!/usr/local/bin/perl -w
2 # $Id: lockers,v 1.1 1998/12/22 01:26:41 jsh Exp $
3 use strict;
4 my $usage = "usage: $0 num_lockers";
5 my $n = shift || die $usage;
6 $[ = 1;
7 my @lockers = (0)x$n;
8 for (my $i=1; $i <= $n; $i++) {
9 for (my $j=$i; $j <= $n; $j += $i) {
10 $lockers[$j] = $lockers[$j] ? 0 : 1;
11 }
12 }
13 for (my $i=1; $i <= $n; $i++) {
14 print "$i\n" if ($lockers[$i]);
15 }
Here, lines 1 to 3 are boilerplate, with a shebang line
containing the -w flag, and the compulsive, nit-picking
strict module that we tend to use because we're poor
typists.
Line 4 and 5 use the first argument as the total number
of lockers, and exit with a bitter complaint if it isn't present.
Normally, Perl arrays begin at index 0, as in C, but we
want our locker numbers to begin at 1, so line 6 says that in
this program, all our array indices are going to begin at 1, as
in FORTRAN.
Line 7 sets up an array of lockers and starts them all closed. (We'll use
to mean locker #5 is closed and$locker[5] = 0;
to mean it's open.)$locker[5] = 1;
Lines 8 to 12 then perform the openings and closings and
lines 13 to 15 print out the numbers of the open lockers.
And the output? (Drumroll, please.)
$ lockers 200 | fmt 1 4 9 16 25 36 49 64 81 100 121 144 169 196
Yup. Squares.
(Like you, middle-schooler Gillian Haemer said
``squares,'' but that requires the sophistication to know what a
square is. Luckily, there's more than one way to look at
patterns. Her little sister, Zoe, said ``3, 5, 7, 9, .... I see
the pattern.'' Do you see what she saw?)
But that's only the first half of the answer.
Why?
Last month, when we were talking about elementary-school
math, we remarked that computers sometimes raise more questions
than they answer. Here's a case where a tiny program gave us a
quick, easy-to-interpret pattern as the answer to an interesting
puzzle. This forced us head-on into the question, ``Why?''
So, let's think. Well, if you're locker #N, who messes
with your door? Easy: the student corresponding to each of your
divisors, including Student 1 and Student N. You end up open if
and only if you have an odd number of divisors.
So squares, and nothing else, have an odd number of
divisors? Precisely.
Okay, why's that? Let's look at the divisors of each
number -- another little program.
1 #!/usr/local/bin/perl -w
2 # $Id: divisors,v 1.1 1998/12/22 01:26:41 jsh Exp $
3 use strict;
4 my $usage = "usage: $0 num_lockers";
5 my $n = shift || die $usage;
6 $[ = 1;
7 my @divisors;
8 for (my $i=1; $i <= $n; $i++) {
9 for (my $j=$i; $j <= $n; $j += $i) {
10 push @{$divisors[$j]}, $i;
11 }
12 }
13 for (my $i=1; $i <= $n; $i++) {
14 my $t = scalar @{$divisors[$i]};
15 printf "%3d [%2d] : ", $i, $t;
16 print "@{$divisors[$i]}\n";
17 }
This program is just a variant of our earlier program.
Instead of opening or closing locker doors, line 14, pushes each
divisor of $j onto the end of the array
@{$divisors[$j]}, and lines 15 and 16 print out these
divisor lists, along with the number of elements in each list.
$ divisors 30 1 [ 1] : 1 2 [ 2] : 1 2 3 [ 2] : 1 3 4 [ 3] : 1 2 4 5 [ 2] : 1 5 6 [ 4] : 1 2 3 6 7 [ 2] : 1 7 8 [ 4] : 1 2 4 8 9 [ 3] : 1 3 9 10 [ 4] : 1 2 5 10 11 [ 2] : 1 11 12 [ 6] : 1 2 3 4 6 12 13 [ 2] : 1 13 14 [ 4] : 1 2 7 14 15 [ 4] : 1 3 5 15 16 [ 5] : 1 2 4 8 16 17 [ 2] : 1 17 18 [ 6] : 1 2 3 6 9 18 19 [ 2] : 1 19 20 [ 6] : 1 2 4 5 10 20 21 [ 4] : 1 3 7 21 22 [ 4] : 1 2 11 22 23 [ 2] : 1 23 24 [ 8] : 1 2 3 4 6 8 12 24 25 [ 3] : 1 5 25 26 [ 4] : 1 2 13 26 27 [ 4] : 1 3 9 27 28 [ 6] : 1 2 4 7 14 28 29 [ 2] : 1 29 30 [ 8] : 1 2 3 5 6 10 15 30
Aha. Well, the first thing we see is something we knew:
only the primes have exactly two divisors -- one and themselves.
What about some of the other compound numbers? The powers are
easy: 2 has two divisors, 4 has three, 8 has four, 16 has 5, and
so on. It's easy to see that for any prime, p**n has n + 1
divisors: p**0, p**1,..., p**n.
But how about the other compound numbers, like 72? 72 =
2**3 x 3**2.
First, we arrange all the divisors in a table, like this:
x | 1 3 9 ------------------ 1 | 1 3 9 2 | 2 6 18 4 | 4 12 36 8 | 8 24 72
Across the top, we have the possible powers of three.
Down the side, the possible powers of two. Taken together, the
table entries constitute all (3+1) x (2+1) = 12 possible
combinations.
Similarly -- though harder to draw -- it should be
pretty clear that the divisors of 900 = 2**2 x 3**2 x 5**2 can be
laid out in a (2+1) x (2+1) x (2+1) = 3 x 3 x 3 cube. (Okay,
okay, ``a three-dimensional rectangular parallelepiped.'')
Much harder to draw would be the four-dimensional grid
of divisors of 4902963250500 = 2**2 x 3**5 x 5**3 x 7**9, but
it's not hard to see how many elements would be in it: 3 x 6 x 4
x 10 = 720.
So which numbers will have a multi-dimensional array of
divisors with an odd number of elements? Only those with an odd
number of elements in every dimension; an even number in any
dimension would make the product of the dimensions even.
And how many elements are there in each dimension? One
more than the power of the prime that dimension represents.
(Thus, in our first example above, 72 = 2**3 x 3**2, we have four
elements in the dimension representing the prime factor 2, and
three elements in the dimension representing the prime factor 3.)
But for each axis to be of odd length, each prime factor
must be raised to an even power. And if each prime factor is
raised to an even power, then the number is a square.
For example, 144 = 12**2 = ( 2**2 x 3**1 )**2 = 2**4 x
3**2 will have (4+1) x (2+1) = 15 factors, and locker #144 will
be open.
Not bad, eh?
Not again!
Okay, now here's another one.
Same students, same lockers, opposite rules. This
time, Student One doesn't open his locker or anyone else's.
Student Two doesn't open locker #2, opens #3, skips
#4, opens #5, and so on.
Student Three doesn't open locker #3, does open #4,
closes #5, ignores #6, and goes on changing the state of
every locker that is not divisible by three.
Now which lockers are open? (``Um. Primes?'' No again.) Here's the code:
#!/usr/local/bin/perl -w
# $Id: lockers2,v 1.1 1998/12/22 15:29:44 jsh Exp $
use strict;
my $usage = "usage: $0 num_lockers";
my $n = shift || die $usage;
$[ = 1;
my @lockers = (0)x$n;
for (my $i=1; $i <= $n; $i++) {
for (my $j=$i; $j <= $n; $j++) {
$lockers[$j] = ($lockers[$j] ? 0 : 1) if $j%$i;
}
}
for (my $i=1; $i <= $n; $i++) {
print "$i\n" unless $lockers[$i];
}
$ lockers2 100 | fmt 45 1 2 6 8 9 10 12 14 18 20 22 24 25 26 28 30 32 34 38 40 42 44 46 48 49 50 52 54 56 58 60 62 66 68 70 72 74 76 78 80 81 82 84 86 88 90 92 94 96 98
Aha! It's the even numbers. Well, almost.
What's the pattern? And why?
We see the answer to the first question, but not a good
proof for the second one. Maybe you have to be a middle schooler
to come up with one; if you have a middle schooler who does,
please pass the proof along, and we'll print it. Meanwhile,
we'll ask Gillian Haemer and Allie Copeland.
Until we hear from you or them, happy trails.