Skip to content

Latest commit

 

History

History
83 lines (63 loc) · 5.33 KB

README.md

File metadata and controls

83 lines (63 loc) · 5.33 KB

Muffins.jl

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.

Requirements

Muffins.jl is built and tested for Julia v1.4.
Download the appropriate version of Julia here.

Installation

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 Muffins

This 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.

Usage

Let m and s be positive Int64-type variables. Let α be a positive Rational{Int64}-type variable.

General Solution

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.

Bounding methods

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, α)

Find Procedure

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.

Matrix Solve

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.

Output mode

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 output to 0 for no printing or result display
  • Set output to 1 for result display without proofs
  • Set output to 2 for 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.

Accuracy

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).

Development

Muffins.jl was developed by Antara Hebbar and Jason Liu during the summer of 2020 under the mentorship of Professor William Gasarch.