Cake Cutting

Mathematics major Christian Bechler and Computer Science major Kenan Bitikofer worked with David Housman on a Maple Scholars project examining cake cutting.  “I cut and you choose” is a two-step algorithm to ensure that two people share a cake in an envy free manner. Selfridge and Conway independently found a four-step algorithm to ensure that three people share a cake in an envy free manner. In 2016, Aziz and Mackenzie claimed to have generalized these results: an algorithm that used a bounded number of steps to ensure that any number of people share a cake in an envy free manner. Christian and Kenan implemented and tested parts of the Aziz and Mackenzie algorithm. What appeared at first to be bugs in their code turned out to be a flaw in the algorithm and proof provided by Aziz and Mackenzie. Christian and Kenan finished the summer by constructing a five person example in which the Aziz and Mackenzie algorithm would stop before completion. Their final report can be accessed from David Housman’s Undergraduate Research Page.

Maple Scholars is an eight-week summer program that gives students the opportunity to participate in independent research projects alongside Goshen College faculty of various disciplines. Scholars keep each other informed of their progress in weekly seminars, and the program ends with a celebration involving a public poster session, presentations, and a dinner. Christian and Kenan also presented their work at MathFest 2017 in Chicago. The picture shows Christian and Kenan relaxing after giving their MathFest talks.