A computer scientist, a mathematician, and a child walk into a bar...

[StevieMolinari]

The Story

It’s a family at a conference, and they’ve popped into a nearby bar for a bite to eat. Realizing this the bartender offers a puzzle of their own creation. They call it “Hilbert’s Utility Closet.”

Hilbert's Utility Closet

Hilbert’s utility closet contains an infinite number of light switches, one for each natural number. One day Hilbert walks into the utility closet when all the switches are turned off. He then goes through many passes (infinitely many, in fact) where he switches some of the light switches accordingly. On the first pass, Hilbert starts with the first light switch and switches every light switch. On the second pass, he starts with the second light switch and switches every second light switch. On the third pass, he starts with the third light switch and switches every third light switch. He does this for every natural number n, where on the nth pass he starts with the nth light switch and switches every nth light switch. The riddle is, “Are there any light switches left on? If so, which ones?”

The arch of the video would be the family working together to determine two facts:

1. A light switch is on if it undergoes an odd number of switches (because they all initially started off)
2. The number of switches that the kth light switch undergoes is the number of factors of k.

Putting these two facts together the puzzle is reduced to finding which natural numbers have an odd number of factors. The rest of the story would detail how each of them solves this puzzle in a distinctly different way.

About the Author

I’m a mathematician/statistician working in the data science space, but my real passion is teaching. For several years in grad school I worked at a math summer camp and many of my ideas (including this one) arose out of my experimentation and conversations with friends/students there.

Quick Summary

The setup above is meant to root the problem (i.e. which natural numbers have an odd number of factors) in a story/puzzle. The idea being that this might grab people’s attention and gets them invested in the story/characters.

The lesson itself is not really about the various solutions to the problem, but rather the portrayal of the different mindsets and problem solving styles of the participants (kinda like what Grant did in this video).

The computer scientist, taking a more empirical, inductive approach, embodies more of the “hacker” mindset valued in the computer science/software communities. They present a quick and easy solution (well… easy if you have a computer) that demonstrates what numbers possess this property. However, they fails to address why this is the case.

On the other hand, the mathematician, taking a more rational, deductive approach, embodies the rigorous (borderline pedantic) mindset of a theoretician/academic. They present a proof that demonstrates why certain numbers have this property, but along the way they lose the forest through the trees, and don’t really characterize these number in the best way (at least in comparison to the computer scientist). That is their solution fails to really address what these number are.

The child, taking a novel and much simpler approach, embodies a pure and playful spirit. I’d like to think Erdos would look at their solution and think, “This is maybe one for The Book”. Their solution doesn’t require the computational/theoretical overheads that their parents’ solution does. In fact, the whole time they are just sitting there quietly shuffling around some sugar packets. Their solution ends with a bit of a “play-on-shapes”... like a play-on-words but with shapes instead words haha.

Target Medium

I don’t know what medium would be best, but I'm open to any and all ideas. I do think that it would need to have a visual component, so video, blog post, comic strip are all viable options.

Basically, I'm looking for someone to animate and bring this idea to life. The ideas are for the most part all flushed out. It's just that they exist only in my head... and I suppose now in this post.

More Details

I presented this in a talk once, but otherwise I haven’t written about or done anything else with it. I can’t take credit for the puzzle itself (I forget where I originally heard about it), but the framing of it as Hilbert’s utility closet is my own touch.

The solutions of each individual are sketched below in the "Answers in the Back of the Book" section.

Contact Details

Emailing me at stephen.molinari@gmail.com would be best. Or you could just respond to this post.

Answers at the Back of the Book

The Computer Scientist's Solution

The computer scientist’s solution takes a more brute force approach, computing the number of factors of the first 1,000 natural numbers and then returning just the ones with an odd number of factors. They write (in R) the following 4 lines of code:

maxN = 10^3; nFactors = numeric(maxN)
for(iN in 1:maxN)
    nFactors[iN] = sum((iN %% (1:iN)) == 0)
print(which((nFactors %% 2) == 1))

which returns the sequence 1, 4, 9, 16, 25,…. They immediately recognize these as the square numbers and move-on having solved the puzzle to their liking.

The Mathematician's Solution

The mathematician’s solution relies on the fact that the number of factors of a natural number $n$, denoted $\phi(n)$, is given as:

$$ \phi(n) = \prod_{i = 1}^k (e_i + 1) $$

where

$$n = \prod_{i = 1}^k p_i ^ {e_i}$$

is the prime factorization of $n$.

From this it’s easy enough to determine that a natural numbers has an odd number of factors if and only if it's prime factorization contains only even powers. This is true and agrees with the computer scientist’s solution, but they stop at this somewhat obtuse result, failing to see the more natural characterization of squares.

The Child's Solution

The child’s solution is much more geometrical (so somewhat hard to explain with words; this is why I think there needs to be a visual component), but basically they think of factors as coming in pairs. For instance, take the number 12, its factor pairs are (1,12), (2, 6), and (3,4). Geometrically, they are thinking of these pairs as rectangular arrays that total to 12. This is why they are shuffling around the sugar packets. Really they are considering factor pairs geometrically! So for 12, there is a long skinny 1x12 rectangle, a 2x6 rectangle, and a 3x4 rectangle.

The child points out that a naïve observer might think that no natural numbers have an odd number of factors, because factors always coming in pairs, the height and width of the rectangle… but what about when the height equals the width... This leads naturally to a solution that informs both what these number are and why they are this way.

The icing on the cake is that the child finishes with an actual square and uses this as both a representation of the answer (square numbers have an odd number of factors!) but also as a punctuation to the end of their argument/proof… like in a QED kind of way ;)
I'd like to think that the scene maybe ends with the two parents, clearly outdone by their child, both beaming with pride.

[trannguyenductam314]

Hi Stevie, I'm keen on making videos and visualizations about problems kinda like yours, I'm a riddle nerd ya know. I've stomped through this problem a few times, and I have a pretty good way to explain both the naive and the overcomplicated kind, hope to share it with you at the earliest time. My name is Tam, if you're wondering, and I'm from Vietnam. Have a good day

[cmh231]

Am not here to offer my services as much as to say that your title really caught my eye, and I look forward to reading through this post in further detail at some point!

[enoch-solano]

Same as Calvin, just dropping by to say I'm looking forward to the outcome of what comes of this post, looks very promising!

[trannguyenductam314]

Oh, and how can I contact you if I want to know more information about this project?

[StevieMolinari]

@trannguyenductam314 hey Tam. shoot me an email when you get a chance. it's in the Contact Details above.

[twtww]

Great idea! Looking forward to the video.