## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 27, 2011, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Heidi Gebauer

## A Doubly Exponentially Crumbled Cake

We consider the following problem, which (in purely mathematical terms) was described by Winkler: Alice has baked a square cake with raisins for Bob, but really she would like to keep most of it for herself. In this, she relies on a peculiar habit of Bob: he eats only rectangular pieces of the cake, with sides parallel to the sides of the cake, that contain exactly one raisin each, and that raisin has to be exactly in the lower left corner. Alice gets whatever remains after Bob has cut out all such pieces. In order to give Bob at least some chance, Alice has to put a raisin in the lower left corner of the whole cake. A natural question is to determine the maximum fraction Bob can achieve. It is known that Alice can limit Bob's share to roughly one half. From the other side not so much is known. We show that, if Alice has not too many points to set, then Bob can secure a reasonable fraction of the cake. More precisely, if Alice wants to prevent Bob from getting more than 1/r of the cake, she needs at least 2^{2^{r/2}} points. A problem which is close to our setting is Winkler's pizza problem, which is now solved due to results of Knauer et al., and Cibulka et al. Joint work with Tobias Christ, Andrea Francke, Jirka Matousek and Takeaki Uno

Information for students and suggested topics for student talks