Math 300

Groupwork

The Frog Problem

Dr. Wilson

A school has 1500 lockers in its halls. One person comes along and opens each locker. A second person comes along and, starting with the second locker, closes every other locker. A third person comes along and starting with the third locker, they go to every third locker, and if the locker is open they close it, and if it is closed they open it. For instance, at this point, the third locker is open; because the first person opened it, and the second person left it open when they closed every other locker starting with the second one. However, the next locker the third person comes to is the 6th locker, and it is closed because the second person closed it, so the third person will open it, etc. A fourth person comes along and starting with the fourth locker, they go to every fourth locker, and if the locker is open they close it, and if it is closed they open it. 1500 people do this. When they are all done, which lockers are open?

 

We will solve enough of the simpler problems to determine the pattern. Let's take the problem where we have 10 lockers.

 

 

We will let red indicate that the locker is closed and black indicate that the locker is open.

 

Person number 1 opens every locker

 

 

Person number 2 starts with the second locker and closes every other locker

 

 

Person number 3 starts with the 3rd locker and changes every third locker.

 

 

 

Person number 4 comes through.

 

 

Person number 5 comes through.

 

 

Person number 6 comes through.

 

 

Person number 7 comes through.

 

 

Person number 8 comes through.

 

 

Person number 9 comes through.

 

 

And person number 10 comes through.

 

 

At this point, we can consider the state of these lockers; because these lockers will be left alone by the rest of the people. Notice which lockers are open at this point: 1, 4, and 9. What property do these numbers have in common?

 

Well, they are all squares. Could it be that all of the lockers that have square numbers will be open and all of the other lockers will be closed?

 

Whether the locker is open or closed is a matter of whether an even or an odd number of people have messed with it. Since the lockers are originally closed, if an odd number of people mess with it, it will be open and if an even number of people mess with it it will be closed. A person messes with a locker if their number divides the number of the locker. So a locker will be open if it has an odd number of divisors and it will be closed if it has an even number of divisors.

 

This raises the question of which numbers have an even and which numbers have an odd number of divisors. Let us look at a number like 24. One way to make sure that we get all of the divisors of 24 is to start with one and check to see whether the number goes into 24 or not.

 

 

If a number goes into 24, put its quotient down next to it. That way, we can save a little effort. We will be able to know that we are done when we get to a number that has appeared in the quotient list. In the example above, after 4 comes 5 which does not go into 24. After 5 comes 6 which has appeared next to the 4 in the list of quotients. At this point we know that we have all of the numbers that go into 24, because if we considered a number bigger than 6, its quotient would be smaller than 4, and we have considered all of the numbers which are smaller than 4. So the list of divisors is

 

1, 2, 3, 4, 6, 8, 12, 24

 

The other thing that this procedure does for us is it allows us to pair each divisor up with its quotient. This sets up a one to one correspondence between divisors that are smaller than the square root and numbers that are bigger than the square root. The divisor that is smaller than the square root will necessarily be smaller than the number that is bigger than the square root unless they are both equal to the square root. We conclude that if the number is not a square, there will be an even number of divisors, and the locker will be closed, but if the number is a square, like 36 for instance,

 

 

we see that all of the divisors except 6 are paired up with a different quotient, but that 6 is paired up with itself, and so there are an odd number of divisors.

 

Since all numbers that are not squares have an even number of divisors, and all numbers that are squares have an odd number of divisors, the lockers which will be left open will be the lockers that have square numbers.

So the lockers that will be left open out of the 1500 lockers will be lockers numbered

 

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, and 484,

529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, and 1444

top

Groupwork