Phan Đình Trung: toán rời rạc

Bài toán 1: Cho hình chữ nhật có kích thước $2$ x $n$ được chia thành các ô vuông đơn vị. Đánh số các ô từ trái sang phải là $1, 2,..., n$ (hàng $n$ ) và $n+1, n+2,..., 2n$ (hàng $2$ ). Lát chúng bằng các quân domino $1$ x $2$ sao cho chúng phủ kín hình chữ nhật và không có hai quân nào đè lên nhau. Ngoài ra, với $n$ lẻ, ta được bổ sung thêm một quân domino “đặc biệt” có thể phủ kín hai ô $n$ và $n+1$ . Hỏi có bao nhiêu cách lát như trên thỏa mãn bài toán.

Lời giải:

Gọi $S_{n}$ là số cách lát thỏa mãn bài toán với hình chữ nhật kích thước $2$ x $n$ .

Giả sử ta đã lát được hình chữ nhật $2$ x $(n+1)$ bằng các quân domino. Xét quân domino phủ lên ô vuông $n$ . Có ba trường hợp xảy ra:

Trường hợp 1: Các quân domino đó phủ lên hai ô $(n,n+1)$ . Khi đó, phần còn lại là một hình chữ nhật kích thước $2$ x $n$ . Số cách lát trong trường hợp này là $S_{n}$ .

Trường hợp 2: Quân domino đó phủ lên hai ô $(n,n+1)$ . Theo đó, cần phải có một quân domino phủ lên hai ô $(2n-1,2n$ ). Khi đó, phần còn lại là hình chữ nhật kích thước $2$ x $(n-1)$ , tức là số cách lát trong trường hợp này là $S_{n-1}$

Trường hợp 3: Quân domino đó phủ lên hai ô $(n,n+1)$ , (với $n$ lẻ). Khi đó, phần còn lại được lát bằng các quân domino nằm ngang (nếu có một quân domino nằm dọc thì nó chia hình chữ nhật thành hai phần, mỗi phần có một số lẻ ô chưa được lát), tức là chỉ có một cách lát cho trường hợp này.

Dễ thấy: $S_{2k}=S_{2k-1}+S_{2k-2}-1$ (do khi $n$ chẵn thì không có quân domino “đặc biệt” nên phải bớt đi một cách của $S_{2k-1}$

$S_{2k+1}=S_{2k}+S_{2k-1}$ .

Bằng qui nạp, ta dễ dàng chỉ ra được $S_{2k}=F_{2k}$ và $S_{2k+1}=F_{2k+1}+1$ , trong đó $F_{k}$ là dãy Fibonacci được xác định bởi:

Cuối cùng, ta thu được:

Đây là kết quả bài toán.

Bài toán 2: Tám đội bóng tham gia giải vô địch trong đó hai đội bất kỳ phải gặp nhau đúng một lần. Biết rằng đến cuối giải không có trận nào kết thúc với tỉ số hoà. Chứng minh rằng trong tám đội nói trên, luôn tìm được bốn đội $A,B,C,D$ sao cho kết quả giữa các trận đấu của họ là $A$ thắng $B,C,D$ ; $B$ thắng $C,D$ ; $C$ thắng $D$ .

Lời giải. Gọi $8$ đội bóng đó là $X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8$ . Theo đề bài thì chắc chắn $X_1$ sẽ đấu với $7$ đội còn lại.

Trường hợp 1. Nếu $X_1$ thắng ít nhất $3$ trong $7$ đội còn lại. Giả sử $X_1$ thắng $X_2,X_3,X_4$ .

Trong ba đội $X_2,X_3,X_4$ , theo nguyên lí Dirichlet thì sẽ tồn tại một đội hoặc thắng cả hai đội, hoặc thua cả hai đội. Không mất tính tổng quát, giả sử $X_2$ thắng $X_3,X_4$ . Khi đó

là bốn đội bóng thỏa mãn đề bài.

Trường hợp 2. Nếu $X_1$ thắng $2$ trong $7$ đội còn lại. Giả sử $\begin{cases} X_1 \; \text{thắng} \; X_2,X_3 \\ X_1 \; \text{thua} \; X_4,X_5,X_6,X_7,X_8 \end{cases}$ .

$\star$ Khả năng 1. Nếu $X_4,X_5,X_6,X_7,X_8$ lần lượt đấu với $X_2,X_3$ đều có ít nhất một lần thua $X_2,X_3$ .

Vì $5=2 \cdot 2+1$ nên khi đó theo nguyên lí Dirichlet thì tồn tại một trong hai đội $X_2,X_3$ thắng ít nhất $3$ trong $5$ đội $X_4,X_5,X_6,X_7,X_8$ . Khi đó ta quay về trường hợp 1, bài toán đúng.

$\star$ Khả năng 2. Nếu $X_4,X_5,X_6,X_7,X_8$ lần lượt đấu với $X_2,X_3$ thì đều thắng. Ta có

thắng $X_2,X_3,X_1$ . Điều này cũng quay về trường hợp 1, bài toán đúng.

Trường hợp 3. Nếu $X_1$ thắng $1$ trong $7$ đội còn lại. Giả sử $\begin{cases} X_1 \; \text{thang} \; X_2 \\ X_1 \; \text{thua} \; X_3,X_4,X_5,X_6,X_7,X_8 \end{cases}$ .

Xét các trận đấu giữa $X_2$ và $X_3,X_4,X_5,X_6,X_7,X_8$ thì nếu $X_2$ thắng ít nhất ba trong $6$ đội $X_3,X_4,X_5,X_6,X_7,X_8$ thì ta quay về trường hợp 1, hiển nhiên thỏa mãn.

Còn nếu $X_2$ thua ít nhất ba trong $6$ đội $X_3,X_4,X_5,X_6,X_7,X_8$ . Lấy $X_2$ thua $X_3,X_4,X_5$ . Trong ba đội $X_3,X_4,X_5$ thì theo nguyên lí Dirichlet sẽ tồn tại một đội trong ba đội trên thắng hai đội còn lại. Giả sử $X_3$ thắng $X_4,X_5$ và cả $X_1$ . Ta quay về trường hợp 1.

Do $X_2$ đấu với $6$ đội $X_3,X_4,X_5,X_6,X_7,X_8$ thì ắt hẳn sẽ tồn tại ít nhất ba trận thắng hoặc ít nhất ba trận thua. Vậy trường hợp này cũng luôn tìm được $4$ đội thỏa mãn bài toán.

Trường hợp 4. Nếu $X_1$ thua $7$ đội còn lại. Khi đó $X_1$ thua $X_2,X_3,X_4$ . Trong ba đội $X_2,X_3,X_4$ thì theo nguyên lí Dirichlet sẽ tồn tại một trong ba đội thắng hai đội còn lại. Giả sử $X_2$ thắng $X_3,X_4$ và thắng cả $X_1$ nên ta quay về trường hợp 1, bài toán đúng.

Ta có điều phải chứng minh.

Bài toán 3 : Giả sử rằng trong một nhóm $n$ người thỏa điều kiện cứ $n-2$ người bất kì thì có $3^k$ số cặp người quen nhau. Tìm $n$ .

Lời giải :

Theo đề bài cứ một nhóm gồm $n-2$ người thì có $3^k$ số cặp quen nhau, mà trong $n$ người, số nhóm $n-2$ người là $C_{n}^{n-2}$ . Do đó số cặp quen nhau trong $n$ người (tính cả các cặp trùng nhau trong các nhóm) là $C_{n}^{n-2}.3^k$ .

Xét hai người $A,B$ quen nhau. Trong $n-2$ người còn lại ta chọn ra $n-4$ người để tạo thành một nhóm $n-2$ người với $A,B$ . Số cách chọn như vậy là $C_{n-2}^{n-4}$ , tức là hai người quen nhau này có mặt trong $C_{n-2}^{n-4}$ nhóm.

Như vậy số cặp người quen nhau trong $n$ người là $m=\dfrac{3^k.C_{n}^{n-2}}{C_{n-2}^{n-4}}$

Ta có :

$m=\dfrac{3^k.C_{n}^{n-2}}{C_{n-2}^{n-4}}\in \mathbb{Z}^{+}\Rightarrow \dfrac{3^k.\dfrac{n!}{2!(n-2)!}}{\dfrac{(n-2)!}{2!(n-4)!}}=\dfrac{3^k.n(n-1)}{(n-2)(n-3)} \in \mathbb{Z}^{+}$

Xét $n\in \left \{ 1,2,3,4 \right \}$ thì nhận $n=4$

Nếu $n-3$ chẵn, đặt $n-3=2t,\;t\in \mathbb{N}^{*}$

Ta được $m=\dfrac{3^k.(2t+3)(2t+2)}{(2t+1).2t}=\dfrac{3^k(2t+3)(t+1)}{(2t+1).t}\in \mathbb{Z}^{+}$

Dễ dàng thấy rằng $gcd(2t+3,2t+1)=gcd(2t+1,t+1)=1$ nên $2t+1\mid 3^k\Rightarrow 2t+1=3^s\;\;,(s<k,s\in \mathbb{N}^*)$

Từ đó suy ra $t=\dfrac{3^s-1}{2}$ . Lúc này :

$m=\dfrac{3^k.(3^s+2).(\dfrac{3^s-1}{2}+1)}{3^s.\dfrac{3^s-1}{2}}=\dfrac{3^{k-s}.(3^s+2)(3^s+1)}{3^s-1}\in \mathbb{Z}^{+}$

Rõ ràng $gcd(3^{k-s},3^s-1)=gcd(3^s+2,3^s-1)=1$ nên $\dfrac{3^s+1}{3^s-1}\in \mathbb{Z}^{+}$ mà $gcd(3^s-1,3^s+1)=2\Rightarrow 3^s-1=2\Rightarrow s=1\Rightarrow n=5$

Nếu $n-3$ lẻ, đặt $n-3=2t+1,\;\;\left ( t\in \mathbb{N}^{*} \right )$

Ta được $m=\dfrac{3^k(2t+4)(2t+3)}{(2t+2)(2t+1)}=\dfrac{3^k(t+2)(2t+3)}{(t+1)(2t+1)}\in \mathbb{Z}^+$

Dễ dàng thấy rằng $gcd(t+1,t+2)=gcd(t+1,2t+3)=1$ nên phải có $t+1\mid 3^k\Rightarrow t=3^s-1,\;\left ( s=k,s\in \mathbb{N}^{*} \right )$

Lúc này :

$m=\dfrac{3^k.(3^s+1)(2.3^s+1)}{3^s(2.3^s-1)}=\dfrac{3^{k-s}.(3^s+1)(2.3^s+1)}{2.3^s-1}\in \mathbb{Z}^{+}$

Dễ thấy $gcd(2.3^s-1,3^s+1)=gcd(2.3^s+1,2.3^s-1)=gcd(3^{k-1},2.3^s-1)=1$ nên trường hợp này bị loại.

Kết luận:

hoặc

Bài toán 4 : Cho $2001$ số tùy ý. Chứng minh rằng ta có thể chọn được một hoặc một số số nào đó mà tổng của chúng chia hết cho $2001$ .

Lời giải :

Gỉa sử $2001$ số đã cho là $a_{1},a_2,...,a_{2001}$ .

Xét $2001$ tổng sau :

$S_1=a_1$

$S_2=a_1+a_2$

$S_3=a_1+a_2+a_3$

…

$S_{2001}=a_1+a_2+...+a_{2001}$ .

Nếu có ít nhất một trong các tổng trên chia hết cho $2001$ thì hiển nhiên ta có điều phải chứng minh.

Giả sử không có tổng nào trong các tổng trên chia hết cho $2001$ , khi đó số dư trong phép chia mỗi tổng cho $2001$ thuộc tập $A=\left \{ 1,2,3,...,2000 \right \}$ .