[CEOI 2014] Optimality proof of problem "Question"

BOJ에서 투 스텝 문제를 필터로 걸고 찾다가, 대충 지문이 짧아보이는 이 문제를 잡았다. 잠이 안 와서 optimality를 생각해보다가 증명을 찾아서 올린다.

Problem

\(n \in \mathbb{N}\)에 대해, \(h: [n] \times [n] \rightarrow [H]\)와 \(f: [n] \times [H] \rightarrow \{0, 1\}\)를 생각하자. 임의의 \(x, y \in [n]\)에 대해, \(f(x, h(x, y)) = 1\), \(f(y, h(x, y)) = 0\)을 만족하게 하는 \(h, f\)가 존재하는 최소의 \(H\)는 얼마인가?

Answer

\(n \leq \binom{2k}{k}\)인 최소의 \(k\)가 답이다.

Proof

Let \(S_x = \{ i \in [H] \mid f(x, i) = 1 \}\). 임의의 \(x \neq y\)에 대해, \(h(x, y) \in S_x\)이지만 \(h(x, y) \not\in S_y\)이다. 비슷하게 \(h(y, x) \not\in S_x\)이지만 \(h(y, x) \in S_y\)이다. 따라서 \(S_x \not\subseteq S_y\)이고 \(S_y \not\subseteq S_x\)이므로, Sperner's theorem에 의해 \(n \leq \binom{2H}{H}\). Construction은 Sperner's theorem의 등호 조건을 따라가면 바로 얻어지니 생략.

Commentary

• 처음에 증명 생각할 때는 훨씬 길고 복잡했는데, 쓰다 보니까 왜 이리 간단해졌나 의문.
• Self-completeness를 위해 sperner's theorem의 증명까지 첨부할까 했으나, 아름답긴 하나 웰노운이라 별 의미가 없을 것 같아 생략.
• 투 스텝 문제는 MSG랑 비슷한 것 같다. 맛있고 자극적이지만 이것만 먹고 살아도 되는가에 대한 찜찜함을 남긴다.
• 투 스텝을 수학적으로 증명해보는 작업은 꽤 educational하다. 문제의 핵심을 정확히 모델링하고 원하는 성질을 끄집어내야 한다는 점에서 그렇다.
• 이 문제는 문제 특성 상 출제를 잘못한 것 같다. 만점 기준으로 \(12\)가 박혀 있는데 \(n \leq 920\)이라, \(\binom{12}{6} = 924\)가 좀 잘 보인다고 생각.