AFTD Auto-Formalizing Theoretical Domains

cake_allocation_uses_at_most_cuts

def

An allocation of the cake [0, 1] among n agents with bundles C : Fin n → Set ℝ uses at most q cuts if there exist an integer k ≤ q and a strictly monotone sequence t : Fin (k + 2) → ℝ with t 0 = 0 and t (Fin.last (k + 1)) = 1 such that for every j : Fin (k + 1), the induced piece (the closed interval Set.Icc (t (Fin.castSucc j)) (t (Fin.succ j)) if j = 0, and the half-open interval Set.Ioc (t (Fin.castSucc j)) (t (Fin.succ j)) if j ≠ 0) is a subset of C i for some agent i : Fin n.

Statement

def cake_allocation_uses_at_most_cuts (n q : ℕ) (C : Fin n → Set ℝ) : Prop
Defined in
scout/2610-19733-exact-cut-complexity-of-equal-length-proportional-cake-cutt.md:235
Verified
23 Oct 2026
Axioms
none listed
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

Read back from the Lean

The definition cake_allocation_uses_at_most_cuts n q C asserts that there exist: 1. a natural number $k$ with $k \le q$, and 2. a function $t : \text{Fin}(k + 2) \to \mathbb{R}$, such that: - $t$ is strictly monotone (StrictMono t), - $t(0) = 0$, - $t(\text{last}) = 1$ (where the last element of $\text{Fin}(k+2)$ is index $k+1$), and - for every $j \in \text{Fin}(k + 1)$, there exists an index $i \in \text{Fin}(n)$ such that: - if $j = 0$, the closed interval $[t(j), t(j+1)]$ is a subset of $C(i)$, - if $j \ne 0$, the left-open, right-closed interval $(t(j), t(j+1)]$ is a subset of $C(i)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An allocation of the cake among n agents uses at most q cuts if there is a strictly monotone partition with at most q interior cuts whose pieces each lie in some bundle. -/
def cake_allocation_uses_at_most_cuts (n q : ℕ) (C : Fin n → Set ℝ) : Prop :=
  ∃ (k : ℕ) (_hk : k ≤ q) (t : Fin (k + 2) → ℝ),
    StrictMono t ∧
    t 0 = 0 ∧
    t (Fin.last (k + 1)) = 1 ∧
    ∀ j : Fin (k + 1), ∃ i : Fin n,
      (if j = 0 then Set.Icc (t (Fin.castSucc j)) (t (Fin.succ j))
       else Set.Ioc (t (Fin.castSucc j)) (t (Fin.succ j))) ⊆ C i
See it in the graphDiscuss this resultChallenge it