Locker Problems

I first encountered the locker problem at a math competition in high school. JRMF used to have a version of it on the books called Lightbulbs, but it was retired because it was too app-dependent. Today we'll look at some manipulatives and sequences for a hands-on, in-person version.

Setup

For the uninitiated, here is the version of the problem I first encountered:

Example

A row of $100$ lockers are numbered $1-100$. In sequence, $100$ students run down the hallway, with the $k$th student changing the state of every $k$th locker starting with locker $k$, closing open lockers and opening closed lockers. (This means student $1$ opens all the lockers, student $2$ re-closes all even-numbered lockers, student $3$ flips the state of every locker that is labeled with a multiple of $3$, and so forth.) After all of the students have made their runs, which lockers are open?

Since fidget and sensory toys have come into vogue, there are a few nice options encouraging numeracy. Here are some bubble board "pop" toys in various numberings:

Rabbit poppers with 1-30 ($5)
Number track with 1-20 ($11)
hand2mind Sensory Bubble Popper with 1-100 ($10)
PETBSNVB pop it with 1-100 ($8)
10-frame boards with 1-10 ($10)
10-frame puppies with 1-10 ($10)
10-frame rabbits with 1-10 ($9)

The options with numbers 1-10 give a short runway, which severely limits the ceiling of the activity. While that makes them alright for younger learners, the fact that this activity has roots in multiplication and division sets the floor high. The options with 1-100 are a little overkill for most of the activity, but students can opt to use the first two or three rows. These are the best option for more advanced learners, with the only concern being that popping this many numbers getting tedious. 1-30 seems like a nice sweet spot in terms of price point, having enough of a runway to engage in tougher questions, and popping not getting too tedious, so we'll hang in this range. I'll write with the 1-30 rabbit poppers in mind. (Though the set comes with six rabbits, each student will only want the three numbered ones.)

Challenges

We'll ditch the locker theme and describe scenarios in terms of popping bubbles, where popping a bubble means changing its state from up to down or down to up. Popping every $k$th bubble will mean popping all multiples of $k$. (For younger students, I typically describe this in terms of counting by $k$'s.) A pop sequence $(k_1, k_2, k_3, ...)$ is a set of numbers directing you to first pop every $k_1$-st bubble, then every $k_2$-nd bubble, then every $k_3$-rd bubble, and so on. The bubbles will always start up by default.

Run the pop sequence $(2,3)$ on bubbles $1-10$. Which bubbles are down when you've finished?
What changes if you run $(1,2,3)$?
What about $(3,2,1)$?
What about $(3,2,1,3)$?
Predict what the pop sequence $(2,3)$ will do to bubbles $1-20$.
Try it out. Was your prediction right?
Run $(1,2,3,4,5)$ on bubbles $1-10$. Which bubbles are down when you've finished?
What about $(6,7,8,9,10)$?
What changes when you run $(6,7,8,9,10)$ on bubbles 11-20?
Run $(1,2,3,4,5,6,7,8,9,10)$ on bubbles $1-10$. Which bubbles are down when you've finished?
Predict what $(1,2,3,...,18,19,20)$ will do to bubbles $1-20$ and then check.
What about $(1,2,3,...,28,29,30)$ on bubbles $1-30$?
What's special about the numbers that are down? Can you explain why they have this pattern?

Here are some interesting pop sequences to try. Can you find the pattern in the bubbles that are down when you're finished? (It will be easier to see on a larger number of bubbles!)

Multiples of $2$: $(2,4,6,8,10,12,14,16,...)$
Non-multiples of $2$: $(1,3,5,7,9,11,13,15,...)$
Multiples of $3$: $(3,6,9,12,15,18,21,24,...)$
Non-multiples of $3$: $(1,2,4,5,7,8,10,11,...)$
Multiples of $4$: $(4,8,12,16,20,24,28,32,...)$
Non-multiples of $4$: $(1,2,3,5,6,7,9,10,11,13,14,15,...)$
Primes: $(2,3,5,7,11,13,17,19,23,29,...)$
Squares: $(1,4,9,16,25,36,49,64,81,...)$
Square-free numbers: $(1,2,3,5,6,7,10,11,13,14,15,17,19,...)$
Non-square-free numbers: $(4,8,9,12,16,18,20,24,25,27,28,32,...)$
Cubes: $(1,8,27,64,125,...)$
Powers of $2$: $(1,2,4,8,16,32,64,...)$

The other side of the coin is to ask for a pop sequence that leaves the bubbles in a given state. See if you can find pop sequences on bubbles $1-30$ that accomplish each of the following:

Leave all bubbles down.
Leave precisely the even bubbles down.
Leave precisely the odd bubbles down.
Leave only bubble $1$ down.
Leave only bubble $2$ down.
Leave only bubble $3$ down.
Leave precisely the square bubbles down.
Leave precisely the cube bubbles down.
Leave precisely the fourth-power bubbles down.
Leave precisely the prime bubbles down.
Leave precisely the bubbles numbered with powers of $2$ down.
Given a set of bubbles you would like to see popped down, can you always find a pop sequence that does it?

