The Mathematics Department Is Running Out Of Numbers
- Carneades.org
- 2 days ago
- 7 min read
Approximately 5 months ago, the webcomic xkcd published a comic entitled “Number Shortage” that sent me on a long and strange journey. This is the story of that journey. The comic itself is quite simple, it portrays a mathematics department running out of numbers, even as they speak, each number they say decreases the available supply.
The comic implies that as numbers are spoken, they are used up. The department goes from 15 2’s to only 13 2’s because it uses up 2 2's in the previous statement. The hover text implies that once they run out of a particular number, they are unable to say how many of that number they have left.
After reading this comic, I went down a rabbit hole. These statements feel in some way paradoxical. The act of saying them seems to change their truth value, such that they have one truth value at the beginning, but a different one at the end. But they are neither fully self refuting, like someone saying “I am silent” nor self affirming like someone writing “I am writing.” But rather they seem to start off true and end false once the numbers are used up. But those paradoxes can await another day, what caught my attention when I saw this was much more practical. A question that haunted me for weeks after reading the comic:
What sets of digits could the mathematics department have on hand that would ensure they never had an amount of digits they could not say?
In other words, what set of digits could they start with that would mean they are always able to say exactly how many digits they have, until they run out completely?
Self-Reducing Bags of Digits
Before I could answer these questions, I needed to clarify a few things about the world of this puzzle to make this possible.
Digits not Numbers: First we are working with digits, as the comic makes clear, not whole numbers. The math department does not have a pile of 12’s they have piles of 1’s and 2’s.
No Other Uses: Second, we are assuming that the numbers will only be used to say how many more numbers there are. Obviously, if this were real, the department could use the numbers in other ways to cheat the process and use up extra numbers that they couldn’t say how many they had. For the sake of this puzzle, that is not allowed. They also aren’t able to spell out numbers or list them in non-traditional ways (e.g. listing "2" as 6/3). Perhaps that would not make them much of a mathematics department, but who has the luxury of doing math when there is a number shortage on?
Consistent Responses and Silence on Nothing: Third, the department will keep responding in the same way, listing all the digits that they have. If they have zero of a digit, they will not say anything about it. So if they have 2 2's, they must say so. But if they have 0 8's they don't need to mention 8's at all (as that would make the challenge impossible, once you get to 0 8's you don't have an 8 to say that you have 0 8's).
Snapshot in Time: Fourth, we are assuming that they are stating the number of digits that were available before they started speaking to avoid issues of changing the order of the numbers changing the results. So if they have 3 2's and 3 3's, they don't need to reassess how many 3's they have mid-sentence because they used one up to talk about the 2's (note that this is slightly out of line with what is implied in the comic, but it allows for our paths to be order invariant).
The Goal: The goal is to make it down to having nothing of every digit exactly. If at any point along the chain they cannot say how many digits they have, that attempt fails.
The goal is to perfectly use up all of the remaining digits in the final statement. A bag of digits that does this that would be called a "self reducing" bag. We are using the term "bag" (also called a multiset or mset) instead of "set" as duplicates are allowed).
For example, the bag of digits represented by the statement "“We have 4 1’s, 7 2’s, 3 3’s, 4 4’s, 3 5’s, 2 7’s and 1 8." is self reducing, because it gets exactly to zero digits. First using up 13 digits with that statement, including all the 3's 7's and 8's to get "We have 2 1’s, 5 2’s, 1 4, and 2 5’s" which in turn uses 8 more digits, leaving us with only "We have 2 2’s." This last statement leaves us with exactly nothing so the original bag of digits and all of the stops along the way are self-reducing.
Say we start with the following bag of digits:
111122222223334444555228
We then say how many of each we have:
We have 4 1’s, 7 2’s, 3 3’s, 4 4’s, 3 5’s, 2 7’s and 1 8.
This uses up several of our digits:
111122222223334444555778
1122222455
Meaning our next statement would be:
We have 2 1’s, 5 2’s, 1 4, and 2 5’s
Which in turn uses up several more of our digits:
1122222455
22
Leaving us with just 2 2's, which we can just barely say, using up the last of our remaining digits
We have 2 2's.
I had a lot of questions about these self-reducing bags. Was there a finite number of them? What did the network map of the bags look like? How did that map change in different bases? I am no mathematician, but I have just enough Python coding ability to very inefficiently get a computer to do the thinking for me.
Starting Off Small
Given the sheer number of possibilities, I started off small, just looking at what this would mean in base 2, as the results are obviously base-dependent. I pulled together some terribly inefficient Python code and created the visualization below. It does not capture all of the binary-self reducing bags (they very well may be infinite), but it captures enough to give you a sense of the structure.
As you can see below, each node represents a self-reducing bag of digits. The lines between them connect each back to the center of the graph, where all the digits have been perfectly used up: "We have no digits." The arrows indicate the direction. The size of the nodes and the size of the edges show how many nodes in the graph connect back to that node. You can zoom in or move around. If you zoom in far enough you will be able to see the labels on each node You can also access a stand alone version of this visualization here.
As you can see, the visualization is very linear, which might be expected in base 2, with few branches and most of the self-reducing bags coalescing around a main trunk that points back to the case of "We have no digits." Most of the bags I found reduced back to "We have 11 0's and 100 1's (3 0's and 4 1's in base 10), which in turn reduced to "We have no digits". Most of the other branches feed into the single main branch. It is interesting to see that there seem to be at most 3 different paths feeding into a single node, a very different pattern than what can be seen in the base 10 version.
The code that was used to create the underlying dataset, the dataset itself, and the code used to create the visualization can be found below (the txt files are Python files, you will need to change the extension to .py to use them).
Into Base 10
While working in binary was a good way to kick the tires with a smaller dataset, it only made me more curious to see what the network in base 10 would look like. Would it have a similar trunk structure? Or be more clustered? I ran several programs which created massive data files to answer these questions, but discovered that most visualization programs have hard limits on the number of nodes that could be visualized, and even with smaller datasets the graphs took a very long time to render. If someone has a system with fewer limitations and wants to create a bigger version of this visualization, I would love to see it. For now we are working with just several thousands nodes.
That said, I still created a visualization, albeit with fewer nodes than I had originally hoped. The interactive visualization takes several minutes to load, and several further minutes to spread out into a recognizable pattern, but if you want to play with it yourself, and be able to see the labels on the individual nodes, you can do so here. But for those that are impatient, an image of the complete graph is included below.
As we can see from this, the pattern is very different from the base 2 option. Base 10 is much more clustered, and almost looks like a fractal. The large circle in the center is of course the "We have no digits" node. This is surrounded by many feeder nodes (not just the two that we saw in base 2). Each of those nodes has a array of many of its own feeder nodes.
However you will also notice a satellite node which has a sizable set pointing back towards the main graph. This second largest point is "We have 2 2s" a very common stopover for many self reducing sets before emptying completely. The other major nodes branching off from 2 2's are "We have 4 2's and 2 4's" and "We have 3 2's and 3 3's". It is important to note that with more data, this graph could be made larger and it is unclear how much this pattern would continue.
As above, here are some of the code files used to construct this visualization and dataset. I am sure they are extremely inefficient and anyone that wants to create a cleaner more efficient version is highly encouraged, as well as anyone that has a network visualization software that can handle hundreds of thousands of nodes, just give Carneades.org and xkcd attribution for the original idea, or send them in and we will feature them.
The Next Chapter
There are many more questions that we could answer with this. Is there a reliable way to get from one self reducing bag to a larger self reducing bag? what patterns are there for finding the next self-reducing bag? Are there a finite number of self-reducing bags? If so how many? Does each node have a finite number of self reducing bags that feed into it?
The answers to these questions will need to await someone with more mathematics skills than I, but if you come up with any of these answers please send them my way, I would love to feature them here.