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

[AnnieSally]

Bài 23:(Thái Lan 2007) 229 học sinh nam và 271 học sinh nữ được chia thành 10 nhóm, mỗi nhóm 50 học sinh được đánh số từ 1 đến 50. Người ta muốn chọn ra một nhóm 4 học sinh, trong đó số học sinh nữ được chọn là lẻ và thoả mãn điều kiện sau đây: 4 người này được chọn từ 2 nhóm và có 2 cặp học sinh có cùng số thứ tự. Chứng minh rằng số cách chọn các nhóm như vậy là một số lẻ.

Lời giải bài này có ở đây (Bài toán 9)

[AnnieSally]

Ủng hộ topic thêm bài nữa

Bài 26: (Iran 2007) Cho I₁, I₂, …, I_n là n đoạn thẳng đóng trên R sao cho từ bất kỳ k đoạn thẳng trong số chúng, luôn tìm được 2 đoạn có điểm chung. Chứng minh rằng có thể tìm được k – 1 điểm trên R sao cho mỗi đoạn thẳng đã cho chứa ít nhất một điểm trong các điểm được chọn.

[LNH]

Bài 25: (UK 2007) Ở nước Hexagonia, 6 thành phố được kết nối bởi hệ thống đường sắt sao cho giữa hai thành phố bất kỳ có đường sắt nối trực tiếp. Vào ngày chủ nhật, một số đoạn đường đóng cửa để sửa chữa. Luật đường sắt quy định là mọi thành phố phải có thể đến được từ một thành phố khác (không nhất thiết trực tiếp) trong mọi thời điểm. Có bao nhiêu cách đóng một vài đoạn đường để yêu cầu này được thoả mãn?

Ý tưởng bài này là chuyển về dạng lí thuyết đồ thị

Gọi 6 thành phố là 6 đỉnh của đồ thị và đường sắt nối 2 thành phố là cạnh nối 2 đỉnh. Thay vì đếm số cách đóng đường sắt ta có thể đếm số đồ thị liên thông được tạo bởi 6 đỉnh đó.

Theo trang http://en.wikipedia....aph_enumeration thì ta có số đồ thị là:

$C_{6}=2^{\binom{6}{2}}-\frac{1}{2}\sum_{k=1}^{5}k\binom{6}{k}2^{\binom{6-k}{2}}C_{k}$

Đây là đáp án bài toán cần tìm (kinh khủng  )

[quocbaolqd11]

bài 26:

Nhận xét 1: $k>[\frac{n}{2}]+1$ với $n$ lẻ và $k>\frac{n}{2}$ với $n$ chẵn. 

chứng minh: giả sử $k \le [\frac{n}{2}]+1$. Ta sẽ chỉ ra 1 TH $k \le [\frac{n}{2}]+1$ thì tồn tại 1 bộ $k$ đoạn không có bất kì 2 đoạn nào giao nhau. Xét TH $k=[\frac{n}{2}]+1$ ($n$ lẻ, với $n$ chẵn thì lấy $k=\frac{n}{2}$) có $k$ đoạn thẳng sao cho giao của chúng khác rỗng (tồn tại 1 điểm nằm trên $k$ đường thẳng đó) và $k-1$ còn lại không giao nhau đôi một và không giao với bất kì 1 đường nào của bộ k đoạn kia thì ta chọn 1 đường trong bộ $k$ đường kia và kết hợp với $k-1$ đường không giao nhau, ta sẽ được 1 bộ k đoạn mà không có đoạn nào có điểm chung.(vô lí)

Nhận xét 2: tồn tại 1 bộ k đoạn thẳng mà giao của $k$ đoạn thẳng đó khác rỗng

giả sử không tồn tại bộ nào thỏa điều này. Xét $k = [\frac{n}{2}]+2$, khi đó sẽ có 1 TH có bộ $k=[\frac{n}{2}]+1$ và chứng minh giống nx 1.
Từ 2 nhận xét trên, dễ thấy nếu trên mỗi đoạn thẳng chỉ có 1 điểm thì có nhiều nhất $k-1$ điểm thỏa ycđb khi  $k=[\frac{n}{2}]+2$ với $n$ lẻ và $k=\frac{n}{2}+1$ với $n$ chẵn. Nếu với các số $k$ lớn hơn thì ta sẽ thêm vào các điểm nằm trên các đoạn đó để có đủ $k-1$ điểm.

Bài viết đã được chỉnh sửa nội dung bởi quocbaolqd11: 08-08-2013 - 17:08

[LNH]

