Đến nội dung

Hình ảnh

Chứng minh có tồn tại $f(\{a,b\})=f(\{b,c\})=f(\{c,a\})=0$.

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
QUANVU

QUANVU

    B&S-D

  • Hiệp sỹ
  • 4378 Bài viết

$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$.


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 06-04-2013 - 16:20

1728

#2
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

$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






1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh