[Toán 10 +11 chuyên tổ hợp] C/m tồn tại

[lebalinhpa1]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

1/ Cho 49 học sinh cùng giải 3 bài toán và điểm của mỗi bài toán được cho là một số nguyên không âm 0,1,3,4,5,6,7.C/m rằng tồn tại 2 học sinh A và B thỏa mãn mỗi bài toán thì điểm học sinh A được nhận không nhỏ hơn số điểm điểm học sinh B được nhận

2/ Trên bàn cờ vua kích thức 8 x 8 được chia thành 64 ô vuông đơn vị , người ta bỏ đi một ô vuông đơn vị nào đó ở vị trí hàng thứ m và cột thứ n. Gọi S(m,n) là số hình chữ nhật được tạo bởi một hay nhiều ô vuông đơn vị của bàn cờ sao cho không có ô nào trùng với vị trí của ô bị xóa ban đầu.Tìm giá trị nhỏ nhất và giá trị lớn nhất của S(m,n)

3/ Cho n là số nguyên dương.Cho một cái cân đĩa và n quả cân có trọng lượng $2^0$,$2^1$,...,$2^n-1$. Ta muốn đặt lên cái cân, lần lượt từng quả một,theo cách đảm bảo đĩa cân bên phải không bao giờ nặng hơn đĩa cân bên tría. Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên đĩa cân bên phải hoặc trái,cho đến khi tất cả các quả cân được đặt lên đĩa. Hỏi có bao nhiêu cách thực hiện việc đặt cân theo đúng mục tiêu đề ra ?

4/ 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à một 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à một số nguyên.Gọi [TEX]Tn[/TEX] là các tập tốt của A. C/m rằng [TEX]Tn[/TEX] - n là một số chẵn

 

[huynhbachkhoa23]

Bài 2.
Hình chữ nhật $ABCD$ thuộc hình vuông ban đầu với $A$ cao tận cùng bên trái, $B$ cao tận cùng bên phải, $C$ thấp tận cùng bên phải và $D$ thấp tận cùng bên trái.
Giả sử chọn đỉnh $A$ thuộc cột $x$ và hàng $y$. Khi đó $B$ có $9-x$ cách chọn. $C$ có $9-y$ cách chọn và $D$ có một cách chọn.
Vậy là có tổng cộng $1296$ hình chữ nhật con trong hình vuông ban đầu.
Xét một hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Khi đó giả sử $A'$ có $mn$ cách chọn. $B'$ chỉ có $9-m$ cách chọn. $C'$ chỉ có $9-n$ cách chọn và $D$ có một cách chọn.
Do đó ta có $mn(9-m)(9-n)$ cách chọn cho hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Vậy $S(m,n)=1296-mn(9-m)(9-n)$. Đến đây dễ rồi.

 

[huynhbachkhoa23]

Bài 3. Ý tưởng truy hồi như sau:
Giả sử $x_n$ là số cách thực hiện với $n$ quả cân.
Xét với $n$ quả cân $2^0, 2^1,...,2^{n-1}$ thì hiển nhiên quả cân $2^{n-1}$ phải đặt ở bên trái.
Giả sử quả cân $2^{n-1}$ được đặt ở bước thứ $i$, thì có tổng cộng $x_{i-1}\binom{n-1}{i-1}$ cách đặt cho các quả cân trước đó. Các quả cân còn lại đặt sao cũng được thì có tổng cộng $2^{n-i}(n-i)!$ cách đặt.
Từ đó tính được hệ thức truy hồi $x_{n}=(2n-1)x_{n-1}$

 

[huynhbachkhoa23]

Bài 4. $T_{n}$ phải là số các tập tốt của $A$
Ta có $n$ tập tốt $1$ phần tử nên ta chỉ cần chứng minh các tập tốt có nhiều hơn một phân từ là số chẵn.
Xét một tập $X$ tốt có một phần tử là trung bình cộng của nó, xóa phần tử đó đi ta được tập $Y$ có trung bình cộng nguyên và không chứa trung bình cộng của nó.
Vậy ta có điều phải chứng minh.

 