Notes

Since the number of times a bubble gets popped determines its end state, order of the pop sequence doesn't matter, so we can shuffle it as much as we like. This also means that the net effect of including a number in the pop sequence an even or odd number of times is equivalent to including it $0$ times or $1$ time, respectively, since applying it twice undoes its action.

When looking at the states of the bubbles after a pop sequence, those that are down are precisely those that were popped an odd number of times and those that are up are precisely those popped an even number of times.
Since popping every $1$st bubble means flipping the state of every bubble, if we have two pop sequences that are identical except one includes $1$ and the other does not, the end results will be complementary. This means that if we figure out a pop sequence $S$ that leaves the bubbles in set $A \subseteq \{1,2,3,...,n\}$ down, then adding $1$ to $S$ or removing $1$ from $S$ gives a pop sequence that leaves the bubbles in set $\overline{A} = \{1,2,3,...,n\}-A$ down. For example, the pop sequence $\{2\}$ leaves precisely the even bubbles down, so $\{1,2\}$ leaves the odd bubbles down.
While the sets of bubbles left down by a pop set can be a little gnarly, in general, if we run the sequence $(1,2,3,...,n)$ on bubbles $1-n$, we'll notice that precisely the square numbers are left down. To see why, consider a bubble $k \in \{1,2,3,...,n\}$. It will get popped once for each of its divisors in $(1,2,3,...,n)$. If $d$ divides $k$, so does $k/d$, so we can pair each small divisor $d < \sqrt{k}$ with a large divisor $k/d > \sqrt{k}$. The only problem with this pairing occurs when one of the divisors is $\sqrt{k}$, since if $d = \sqrt{k}$, then $k/d = \sqrt{k}$, and $d$ is paired with itself. This means the values $k$ with an odd number of divisors in the sequence $(1,2,3,...,n)$ are precisely those where $\sqrt{k}$ is an integer -- i.e., the perfect squares -- so those will be precisely the bubbles left down.
If we wish to see precisely the bubbles in a set $A$ popped down, then a nice way to construct a pop sequence is as follows: Start with all bubbles popped up. Find the first bubble that is in the wrong state when compared to $A$, writing down its number $k_1$. Pop it and every $k_1$st bubble. Since this doesn't affect any of the previous bubbles and now bubble $k_1$ is in the right state, the next bubble in the wrong state (if it exists) is numbered $k_2 > k_1$. Repeat this procedure recording the sequence $k_1,k_2,k_3,...$ as you go. Eventually every bubble will be in the right state, and $(k_1,k_2,k_3,...)$ is the pop sequence that did it. While this is an easy algorithm that kids will intuitively figure out, predicting $(k_1,k_2,k_3,...)$ in advance is much tougher!

