$n$ là nguyên dương và $|S|=2^n+1$.Cho $f$ là hàm từ tập các tập con hai phần tử của $S$ tới $\{0,1,...,2^{n-1}-1\}$ sao cho với mỗi $f(\{x,y\}),f(\{y,z\}),f(\{z,x\})$ sẽ bằng tổng hai số còn lại.Chứng minh có tồn tại $f(\{a,b\})=f(\{b,c\})=f(\{c,a\})=0$.
Ta chứng minh bằng quy nạp.
Với $n=1$ thì bài toán hiển nhiên đúng.
GIả sử bài toán đúng với $n=k$, $k \geq 1$
Xét $n=k+1$:
Xét $a \in S$, ta quy ước $f\left ( \left \{ a,a \right \} \right )=0$
Ta phân hoạch $S$ thành $2$ tập $U,V$ như sau:
Với $x \in S$, $x \in U$ kvck $f\left ( \left \{ x,a \right \} \right )$ chẵn
Với $x \in S$, $x \in V$ kvck $f\left ( \left \{ x,a \right \} \right )$ lẻ
Theo nguyên tắc Dirichlet, tồn tại một trong $2$ tập $U,V$ có số phần tử không nhỏ hơn $2^k+1$
Giả sử $\left | U \right | \geq 2^k+1$
Với mọi x,y thuộc $U$, ta có $f\left ( \left \{ x,a \right \} \right )+f\left ( \left \{ y,a \right \} \right )+f\left ( \left \{ x,y \right \} \right ) \vdots 2$
$f\left ( \left \{ x,a \right \} \right )+f\left ( \left \{ y,a \right \} \right ) \vdots 2$
Suy ra $f\left ( \left \{ x,y \right \} \right ) \vdots 2, \forall x,y \in U$
Đặt $g\left ( \left \{ x,y \right \} \right )=\frac{f\left ( \left \{ x,y \right \} \right )}{2}$ $\Rightarrow g\left ( \left \{ x,y \right \} \right ) \in \left \{ 0,...,2^{k-1}-1 \right \}$
Theo giả thiết quy nạp, tồn tại $x,y,z \in U$ sao cho $g\left ( \left \{ x,y \right \} \right )=g\left ( \left \{ x,z \right \} \right )=g\left ( \left \{ y,z \right \} \right )=0$
Suy ra $f\left ( \left \{ x,y \right \} \right )=f\left ( \left \{ x,z \right \} \right )=f\left ( \left \{ y,z \right \} \right )=0$
Theo nguyên lí quy nạp, ta có đpcm