pyranim_collision_prob_one
The collision probability pyranim_collision_prob 1 for a 1-tier pyramid game is equal to 1 / 2.
Statement
theorem pyranim_collision_prob_one : pyranim_collision_prob 1 = 1 / 2- Formalizes
- arXiv:2611.16153 Sec. 5.3, Question 4
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- pyranim_collision_probFor a natural number n, pyranim_collision_prob n is the ratio of the number of pairs (X, Y) in pyranim_stable_positions n ×ˢ…
- pyranim_full_pyramidThe finite set pyranim_full_pyramid n : Finset (ℕ × ℕ) of pairs of natural numbers (i, j) such that 1 ≤ i ≤ j ≤ n, defined by filtering…
- pyranim_optionsFor a position X : Finset (ℕ × ℕ), pyranim_options X is the finite set of successor positions obtained by applying pyranim_remove X c for…
- pyranim_stable_positionsFor a natural number n, pyranim_stable_positions n is the finite set of all subsets X of pyranim_full_pyramid n that satisfy the order…
- pyranim_game_isoTwo Pyranim positions X and Y are game-isomorphic if there exists a bisimulation relation R relating X and Y such that whenever R A B…
- pyranim_is_order_idealA finite set of chips X : Finset (ℕ × ℕ) is an order ideal if whenever p ∈ X and a, b are natural numbers with p.1 ≤ a ≤ b ≤ p.2, the…
Read back from the Lean
The value of pyranim_collision_prob at 1 is equal to 1 / 2 (as a real number).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The collision probability for a 1-tier pyramid game is computed by explicitly finding all stable positions and determining which pairs among them are game-isomorphic. For n = 1, the full pyramid consists only of the cell (1, 1), so its stable positions (order ideals) are just the empty set ∅ and the singleton {(1, 1)}. Reflexivity shows that the two diagonal pairs are game-isomorphic, whereas the two mixed pairs cannot be isomorphic because the empty position has 0 options while the singleton position has 1 option. Exactly 2 of the 2² = 4 pairs of stable positions are isomorphic, giving a collision probability of 2 / 4 = 1/2.
Game isomorphism is reflexive: every position X is game-isomorphic to itself.
We show pyranim_game_iso X X by witnessing the equality relation R A B := (A = B) as a game bisimulation. The base condition R X X holds by reflexivity. Given A = B, the identity equivalence Equiv.refl between pyranim_options A and pyranim_options B maps every option o to itself, satisfying R o (Equiv.refl o).
uses
Equiv.refluse (fun A B => A = B) refine ⟨rfl, ?_⟩ intro A B h subst h refine ⟨Equiv.refl _, ?_⟩ intro o rfl
The empty position ∅ and the singleton position {(1, 1)} are not game-isomorphic.
Suppose for contradiction that ∅ and {(1, 1)} are isomorphic via a bisimulation R. Then there exists an equivalence f between their option sets. However, pyranim_options ∅ is empty, whereas pyranim_options {(1, 1)} = {∅} is nonempty (containing ∅ by Finset.mem_singleton_self). Applying the inverse equivalence f.symm to this option yields an element of an empty type, which contradicts IsEmpty.false.
uses
Finset.mem_singleton_self,IsEmpty.falseintro ⟨R, hR, hstep⟩ rcases hstep ∅ {(1, 1)} hR with ⟨f, hf⟩ have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide] infer_instance have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide] exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩ exact IsEmpty.false (f.symm h2.some)
The singleton position {(1, 1)} and the empty position ∅ are not game-isomorphic.
Suppose for contradiction that {(1, 1)} and ∅ are isomorphic. Then there is an equivalence f from pyranim_options {(1, 1)} to pyranim_options ∅. As pyranim_options {(1, 1)} contains ∅ by Finset.mem_singleton_self, applying f produces an element in the empty type pyranim_options ∅, yielding a contradiction via IsEmpty.false.
uses
Finset.mem_singleton_self,IsEmpty.falseintro ⟨R, hR, hstep⟩ rcases hstep {(1, 1)} ∅ hR with ⟨f, hf⟩ have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide] infer_instance have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide] exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩ exact IsEmpty.false (f h2.some)
The game-isomorphic pairs in {∅, {(1, 1)}} ×ˢ {∅, {(1, 1)}} are precisely (∅, ∅) and ({(1, 1)}, {(1, 1)}).
By extensionality, a pair (X, Y) belongs to the filtered Cartesian product if and only if X, Y ∈ {∅, {(1, 1)}} and X ≅ Y. Unfolding membership with Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, and Prod.mk.injEq gives four cases. The mixed pairs (∅, {(1, 1)}) and ({(1, 1)}, ∅) are ruled out via False.elim using pyranim_collision_prob_one_not_game_iso_empty_singleton and pyranim_collision_prob_one_not_game_iso_singleton_empty. Conversely, the diagonal pairs (∅, ∅) and ({(1, 1)}, {(1, 1)}) are isomorphic by pyranim_collision_prob_one_game_iso_refl.
uses
Finset.mem_filter,Finset.mem_product,Finset.mem_insert,Finset.mem_singleton,Prod.mk.injEq,False.elim,pyranim_collision_prob_one_not_game_iso_empty_singleton,pyranim_collision_prob_one_not_game_iso_singleton_empty,pyranim_collision_prob_one_game_iso_reflext ⟨X, Y⟩ simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq] constructor · rintro ⟨⟨rfl | rfl, rfl | rfl⟩, h_iso⟩ · left; exact ⟨rfl, rfl⟩ · exact False.elim (pyranim_collision_prob_one_not_game_iso_empty_singleton h_iso) · exact False.elim (pyranim_collision_prob_one_not_game_iso_singleton_empty h_iso) · right; exact ⟨rfl, rfl⟩ · rintro (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl ∅⟩ · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl {(1, 1)}⟩
The stable positions for a 1-tier pyramid are precisely ∅ and {(1, 1)}.
Unfolding pyranim_collision_prob and pyranim_stable_positions, stable positions are defined as the order ideals contained in pyranim_full_pyramid 1, which evaluates by computation (decide) to {(1, 1)}. By Finset.mem_filter and Finset.mem_powerset, any stable position is a subset of {(1, 1)}, hence must be ∅ or {(1, 1)} by Finset.subset_singleton_iff. Conversely, both are order ideals: ∅ satisfies the condition vacuously, and for {(1, 1)}, any point (a, b) below (1, 1) has coordinates in [1, 1] by Finset.mem_Icc, which linear integer arithmetic (omega) forces to a = 1 and b = 1, so (a, b) = (1, 1) ∈ {(1, 1)} by Finset.mem_singleton.
uses
Finset.mem_filter,Finset.mem_powerset,Finset.mem_insert,Finset.mem_singleton,Finset.subset_singleton_iff,Finset.mem_Iccdsimp [pyranim_collision_prob] have hT : pyranim_stable_positions 1 = {∅, {(1, 1)}} := by dsimp [pyranim_stable_positions] have h_pyr : pyranim_full_pyramid 1 = {(1, 1)} := by decide rw [h_pyr] ext X simp only [Finset.mem_filter, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨hsub, _⟩ rw [Finset.subset_singleton_iff] at hsub exact hsub · rintro (rfl | rfl) · refine ⟨by simp, ?_⟩ intro p hp simp at hp · refine ⟨by simp, ?_⟩ intro p hp a ha b hb simp only [Finset.mem_singleton] at hp subst hp simp only [Finset.mem_Icc] at ha hb have ha1 : a = 1 := by omega have hb1 : b = 1 := by omega subst ha1 hb1 simp
The game-isomorphism collision probability for 1-tier Pyranim is 1 / 2.
Rewriting with the determination of stable positions hT replaces the position set with {∅, {(1, 1)}}. Rewriting with pyranim_collision_prob_one_filter_iso_eq simplifies the set of isomorphic pairs in the numerator to {(∅, ∅), ({(1, 1)}, {(1, 1)})}. Both the numerator set and the denominator set have cardinality 2 (verified by decide), so the ratio reduces to 2 / 2² = 1 / 2, evaluated by norm_num.
uses
pyranim_collision_prob_one_filter_iso_eqrw [hT] rw [pyranim_collision_prob_one_filter_iso_eq] have h_card_num : ({(∅, ∅), ({(1, 1)}, {(1, 1)})} : Finset (Finset (ℕ × ℕ) × Finset (ℕ × ℕ))).card = 2 := by decide have h_card_den : ({∅, {(1, 1)}} : Finset (Finset (ℕ × ℕ))).card = 2 := by decide rw [h_card_num, h_card_den] norm_num
Equiv.refl- The identity equivalence from any type to itself.
False.elim- From a contradiction (False), any proposition follows.
Finset.mem_Icc- An element belongs to a closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or is already in s.
Finset.mem_powerset- A finite set belongs to the powerset of t if and only if it is a subset of t.
Finset.mem_product- An ordered pair belongs to the Cartesian product s ×ˢ t if and only if its first component is in s and its second component is in t.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_singleton_self- An element belongs to the singleton set containing only itself.
Finset.subset_singleton_iff- A finite set is a subset of a singleton {a} if and only if it is empty or {a}.
IsEmpty.false- An element of an empty type yields a contradiction.
Prod.mk.injEq- Two ordered pairs are equal if and only if their respective components are equal.
pyranim_collision_prob_one_filter_iso_eq- The set of pairs in {∅, {(1, 1)}} ×ˢ {∅, {(1, 1)}} that are game-isomorphic is {(∅, ∅), ({(1, 1)}, {(1, 1)})}.
pyranim_collision_prob_one_game_iso_refl- Every Pyranim game position is game-isomorphic to itself.
pyranim_collision_prob_one_not_game_iso_empty_singleton- The empty position and the singleton position {(1, 1)} are not game-isomorphic.
pyranim_collision_prob_one_not_game_iso_singleton_empty- The singleton position {(1, 1)} and the empty position are not game-isomorphic.
- Finite set option computations and set cardinalities are evaluated by the `decide` decision procedure, while coordinate bounds are checked using linear integer arithmetic (`omega`).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma pyranim_collision_prob_one_game_iso_refl (X : Finset (ℕ × ℕ)) : pyranim_game_iso X X := by use (fun A B => A = B) refine ⟨rfl, ?_⟩ intro A B h subst h refine ⟨Equiv.refl _, ?_⟩ intro o rfllemma pyranim_collision_prob_one_not_game_iso_empty_singleton : ¬ pyranim_game_iso ∅ {(1, 1)} := by intro ⟨R, hR, hstep⟩ rcases hstep ∅ {(1, 1)} hR with ⟨f, hf⟩ have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide] infer_instance have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide] exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩ exact IsEmpty.false (f.symm h2.some)lemma pyranim_collision_prob_one_not_game_iso_singleton_empty : ¬ pyranim_game_iso {(1, 1)} ∅ := by intro ⟨R, hR, hstep⟩ rcases hstep {(1, 1)} ∅ hR with ⟨f, hf⟩ have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide] infer_instance have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide] exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩ exact IsEmpty.false (f h2.some)lemma pyranim_collision_prob_one_filter_iso_eq : (@Finset.filter (Finset (ℕ × ℕ) × Finset (ℕ × ℕ)) (fun ⟨X, Y⟩ => pyranim_game_iso X Y) (fun _ => Classical.propDecidable _) ({∅, {(1, 1)}} ×ˢ {∅, {(1, 1)}})) = {(∅, ∅), ({(1, 1)}, {(1, 1)})} := by ext ⟨X, Y⟩ simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq] constructor · rintro ⟨⟨rfl | rfl, rfl | rfl⟩, h_iso⟩ · left; exact ⟨rfl, rfl⟩ · exact False.elim (pyranim_collision_prob_one_not_game_iso_empty_singleton h_iso) · exact False.elim (pyranim_collision_prob_one_not_game_iso_singleton_empty h_iso) · right; exact ⟨rfl, rfl⟩ · rintro (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl ∅⟩ · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl {(1, 1)}⟩/-- The game-isomorphism collision probability for 1-tier Pyranim is 1/2. -/theorem pyranim_collision_prob_one : pyranim_collision_prob 1 = 1 / 2 := by dsimp [pyranim_collision_prob] have hT : pyranim_stable_positions 1 = {∅, {(1, 1)}} := by dsimp [pyranim_stable_positions] have h_pyr : pyranim_full_pyramid 1 = {(1, 1)} := by decide rw [h_pyr] ext X simp only [Finset.mem_filter, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨hsub, _⟩ rw [Finset.subset_singleton_iff] at hsub exact hsub · rintro (rfl | rfl) · refine ⟨by simp, ?_⟩ intro p hp simp at hp · refine ⟨by simp, ?_⟩ intro p hp a ha b hb simp only [Finset.mem_singleton] at hp subst hp simp only [Finset.mem_Icc] at ha hb have ha1 : a = 1 := by omega have hb1 : b = 1 := by omega subst ha1 hb1 simp rw [hT] rw [pyranim_collision_prob_one_filter_iso_eq] have h_card_num : ({(∅, ∅), ({(1, 1)}, {(1, 1)})} : Finset (Finset (ℕ × ℕ) × Finset (ℕ × ℕ))).card = 2 := by decide have h_card_den : ({∅, {(1, 1)}} : Finset (Finset (ℕ × ℕ))).card = 2 := by decide rw [h_card_num, h_card_den] norm_num