Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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
  • Giới tính:Nam

Đã gửi 28-11-2005 - 15:11

$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
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 27-01-2015 - 17:31

$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