Cho n là số nguyên dương lớn hơn hay bằng 2. Kí hiệu A = {1, 2, …, n}. Tập con B của tập A được gọi là 1 tập "tốt" nếu B khác rỗng và trung bình cộng của các phần tử của B là 1 số nguyên. Gọi Tn là số các tập tốt của tập A. Chứng minh rằng Tn – n là 1 số chẵn.
Bài tổ hợp liên quan đến số tập tốt
#1
Đã gửi 24-05-2013 - 21:56
#2
Đã gửi 24-05-2013 - 22:59
Không biết ý nghĩa của n trong $T_n$ là như thế nào nhỉ, vì nó không liên quan đến tập B.
#3
Đã gửi 03-06-2019 - 10:18
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 BurakkuYokuro11: 03-06-2019 - 10:22
WangtaX
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh