Nanobot Factory

I've been toying with some potential activities that involve division. Today we'll look at an activity that makes heavy use of division and partitions, skinned as a factory trying to make as many nanobots as possible.

Setup

This will almost certainly transition to a pen and paper activity if students get deep enough into it, but to start it might be helpful to use counters. Counters that link would be particularly nice:

• Centimeter cubes (1000 for $42)

• Snap cubes (100 for $9)

• Math cubes (200 for $16)

We'll play around with the rules later on, but we'll start with the following problem. You have a factory and start with \(5\) nanobots. Each day there are two phases.

1. Setup: Nanobots are reclustered into machines however you like.

2. Production: Each machine produces a cluster of nanobots for each of its proper divisors.

For instance,

• A \(1\)-nonbot machine produces \(0\) new nanobots

• A \(2\)-nonbot machine 2 produces \(1\) nanobot

• A \(3\)-nonbot machine 3 produces \(1\) nanobot

• A \(4\)-nanobot machine produces \(1+2 = 3\) new nanobots

What's the largest number of nanobots you can end with after \(5\) days?

Example

One possible way to set up the \(5\) days is as follows:

1. Arrange the \(5\) nanobots into a \(2\)-machine and \(3\)-machine. These machines produce \(1\)\(+\)\(1\) \(= 2\) new nanobots, leaving \(5+2 = 7\) total.

2. Arrange the \(7\) nanobots into a \(6\)-machine and \(1\)-machine. These machines produce \(1\)\(+\)\(2\)\(+\)\(3\)\(+\)\(0\) \(= 6\) new nanobots, leaving \(7+6 = 13\) total.

3. Arrange the \(13\) nanobots into a \(4\)-machine, \(4\)-machine, and \(5\)-machine. These machines produce \(1\)\(+\)\(2\)\(+\)\(1\)\(+\)\(2\)\(+\)\(1\) \(= 7\) new nanobots, leaving \(13+7 = 20\) total.

4. Arrange the \(20\) nanobots into a \(20\)-machine. This machines produces \(1\)\(+\)\(2\)\(+\)\(4\)\(+\)\(5\)\(+\)\(10\) \(= 22\) new nanobots, leaving \(20+22 = 42\) total.

5. Arrange the \(42\) nanobots into a \(12\)-machine, \(10\)-machine, \(14\)-machine, and \(6\)-machine. These machines produce \(1\)\(+\)\(2\)\(+\)\(3\)\(+\)\(4\)\(+\)\(6\)\(+\)\(1\)\(+\)\(2\)\(+\)\(5\)\(+\)\(1\)\(+\)\(2\)\(+\)\(7\)\(+\)\(1\)\(+\)\(2\)\(+\)\(3\) \(= 40\) new nanobots, leaving \(42+40 = 82\) total.

The total nanobot count at the end is \(82\).

Initial Questions

• The example \(5\)-day cycle above is not optimal. Can you find a way to beat it?

• What are some strategies for setting up machines each day? Are some machines better than others?

• What is the largest number of nanobots you can end with after \(5\) days?

• How does this problem change if we change the number of nanobots we start with? The number of days?

Explorations

• Since anything that can be made with \(n\) nanobots can be made with \(n+k\) by leaving the last \(k\) nanobots as singletons, it is never worse for production to have more nanobots. This means that the goal of maximizing production for a multiple day stretch can be viewed as maximizing production for the first day, then for the second day, and so on.

• Students should quickly get a sense that some machines are better than others. An early observation is that combining all five nanobots into a \(5\)-machine is worse than making a \(4\)-machine and a \(1\)-machine, since the \(4\)-machine more than makes up for the fact that the \(1\)-machine produces nothing. Here are the outputs of some small machines:

  \(n\)	Proper Divisors	Proper Divisor Sum
  \(1\)	\(\{\}\)	\(0\)
  \(2\)	\(\{1\}\)	\(1\)
  \(3\)	\(\{1\}\)	\(1\)
  \(4\)	\(\{1,2\}\)	\(3\)
  \(5\)	\(\{1\}\)	\(1\)
  \(6\)	\(\{1,2,3\}\)	\(6\)
  \(7\)	\(\{1\}\)	\(1\)
  \(8\)	\(\{1,2,4\}\)	\(7\)
  \(9\)	\(\{1,3\}\)	\(4\)
  \(10\)	\(\{1,2,5\}\)	\(8\)
  \(11\)	\(\{1\}\)	\(1\)
  \(12\)	\(\{1,2,3,4,6\}\)	\(16\)
  \(13\)	\(\{1\}\)	\(1\)
  \(14\)	\(\{1,2,7\}\)	\(10\)
  \(15\)	\(\{1,3,5\}\)	\(9\)
  \(16\)	\(\{1,2,4,8\}\)	\(15\)
  \(17\)	\(\{1\}\)	\(1\)
  \(18\)	\(\{1,2,3,6,9\}\)	\(21\)
  \(19\)	\(\{1\}\)	\(1\)
  \(20\)	\(\{1,2,4,5,10\}\)	\(22\)
  \(21\)	\(\{1,3,7\}\)	\(11\)
  \(22\)	\(\{1,2,11\}\)	\(14\)
  \(23\)	\(\{1\}\)	\(1\)
  \(24\)	\(\{1,2,3,4,6,8,12\}\)	\(36\)
  \(25\)	\(\{1,5\}\)	\(6\)
  \(26\)	\(\{1,2,13\}\)	\(16\)
  \(27\)	\(\{1,3,9\}\)	\(13\)
  \(28\)	\(\{1,2,4,7,14\}\)	\(28\)
  \(29\)	\(\{1\}\)	\(1\)
  \(30\)	\(\{1,2,3,5,6,10,15\}\)	\(42\)
  \(31\)	\(\{1\}\)	\(1\)
  \(32\)	\(\{1,2,4,8,16\}\)	\(31\)

