I’m a big fan of xkcd.com, a webcomic written by Randall Munroe. Last Monday’s comic, entitled “Nine”, became the inspiration for this post. Here it is:

The alt-text reads:

FYI: If you get curious and start trying to calculate the time adjustment function that minimizes the gap between the most-used and least-used digit (for a representative sample of common cook times) without altering any time by more than 10%, and someone asks you what you’re doing, it’s easier to just lie.

It seems Randall is trying to find (or has already found) a closed-form function to accomplish this task. I don’t endorse number discrimination either; unlike my wife who insists on adjusting restaurant tips so that the cents portion of the total amount is either zero or 50, but I digress… I’m not sure exactly how to find these adjusted cook times with a closed-form function, but I can certainly do it with OR, more specifically with an integer program. So here we go. For simplicity, I’ll restrict myself to cook times under 10 minutes.

Let’s begin with an example. As I think about the microwave usage in my house, I end up with the following cook times and how often each one is used:

So let’s first calculate the usage frequency of each digit from zero to nine. The above table can be interpreted in the following way. For every 100 times I use the microwave, 20 of those times I type a 3 followed by a zero (to input a 30-second cook time), 30 of those times I type a 1 followed by two zeroes, etc. Therefore, during these 100 uses of the microwave, I type a total of 280 digits. Out of those 280 digits, 160 are zeroes, 40 are 1’s, 30 are 2’s, and so on. Hence, the usage frequency of zero—the most-used digit—is . (Usage frequencies for the remaining digits can be calculated in a similar way.) Digits 5 through 9 are apparently never used in my house, so the current difference between the most-used and least-used digit in my house is (57.1-0)%.

If, as Randall suggests, I’m allowed to adjust cook times by no more than 10% (up or down) and I want to minimize the difference in usage between the most-used and least-used digit, here’s one possible adjustment table:

Now let’s compare the usage frequency of each digit before and after the adjustment:

After the adjustment, the most frequently used digits are 0, 1, 2, 3, 5, 8, and 9 (12% of the time), whereas the least frequently used digits are 6 and 7 (4% of the time). The difference now is 12-4=8%, which is significantly less than 57.1%. In my household, there’s absolutely no way to do better than that. Guaranteed! (Note: this doesn’t mean there aren’t other adjustment tables that achieve the same 8% difference. In fact, there are many other ways to achieve the 8% difference.)

If you’re curious about how I computed the time-adjustment table, read on. I’ll explain the optimization model that was run behind the scenes and I’ll even provide you with an Excel spreadsheet that allows you to compute your own adjusted cook times. Let the fun begin!

Let be the set of typical cook times for the household in question. In my case, . For each , let be the set of cook times that fall within 10%—or any other range you want—of . For example, . In addition, for each , let be the usage frequency of cook time . In my example, , , and so on.

For each and , create a binary variable that is equal to 1 if cook time is to be adjusted to cook time , and equal to zero otherwise. There are such variables. In my example, 119 of them. Because each original cook time has to be adjusted to (or mapped to) a unique (likely different) cook time, the first constraints of our optimization model are

To be able to calculate the difference between the most-used and least-used digit (in order to minimize it), we need to know how many times each digit is used. Let this quantity be represented by variable , for all . In my house, before the adjustment, and . We now need to relate variables and .

For each and , let equal the number of times digit appears in cook time . For example, , , and . We are now ready to write the following constraint

Once the adjusted cook times are chosen by setting the appropriate variables to 1, the above constraint will count the total number of times each digit is used, storing that value in .

Our goal is to minimize the maximum difference, in absolute value, between all distinct pairs of variables. Because the absolute value function is not linear, and we want to preserve linearity in our optimization model (why?), I’m going to use a standard modeling trick. Let be a new variable representing the maximum difference between any distinct pair of variables. The objective function is simple: . To create a connection between and , we include the following constraints in the model

With 10 digits, we end up with 90 such constraints, for a grand total of 105 constraints, plus 130 variables. This model is small enough to be solved with the student version of Excel Solver. I would, however, recommend using OpenSolver, if you can.

Here’s my Excel sheet that implements the model described above. It shouldn’t be too hard to understand, but feel free to ask me questions about it in the comments below. Variable cells are painted gray. Variables are in column E, variables are in the range K3:T3, and variable is in cell K96. The values and the formulas relating with are calculated with the help of SUMIF functions in the range K3:T3. The differences between all pairs of variables are in column U. All Solver parameters are already typed in. The final values assigned to variables (range K3:T3) represent absolute counts. To obtain the percentages I list above, divide those values by the sum of all ‘s. (The same applies to the value of in cell K96.)

Feel free to modify this spreadsheet with your own favorite cook times and help end number discrimination in the microwaving world! Enjoy!

I just found that I have zero number discrimination (but also zero number use) because I only use the buttons +0:30 and +1:00.

However, it is not as fun as solving an IP model to set my cooking times…

Pingback: Carnival of Mathematics 98 | andrewt.net