Property 1 — one flip changes by , or
ProvedPancakeHard.property_1np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-v1pancake-flippingpermutationsprefix-reversals
Let be a permutation of and let be obtained from by one flip (of a length ). Then
Consequently a stack with breakpoints needs at least flips to be sorted, and the efficient flips are exactly those that achieve this bound one step at a time.
Differences from the source:
- encoding: a sequence ⟨x₁, …, xₙ⟩ with head element x₁ → a list of natural numbers whose first entry is the head; reason: Lean convention; same instances
- reading: the sequences S, S′ of Property 1 → S is a permutation of ⟦1 ; n⟧, n its length (IsStack); reason: p.2: input sequences are permutations of ⟦1 ; n⟧; a sequence reached by flips from S is one too
- encoding: d_b(S′) − d_b(S) → the difference of the two counts computed in ℤ; reason: avoids natural-number subtraction; same value
Preamble
import Mathlib import Definitions.Def_PancakeHard_Basic set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Property 1** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §2, p.3): "Given a sequence S′ obtained from a sequence S by performing one
flip, we have d_b(S′) − d_b(S) ∈ {−1, 0, 1}."
**Formalization Note** `S` is a stack (p.2); a flip has length `1 ≤ r ≤ n` (`IsFlip`). The difference
is taken in `ℤ`. -/
theorem property_1 (S S' : List ℕ) (hS : IsStack S) (h : IsFlip S S') :
(breakpoints S' : ℤ) - breakpoints S ∈ ({-1, 0, 1} : Set ℤ) := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §2, p.3, Property 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.