Zulip Chat Archive
Stream: general
Topic: Is this a correct formalization of IOI 2024 question 2?
Daniel Weber (Sep 19 2024 at 05:15):
I'm trying to formalize the mathematical part of the solution to question 2 from IOI 2024. I haven't started with the proof yet, but since the problem is quite complex, I'm unsure if I formalized the statement correctly. Does the following formalization look valid? The question is available on https://github.com/ioi-2024/tasks/blob/main/day1/message/statements/en.pdf
import Mathlib.Data.Vector.Defs
import Mathlib.Data.Fintype.Card
def Message := {l : List Bool // l.length ∈ Set.Icc 1 1024}
def Compromised := {s : Finset (Fin 31) // s.card = 15}
def Aisha := Message → Compromised → List (Mathlib.Vector Bool 31) →
Option (Mathlib.Vector Bool 31)
def Basma := List (Mathlib.Vector Bool 31) → Message
def Aisha.ValidPreRun (aisha : Aisha) (msg : Message) (comp : Compromised)
(run : List (Mathlib.Vector Bool 31)) : Prop :=
∀ i : Fin run.length, (aisha msg comp (run.take i)).any
(fun v ↦ ∀ j ∉ comp.val, run[i][j] = v[j])
def Aisha.ValidRun (aisha : Aisha) (msg : Message) (comp : Compromised)
(run : List (Mathlib.Vector Bool 31)) : Prop :=
aisha.ValidPreRun msg comp run ∧ aisha msg comp run = none
def Aisha.Small (aisha : Aisha) : Prop :=
∀ msg comp run, aisha.ValidPreRun msg comp run → run.length ≤ 66
def Aisha.Correct (aisha : Aisha) (basma : Basma) : Prop :=
∀ msg comp run, aisha.ValidRun msg comp run → basma run = msg
def Aisha.winningStrat : Aisha :=
sorry
def Basma.winningStrat : Basma :=
sorry
theorem IOI2024Q2 :
Aisha.winningStrat.Small ∧
Aisha.winningStrat.Correct Basma.winningStrat := by
sorry
Last updated: May 02 2025 at 03:31 UTC