A Doubly Exponentially Crumbled Cake

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125601" target="_blank" >RIV/00216208:11320/12:10125601 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S1571065311001132" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1571065311001132</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.endm.2011.09.044" target="_blank" >10.1016/j.endm.2011.09.044</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Doubly Exponentially Crumbled Cake

Popis výsledku v původním jazyce

We consider the following cake cutting game: Alice chooses a set P of n points in the square (cake) image [0,1]^2, where (0,0) is in P; Bob cuts out n axis-parallel rectangles with disjoint interiors, each of them having a point of P as the lower left corner; Alice keeps the rest. It has been conjectured that Bob can always secure at least half of the cake. This remains unsettled, and it is not even known whether Bob can get any positive fraction independent of n. We prove that if Alice can force Bob?sshare to tend to zero, then she must use very many points; namely, to prevent Bob from gaining more than 1/r of the cake, she needs at least 2^{2^Omega(r)} points.

Název v anglickém jazyce

A Doubly Exponentially Crumbled Cake

Popis výsledku anglicky

We consider the following cake cutting game: Alice chooses a set P of n points in the square (cake) image [0,1]^2, where (0,0) is in P; Bob cuts out n axis-parallel rectangles with disjoint interiors, each of them having a point of P as the lower left corner; Alice keeps the rest. It has been conjectured that Bob can always secure at least half of the cake. This remains unsettled, and it is not even known whether Bob can get any positive fraction independent of n. We prove that if Alice can force Bob?sshare to tend to zero, then she must use very many points; namely, to prevent Bob from gaining more than 1/r of the cake, she needs at least 2^{2^Omega(r)} points.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Notes in Discrete Mathematics

ISSN

1571-0653

e-ISSN

—

Svazek periodika

2011

Číslo periodika v rámci svazku

38

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

7

Strana od-do

265-271

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—