Chủ đề này có 1 trả lời

[Namthemaster1234]

Cho $n$ là số nguyên dương. Tập con $S$ của tập $X=\left \{ 1,2,..,n \right \}$ được gọi là "tốt" nếu trung bình cộng của các phần tử thuộc $S$ là một só nguyên. Gọi $T_n$ là số tập con "tốt của $X$. Chứng minh $T_n-n$ chẵn. 

[viet nam in my heart]

Cho $n$ là số nguyên dương. Tập con $S$ của tập $X=\left \{ 1,2,..,n \right \}$ được gọi là "tốt" nếu trung bình cộng của các phần tử thuộc $S$ là một só nguyên. Gọi $T_n$ là số tập con "tốt của $X$. Chứng minh $T_n-n$ chẵn. 

Bài toán quen thuộc sử dụng phương pháp song ánh

Ta bỏ đi $n$ tập con có $1$ phần tử của $T_n$

$T_n-n$ tập "tốt" còn lại chia vào $2$ loại: Tập đó chứa trung bình cộng các phần tử của nó hoặc Tập đó không chứa trung bình cộng các phần tử của nó

Giờ xét tập con của $S=\{a_1,a_2,...,a_k\}$ trong đó trung bình cộng của các phần tử của nó là $a_k$. Khi đó $S \setminus \{a_k\}$ cũng là một tập "tốt" và nó không chứa trung bình cộng các phần tử của nó. Dễ thấy phép biến đổi này là một đơn ánh

Tương tự nếu $S=\{a_1,...,a_k\}$ có trung bình cộng các phần tử của $S$ là $b$ và $b \neq a_i$. Dễ thấy $k<n$ vì $\dfrac{1+2+...+n}{n}$ nếu là số nguyên thì nó cũng nằm trong $X$. Do đó nếu xét $S'$ là hợp của $S$ với $b$ thì $S'$ là một tập con của $X$ và dễ thấy đây cũng là một đơn ánh

Vậy tồn tại một song ánh đi từ $2$ loại tập tốt này vào nhau. Do đó số lượng tập tốt ở mỗi loại này bằng nhau

Do đó $T_n -n  \vdots 2$

Bài viết đã được chỉnh sửa nội dung bởi viet nam in my heart: 18-09-2016 - 23:39