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

[MIM]

Mấy bài này thầy mình ra về nhà nhưng không có thời gian sửa .Khó quá mình chẳng biết làm thế nào . giúp mình nha. Mấy bạn làm chi tiết giùm nha, mình đang học bài hoán vị và tổ hợp.(Chưa học bài sử dụng song ánh để giải toán tổ hợp).

Bài 1: Cho đa giác lồi n cạnh (n $\geq 3$ ).Tìm số đường chéo của đa giác.Đa giác nào có số cạnh bằng số đường chéo ?Tìm số tam giác có đỉnh trùng với đỉnh đa giác ?Có bao nhiêu giao điểm do các đường chéo tạo nên nếu không có 3 đường chéo nào là đồng quy???

Bài 2: Có 12 chiếc bánh ngọt khác nhau.Hỏi có bao nhiêu cách xếp chúng vào 6 hộp giống nhau,không kể thứ tự các hộp sao cho mỗi hộp có 2 bánh.

Bài 3: Cho một số hữu tỉ ,viết nó dưới dạng phân số tối giản rồi nhân tử và mẫu với nhau.Tìm số các số hữu tỉ nằm trong khoảng (0;1) thỏa mãn tích của tử và mẫu bằng 20!.

Bài 4: Bạn A cùng một nhóm gồm 2010 học sinh ngồi quanh một vòng tròn và chơi một trò chơi như sau: bắt đầu từ bạn A và đếm theo chiều kim đồng hồ,thứ tự từ 1 đến 3 rồi lại lặp lại,bạn nào mang số thứ tự 2 hoặc 3 phải rời khỏi vòng tròn.Việc đếm và loại cứ tiếp tục đến khi chỉ còn một bạn ở vòng tròn.Xác định vị trí của bạn còn lại???????????

Bài 5:Có bao nhiêu cặp số nguyên kế tiếp nhau trong tập {1000,1001,...,2000} thỏa mãn: trong khi thực hiện phép cộng 2 số đó thì không có nhớ???????????

Bài 6: Sắp xếp 100 số thực khác nhau từng đôi một quanh một vòng tròn.CMR bao giờ cũng tồn tại 4 số liên tiếp nhau theo sự sắp xếp đó sao cho tổng của các số ở giữa nhỏ hơn hẳn tổng của 2 số còn lại.

Bài 7 : Hãy sử dụng phép chứng minh bằng lý luận tổ hợp để chứng minh công thức

$C_{m+n}^{2}$-$C_{m}^{2}$-$C_{n}^{2}$=mn

Bài 8:Cho $n\geq 1$ là số tự nhiên.CM các đẳng thức sau bằng suy luận tổ hợp:
a)
$(C_{n}^{0})^{2}$+$(C_{n}^{1})^{2}$+...+$(C_{n}^{n})^{2}$=$C_{2n}^{n}$
b)
$\sum_{k=0}^{n}2^kC_n^kC_{n-k}^{[\dfrac{n-k}{2}]}$=$C_{2n+1}^{n}$
c)
$C_{n}^{1}$+$2C_{n}^{2}$+$3C_{n}^{3}$+...+$nC_{n}^{n}$=$n.2^{n-1}$

Thầy mình ra cả tập bài nhưng đánh chừng đó mỏi tay quá

Bài viết đã được chỉnh sửa nội dung bởi E. Galois: 19-12-2011 - 16:05

[hoangtrong2305]

Bài 1:

trong đa giác chọn 2 điểm bất kỳ, có $C_{n}^{2}$ cách

Ta có: 2 điểm bất kỳ tạo thành 1 đoạn thẳng => có $C_{n}^{2}$ đoạn thẳng tạo thành
Nhưng trong $C_{n}^{2}$ đoạn thẳng tạo thành sẽ có n đoạn thẳng chính là cạnh của đa giác, vì vậy sẽ có $C_{n}^{2}-n$ đường chéo tạo thành

Để đa giác có số cạnh bằng số đường chéo, có nghĩa là ta có pt sau:

$C_{n}^{2}=2n$

