import Mathlib /-! # Soup Servings There are two types of soup: type A and type B. Initially, we have n ml of each type of soup. There are four kinds of operations: Serve 100 ml of soup A and 0 ml of soup B, Serve 75 ml of soup A and 25 ml of soup B, Serve 50 ml of soup A and 50 ml of soup B, and Serve 25 ml of soup A and 75 ml of soup B. When we serve some soup, we give it to someone, and we no longer have it. Each turn, we will choose from the four operations with an equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as possible. Both soups are served simultaneously in each turn. We stop as soon as either soup is empty. Note that we do not have an operation where all 100 ml's of soup B are used first. Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time. Answers within 10^-5 of the actual answer will be accepted. ## Constraints - 0 <= n <= 10^9 ## Provided examples - `n = 50` → `0.625` - `n = 100` → `0.71875` - `n = 0` → `0.5` ## Synthesized negative examples - invalid input: `n = 1000000001` ([structural] a predicate that admits 0 <= n <= 10^9. one step above the stated maximum) - invalid input: `n = 10000000000` ([structural] a predicate that admits 0 <= n <= 10^9. an order of magnitude above the ceiling) - invalid input: `n = 1000000000000000000` ([structural] a predicate that admits 0 <= n <= 10^9. far beyond the stated maximum) - `n = 50` → `0.5` is wrong ([structural] omits the +0.5 P(tie) term. drops tie contribution) - `n = 100` → `0.8125` is wrong ([structural] the tie contribution is added without the half factor. counts a tie as full success instead of half) - `n = 0` → `0.0` is wrong ([structural] n=0 is special-cased to zero without considering the process. no operations occur, so the answer is taken as 0) -/ namespace PSoupServings abbrev Input := Nat abbrev Output := Float /-! ### Specification helpers -/ /-- The four allowed operations as (ml of A, ml of B) pairs. -/ def SoupOps : List (Nat × Nat) := [(100, 0), (75, 25), (50, 50), (25, 75)] /-- One operation applied to a state; truncated subtraction serves as much as remains. -/ def soupStep (s op : Nat × Nat) : Nat × Nat := (s.1 - op.1, s.2 - op.2) /-- The state reached from `n` ml of each soup by performing the operations in order. -/ def soupStateAfter (ops : List (Nat × Nat)) (n : Nat) : Nat × Nat := ops.foldl soupStep (n, n) /-- At least one soup is empty, which is where serving stops. -/ def SoupTerminalState (s : Nat × Nat) : Prop := s.1 = 0 ∨ s.2 = 0 /-- `s` is a run of allowed operations from `(n, n)` that first turns terminal at its end with A empty and B remaining. -/ def SoupRunAFirst (s : List (Nat × Nat)) (n : Nat) : Prop := (∀ op ∈ s, op ∈ SoupOps) ∧ (∀ k : Nat, k < s.length → ¬ SoupTerminalState (soupStateAfter (s.take k) n)) ∧ (soupStateAfter s n).1 = 0 ∧ 0 < (soupStateAfter s n).2 /-- `s` is a run of allowed operations from `(n, n)` that first turns terminal at its end with both soups empty. -/ def SoupRunTie (s : List (Nat × Nat)) (n : Nat) : Prop := (∀ op ∈ s, op ∈ SoupOps) ∧ (∀ k : Nat, k < s.length → ¬ SoupTerminalState (soupStateAfter (s.take k) n)) ∧ (soupStateAfter s n).1 = 0 ∧ (soupStateAfter s n).2 = 0 /-- A nonnegative Float read as a rational: the floor of `f * 10^12` divided by `10^12`. -/ def floatToRat (f : Float) : Rat := (Float.toUInt64 (f * 1e12)).toNat / 1000000000000 /-! ### Validity predicate (V) -/ /-- Valid input: an initial volume of at most 10^9 ml. -/ def isValidInput (input : Input) : Bool := decide (input ≤ 1000000000) /-! ### Ideal specification (P_spec) -/ /-- `result` is within `10^-5` of the exact answer: the probability that A empties first plus half the probability of a simultaneous emptying. -/ def soupServingsProbability_spec (input : Input) (result : Output) : Prop := ∃ p : ℝ, |(floatToRat result : ℝ) - p| ≤ (1 : ℝ) / 10 ^ 5 ∧ p = (∑' s : {s : List (Nat × Nat) // SoupRunAFirst s input}, (1 / 4 : ℝ) ^ s.val.length) + (1 / 2 : ℝ) * (∑' s : {s : List (Nat × Nat) // SoupRunTie s input}, (1 / 4 : ℝ) ^ s.val.length) /-! ### Decidable specification (P_check) -/ /-- All sequences of allowed operations of a given length. -/ def soupSeqsOfLen : Nat → List (List (Nat × Nat)) | 0 => [[]] | k + 1 => (soupSeqsOfLen k).flatMap fun s => SoupOps.map fun op => op :: s /-- Upper bound on run length: each operation serves at least 25 ml of A, so from `(n, n)` A empties within `n / 25 + 1` operations. -/ def soupRunBound (n : Nat) : Nat := n / 25 + 1 /-- All operation sequences up to the run-length bound, which includes every run from `(n, n)`. -/ def soupSeqsToBound (n : Nat) : List (List (Nat × Nat)) := (List.range (soupRunBound n + 1)).flatMap soupSeqsOfLen /-- Boolean test for `SoupRunAFirst`: every operation is allowed, no proper prefix is terminal, and the final state has A empty with B remaining. -/ def soupRunAFirstTest (s : List (Nat × Nat)) (n : Nat) : Bool := s.all (fun op => SoupOps.any (fun o => decide (op = o))) && (List.range s.length).all (fun k => let st := soupStateAfter (s.take k) n st.1 != 0 && st.2 != 0) && decide ((soupStateAfter s n).1 = 0) && decide (0 < (soupStateAfter s n).2) /-- Boolean test for `SoupRunTie`: every operation is allowed, no proper prefix is terminal, and the final state has both soups empty. -/ def soupRunTieTest (s : List (Nat × Nat)) (n : Nat) : Bool := s.all (fun op => SoupOps.any (fun o => decide (op = o))) && (List.range s.length).all (fun k => let st := soupStateAfter (s.take k) n st.1 != 0 && st.2 != 0) && decide ((soupStateAfter s n).1 = 0) && decide ((soupStateAfter s n).2 = 0) /-- The total `(1/4)^length` weight of the enumerated sequences passing the given run test. -/ def soupWeight (n : Nat) (runTest : List (Nat × Nat) → Bool) : Rat := ((soupSeqsToBound n).filter runTest).foldr (fun s acc => (1 / 4 : Rat) ^ s.length + acc) 0 /-- The exact answer as a rational: the A-first weight plus half the tie weight over all runs. -/ def soupProbExact (n : Nat) : Rat := soupWeight n (fun s => soupRunAFirstTest s n) + (1 / 2 : Rat) * soupWeight n (fun s => soupRunTieTest s n) /-- Executable checker for `soupServingsProbability_spec`: compare `result` with the exact probability to within `10^-5`. -/ def soupServingsProbability_check (input : Input) (result : Output) : Bool := decide (|floatToRat result - soupProbExact input| ≤ (1 : Rat) / 10 ^ 5) /-- The tolerance comparison is the same question in ℚ and in ℝ. -/ theorem soup_abs_cast_le (a b : ℚ) : |((a : ℝ)) - ((b : ℝ))| ≤ (1 : ℝ) / 10 ^ 5 ↔ |a - b| ≤ (1 : ℚ) / 10 ^ 5 := by rw [← Rat.cast_sub, ← Rat.cast_abs, show ((1 : ℝ) / 10 ^ 5) = (((1 : ℚ) / 10 ^ 5 : ℚ) : ℝ) by push_cast; ring] exact Rat.cast_le /-- `soupSeqsOfLen k` is exactly the operation sequences of length `k`. -/ theorem soup_mem_seqsOfLen : ∀ (k : Nat) (s : List (Nat × Nat)), s ∈ soupSeqsOfLen k ↔ (s.length = k ∧ ∀ op ∈ s, op ∈ SoupOps) := by intro k induction k with | zero => intro s simp only [soupSeqsOfLen, List.mem_singleton] constructor · rintro rfl; simp · rintro ⟨h, -⟩; exact List.length_eq_zero_iff.mp h | succ k ih => intro s constructor · intro hs simp only [soupSeqsOfLen, List.mem_flatMap, List.mem_map] at hs obtain ⟨t, ht, op, hop, rfl⟩ := hs obtain ⟨hlen, hall⟩ := (ih t).mp ht refine ⟨by simp [hlen], ?_⟩ intro o ho rcases List.mem_cons.mp ho with rfl | ho' · exact hop · exact hall _ ho' · rintro ⟨hlen, hall⟩ cases s with | nil => simp at hlen | cons op t => simp only [soupSeqsOfLen, List.mem_flatMap, List.mem_map] refine ⟨t, (ih t).mpr ⟨by simpa using hlen, fun o ho => hall o (by simp [ho])⟩, op, hall op (by simp), rfl⟩ /-- The enumeration of a fixed length repeats nothing. -/ theorem soup_nodup_seqsOfLen : ∀ k : Nat, (soupSeqsOfLen k).Nodup := by intro k induction k with | zero => simp [soupSeqsOfLen] | succ k ih => simp only [soupSeqsOfLen] refine List.nodup_flatMap.2 ⟨?_, ?_⟩ · intro t _ refine List.Nodup.map ?_ (by decide) intro a b hab exact (List.cons_eq_cons.mp hab).1 · refine List.Pairwise.imp ?_ ih intro a₁ a₂ hne x h₁ h₂ obtain ⟨o₁, -, e₁⟩ := List.mem_map.1 h₁ obtain ⟨o₂, -, e₂⟩ := List.mem_map.1 h₂ exact hne (List.cons_eq_cons.mp (e₁.trans e₂.symm)).2 /-- `soupSeqsToBound n` is exactly the operation sequences no longer than the bound. -/ theorem soup_mem_seqsToBound (n : Nat) (s : List (Nat × Nat)) : s ∈ soupSeqsToBound n ↔ (s.length ≤ soupRunBound n ∧ ∀ op ∈ s, op ∈ SoupOps) := by simp only [soupSeqsToBound, List.mem_flatMap, List.mem_range] constructor · rintro ⟨k, hk, hs⟩ obtain ⟨hlen, hall⟩ := (soup_mem_seqsOfLen k s).mp hs exact ⟨by omega, hall⟩ · rintro ⟨hlen, hall⟩ exact ⟨s.length, by omega, (soup_mem_seqsOfLen s.length s).mpr ⟨rfl, hall⟩⟩ /-- The enumeration up to the bound repeats nothing. -/ theorem soup_nodup_seqsToBound (n : Nat) : (soupSeqsToBound n).Nodup := by simp only [soupSeqsToBound] refine List.nodup_flatMap.2 ⟨fun k _ => soup_nodup_seqsOfLen k, ?_⟩ refine List.Pairwise.imp ?_ List.nodup_range intro a₁ a₂ hne x h₁ h₂ exact hne (((soup_mem_seqsOfLen a₁ x).mp h₁).1.symm.trans ((soup_mem_seqsOfLen a₂ x).mp h₂).1) /-- Every allowed operation serves at least 25 ml of soup A. -/ theorem soup_op_ge (op : Nat × Nat) (hop : op ∈ SoupOps) : 25 ≤ op.1 := by fin_cases hop <;> norm_num /-- After `k` allowed operations soup A has fallen by at least `25 * k`. -/ theorem soup_fst_le : ∀ (s : List (Nat × Nat)) (a b : Nat), (∀ op ∈ s, op ∈ SoupOps) → (s.foldl soupStep (a, b)).1 ≤ a - 25 * s.length := by intro s induction s with | nil => intro a b _; simp | cons op t ih => intro a b hops have hop : 25 ≤ op.1 := soup_op_ge op (hops op (by simp)) have hrec := ih (a - op.1) (b - op.2) (fun o ho => hops o (by simp [ho])) simp only [List.foldl_cons, soupStep, List.length_cons] omega /-- A run whose proper prefixes are all non-terminal is no longer than the bound. -/ theorem soup_len_le (n : Nat) (s : List (Nat × Nat)) (hops : ∀ op ∈ s, op ∈ SoupOps) (hpre : ∀ k : Nat, k < s.length → ¬ SoupTerminalState (soupStateAfter (s.take k) n)) : s.length ≤ soupRunBound n := by rcases Nat.eq_zero_or_pos s.length with h0 | hpos · simp only [soupRunBound]; omega · have hnt := hpre (s.length - 1) (by omega) simp only [SoupTerminalState, not_or, soupStateAfter] at hnt have hle := soup_fst_le (s.take (s.length - 1)) n n (fun o ho => hops o (List.take_subset _ _ ho)) have hlen : (s.take (s.length - 1)).length = s.length - 1 := by simp only [List.length_take]; omega rw [hlen] at hle simp only [soupRunBound] omega /-- The boolean run test is the run predicate, clause for clause. -/ theorem soupRunAFirstTest_iff (s : List (Nat × Nat)) (n : Nat) : soupRunAFirstTest s n = true ↔ SoupRunAFirst s n := by simp [soupRunAFirstTest, SoupRunAFirst, SoupTerminalState, not_or, and_assoc] /-- The boolean tie test is the tie predicate, clause for clause. -/ theorem soupRunTieTest_iff (s : List (Nat × Nat)) (n : Nat) : soupRunTieTest s n = true ↔ SoupRunTie s n := by simp [soupRunTieTest, SoupRunTie, SoupTerminalState, not_or, and_assoc] /-- The enumerated rational weight of a run predicate is its real-valued sum over all runs. -/ theorem soup_weight_eq_tsum (n : Nat) (P : List (Nat × Nat) → Prop) (test : List (Nat × Nat) → Bool) (hiff : ∀ s, test s = true ↔ P s) (hsub : ∀ s, P s → s.length ≤ soupRunBound n ∧ ∀ op ∈ s, op ∈ SoupOps) : ((soupWeight n test : ℚ) : ℝ) = ∑' s : {s : List (Nat × Nat) // P s}, (1 / 4 : ℝ) ^ s.val.length := by have hmem : ∀ s : List (Nat × Nat), s ∈ (soupSeqsToBound n).filter test ↔ P s := by intro s rw [List.mem_filter, soup_mem_seqsToBound] constructor · rintro ⟨-, ht⟩; exact (hiff s).mp ht · intro hp; exact ⟨hsub s hp, (hiff s).mpr hp⟩ have hnodup : ((soupSeqsToBound n).filter test).Nodup := List.Nodup.filter _ (soup_nodup_seqsToBound n) have hfold : ∀ l : List (List (Nat × Nat)), ((l.foldr (fun s acc => (1 / 4 : ℚ) ^ s.length + acc) 0 : ℚ) : ℝ) = (l.map (fun s => (1 / 4 : ℝ) ^ s.length)).sum := by intro l induction l with | nil => simp | cons a t ih => simp only [List.foldr_cons, List.map_cons, List.sum_cons, Rat.cast_add, ih] push_cast ring calc ((soupWeight n test : ℚ) : ℝ) = (((soupSeqsToBound n).filter test).map (fun s => (1 / 4 : ℝ) ^ s.length)).sum := by simp only [soupWeight]; exact hfold _ _ = ∑ x ∈ ((soupSeqsToBound n).filter test).toFinset, (1 / 4 : ℝ) ^ x.length := (List.sum_toFinset (fun s : List (Nat × Nat) => (1 / 4 : ℝ) ^ s.length) hnodup).symm _ = ∑' x : {x : List (Nat × Nat) // x ∈ ((soupSeqsToBound n).filter test).toFinset}, (1 / 4 : ℝ) ^ (x : List (Nat × Nat)).length := (Finset.tsum_subtype ((soupSeqsToBound n).filter test).toFinset (fun s : List (Nat × Nat) => (1 / 4 : ℝ) ^ s.length)).symm _ = ∑' s : {s : List (Nat × Nat) // P s}, (1 / 4 : ℝ) ^ s.val.length := (Equiv.tsum_eq (Equiv.subtypeEquivRight (fun x => ((List.mem_toFinset).trans (hmem x)).symm)) (fun x : {x : List (Nat × Nat) // x ∈ ((soupSeqsToBound n).filter test).toFinset} => (1 / 4 : ℝ) ^ (x : List (Nat × Nat)).length)).symm.trans (tsum_congr (fun _ => by rfl)) /-- The exact rational the checker computes is the specification's real-valued sum. -/ theorem soup_exact_eq_tsum (n : Nat) : ((soupProbExact n : ℚ) : ℝ) = (∑' s : {s : List (Nat × Nat) // SoupRunAFirst s n}, (1 / 4 : ℝ) ^ s.val.length) + (1 / 2 : ℝ) * (∑' s : {s : List (Nat × Nat) // SoupRunTie s n}, (1 / 4 : ℝ) ^ s.val.length) := by have hA : ((soupWeight n (fun s => soupRunAFirstTest s n) : ℚ) : ℝ) = ∑' s : {s : List (Nat × Nat) // SoupRunAFirst s n}, (1 / 4 : ℝ) ^ s.val.length := soup_weight_eq_tsum n (fun s => SoupRunAFirst s n) (fun s => soupRunAFirstTest s n) (fun s => soupRunAFirstTest_iff s n) (fun s hs => ⟨soup_len_le n s hs.1 hs.2.1, hs.1⟩) have hT : ((soupWeight n (fun s => soupRunTieTest s n) : ℚ) : ℝ) = ∑' s : {s : List (Nat × Nat) // SoupRunTie s n}, (1 / 4 : ℝ) ^ s.val.length := soup_weight_eq_tsum n (fun s => SoupRunTie s n) (fun s => soupRunTieTest s n) (fun s => soupRunTieTest_iff s n) (fun s hs => ⟨soup_len_le n s hs.1 hs.2.1, hs.1⟩) simp only [soupProbExact] push_cast rw [hA, hT] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem soupServingsProbability_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : soupServingsProbability_check input result ↔ soupServingsProbability_spec input result := by unfold soupServingsProbability_check soupServingsProbability_spec rw [decide_eq_true_iff] constructor · intro hc refine ⟨((soupProbExact input : ℚ) : ℝ), ?_, soup_exact_eq_tsum input⟩ exact (soup_abs_cast_le _ _).mpr hc · rintro ⟨p, hp, rfl⟩ rw [← soup_exact_eq_tsum input] at hp exact (soup_abs_cast_le _ _).mp hp /-! ### Implementation helpers -/ /-- The scaled unit count: `ceil(n / 25)` servings of 25 ml. -/ def scaleAmount (n : Nat) : Nat := (n + 24) / 25 /-- The successor of the scaled state `s` under operation `op`: serve `op` from `(25*s.1, 25*s.2)` via `soupStep` and rescale. -/ def scaledNext (s op : Nat × Nat) : Nat × Nat := let st := soupStep (25 * s.1, 25 * s.2) op (st.1 / 25, st.2 / 25) /-- Bottom-up DP over scaled states `(a, b)` with `a, b ≤ m`, filled in increasing `a + b` order; returns `p(m, m)`. -/ def soupDp (m : Nat) : Float := let size := m + 1 let value (tbl : Array Float) (a b : Nat) : Float := if a = 0 ∧ b = 0 then 0.5 else if a = 0 then 1.0 else if b = 0 then 0.0 else let total := SoupOps.foldl (fun acc op => let nxt := scaledNext (a, b) op acc + tbl[nxt.1 * size + nxt.2]!) 0.0 total / 4.0 let tbl := (List.range (2 * m + 1)).foldl (fun (tbl : Array Float) k => (List.range size).foldl (fun (tbl : Array Float) a => let b := k - a if b < size then tbl.setIfInBounds (a * size + b) (value tbl a b) else tbl) tbl) (List.replicate (size * size) 0.0).toArray tbl[m * size + m]! /-! ### Main algorithm (impl) -/ /-- Soup-servings probability by dynamic programming over 25 ml units, with the answer 1.0 once `n > 4800`. -/ def soupServings (input : Input) : Output := if input > 4800 then 1.0 else soupDp (scaleAmount input) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem soupServings_correct (input : Input) (h : isValidInput input) : soupServingsProbability_spec input (soupServings input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 50 #guard isValidInput 100 #guard isValidInput 0 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 1000000001) #guard !(isValidInput 10000000000) #guard !(isValidInput 1000000000000000000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard soupServingsProbability_check 50 0.625 #guard soupServingsProbability_check 100 0.71875 #guard soupServingsProbability_check 0 0.5 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(soupServingsProbability_check 50 0.5) #guard !(soupServingsProbability_check 100 0.8125) #guard !(soupServingsProbability_check 0 0.0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard soupServings 50 == 0.625 #guard soupServings 100 == 0.71875 #guard soupServings 0 == 0.5 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard soupServingsProbability_check 50 (soupServings 50) #guard soupServingsProbability_check 100 (soupServings 100) #guard soupServingsProbability_check 0 (soupServings 0) end PSoupServings