• A slightly more subtle concept than the output of a machine is its proportional output. For example, a \(20\)-machine produces \(22\) nanobots while a \(12\)-machine only produces \(16\). However, if we tried to measure whether these machines were "pulling their weight," we might note that

  \[ \frac{22}{20} = 1.1 < 1.\overline{3} = \frac{16}{12} \]

  and say something like a \(12\)-machine has a \(133\%\) yield compared to a \(20\)-machine's \(110\%\) yield.

  In number theory, the sum of all divisors of a number \(n\) is written \(\sigma(n)\), so the sum of proper divisors is \(\sigma(n)-n\). In this language, we say that an \(n\)-machine is more efficient than an \(m\)-machine if

  \[ \begin{eqnarray*} \frac{\sigma(m)-m}{m} < \frac{\sigma(n)-n}{n} & \qquad \Leftrightarrow \qquad & \frac{\sigma(m)}{m} - \frac{m}{m} < \frac{\sigma(n)}{n} - \frac{n}{n} \\ & & \\ & \qquad \Leftrightarrow \qquad & \frac{\sigma(m)}{m} < \frac{\sigma(n)}{n} \end{eqnarray*} \]

  Thus, we can think of \(\sigma(n)/n\) as a measure of how efficient an \(n\)-machine is.

• Since machines persist, we can also think about the yield of an \(n\)-machine as being \(\sigma(n)\), if we include the machine itself. In this language, the problem of maximizing yield is to find a partition of \(n\)

  \[ n = a_1 + a_2 + ... + a_k \]

  so that

  \[ \sigma(a_1) + \sigma(a_2) + ... + \sigma(a_k) \]

  is maximal.

• We've seen that we can use \(\sigma(n)/n\) as a measure of how efficient an \(n\)-machine is. The set of numbers \(n\) that have the property that \(\sigma(m)/m < \sigma(n)/n\) for all \(m < n\) are called superabundant numbers and the first several of them are

  \[ 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 10080, 15120, ... \]

  Superabundant numbers provide good machines. If the number of nanobots on hand is a superabundant number, then by definition, the best one can do is make one large machine out of all of the nanobots. Otherwise, you might suspect that using some sum of superabundant numbers is a good strategy. In fact, up until \(420\) nanobots, the best setups can all be found by decomposing \(n\) into a sum of superabundant numbers, always choosing the largest that works! We'll call this a greedy superabundant partition.

  For example, with \(320\) nanobots, the largest superabundant number smaller than this is \(240\), leaving \(320-240 = 80\). The next viable superabundant number is \(60\), and \(80-60 = 20\). Next \(12\), for \(20-12 = 8\). Then \(6\), for \(8-6 = 2\), which is also superabundant. The greedy superabundant partition of \(320\) is then

  \[ 320 = 240+60+12+6+2. \]

  This gives the best output one could expect from \(320\) nanobots. Starting at \(420\), we start to see some funkiness. The greedy superabundant partition of \(420\) is

  \[ 420 = 360+60 \]

  However,

  \[ \sigma(360)+\sigma(60) = 1170 + 168 = 1338 < 1344 = \sigma(420). \]

  Despite the fact that \(420\) is not superabundant, a \(420\)-machine is better than a \(360\)-machine and a \(60\)-machine. \(420\) plays a role in early counterexamples to the greedy superabundant partition giving the best yield.

  \(1560\) provides the first of another sort of counterexample. While we might expect that the best yield would come from the greedy superabundant partition

  \[ 1560 = 1260+240+60, \]

  it instead comes from

  \[ 1560 = 840+720 \]

  where both \(840\) and \(720\) are superabundant.

• The toy problem falls within the scope where a greedy superabundant partition is optimal. Here are all possible optimal configurations for each day:

  Day	Nanobots (start)	Optimal Partition(s)	Yield	Nanobots (end)
  \(1\)	\(5\)	\(4+1\)	\(3\)	\(8\)
  \(2\)	\(8\)	\(8, \,\, 6+2\)	\(7\)	\(15\)
  \(3\)	\(15\)	\(12+3, \,\, 12+2+1\)	\(17\)	\(32\)
  \(4\)	\(32\)	\(30+2, \,\, 24+8, \,\, 24+6+2\)	\(43\)	\(75\)
  \(5\)	\(75\)	\(60+12+3, \,\, 60+12+2+1\)	\(125\)	\(200\)

  So \(200\) is the best you can end with.

Wrap-Up Questions

• What was the largest number of nanobots you were able to end with?

• What are some strategies you found for clustering the nanobots?

Extensions

Here are some ideas that change the core mechanisms slightly:

• Add some constraints on the number and types of machines that can be made:

  • What if each setup you have to make exactly \(2\) machines?

  • What if no machine can be larger than \(100\) nanobots?

• Add some constraints on reconfiguring machines: What if machines can be fused but not broken down and new nanobots come pre-fused? (For example, making a \(4\)-machine binds those \(4\) nanobots together forever. That \(4\)-machine produces a \(1\)-machine and a \(2\)-machine rather than \(3\) nanobots.)

• Change the output mechanism: What if each machine only produces nanobots in clusters of its

  • Prime divisors?

  • Proper prime divisors?

  • Prime power divisors?

  • Proper prime power divisors?

Gord Hamilton suggested a variation of a geometric flavor: Each machine must be an \(a \times b\) rectangle and the products of a machine each cycle are the \(c \times d\) rectangles that can tile it.

This post was sponsored by the Julia Robinson Mathematics Festival