Muffins.jl is a Julia package for solving the Muffin Problem:
Given m muffins and s students, divide the muffins in such a way that all students can receive equal amounts of muffin.
Determine muffins(m, s), the smallest piece size in the distribution of muffins that maximizes the smallest piece
The Muffin Problem was first proposed by Alan Frank in 2011. Algorithms and solution methods were later extensively developed in The Muffin Book (2019), a collaboration between William Gasarch, Erik Metz, Jacob Prinz, and Daniel Smolyak, among others.
The theorems, conjectures, and procedures referenced by Muffins.jl are expanded upon and proven on the Muffin Website and in The Muffin Book.
For a larger, more advanced Julia package to solve more Muffin Problems, see The Muffin Package, developed by Stephanie Warman.
Muffins.jl is built and tested for Julia v1.4.
Download the appropriate version of Julia here.
Run julia in the terminal to open the Julia REPL and load the package by entering the following commands after the julia> prompt:
using Pkg
Pkg.add(PackageSpec(url="https://github.com/GeneralPoxter/Muffins.jl"))
using MuffinsThis installs Muffins.jl to your local Julia environment.
Include using Muffins at the top of any Julia file or in the Julia REPL after installation to run any of the below methods.
Let m and s be positive Int64-type variables. Let α be a positive Rational{Int64}-type variable.
To solve the Muffin Problem for m muffins and s students:
Muffins.muffins(m, s)An upper bound α for muffins(m, s) is found by testing (m, s) on all the bounding methods in the package (see Bounding methods). The upper bound α is then verified to be a lower bound for muffins(m, s) by finding a procedure where α is the smallest muffin piece cut (see Find Procedure). If all tests are conclusive, α is returned as the solution to muffins(m, s). Else, the method returns a lower bound for muffins(m,s) with a verifiable procedure.
Given (m, s), each bounding method finds and returns the upper bound α for muffins(m, s).
Most bounding methods also have a v-method that returns a boolean, verifying whether that bounding method can prove that the given α is an upper bound for muffins(m, s).
| Method | To find upper bound α: |
To verify α: |
|---|---|---|
| Floor-Ceiling Theorem | Muffins.fc(m, s) |
No v-method |
| Half Method | Muffins.half(m, s) |
Muffins.vhalf(m, s, α) |
| Interval Method | Muffins.int(m, s) |
Muffins.vint(m, s, α) |
| Midpoint Method | Muffins.mid(m, s) |
Muffins.vmid(m, s, α) |
| Easy Buddy Match | Muffins.ebm(m, s) |
No v-method |
| Hard Buddy Match | Muffins.hbm(m, s) |
No v-method |
| Gap Method | Muffins.gap(m, s) |
Muffins.vgap(m, s, α) |
To find potential procedures/solutions for dividing m muffins among s students where α is the smallest muffin piece cut:
Muffins.findproc(m, s, α)Returns an array of solutions. This method does not return all possible procedures.
To apply linear algebra and Cbc.jl to find muffins(m, s):
Muffins.solve(m, s)Returns the solution α. This is a work in progress in terms of speed and accuracy and should only be treated as a novelty.
All methods except for Matrix Solve can display their results and justify the process with a proof. How much text is displayed is determined by the optional keyword argument output:
- Set
outputto0for no printing or result display - Set
outputto1for result display without proofs - Set
outputto2for detailed proofs and result display
By default, output is set to 1 for Muffins.muffins(m, s) and 2 for all other methods with output.
For example, while Muffins.muffins(m, s) displays results without proofs, Muffins.muffins(m, s, output=2) displays results with proofs.
Except for Matrix Solve and the cases listed here, all Muffins.jl methods are correct for all cases listed in test.txt.
The user is free to test Muffins.jl by customizing and running test.jl (this would require accessing and modifying files in the package).
Muffins.jl was developed by Antara Hebbar and Jason Liu during the summer of 2020 under the mentorship of Professor William Gasarch.