Bài 27:Tô màu các đỉnh của đa giác đều 12 cạnh bằng hai màu khác nhau. Hãy tìm tất cả các cách tô màu sao cho không có đa giác đều nào có các đỉnh cùng màu.

[thuan192]

Bài 28:Cho bảng hình vuông gồm 13x13 ô vuông.người tatoo màu đỏ ở S ô vuông của bảng sao cho không có 4 ô đỏ nào nằm ở bốn góc của một hình chữ nhật.Hỏi giá trị lớn nhất của S có thể là bao nhiêu ?

Bài viết đã được chỉnh sửa nội dung bởi thuan192: 03-09-2013 - 12:08

[thuan192]

Bài 28:Cho bảng hình vuông gồm 13x13 ô vuông.người tatoo màu đỏ ở S ô vuông của bảng sao cho không có 4 ô đỏ nào nằm ở bốn góc của một hình chữ nhật.Hỏi giá trị lớn nhất của S có thể là bao nhiêu ?

Gọi $x_{i}$ là số ô đỏ ở dòng thứ i. Ta có S=$\sum_{i=1}^{13}x_{i}$ .Ở hàng thứ i số các cặp ô đỏ là$C_{x_{i}}^{2}=\frac{x_{i}\left ( x_{i}-1 \right )}{2}$

       Vậy tổng số các cặp ô đỏ là $A=\sum_{i=3}^{13}\frac{x_{i}\left ( x_{i}-1 \right )}{2}$

        

         Chiếu các cặp ô đỏ xuống một hàng ngang nào đó . Do giả thiết thì không có cặp ô đỏ nào có hình chiếu trùng nhau.Vậy

                          $C_{13}^{2}=78\geq A=\sum_{i=3}^{13}\frac{x_{i}\left ( x_{i}-1 \right )}{2}$

                      <=>$\sum_{i=1}^{13}x_{i}^{2}-\sum_{i=1}^{13}x_{i}\leq 156$

           Theo BĐT Bunhiacopxki:

 

                            $\left ( \sum_{i=1}^{13} x_{i}\right )^{2}\leq 13\left ( \sum_{i=1}^{13}x_{i}^{2} \right )$     ta suy ra 

                                        

                              $\frac{S^{2}}{13}-S\leq \sum_{i=1}^{13}x_{i}^{2}-\sum_{i=1}^{13}x_{i}\leq 156$

                   

                                 <=>$S^{2}-13S-2028\leq 0$

 

                                 => $S\leq 52$

 

                                 Đẳng thức xảy ra khi $x_{1}=x_{2}=...=x_{13}=4$

 

                                    Mỗi dòng có 4 ô tô đỏ .Ta có thể đễ dàng thực hiện được cách tô màu như vậy.Vậy $S_{Max}=52$

[thuan192]

Bài 29:Trong một phòng thi gồn có 9 thí sinh được xếp ngồi xung quanh một bàn tròn.TRong ngân hàng đề có 9 loại đề khác nhau mỗi loại có nhiều bản.Một cách phát đề được coi là hợp lệ nếu mỗi thí sinh được nhận chỉ một đề và hai thí sinh ngồi cạnh nhau thì nhận được hai loại đề khác nhau.Hỏi có tất cả bao nhiêu cách phát đề hợp lý?

[AnnieSally]

Bài 29:Trong một phòng thi gồn có 9 thí sinh được xếp ngồi xung quanh một bàn tròn.TRong ngân hàng đề có 9 loại đề khác nhau mỗi loại có nhiều bản.Một cách phát đề được coi là hợp lệ nếu mỗi thí sinh được nhận chỉ một đề và hai thí sinh ngồi cạnh nhau thì nhận được hai loại đề khác nhau.Hỏi có tất cả bao nhiêu cách phát đề hợp lý?

Bài này dễ xơi nhỉ

Gọi 9 thí sinh ngồi trên bàn tròn theo thứ tự là $a_1,a_2,...,a_9$

Có 9 cách chọn đề cho $a_1$

Có 8 cách chọn đề cho $a_2$

Có 8 cách chọn đề cho $a_3$

...

Có 8 cách chọn đề cho $a_8$

Có 7 cách chọn đề cho $a_9$

Số cách phát đề hợp lệ là: $9.8^7.7=132120576$

Bài viết đã được chỉnh sửa nội dung bởi AnnieSally: 07-09-2013 - 09:43

[AnnieSally]

Bài 30: Chứng minh rằng với $n\geq k\geq r\geq s$, ta có:

$C_{n}^{k}C_{k}^{r}C_{r}^{s}=C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$