[hoangnhantk17lqd]

Bnạ có thể chỉ mình kĩ hơn được không, tại mình mới học loại này nên không hỉu mấy cái này cho lắm

 

[huynhbachkhoa23]

Bnạ có thể chỉ mình kĩ hơn được không, tại mình mới học loại này nên không hỉu mấy cái này cho lắm

Bài 3 dùng phương pháp đếm truy hồi, bạn có thể tham khảo thêm ở các tài liệu tổ hợp, truy hồi này học qua rồi thì thấy đơn giản lắm.
Bài 4 thì ta dùng phương pháp đếm bằng song ánh.
Các tập tốt có hai loại:
Loại 1 là loại có $1$ phần tử, loại này gồm $n$ tập.
Loại 2 là loại có trên $1$ phần tử, ta chia loại này thành hai loại con
Loại 2.1 là tập con trên $1$ phần tử chứa trung bình cộng của nó, ví dụ $\{1,5,9\}$ có trung bình cộng là $5$, bản thân tập này chứa số $5$.
Loại 2.2 là tập con trên $1$ phần tử không chứa trung bình cộng của nó.
Ta xét tập loại $2.1$ là $\{x_1,x_2,...,x_k\}$, giả sử $x_1$ là trung bình cộng của nó thì ta có $\dfrac{x_1+x_2+...+x_k}{k}=x_1$ nên $\dfrac{x_2+...+x_k}{k-1}=x_1$, vậy ta đã thiết lập tập loại $2.2$ từ tập $2.1$
Ta xét tập loại $2.2$ là $\{x_1,x_2,...,x_k\}$ có trung bình cộng là $x$, khi đó ta thêm vào nó phần tử $x$ thì ta được tập loại $2.1$
Vậy ta đã thiết lập một song ánh từ tập hợp tập con loại $2.1$ vào tập hợp tập con loại $2.2$
Do đó số tập con loại $2.1$ bằng số tập con loại $2.2$ nên số tập con loại $2$ là số chẵn.
$T_n-n$ là số tập con loại $2$ nên là số chẵn.
Bài 2 thì là bài đếm cơ bản, không dùng phương pháp đếm nâng cao nào khác.

 

[hoangnhantk17lqd]

Cảm ơn bạn nhiều, mình đã hiểu rồi thanks nhá à mà tại sao song ánh lak số phần tử của 2 tập bằng nhau
vậy mình không hỉu

 

[huynhbachkhoa23]

Cảm ơn bạn nhiều, mình đã hiểu rồi thanks nhá à mà tại sao song ánh lak số phần tử của 2 tập bằng nhau
vậy mình không hỉu

Theo định nghĩa nếu $f: \mathbb{A}\to \mathbb{B}$ là song ánh thì ứng với mỗi $b\in\mathbb{B}$ tồn tại duy nhất một $a\in\mathbb{A}$ sao cho $f(a)=b$
Do đó $|\mathbb{A}|=|\mathbb{B}|$

 

[hoangnhantk17lqd]

ò mình hỉu r thanks bạn nhiều nhan còn mấy bài trên bạn giải chi tiết zùm cái , tại hùi giờ mình chưa học mấy cái này

 

[hoangnhantk17lqd]

Bài 3. Ý tưởng truy hồi như sau:
Giả sử $x_n$ là số cách thực hiện với $n$ quả cân.
Xét với $n$ quả cân $2^0, 2^1,...,2^{n-1}$ thì hiển nhiên quả cân $2^{n-1}$ phải đặt ở bên trái.
Giả sử quả cân $2^{n-1}$ được đặt ở bước thứ $i$, thì có tổng cộng $x_{i-1}\binom{n-1}{i-1}$ cách đặt cho các quả cân trước đó. Các quả cân còn lại đặt sao cũng được thì có tổng cộng $2^{n-i}(n-i)!$ cách đặt.
Từ đó tính được hệ thức truy hồi $x_{n}=(2n-1)x_{n-1}$

