Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login