Trong các đề thi có nhiều trường hợp phải đếm số lượng phần tử của một tập hợp thông qua các tập con của chúng. Ta sẽ xét cách giải các bài toán dạng này như thế nào? Tôi sưu tầm cách giải này thông qua các cuốn bồi dưỡng học sinh giỏi. Đây là nôi dung của thầy Vũ Đình Hoà (người đã từng đoạt giải toán quốc tế, thế kỷ trước) hướng dẫn.

Ví dụ 1. Có 2 bài toán kiểm tra, nhưng lớp chỉ có 30 hs làm được bài thứ nhất và 20 hs làm được bài thứ 2. Chỉ có 10 hs làm được cả 2 bài. Hỏi số học sinh trong lớp?

Giải:
Gọi A là tạp hợp hs giải được bài 1, và B là tập hợp hs giải được bài 2 thì A ∩ B là tập hợp hs giải được cả 2 bài toán. Bài toán đặt ra là tính số phần tử A U B.

Nếu A và B là 2 tập rời nhau thì:
|A ∩ B| = |A| + |B|

Trong trường hợp A và B giao khác Ø thì phải áp dụng công thức:
|A U B| = |A| + |B| - |A ∩ B|
bởi trong tổng |A| + |B| thì các phần tử chung trong |A ∩ B| (của cả A và B) được tính lặp đúng 2 lần.

Sử dụng công thức này ta thấy số học sinh của lớp là:
30 + 20 - 10 = 40 hs.

Ví dụ 2. Giờ kiểm tra TRR có 3 bài. Biết rằng, mỗi hs làm được ít nhất 1 bài. Có
20 hs làm được bài 1.
14 hs làm được bài 2.
10 hs làm được bài 3.
6 hs giải được bài 1 và 3.
5 hs giải được bài 2 và bài 3.
2 hs giải được bài 1 và 2.
1 hs giải được cả 3 bài.
Hỏi lớp có bao nhiêu học sinh.

Giải:
Gọi A là số hs giải bài 1. B là số hs giải bài 2. C là số hs giải bài 3. Tính số học sinh tức là tính A U B U C.
Lập luận tương tự bài trên để có công thức:
|A U B U C| = |A| + |B| + |C| - (A ∩ B| - |B∩C| - |C∩A| + |A ∩B ∩C|
= 20 + 14 + 10 - 6 - 5 - 2 + 1 = 32

Bây giờ ta hãy giải đề thi năm 2007. Câu 1b.
Trong lớp có 60 sv sau kỳ thi gòm 3 môn.
25 sv không phải thi lại TRR.
30 sv không phải thi lại CTDL.
35 sv không phải thi lại Tiếng Anh.
45 sv không phải thi lại ít nhất 2 môn.
12 sv phải thi lại cả 3 môn.
Tính số sv không phải thi lại môn nào.

Bài toán này đảo vị trí các dữ liệu với 2 ví dụ trên. Có thể hiểu là:
không phải thi lại = tổng số - thi lại
Hoặc tổng = X + Y chẳng hạn, thì Y = Tổng - X

Hãy giải đề thi trên bằng nhiều cách nhé!

Bài anh giải là dựa trên nguyên lý bao hàm loại trừ.
Nguyên lý này phát biểu tổng quát và chứng minh khá chi tiết ở [You must be registered and logged in to see this link.]
Công thức tổng quát của nó hay dùng nhất là:
|Hợp của các tập hợp ∩ nhau| = |tổng của các tập đơn| - |Tổng của ∩ tập đôi| + |tổng của ∩ tập ba| - |Tổng của ∩ tập bốn|...
cứ cộng trừ xen kẽ...
Nhiều bài tập ở link trên giống đề thi cao học lắm. Các anh chị chịu khó làm theo nguyên lý này cho dễ nha.
Ví dụ: Trong tập S{1..280} có bao nhiêu số không chia hết cho 2, 3, 5 , 7
Đặt A₁ là tập các số chia hết cho 2
Đặt A₂ là tập các số chia hết cho 3
Đặt A₃ là tập các số chia hết cho 5
Đặt A₄ là tập các số chia hết cho 7
Khi đó A₁ U A₂ U A₃ U A₄ là tập các số chia hết cho ít nhất một trong các số 2, 3, 5, 7.
Tính bằng cách lấy 280 chia cho số chia hết, lấy phần nguyên.
Ta sẽ được A₁ = 280/2 = 140;           A₂ = 280/3 = 93;           A₃ = 280/5;           A₄ = 280/7 =40
Tính A₁ ∩ A₂ = 280/6 =46,           Tính A₁ ∩ A₃ = 280/10 =28
Tính A₁ ∩ A₄ = 280/14 =20,           Tính A₂ ∩ A₃ = 280/15 =18
Tính A₂ ∩ A₄ = 280/21 =13,           Tính A₃ ∩ A₄ = 280/35 =8
Tính A₁ ∩ A₂ ∩ A₃ = 280/30 =9,           Tính A₁ ∩ A₂ ∩ A₄ = 280/42 =6
Tính A₁ ∩ A₃ ∩ A₄ = 280/70 =4,           Tính A₂ ∩ A₃ ∩ A₄ = 280/105 =2
Tính A₁ ∩ A₂ ∩ A₃ ∩ A₄ = 280/210 = 1
Sử dụng công thức bao hàm loại trừ tìm được A₁ U A₂ U A₃ U A₄ = 216
Số không chia hết cho 2, 3, 5, 7 trong S là 280 - 216 = 64.
[You must be registered and logged in to see this image.] Các anh chị vui tính quá! Tiêu đề bài shock ghê!

Trong sách thì nguyên lý này được gọi là nguyên lý bù trừ (trang 65), và nó được chứng minh tổng quát ở trang 68. Có phát biểu tổng quát và rút ra được giống như link mà bạn Hải Yến đã nêu.


Bây giờ ta hãy giải đề thi năm 2007. Câu 1b.

Trong lớp có 60 sv sau kỳ thi gòm 3 môn.

25 sv không phải thi lại TRR.

30 sv không phải thi lại CTDL.

35 sv không phải thi lại Tiếng Anh.

45 sv không phải thi lại ít nhất 2 môn.

12 sv phải thi lại cả 3 môn.

Tính số sv không phải thi lại môn nào.



Bài này đề năm 2007 ra sai. Nên nếu giải ra sẽ có đáp số âm. Hôm nay thầy chỉnh lại 1 con số, đó là sĩ số lớp 70 chứ không phải 60 học sinh.
Đây là tóm tắt lời giải của thầy trên lớp, nếu Khách viếng thăm không đi học, có thể tham khảo. Nếu Khách viếng thăm có đi học, thì kiểm tra xem lời giải có đúng như thầy chữa trên lớp không? Bởi tốc độ của thầy như ngựa phi, ai mà chưa kịp định thần thì đã sang nội dung khác mất rồi.

Gọi a là số sinh viên thi lại TRR. Ta có: Na = 70 - 25 = 45
Gọi b là số sinh viên thi lại CTDL. Ta có Nb = 70 - 30 = 40
Gọi c là số sinh viên thi lại Tiếng Anh. Ta có Nb = 70 - 35 = 35

Ta có: N(a ∩ b ∩ c) = 12
N (a ∩ b) + N (b ∩ c) + N (a ∩ c) - 2N (a ∩ b ∩ c) = 45
N (a ∩ b) + N (b ∩ c) + N (a ∩ c) = 45 + 24 = 69

Theo nguyên lý bù trừ:
N(a U b U c) = Na + Nb + Nc - N (a ∩ b) + N (b ∩ c) + N (a ∩ c) + N(a ∩ b ∩ c)
= 45 + 40 + 35 - 69 + 12 = 63

Vậy số sv không phải thi lại môn nào là:
70 - 63 = 7

thầy ơi giải giúp em bài này theo nguyên lý bù trừ : có bao nhiêu số nguyên dương nhỏ hơn hoặc bằng 1000 hoặc là số lẻ hoặc là số chính phương?.em mới học tới nguyên lý này nên chưa lắm rõ.thanks thầy

vodoi1801 đã viết:thầy ơi giải giúp em bài này theo nguyên lý bù trừ : có bao nhiêu số nguyên dương nhỏ hơn hoặc bằng 1000 hoặc là số lẻ hoặc là số chính phương?.em mới học tới nguyên lý này nên chưa lắm rõ.thanks thầy

không ai trả lời hô bạn à
mình cũng đang phân vân câu này híc