tại sao lại có được cái chỗ $x_{i-1}\binom{n-1}{i-1}$ cách đặt v và cái chỗ công thức $x_{i-1}\binom{n-1}{i-1}$ lak sao,mình ko biết cái công thức này

 

[hoangnhantk17lqd]

Bài 2.
Hình chữ nhật $ABCD$ thuộc hình vuông ban đầu với $A$ cao tận cùng bên trái, $B$ cao tận cùng bên phải, $C$ thấp tận cùng bên phải và $D$ thấp tận cùng bên trái.
Giả sử chọn đỉnh $A$ thuộc cột $x$ và hàng $y$. Khi đó $B$ có $9-x$ cách chọn. $C$ có $9-y$ cách chọn và $D$ có một cách chọn.
Vậy là có tổng cộng $1296$ hình chữ nhật con trong hình vuông ban đầu.
Xét một hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Khi đó giả sử $A'$ có $mn$ cách chọn. $B'$ chỉ có $9-m$ cách chọn. $C'$ chỉ có $9-n$ cách chọn và $D$ có một cách chọn.
Do đó ta có $mn(9-m)(9-n)$ cách chọn cho hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Vậy $S(m,n)=1296-mn(9-m)(9-n)$. Đến đây dễ rồi.

cái chỗ kia làm sao biết được là có 1296 hình chữ nhật con

 

[hoangnhantk17lqd]

Bài 2.
Hình chữ nhật $ABCD$ thuộc hình vuông ban đầu với $A$ cao tận cùng bên trái, $B$ cao tận cùng bên phải, $C$ thấp tận cùng bên phải và $D$ thấp tận cùng bên trái.
Giả sử chọn đỉnh $A$ thuộc cột $x$ và hàng $y$. Khi đó $B$ có $9-x$ cách chọn. $C$ có $9-y$ cách chọn và $D$ có một cách chọn.
Vậy là có tổng cộng $1296$ hình chữ nhật con trong hình vuông ban đầu.
Xét một hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Khi đó giả sử $A'$ có $mn$ cách chọn. $B'$ chỉ có $9-m$ cách chọn. $C'$ chỉ có $9-n$ cách chọn và $D$ có một cách chọn.
Do đó ta có $mn(9-m)(9-n)$ cách chọn cho hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Vậy $S(m,n)=1296-mn(9-m)(9-n)$. Đến đây dễ rồi.

Mà hình vuông có độ dài 1 cạnh lak 8 mk đào đâu ra số 9 v, bài này mình gần hiểu r

 

[hoangnhantk17lqd]

Bài 2.
Hình chữ nhật $ABCD$ thuộc hình vuông ban đầu với $A$ cao tận cùng bên trái, $B$ cao tận cùng bên phải, $C$ thấp tận cùng bên phải và $D$ thấp tận cùng bên trái.
Giả sử chọn đỉnh $A$ thuộc cột $x$ và hàng $y$. Khi đó $B$ có $9-x$ cách chọn. $C$ có $9-y$ cách chọn và $D$ có một cách chọn.
Vậy là có tổng cộng $1296$ hình chữ nhật con trong hình vuông ban đầu.
Xét một hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Khi đó giả sử $A'$ có $mn$ cách chọn. $B'$ chỉ có $9-m$ cách chọn. $C'$ chỉ có $9-n$ cách chọn và $D$ có một cách chọn.
Do đó ta có $mn(9-m)(9-n)$ cách chọn cho hình chữ nhật $A'B'C'D'$ chứa ô bị xóa.
Vậy $S(m,n)=1296-mn(9-m)(9-n)$. Đến đây dễ rồi.

rolling on the floor rolling on the floor rolling on the floor rolling on the floor rolling on the floor

 

[hoangnhantk17lqd]

Từ các số thuộc tập E={1;2;3;...;9} có thể lập được bao nhiêu số tự nhiên có n chữ số mà trong mỗi số đó đều chứa một số lẻ số số 1 và một số chẵn số số 2 (n là số nguyên dương cho trước )