<=>$\dfrac{n!}{2!(n-2)!}=2n$

<=>$n(n-1)=4n$

<=>$n^{2}-5n=0$

<=>n=5

=> ngũ giác lồi là hình có số cạnh bằng số đường chéo


Ta có: trong đa giác lồi có $C_{n}^{2}-n$ đường chéo (1)

Trong các đường chéo đó chọn 2 đường chéo bất kỳ, có $C_{(1)}^{2}$ cách

2 đường chéo nếu ko đặc biệt (tức ko có 3 đường nào đồng quy hay ko song song) thì chúng sẽ cắt nhau, nhưng 2 đường ấy có thể cắt nhau tại đỉnh của đa giác, vậy ta có $C_{(1)}^{2}-n$ điểm tạo thành.

[hoangtrong2305]

Bài 2

chọn 2 cái bánh bất kỳ: $A_{12}^{2}$ cách

chọn 1 hộp bất kỳ: 6 cách

=> có $A_{12}^{2}.6=792$ cách

Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 05-11-2011 - 22:50

[phuonganh_lms]

Bài 8:Cho $n\geq 1$ là số tự nhiên.CM các đẳng thức sau bằng suy luận tổ hợp:
a)
$(C_{n}^{0})^{2}$+$(C_{n}^{1})^{2}$+...+$(C_{n}^{n})^{2}$=$C_{2n}^{n}$

Xét khai triển:
$ (1+x)^n=C_{n}^0+C_{n}^1+...+C_{n}^n.x^n$
$ (x+1)^n=C_{n}^0.x^n+C_{n}^1.x^{n-1}+....+C_{n}^n$
Nhân 2 khai triển trên với nhau ta có $(x+1)^{2n}=((C_{n}^0)^2+...+(C_{n}^n)^2).x^n$
Xét khai triển $(1+x)^{2n}=C_{2n}^0+C_{2n}^1.x+....+C_{2n}^n.x^n$
Đồng nhất hệ số ta có dpcm

[hoangtrong2305]

chém thử bài 3
Theo để bài, ta có a và b phải thoả:
$\left\{\begin{matrix} 0<\dfrac{a}{b}<1(1)\\ a.b=20!(2) \end{matrix}\right.$

(2) =>$a=\dfrac{20!}{b}$

Thay vào 1, ta có hệ <=> $0<\dfrac{20!}{b^{2}}<1$ với $b\neq 0$

<=>$20!<b^{2}$

<=>$1559776269<b$ (3)

với mỗi b ở (3) ta có a tương ứng: $a=\dfrac{20!}{b}$

Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 05-11-2011 - 23:54

[MIM]

Bài 8 đề yêu cầu chứng minh bằng suy luận tổ hợp mà >.<.cái khó là chỗ đó.mình k hỉu cái suy luận đó nó như thế nào

Bài viết đã được chỉnh sửa nội dung bởi huynhmylinh: 05-11-2011 - 23:59

[hxthanh]

Chém bài 8 a) chỉ bằng suy luận tổ hợp cho bạn nè!
" Có $n$ viên bi đỏ và $n$ viên bi xanh "
Có bao nhiêu cách lấy ra sao $n$ viên bi ?
- Cách 1, rõ ràng là có $2n$ viên bi, nên sẽ có $C_{2n}^n$ cách lấy ra $n$ viên
- Cách 2, ta phân loại ra thành $n+1$ trường hợp:

• Lấy $0$ viên đỏ và $n$ viên xanh có $C_n^0C_n^n=(C_n^0)^2$ cách
• Lấy $1$ viên đỏ và $n-1$ viên xanh có $C_n^1C_n^{n-1}=(C_n^1)^2$ cách
• ...
• Lấy $n$ viên đỏ và $0$ viên xanh có $C_n^nC_n^0=(C_n^n)^2$ cách

Tổng cộng ta có $(C_n^0)^2+(C_n^1)^2+...+(C_n^n)^2$ cách lấy ra $n$ viên bi

Bài viết đã được chỉnh sửa nội dung bởi UEVOLI: 06-11-2011 - 04:37

[hxthanh]

Bài 7 - Mình có một minh hoạ rất vui như thế này:

Bạn có $m$ cái quần và $n$ cái áo . Hỏi có bao nhiêu cách chọn ra $1$ bộ quần-áo

Cách 1: Theo quy tắc nhân, ta có $m.n$ cách chọn ra $1$ bộ quần-áo
Cách 2:
- Chọn ra 2 cái (trong m+n cái cả quần lẫn áo ) có $C_{m+n}^2$ trường hợp
- Trả lại nếu đó là 2 cái quần: Có $C_m^2$ trường hợp
- Trả lại nếu đó là 2 cái áo: Có $C_n^2$ trường hợp
- Vậy ta có $C_{m+n}^2-C_m^2-C_n^2$ trường hợp chọn được 1 bộ quần-áo
---------------------------
 

[Nguyễn Hưng]

Bài 8 câu c nhé

Xét bài toán sau: Đếm số cách chọn ra một nhóm người trong n người, trong đó có 1 đội trưởng.

* Đếm theo cách 1:

- Ta có những trường hợp sau:

+ Nhóm 1 người: có $C_n^1$ cách chọn 1 người, sau đó có 1 cách chọn nhóm trưởng trong nhóm 1 người đó

+ Nhóm 2 người: có $C_n^2$ cách chọn 2 người, sau đó có 2 cách chọn nhóm trưởng trong nhóm 2 người đó

+ ................

+ Nhóm n người: có $C_n^n$ cách chọn n người, sau đó có n cách chọn nhóm trưởng trong nhóm n người đó

Theo qui tắc cộng, có tất cả $C_n^1 + 2C_n^2 + 3C_n^3 + ... + nC_n^n$ cách chọn.

* Đếm theo cách 2: đầu tiên ta chọn một người nhóm trưởng cho nhóm, có $n$ cách chọn. Sau đó ta chọn những người còn lại của nhóm trong số $n-1$ người còn lại, có tất cả $2^{n-1}$ cách chọn (vì mỗi người trong số $n-1$ người còn lại có 2 trạng thái: thuộc hoặc không thuộc nhóm). Vậy theo qui tắc nhân, tất cả có $n2^{n-1}$ cách chọn.

Đáp số của cả hai cách đếm đều phải có giá trị như nhau, từ đó suy ra đẳng thức ban đầu.

[hxthanh]

Câu 8b. (Theo Jian Gu)

Thầy Thế, GVCN lớp 10A gồm $n$ học sinh nam và $n$ học sinh nữ. Tối nay, ở Rạp chiếu phim quốc gia, chiếu một bộ phim rất hay, thầy định tổ chức cho cả lớp đi xem... Cuối cùng thầy Thế chỉ mua được $n$ vé. Thầy suy nghĩ:

- Nếu $n$ vé được chia ngẫu nhiên cho $2n$ học sinh và cả mình thì xảy ra $C_{2n+1}^n$ trường hợp.

Vậy là thầy Thế nghĩ ra một cách chia như sau:
Thầy ghép $n$ học sinh nam và $n$ học sinh nữ thành $n$ đôi. (việc làm này coi như thực hiện từ đầu và không ảnh hưởng gì đến cách chia vé của thầy)

- Chọn ra $k$ đôi và chia cho mỗi đôi 1 vé - có $2^k.C_n^k$ cách chọn (vì mỗi đôi có $1$ vé nên $k$ đôi sẽ có $2^k$ kết cục khác nhau), như vậy còn lại $n-k$ vé và $n-k$ đôi còn lại. Thầy tiếp tục chọn ra $\left\lfloor\dfrac{n-k}{2}\right\rfloor $ đôi và chia cho mỗi đôi $2$ vé - có $C_{n-k}^{\left\lfloor\dfrac{n-k}{2}\right\rfloor}$ cách.

- Bây giờ thầy còn lại $S=n-k-2\left\lfloor\dfrac{n-k}{2}\right\rfloor$ vé.
$S=0$ nếu $n-k$ là số chẵn (khi đó $n$ vé đã được chia hết)
$S=1$ nếu $n-k$ là số lẻ (khi đó chiếc vé còn lại dành cho thầy )
- Dễ thấy rằng $k$ có thể nhận các giá trị từ $0$ đến $n$
Do đó, theo cách chia đó của thầy ta có tất cả:

$\sum\limits_{k=0}^n 2^k C_n^k C_{n-k}^{\left\lfloor\dfrac{n-k}{2}\right\rfloor}$

các cách chia $n$ vé cho $2n+1$ người.

Suy ra điều phải chứng minh.

[Crystal]

Một cách khác tham khảo cho bài 8a: dùng hàm sinh.

Xét đa thức: ${\left( {1 + x} \right)^{2n}}$ có hệ số của ${x^n}$ là $C_{2n}^n\,\,\,\,\,\,\,(1)$

Mặt khác ta có: $${\left( {1 + x} \right)^{2n}} = {\left( {1 + x} \right)^n}{\left( {1 + x} \right)^n}$$
Xét hàm sinh: $F\left( x \right) = G\left( x \right) = {\left( {1 + x} \right)^n}$ có hệ số ${a_r} = {b_r} = C_n^r$

Hệ số ${x^n}$ của $F\left( x \right)G\left( x \right)$ là ${a_0}{b_n} + {a_1}{b_{n - 1}} + ... + {a_n}{b_0} = {\left( {C_n^0} \right)^2} + {\left( {C_n^1} \right)^2} + ... + {\left( {C_n^n} \right)^2}\,\,\,\,\,\,\,(2)$

Từ $(1)$ và $(2)$ suy ra: $${\left( {C_n^0} \right)^2} + {\left( {C_n^1} \right)^2} + ... + {\left( {C_n^n} \right)^2} = \,C_{2n}^n$$

P/s: Cách giải này hoàn toàn giống cách của bạn phuonganh_lms

[Karl Heinrich Marx]

Một cách khác cho câu 8b. Để ý $ \binom{n-k}{{\left\lfloor\dfrac{n-k}{2}\right\rfloor}}$ là hệ số tự do trong khai triển $(x+1)(x+\dfrac{1}{x})^{n-k}$ do đó $ \sum\limits_{k=0}^{n}2^k\binom{n}{k}\binom{n-k}{{\left\lfloor\dfrac{n-k}{2}\right\rfloor}}$ là hệ số tự do trong khai triển $\sum\limits_{k=0}^{n}2^k\binom{n}{k}(x+1)(x+\dfrac{1}{x})^{n-k}=\dfrac{(1+x)^{2n+1}}{x^n}$

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 29-12-2011 - 12:44

[hxthanh]

Bài 1:

trong đa giác chọn 2 điểm bất kỳ, có $C_{n}^{2}$ cách

Ta có: 2 điểm bất kỳ tạo thành 1 đoạn thẳng => có $C_{n}^{2}$ đoạn thẳng tạo thành
Nhưng trong $C_{n}^{2}$ đoạn thẳng tạo thành sẽ có n đoạn thẳng chính là cạnh của đa giác, vì vậy sẽ có $C_{n}^{2}-n$ đường chéo tạo thành

...

Ta có: trong đa giác lồi có $C_{n}^{2}-n$ đường chéo (1)

Trong các đường chéo đó chọn 2 đường chéo bất kỳ, có $C_{(1)}^{2}$ cách

2 đường chéo nếu ko đặc biệt (tức ko có 3 đường nào đồng quy hay ko song song) thì chúng sẽ cắt nhau, nhưng 2 đường ấy có thể cắt nhau tại đỉnh của đa giác, vậy ta có $C_{(1)}^{2}-n$ điểm tạo thành.

 

Chỗ này sai!

Với $n$ đỉnh của đa giác thì có $C_n^4$ cách chọn một tứ giác. Mỗi tứ giác đều có hai đường chéo giao nhau tạo nên một điểm khác với đỉnh. Do đó nếu không có 3 đường chéo nào đồng quy thì số điểm tạo thành là $C_n^4$