Bài 31: $m,n$ là 2 số nguyên dương, $m \geq n$. CMR:

$\sum_{k=0}^{n}\left ( -1 \right )^kC_{n}^{m-k}C_{n}^{k}=1$

Bài viết đã được chỉnh sửa nội dung bởi AnnieSally: 07-09-2013 - 10:06

[quocbaolqd11]

Bài 29:Trong một phòng thi gồn có 9 thí sinh được xếp ngồi xung quanh một bàn tròn.TRong ngân hàng đề có 9 loại đề khác nhau mỗi loại có nhiều bản.Một cách phát đề được coi là hợp lệ nếu mỗi thí sinh được nhận chỉ một đề và hai thí sinh ngồi cạnh nhau thì nhận được hai loại đề khác nhau.Hỏi có tất cả bao nhiêu cách phát đề hợp lý?

ta có thể làm khó bài toán hơn bằng cách thay giả thiết "9 loại đề" thành "9 đề thi".

[thuan192]

Bài này dễ xơi nhỉ

Gọi 9 thí sinh ngồi trên bàn tròn theo thứ tự là $a_1,a_2,...,a_9$

Có 9 cách chọn đề cho $a_1$

Có 8 cách chọn đề cho $a_2$

Có 8 cách chọn đề cho $a_3$

...

Có 8 cách chọn đề cho $a_8$

Có 7 cách chọn đề cho $a_9$

Số cách phát đề hợp lệ là: $9.8^7.7=132120576$

Hình như đáp án này không đúng rồi

[quocbaolqd11]

Bài 30: Chứng minh rằng với $n\geq k\geq r\geq s$, ta có:

$C_{n}^{k}C_{k}^{r}C_{r}^{s}=C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$

Bài 31: $m,n$ là 2 số nguyên dương, $m \geq n$. CMR:

$\sum_{k=0}^{n}\left ( -1 \right )^kC_{n}^{m-k}C_{n}^{k}$

P/s: làm chút đẳng thức tổ hợp cho nó máu

bài 31 yêu cầu chứng minh cái gì ?

[LNH]

Bài 30: Chứng minh rằng với $n\geq k\geq r\geq s$, ta có:

$C_{n}^{k}C_{k}^{r}C_{r}^{s}=C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$

Bài 31: $m,n$ là 2 số nguyên dương, $m \geq n$. CMR:

$\sum_{k=0}^{n}\left ( -1 \right )^kC_{n}^{m-k}C_{n}^{k}$

P/s: làm chút đẳng thức tổ hợp cho nó máu

 

 

bài 31 yêu cầu chứng minh cái gì ?

Bài 31 yêu cầu CM:

$\sum_{k=0}^{n}\left ( -1 \right )^kC_{n}^{m-k}C_{n}^{k}=1$

[HeilHitler]

Bài 30: Chứng minh rằng với $n\geq k\geq r\geq s$, ta có:

$C_{n}^{k}C_{k}^{r}C_{r}^{s}=C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$

Bài 31: $m,n$ là 2 số nguyên dương, $m \geq n$. CMR:

$\sum_{k=0}^{n}\left ( -1 \right )^kC_{n}^{m-k}C_{n}^{k}=1$

Câu 30: Biến đổi trực tiếp hoặc dùng tính chất $C_{n}^{x}.C_{n-x}^{y}=C_{x+y}^{x}.C_{n}^{x+y}$.

Câu 31: Câu này hình như sai đề, mình tính ra biểu thức này phải bằng 0 nếu $m$ lẻ, còn bằng $(-1)^tC_{n}^{t}$ nếu $m=2t$.

Bài viết đã được chỉnh sửa nội dung bởi HeilHitler: 14-09-2013 - 12:29

[LNH]

Câu 30: Biến đổi trực tiếp hoặc dùng tính chất $C_{n}^{x}.C_{n-x}^{y}=C_{x+y}^{x}.C_{n}^{x+y}$.

Câu 31: Câu này hình như sai đề, mình tính ra biểu thức này phải bằng 0 nếu $m$ lẻ, còn bằng $(-1)^tC_{n}^{t}$ nếu $m=2t$.

Mình nghĩ 2 bài này chủ yếu là dùng đếm bằng 2 cách

[HeilHitler]

Mình nghĩ 2 bài này chủ yếu là dùng đếm bằng 2 cách

Nếu pé thích thì có thể dùng khai triển và đồng nhất hệ số:
Để ý rằng $[\sum_{i=0}^{n}x^i.C_{n}^{i}].[\sum_{j=0}^{n}(-x)^j.C_{n}^{j}]=(1+x)^n.(1-x)^n=(1-x^2)^n$.

