Các bài toán đếm - xác suất hay và khó

CHUYÊN MỤC MỖI TUẦN MỘT CHỦ ĐỀ - CHỦ ĐỀ SỐ 2 NGÀY 27/8/2018

Fanpage: Tạp chí và tư liệu toán học Chinh phục olympic toán | 1

CÁC BÀI TOÁN ĐẾM – XÁC SUẤT HAY VÀ KHÓ

Tạp chí và tư liệu toán học

Tiếp nối thành công của số trước, trong số này chúng ta sẽ cñng đi tëm hiểu các bài toán

đếm – xác suất hay và khó. Bên cạnh các phương pháp tình xác suất cơ bản như trong sách

giáo khoa, trong bài viết này mình sẽ giới thiệu cho các bạn một vài công cụ mạnh nữa để

giải quyết các bài toán xác suất. Bản pdf được đăng trên blog Chinh phục Olympic toán

các bạn chò ó đîn đọc nhé!

I. HAI BÀI TOÁN TÍNH XÁC SUẤT CÓ NHIỀU ỨNG DỤNG

1. BÀI TOÁN CHIA KẸO EULER

Bài toán chia kẹo của Euler là bài toán nổi tiếng trong Lý thuyết tổ hợp. Với những học

sinh chuyên Toán cấp 3 thë đây là bài toán quen thuộc và có nhiều ứng dụng. Dưới đây là

một cách tiếp cận bài toán chia kẹo của Euler cho học sinh lớp 6 & 7 để thấy rằng các bài

toán đếm nói riêng và các bài toán tổ hợp nói chung luôn là những bài toán mà lời giải của

nó chứa đựng sự hồn nhiên và ngây thơ. Trước hết, xin phát biểu lại bài toán chia kẹo của

Euler

Bài toán chia kẹo của Euler:

Có n cái kẹo (giống nhau) chia cho k em bé, hỏi có bao nhiêu cách chia sao cho em nào

cũng cî kẹo.

Một cách hợp lì, ta hãy xét bài toán trong trường hợp cụ thể, đơn giản hơn để từ đî định

hướng đưa ra lời giải cho bài toán tổng quát.

Bài toán 1. Có 20 cái kẹo (giống nhau) chia cho 3 em bé, hỏi có bao nhiêu cách chia sao cho

a) Mỗi em có ít nhất 1 cái kẹo.

b) Mỗi em có ít nhất 2 cái kẹo.

c) Em thứ nhất có ít nhất 1 cái kẹo, em thứ hai có ít nhất 2 cái kẹo và em thứ ba có nhiều

nhất 3 cái kẹo.

Lời giải.

a) Nhận thấy rằng, vì mỗi em có ít nhất một cái kẹo nên số kẹo của em thứ nhất nhận được

ít nhất là 1 và nhiều nhất là 18 Xét các trường hợp

Trường hợp 1. Em thứ nhất nhận được 1 cái kẹo, thì số kẹo của em thứ hai có thể

là 1,2,3,...,18 em thứ ba nhận số kẹo còn lại sau khi chia cho em thứ nhất và em thứ hai

xong, nghĩa là trong trường hợp này có 18 cách chia kẹo.

Trường hợp 2. Em thứ nhất nhận được 2 cái kẹo, khi đî số kẹo của em thứ hai có thể

là 1,2,3,...,17 em thứ ba nhận số kẹo còn lại, nghĩa là trong trường hợp này có 17 cách

chia kẹo

…

TỔ HỢP – XÁC SUẤT VÀ CÁC BÀI TOÁN ĐẾM KHÓ

2 | Chinh phục olympic toán Fanpage: Tạp chí và tư liệu toán học

Hoàn toàn tương tự cho các trường hợp còn lại, ta nhận thấy số cách chia 20 cái kẹo cho 3

em bé sao cho em nào cũng cî kẹo là 18 17 ... 2 1 171     

Phát biểu tổng quát.

Nếu k 1  thì chỉ có 1 cách chia kẹo

Nếu k 2  ta trải n chiếc kẹo thành dàn hàng ngang, tiếp theo ta dùng   k 1  chiếc thước đặt vào

  n 1  khe giữa các viên kẹo để nó chia thành k phần. Như vậy có tất cả k 1 n 1 C 

 cách.

Cả 2 trường hợp ta đều có k 1 n 1 C 

 cách chia kẹo.

Trên đây là lời giải của bài toán chia kẹo Euler – bài toán đếm nổi tiếng với nhiều ứng dụng trong

các bài toán đếm khác. Bài này tác giả sẽ trình bày bài toán gốc cơ bản và một số bài toán đếm

dạng ứng dụng mà nếu đếm theo cách thïng thường sẽ rất khî khăn, nhưng khi hiểu theo các đếm

của bài toán Euler thì bài toán lại trở thành đơn giản.

Sau đây ta sẽ cùng tìm hiểu một ứng dụng rất lớn trong việc đếm số nghiệm nguyên của

phương trënh.

Bài toán 1. Phương trënh  

k

i i 1

x n n k



   có bao nhiêu nghiệm nguyên dương?

Coi ix là phần kẹo của em nhỏ thứ i trong bài toán chia kẹo thì số nghiệm của phương

trình chính là số cách chia n chiếc kẹo cho k em nhỏ. Vậy phương trënh cî k 1 n 1 C 

 nghiệm

nguyên dương.

Bài toán 2. Phương trënh  

k

i i 1

x n n k



   có bao nhiêu nghiệm nguyên không âm?

Ta có      1 2 k 1 2 k x x ... x n x 1 x 1 ... x 1 n k             

Đặt i i x ' x 1   thì ix ' là các số nguyên dương.

Áp dụng bài toán gốc ta có tất cả k 1 n k 1 C 

 nghiệm nguyên không âm của phương trënh

Bài toán 3. Bất phương trënh  

k

i i 1

x n n k 1



    có bao nhiêu nghiệm nguyên dương?

Ta luôn có  

k k

i i i …