کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435556 | 689915 | 2016 | 16 صفحه PDF | دانلود رایگان |
A stack of n pancakes can be rearranged in all n ! ways by a sequence of n!−1n!−1 flips, and a stack of n ‘burnt’ pancakes can be rearranged in all 2nn!2nn! ways by a sequence of 2nn!−12nn!−1 flips. In both cases, a computer program can efficiently generate suitable solutions. We approach these tasks instead from a human perspective. How can we determine the next flip directly from the current stack? How can we flip the minimum or maximum number of (burnt) pancakes overall? What if we are only allowed to flip the top n−2n−2, n−1n−1, or n (burnt) pancakes? We answer the first question with simple successor rules that take worst-case O(n)O(n)-time and amortized O(1)O(1)-time. Then we answer the second question exactly for minimization, and provide conjectures for maximization. For the third question, we prove that solutions almost certainly exist for pancakes and burnt pancakes using only these three flips. More broadly, we discuss how efficiency and optimality can shape iterative solutions to Hamilton cycle problems in highly symmetric graphs.
Journal: Theoretical Computer Science - Volume 609, Part 1, 4 January 2016, Pages 60–75