EUVIMEDEUVIMED entdecken
Crossref

Exact Number of Flips Required to Sort a Burnt Stack of Pancakes

Gerold Jäger, Nacim Oijid

Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 84-92

DOI: 10.1609/socs.v19i1.43076 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Gerold Jäger und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this work, we consider the burnt pancake problem, which is a well-studied problem going back to a work of Gates and Papadimitriou from 1979. The problem is to sort a stack of n one-sided burnt pancakes of different sizes, by a sequence of flips of the top pancakes, such that at the end of the flipping sequence the pancakes have increasing size and the burnt sides of all pancakes are face-down. The pancakes are denoted by 1, 2, ..., n, and a number is multiplied by -1, if the corresponding pancake has burnt side face-up. Let T(n) be the minimum number of flips to sort a special stack of n pancakes, namely [-1,-2,...,-n]. This instance has strong relevance because of its easy structure and as it has been shown to be a worst-case instance for several small n. Heydari and Sudborough gave in 1997 the currently best upper bound of T(n), namely (3n+3)/2 for n = 3 mod 4, which later has been shown to be exact by a work of Cibulka from 2011. Except these two works, no progress regarding lower and upper bounds has been made until now. In our work, we present that (3n+3)/2 is also an upper bound of T(n) for n = 1 mod 4, which again matches the lower bound of Cibulka in 2011 and thus is exact. Furthermore, we show that our construction approach for n = 1 mod 4 and the one of Heydari and Sudborough for n = 3 mod 4 cannot be applied for even n. However, as there might be different construction approaches, the case of even n remains an open problem, where two possible values for T(n) are possible, namely (3/2)n + 1 or (3/2)n + 2. Finally, we found two values, namely n = 24, n = 26, where the lower bound is attained.

Zitieren

APA

Jäger, G., & Oijid, N. (2026). Exact Number of Flips Required to Sort a Burnt Stack of Pancakes. Proceedings of the International Symposium on Combinatorial Search, 19(1), 84-92. https://doi.org/10.1609/socs.v19i1.43076

Vancouver

Jäger G, Oijid N. Exact Number of Flips Required to Sort a Burnt Stack of Pancakes. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):84-92. doi:10.1609/socs.v19i1.43076

BibTeX
@article{Jger2026,
  author = {Jäger, Gerold and Oijid, Nacim},
  title = {Exact Number of Flips Required to Sort a Burnt Stack of Pancakes},
  journal = {Proceedings of the International Symposium on Combinatorial Search},
  year = {2026},
  volume = {19},
  number = {1},
  pages = {84--92},
  doi = {10.1609/socs.v19i1.43076}
}
Kostenlos starten →