Maximizing Doughnut Orders: A Frustratingly Complex Problem

Doughnuts are often sold in boxes of 7, 13, or 25, which can make it tricky to order a specific number of doughnuts. This article explores the mathematical intricacies behind this ordering issue, using the Frobenius Coin Problem and the Chicken McNugget Theorem to identify the maximum number of doughnuts that cannot be ordered using these box sizes.

Understanding the Problem

The Frobenius Coin Problem (also known as the Chicken McNugget Theorem) provides a way to solve such problems. However, when dealing with three different box sizes (7, 13, and 25 doughnuts), the problem becomes significantly more complex than the classic two-coin scenario.

Step-by-Step Solution

The steps to find the maximum number of doughnuts that cannot be ordered using combinations of these sizes are as follows:

Step 1: Identify the Box Sizes

We have three distinct box sizes:

Step 2: Check Combinations

To find the largest number that cannot be obtained with these combinations, we need to systematically check various combinations of these box sizes.

Step 3: Use the Chicken McNugget Theorem

The Chicken McNugget Theorem states that for two coprime integers ( m ) and ( n ), the largest integer not expressible as a non-negative combination of ( m ) and ( n ) is given by ( mn - m - n ). However, this theorem applies directly only to two sizes and is insufficient for the case of three sizes.

Step 4: Consider All Combinations

To find the maximum number of doughnuts that cannot be made, we can use a brute force approach or systematically check combinations up to a certain limit. We start by checking combinations of the three box sizes until we find a number that can be constructed from the sums of these sizes.

Step 5: Brute Force Checking

We can check combinations of 7, 13, and 25 up to a reasonable limit, say 100, to identify which numbers cannot be formed. Through this checking process, it was determined that the largest number that cannot be formed is 49.

Conclusion

Therefore, the maximum number of doughnuts that cannot be ordered using combinations of boxes of 7, 13, and 25 is 49.

When Only Two Sizes Are Available

If you only have two sizes, such as 7 and 13, and these sizes are coprime, the largest value you cannot make is given by the formula ( mn - m - n ). For 7 and 13, this formula gives us 7 * 13 - 7 - 13 71.

Dealing with Three Sizes

For three sizes, there is no simple formula, but there are algorithms that can help you find the answer. As noted, the largest number that you cannot make from boxes of 7, 13, and 25 is 44.

Further Considerations

It is useful to organize the numbers into their remainders modulo 7. For example, since you can make 38 doughnuts, which is 3 mod 7, with a 25 box and a 13 box, you know that you can also make every value larger than 38 that is 3 mod 7 by adding as many boxes of 7 as needed.

Understanding these mathematical principles not only helps in solving the doughnut ordering problem but also provides insights into a broader range of combinatorial and number theory problems.