Hai bài số học của Mỹ và Trung Quốc.

1/ (Mỹ) Chứng minh rằng với mỗi số nguyên $n \ge 2$ đều tồn tại một tập S gồm n số nguyên thoả mãn $(a-b)^2$ là ước của ab với mọi a,b thuộc S phân biệt.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab

Giải

1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.

Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:

$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}

Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.

Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$

Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)

Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):



(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);

(12, 4); (24, 8); (36, 12); (48, 16)

(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)

(30, 6)

(42, 7), (35, 14), (28, 21)

(40, 24)

(45, 36)


Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.


Vậy K nhỏ nhất là 39.

Dùng phép song ánh để chứng minh bài toán tổ hợp- Phần 2

Hôm nay ta tiếp tục dùng phép song ánh để giải bài toán đếm trong tổ hợp.

Ví dụ 2: Cho tập A={1,2,..,2n}. Một tập con B của A gọi là một tập cân nếu trong tập đó số các số chẵn và các số lẻ bằng nhau. ( Tập rỗng là một tập cân). Tính số tập cân của A.

Giải.
Gọi N là họ các tập con của A có đúng n phần tử, B là một tập cân. $B_1, B_2$ tương ứng các tập số chẵn và lẻ của B thì $B_1=B_2$.

Ta xây dựng một ánh xạ như sau;

$f: B \rightarrow  N$

Trong đó $f(B)=B_1 \cup (Y\setminus B_2)$

$\Rightarrow |f(B)|=|B_1|+|Y|-|B_2|$ vậy muốn cho $f(B)$ thuộc $N$ thì trước hết $Y$ phải có n phần tử và Y không có phần tử chung với $B_1$. Như vậy $Y$ phải tập tất cả số lẻ của tập $A$ ($|Y|=n)$

Nên f đơn ánh

Nếu có tập $M$ thuộc $N$. Kí hiệu $M_1$, $M_2$ là tập số chẵn số lẻ của M thì $|M_1|+|M_2|=n$. Ta phải tìm xây dựng $B_1,B_2$ theo $M_1, M_2$ sao cho $|B_1|=|B_2|$ thì $B_2=Y \setminus M_2$ và $B_1=M_1$. $\Rightarrow f(B)=M$.

Như vậy ta xây dựng song ánh giữa B và N.

Vậy A có tấp cả $C^n_{2n}$

Nhận xét: Tại sao lại xây dựng f đi từ B đến N ? Thực ra qua một vài phép liệt kê ta sẽ thấy !
Một số bài tập cho bạn đọc:

1/(Bài toán chia kẹo của Euler) Có m chiếc kẹo giống nhau chia cho n em bé. Hỏi có bao nhiêu cách chia?

Đây cũng chính là bài toán: “Tìm số nghiệm không âm của phương trình :  ($n, m \in N^*$). 

Các bạn có thể nghiên cứu chuyên đề tại đây.

2( Lấy trong TLCT)/ Cho trước số nguyên dương n và số nguyên dương r thoả $r<n-r+1$. Giả sử X={1,2..n}. Hoi r có bao nhiêu tập con A của X đồng thời có tính chất:

+ Chứa r phần tử

+ Không chứa hai số nguyên liên tiếp.

(Gợi ý: Các bạn thử liệt kê như Vd 2 các bạn sẽ có hướng làm).