Grabbing Olives on Linear Pizzas and Pissaladières

Authors Jean-Claude Bermond, Frédéric Havet, Michel Cosnard



PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.12.pdf
  • Filesize: 1.84 MB
  • 20 pages

Document Identifiers

Author Details

Jean-Claude Bermond
  • Université Côte d'Azur, Coati, I3S, CNRS, INRIA, Sophia Antipolis, France
Frédéric Havet
  • Université Côte d'Azur, Coati, I3S, CNRS, INRIA, Sophia Antipolis, France
Michel Cosnard
  • Université Côte d'Azur, Coati, I3S, CNRS, INRIA, Sophia Antipolis, France

Cite AsGet BibTex

Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.12

Abstract

In this paper we revisit the problem entitled Sharing a Pizza stated by P. Winkler by considering a new puzzle called Sharing a Pissaladiere. The game is played by two polite coatis Alice and Bob who share a pissaladière (a p×q grid) which is divided into rectangular slices. Alice starts in a corner and then the coatis alternate removing a remaining slice adjacent to at most two other slices. On some slices there are precious olives of Nice and the aim of each coati is to grab the maximum number of olives. We first study the particular case of 1×n grid (i.e. a path) where the game is a graph grabbing game known as Sharing a linear pizza. In that case each player can take only an end vertex of the remaining path. These problems are particular cases of a new class of games called d-degenerate games played on a graph with non negative weights assigned to the vertices with the rule that coatis alternatively take a vertex of degree at most d. Our main results are the following. We give optimal strategies for paths (linear pizzas) with no two adjacent weighty vertices. We also give a recurrence formula to compute the gains which depend only on the parity of n and of the respective parities of weighty vertices with a complexity in O(h²) where h denotes the number of parity changes in the weighty vertices. When the weights are only {0,1} we reduce the computation of the average number of olives collected by each player to a word counting problem. We solve Sharing a pissaladière with {0,1} weights, when there is one olive or 2 olives. In that case Alice (resp. Bob) grabs almost all the olives if the number of vertices of the grid n = p×q is odd (resp. even). We prove that for a 2×q grid with a fixed number k of olives Bob grabs at least ⌈(k-1)/3⌉ olives and almost always grabs all the k olives.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Grabbing game
  • degenerate graph
  • path
  • grid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jean-Claude Bermond, Michel Cosnard, and Frédéric Havet. Grabbing olives on linear pizzas and pissaladières. Working paper, March 2022. URL: https://hal.inria.fr/hal-03623938.
  2. Josef Cibulka, Jan Kyncl, Viola Mészáros, Rudolf Stolar, and Pavel Valtr. Solution of Peter Winkler’s pizza problem. In Jirí Fiala, Jan Kratochvíl, and Mirka Miller, editors, International Workshop on Combinatorial Algorithms - IWOCA, volume 5874 of Lecture Notes in Computer Science, pages 356-367. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-10217-2_35.
  3. Josef Cibulka, Jan Kyncl, Viola Mészáros, Rudolf Stolar, and Pavel Valtr. Graph sharing games: Complexity and connectivity. Theoretical Computer Science, 494:49-62, 2013. URL: https://doi.org/10.1016/j.tcs.2012.12.029.
  4. Yoshimi Egawa, Hikoe Enomoto, and Naoki Matsumoto. The graph grabbing game on K_m,n-trees. Discrete Mathematics, 341(6):1555-1560, 2018. URL: https://doi.org/10.1016/j.disc.2018.02.023.
  5. Soogang Eoh and Jihoon Choi. The graph grabbing game on 0,1-weighted graphs. Results in Applied Mathematics, 3:100028, 2019. URL: https://doi.org/10.1016/j.rinam.2019.100028.
  6. Kolja Knauer, Piotr Micek, and Torsten Ueckerdt. How to eat 4/9 of a pizza. Discrete Mathematics, 311(16):1635-1645, 2011. URL: https://doi.org/10.1016/j.disc.2011.03.015.
  7. Urban Larsson, Richard J. Nowakowski, and Carlos Pereira dos Santos. Games of No Chance 5, volume 70 of MSRI Publications, chapter 3 Scoring games: the state of the play, pages 89-111. Cambridge University Press, 2017. Google Scholar
  8. Piotr Micek and Bartosz Walczak. A graph-grabbing game. Combinatorics, Probability and Computing, 20(4):623-629, 2011. URL: https://doi.org/10.1017/S0963548311000071.
  9. Piotr Micek and Bartosz Walczak. Parity in graph sharing games. Discrete Mathematics, 312(10):1788-1795, 2012. URL: https://doi.org/10.1016/j.disc.2012.01.037.
  10. Moshe Rosenfeld. A gold grabbing game, http://garden.irmacs.sfu.ca/category/rosenfeld, 2009. Google Scholar
  11. Deborah E. Seacrest and Tyler Seacrest. Grabbing the gold. Discrete Mathematics, 312(10):1804-1806, 2012. URL: https://doi.org/10.1016/j.disc.2012.01.010.
  12. Peter Winkler. Mathematical Puzzles: a connoisseur’s collection. CRC Press, 2004. Google Scholar
  13. Peter Winkler. Problem posed at Building Bridges, a conference in honour of 60th birthday of L. Lovász, Budapest, 2008. Google Scholar
  14. Peter Winkler. Mathematical Puzzles. A K Peters CRC Press, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail