Trường hợp xấu nhất

Cách giải tổng quát:

Bước 1: Chọn ra trường hợp xấu nhất có thể xãy ra, ví du: nếu có 3 màu bi thì lấy 2 màu bi có số lượng lớn nhất.

Bước 2: Tùy theo yêu cầu đề bài, có thể lấy thêm đúng 1 viên bi để có thể đảm bảo lúc nào cũng có thể lấy được 3 màu hoặc lấy thêm 3 viên bi để đủ 3 màu và mỗi màu có ít nhất 3 viên...

==>  Chọn trường hợp xấu nhất với giá trị lớn nhất nhưng không thỏa yêu cầu đề bài 

Tại sao phải đếm theo trường hợp xấu nhất? Để dù trường hợp nào xảy ra thì ta vẫn luôn chắc chắn thỏa mãn đề bài.

Example.

Numbers are drawn from the 76 integers 25 to 100. At least how many numbers are drawn at random to ensure that there are two numbers whose sum is 120?

Có 76 số nguyên từ 25 đến 100. Hỏi cần lấy ra ngẫu nhiên ít nhất bao nhiêu số để chắc chắn trong đó có 2 số có tổng là 120?

Lời giải

Ta có: 120 = 25+95=26+94=27+93 = ... = 59 +61

Từ 25, 26, 27, ... đến 59 có 35 số.

Do đó, ta có 35 cặp số có tổng là 120.

Có 70 số thuộc 35 cặp đó.

Còn lại: 76 – 70 = 6 (số) không thể tạo thành tổng 120.

Xét trường hợp xấu nhất ta chọn được:

• 6 số không thể ghép lại thành tổng 120.
• 35 số lần lượt thuộc 35 cặp.
• Ta lấy tiếp 1 số, số này sẽ ghép với 1 trong 35 số trên tạo thành tổng là 120.

Vậy ta cần lấy: 6 + 35 + 1 = 42 (số).

Đáp số: 42.

Nhận xét: Ta có cách làm với bài toán dạng này như sau:

• Bước 1: Tách tổng thành các cặp để đếm số cặp ⇨ Đếm các số thuộc các cặp đó.
• Bước 2: Đếm các số không thuộc cặp nào.
• Bước 3: Xét trường hợp xấu nhất.

• Chọn tất cả các số không thuộc cặp nào.
• Chọn mỗi cặp 1 số
• Lấy thêm một số nữa

• Bước 4: Số các số cần lấy bằng tổng các phần trong bước 3.