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

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

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

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Heidi Gebauer

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