One consequence of this is that there are $2^n$ possible pop sequences (that don't repeat numbers) we can construct for bubbles $1-n$ and there are $2^n$ possible states the bubbles can be left in, which are all achievable by some pop sequence. Because of this bijection, for each possible end state of the bubbles, there is a unique non-repeating pop sequence that produces it.

If we want to see precisely the bubble $1$ left down, we need a sequence of numbers where an odd number of them divide $1$ and an even number divide each of $2$ through $n$ an even number of times. To get this sequence, consider the square-free numbers: the numbers whose prime divisors are all distinct. (Note: $1$ is considered square-free because no primes divide it.) If $k$ is square-free, we can write it \[ k = p_1 \cdot p_2 \cdot \cdot \cdot p_r \]

For distinct primes. Its divisors are then numbers of the form

\[ k = p_1^{c_1} \cdot p_2^{c_2} \cdot ... \cdot p_r^{c_r} \]

where each $c_i$ is $0$ or $1$. Thus, the number of divisors of $k$ is $2^r$. This is an even number unless $k = 1$, since then $r = 0$. And these divisors are again square-free. If all numbers were square-free, then $(1,2,3,...,n)$ would be precisely the right sequence to run! However, plenty of numbers are not square-free, and we've seen running the pop sequence $(1,2,3,...,n)$ leaves all of the squares down and not just $1$.

But what happens if we run the pop sequence of square-free integers $(1,2,3,5,6,7,10,11,13,14,15,...)$ on bubbles $1-n$? It turns out that the number of square-free divisors of $k$ is odd precisely when $k=1$. To see this, consider the radical of a positive integer $k$. The radical of $k$, denoted $\textrm{rad}(k)$, is the product of the distinct primes dividing $k$. Here is a table of some small numbers and their radicals:

$k$	$\textrm{rad}(k)$
1	1
2	2
3	3
4	2
5	5
6	6
7	7
8	2
9	3
10	10
11	11
12	6
13	13
14	14
15	15
16	2

For larger numbers, we can get it from the prime factorization. For example, since

\[ 360 = 2^3 \cdot 3^2 \cdot 5, \] we have \[ \textrm{rad}(360) = 2 \cdot 3 \cdot 5 = 30. \]

If a number $d$ divides $\textrm{rad}(k)$, since $\textrm{rad}(k)$ divides $k$, then $d$ must also divide $k$. (Since $\textrm{rad}(k)$ is square-free, $d$ would also have to be square-free.) On the other hand, If a square-free number $d$ divides $k$, it must also divide $\textrm{rad}(k)$. This means the square-free divisors of $k$ are precisely the (square-free) divisors of $\textrm{rad}(k)$, so the number of square-free divisors of $k$ is odd if and only if $k = 1$.

We can then conclude that if we want to see only $1$ popped down, the square-free integers

\[ S = (1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,...) \]

are the pop sequence that does it.

If we want to see only the bubble $k$ popped down, then we can multiply the square-free numbers by $k$ to get the pop sequence
\[ kS = (k,2k,3k,5k,6k,7k,10k,11k,13k,14k,15k,17k,19k,21k,22k,23k,26k,...) \]
This does not pop any number not divisible by $k$ and $mk$ has an even number of divisors in the above set if and only if $m$ has an even number of square-free divisors.
There are a few frameworks for thinking about this problem that more advanced students might like to explore.
- Set theory: When we pop the bubbles in a set $A$ the bubbles in a set $B$, the bubbles in both, $A \cap B$, get double-popped. This means that the result of popping the bubbles in $A$ and then the bubbles in $B$ is leaving precisely the bubbles in
  \[ (A \cup B)-(A \cap B) \]
  down. This is called a symmetric difference and often written
  \[ A \Delta B = (A \cup B)-(A \cap B) \]
  Another way to say this: if pop sequence $S$ results in bubbles $A$ being left down and sequence $T$ leaves $B$ down, then $S \Delta T$ leaves $A \Delta B$ down.
  
  The algebra of symmetric differences could be used to get some insight in small cases.
- Linear algebra: We can think about each pop sequence on bubbles $1-n$ as giving a vector with $n$ coordinates where the $i$th coordinate is $1$ if the pop sequence leaves bubble $i$ down and $0$ otherwise. If we take addition $(\textrm{mod} 2)$ (i.e., $0+0 \equiv 1+1 \equiv 0$ and $0+1 \equiv 1+0 \equiv 1$, then if $S$ and $T$ are two pop sequences with vectors $v_S$ and $v_T$, then the vector $v_S + v_T$ is precisely the vector associated to running $S$ and then $T$, i.e.,
  \[ v_S + v_T = v_{S \Delta T} \]
  It will turn out that the vectors
  \[ \{v_{(1)}, v_{(2)}, v_{(3)}, ..., v_{(n)}\} \]
  form a basis for this space.
Bruce Torrence and Stan Wagon wrote a nice article exploring some aspects of this problem. They give a couple functions defined in terms of prime signatures and symmetric differences that can be used to characterize the relationship between pop sequences and bubble end states. The article is short and well-presented, so I won't reproduce it here.

Extra Challenges

What if we use geometric sequences instead? I.e., $k$ in our pop sequence means popping all bubbles in the set
\[ \{1,k,k^2,k^3,...\} \]
What if we allow more general arithmetic sequences? Instead of taking popping every $k$th bubble to mean popping bubbles $k,2k,3k,...$, we could pop those of the form $a+b,2a+b,3a+b,...$ for parameters $(a,b)$. This is related to the fence-painting problem, except painting the same picket twice "unpaints" it. Note that the number of end states for bubbles $\{1,2,3,...,n\}$ is still $2^n$ while the number of pop sequences is $2^{n(n+1)/2}$, so there's a lot of redundancy. Since there are a lot of trivial solutions, you would want to look at interesting constraints like "for each $(a_i,b_i)$ in the pop sequence, the $a_i$ must be distinct."
In the original problem, each number $k$ in a pop sequence pops the values in
\[ \{kn \, : \, n \in \mathbb{N}\} \]
For each $k$, we can think about $kn$ as being a polynomial $p_k(n)$. Are the other interesting families of polynomials $\{p_1(n), p_2(n), p_3(n), ...$ we can use, taking the pop sequence $(k_1, k_2, k_3, ...)$ to mean popping the bubbles \[ \{p_{k_1}(n) \, : \, n \in \mathbb{N}\}, \{p_{k_2}(n) \, : \, n \in \mathbb{N}\}, \{p_{k_3}(n) \, : \, n \in \mathbb{N}\}, ... \]

This post was sponsored by the Julia Robinson Mathematics Festival

Search This Blog

math them

Locker Problems

Setup

Example

Challenges

Notes

Extra Challenges

Comments

Post a Comment

Popular posts from this blog

Modular Origami with Sonobe Units

Stepping Stones

Instant Insanity

\(k\)	\(\textrm{rad}(k)\)
1	1
2	2
3	3
4	2
5	5
6	6
7	7
8	2
9	3
10	10
11	11
12	6
13	13
14	14
15	15
16	2