Đồng nhất hệ số của $x^m$ ở hai vế:

$\sum_{k=0}^{m}C_{n}^{m-k}.C_{n}^{k}(-1)^k=$ hệ số của $x^m$ ở vế phải.

+Nếu $m$ lẻ thì hiển nhiên hệ số này ở vế phải bằng 0.

+Nếu $m$ chẵn thì đặt $m=2t$, hệ số này ở vế phải bằng $(-1)^tC_{n}^{t}$.

PS: Pé thử cố gắng nghĩ thêm cách đếm bằng 2 cách đi cho trọn vẹn. Như vậy sẽ đẹp hơn.

[LNH]

Bài 30: Chứng minh rằng với $n\geq k\geq r\geq s$, ta có:

$C_{n}^{k}C_{k}^{r}C_{r}^{s}=C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$

 

Nếu pé thích thì có thể dùng khai triển và đồng nhất hệ số:
Để ý rằng $[\sum_{i=0}^{n}x^i.C_{n}^{i}].[\sum_{j=0}^{n}(-x)^j.C_{n}^{j}]=(1+x)^n.(1-x)^n=(1-x^2)^n$.

Đồng nhất hệ số của $x^m$ ở hai vế:

$\sum_{k=0}^{m}C_{n}^{m-k}.C_{n}^{k}(-1)^k=$ hệ số của $x^m$ ở vế phải.

+Nếu $m$ lẻ thì hiển nhiên hệ số này ở vế phải bằng 0.

+Nếu $m$ chẵn thì đặt $m=2t$, hệ số này ở vế phải bằng $(-1)^tC_{n}^{t}$.

PS: Pé thử cố gắng nghĩ thêm cách đếm bằng 2 cách đi cho trọn vẹn. Như vậy sẽ đẹp hơn.

Em chỉ nghĩ ra được bài 30 thôi

Ta làm như sau:

Cho $n$ điểm. Tìm số cách tô $n$ điểm đó sao cho có $k-r$ điểm đỏ, $r-s$ điểm xanh, $s$ điểm đen

Cách 1: Đầu tiên ta tô $k$ điểm màu đỏ. Có $C_{n}^{k}$ cách tô. Lấy $k$ điểm này ta tô $r$ điểm màu xanh. Có $C_{k}^{r}$ cách tô. Lấy $r$ điểm trên và tô màu đen. Có $C_{r}^{s}$ cách tô. Vậy có tổng công $C_{n}^{k}C_{k}^{r}C_{r}^{s}$ cách tô

Cách 2: Ta dễ thấy số cách tô màu các điểm của bài toán trên là $C_{n}^{s}C_{n-s}^{r-s}C_{n-r}^{k-r}$

Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 14-09-2013 - 18:00

[LNH]

Hai bài về bất đẳng thức và cực trị tổ hợp 

Bài 32: (China 2010) Cho $A_1,A_2,...,A_{2n}$ là tập con đôi một khác nhau của tập $\left \{ 1,2,...,n \right \}$. Tìm giá trị lớn nhất của $\sum_{i=1}^{2n}\frac{\left | A_i \cap A_{i+1} \right |}{\left | A_i \right |.\left | A_{i+1} \right |}$

(với $A_{2n+1}=A_1$)

Bài 33: (Russia 2011) Cho một bảng gồm $10$ cột và $n$ hàng. Ở mỗi ô một chữ số được viết vào. Với một hàng $A$ và $2$ cột bất kì, ta có thể tìm một hàng chỉ khác $A$ tại $2$ ô giao với 2 cột đó. CMR: $n \geq 512$

Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 22-09-2013 - 19:10

[quocbaolqd11]

Hai bài về bất đẳng thức và cực trị tổ hợp 

Bài 32: (China 2010) Cho $A_1,A_2,...,A_{2n}$ là tập con đôi một khác nhau của tập $\left \{ 1,2,...,n \right \}$. Tìm giá trị lớn nhất của $\sum_{i=1}^{2n}\frac{\left | A_i \cap A_{i+1} \right |}{\left | A_i \right |.\left | A_{i+1} \right |}$

(với $A_{2n+1}=A_1$)

bài 32:

có lẽ sử dụng cái này:
đặt $A_i\cap A_{i+1}=:X$
$\[ \frac{|A_{i}\cap A_{i+1}|}{|A_{i}|\cdot |A_{i+1}|}\le\frac{|X|}{|X|\cdot (|X|+1)}\le\frac{1}2. \]$