01.4.Nguyên lý bao hàm loại trừ

Giới thiệu

Được giới thiệu từ những năm đầu thế kỷ 18, nguyên lý bao hàm - loại trừ là một phương pháp tổng quát để đếm lực lượng của hợp các tập hợp. Không chỉ hữu dụng trong lý thuyết tập hợp, nguyên lý này cũng có thể được dùng để giải rất nhiều bài toán phức tạp trong lý thuyết số, lý thuyết đồ thị và xác suất.

Tài liệu tham khảo

• Wikipedia - Nguyên lý bao hàm - loại trừ

• VNOI Wiki - Bao hàm - loại trừ

• CP Algorithms - the Inclusion - Exclusion Principle

• Tài liệu chuyên đề Duyên Hải Bắc Bộ 2023 - Nguyên lý bao hàm - loại trừ

Phát biểu nguyên lý

Đúng như tên gọi, nguyên lý này dùng để đếm chính xác lực lượng (số phần tử) của hợp các phần tử hữu hạn. Để dễ hiểu chúng ta bắt đầu với hai tập hợp A và B. Ta gọi số phần tử của một tập hữu hạn X là lực lượng của X và ký hiệu |X|. Như vậy:

|A ∪ B| = |A| + |B| - |A ∩ B|

Sở dĩ ta trừ đi phần giao là vì trong trường hợp A và B có nếu có phần giao, các phần tử trong phần này sẽ bị đếm hai lần vì chúng vừa thuộc A lại vừa thuộc B. Đây chính là nền tảng của nguyên lý bao hàm loại trừ, tức là bao hàm các phần của từng tập hợp nhưng phải loại trừ đi những phần bị trùng lặp. Để cho trực quan, các em nhìn vào biểu đồ Venn bên dưới:

Ví dụ 1:

Cho ba số nguyên dương a, b, N. Hãy đếm xem có bao nhiêu số nguyên trong đoạn [1, N] chia hết cho a hoặc b.

Input: một dòng duy nhất chứa ba số nguyên dương a, b, N cách nhau bằng khoảng trắng (1 <=a,b,N<=10^18)

Output: một số nguyên dương duy nhất là số các số thỏa mãn yêu cầu bài toán

ví dụ:

• input: 2, 3, 20

• output: 13

Giải thích:

• Các số chia hết cho 2 từ 1 -->20, gọi là tập A: 2 4 6 8 10 12 14 16 18 20 --> có |A| = 10

• Các số chia hết cho 3 từ 1 -->20, gọi là tập B: 3 6 9 12 15 18 --> có |B| =  6

• Nếu hai tập hợp này rời nhau, ta chỉ đơn giản lấy 10 + 6 = 16 số, nhưng hai tập này giao nhau, đó là những số vừa chia hết cho 2 vừa chia hết cho 3, chính là tập {6, 12, 18} tạm gọi là tập AB, với |AB|= 3. Vậy khi đếm lực lượng của hai tập A, B, các phần tử thuộc tập AB được đếm 2 lần. Cho nên kết quả cuối cùng sẽ là: |A ∪ B| = |A| + |B| - |A ∩ B|

Nhiệm vụ 1. Code hoàn chỉnh ví dụ 1

Trường hợp trên cho hai tập hợp giúp chúng ta dễ hiểu được nền tảng của nguyên lý nhưng nó chưa cho chúng ta thấy được cái nhìn bao quát. Bởi khi xét trường hợp có ba tập hợp A, B, C, làm sao chung ta tính được lực lượng của hợp ba tập hợp này? nghịa là cần tính |A ∪ B ∪ C|. Để dễ hình dung, các em có thể nhìn vòa biểu đồ Venn bên dưới:

Để dễ hiểu, các em lấy A ∪ B rồi sau đó ∪ với C. trước tiên để tính |A ∪ B| thì chúng ta đã biết bên trên, ta phải trừ phần |A ∩ B|. Sau đó lấy phần |A U B| này gộp với C thì phải trừ đi khu vực B  ∩ C  và A ∩ C, lúc đó phần giao của hai khu vực giao này, tức là A ∩ B ∩ C bị trừ 2 lần --> ta phải cộng lại một lực lượng này. Vậy kết quả cuối cùng là:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Ví dụ 2: 

Cho bốn số nguyên a, b, c và N. Đếm xem có bao nhiêu số trong đoạn [1, N] chia hết cho a, b, hoặc c.

Input: một dòng duy nhất chứa bốn số nguyên dương a, b, c, N cách nhau bằng khoảng trắng (1 <=a,b,c,N<=10^18)

Output: một số nguyên dương duy nhất là số các số thỏa mãn yêu cầu bài toán

ví dụ:

• input: 2, 3, 5, 100

• output: 74

Giải thích:

Gọi S = {1,...,100} và P1 là tính chất số nguyên chia hết cho 2, P2 là tính chất số nguyên chia hết cho 3 và P3 là tính chất số nguyên chia hết cho 5. Gọi Ai là tập con của S chứa các phần tử có tính chất Pi, ta đếm được rằng: |A1| = 50, |A2| = 33, và |A3| = 20. Có 16 số nguyên chia hết cho 6, 10 số chia hết cho 10, và 6 số chia hết cho 15. Và cuối cùng, chỉ có 3 số chia hết cho 30, nên số các số nguyên cho 2, 3 hoặc 5 được tính bằng:

(50 + 33 + 20) - (16 + 10 + 6) + 3 = 74.

(Nguồn: Wikipedia - nguyên lý bao hàm loại trừ)

Nhiệm vụ 2. Code hoàn chỉnh ví dụ 2

Nguyên lý

Từ các ví dụ trên, ta có thể rút ra được dạng tổng quát của nguyên lý này:

Để tính lực lượng của hợp các tập hợp, ta tính tổng lực lượng từng tập hợp, sau đó trừ đi tổng lực lượng của các phần tử xuất hiện trong hai tập hợp, rồi lại cộng cho lực lượng các phần tử xuất hiện trong ba tập hợp, ....

Quá trình được viết theo dạng thuật toán như sau:

Để tìm lực lượng của hợp của n tập hợp:

1. Thêm lực lượng của các tập hợp.

2. Trừ lực lượng của các phần giao của 2 tập hợp.

3. Thêm lực lượng của các phần giao của 3 tập hợp.

4. Trừ lực lượng của các phần giao của 4 tập hợp.

5. Thêm lực lượng của các phần giao của 5 tập hợp..

6. Tiếp tục cho đến khi xét hết phần giao của n tập hợp. Bước cuối sẽ là thêm vào nếu n lẻ và trừ đi nếu n chẵn}}.

Công thức

Dạng công thức của quá trình trên được viết:

Phần bù

Trong ứng dụng giải các bài toán CP, nguyên lý này thường được áp dụng trong việc tìm phần bù.

Cho một tập hợp S, gọi A là tập con của S, thì phần bù của A trong S ký hiệu là A' hoặc S\A hoạc A mũ c hoặc A gạch đầu tùy theo các sách, nhưng tóm lại nó là các phần tử thuộc S nhưng không thuộc A. 

|S\A| = |S| - |A|

Trong nhiều bài toán, việc tính trực tiếp lực lượng của tập hợp các phần tử theo mô tả đề bài là rất khó, nhưng nếu ta tính phần bù của nó rồi lấy lực lượng của tập tổng trừ đí phần bù thì lại dễ hơn. Đây chính là hướng tiếp cận để giải nhiều bài toán áp dụng phương pháp bao hàm loại trừ.

Công thức tổng quát phần bù

gọi S là tập phổ dụng hữu hạn chứa tất cả các tập Ai và ta gọi Ai¯ là phần bù của Ai trong S, theo luật De Morgan, ta có:

Ví dụ 3:

Cho hai số nguyên N, R. Hãy đếm các số nguyên tố cùng nhau với N trong đoạn [1, R].

Số a nguyên tố cùng nhau với N khi ước chung lớn nhất của a và N bằng 1.

Input: hai số nguyên N, R cách nhau bằng khoảng trắng (1<=N,R<=10^18)

Output: một số nguyên duy nhất là số lượng số nguyên tổ cùng nhau với N trong đoạn [1,R]

Ví dụ:

Input: 12 10

Output: 3

Giải thích:

Các số nguyên tố cùng nhau với 12 trong đoạn [1, 10] là {1, 5, 7} 

Hướng tiếp cận:

Cách 1: 

Duyệt một vòng lặp cho i  chạy từ 1 đến R, kiểm tra gcd(N,i) để tăng biến đếm nếu gcd(N,i) ==1.

Cách này rất dễ hiểu và dễ triển khai, tuy nhiên độ phức tạp phụ thuộc vào R nên không khả thi khi R lên đến 10^18.

Cách 2:

Thay vì đếm trực tiếp số lượng các số nguyên tố cùng nhau với N ta đếm số lượng các số không nguyên tố cùng nhau với N rồi lấy R trừ đi số đó. Đây chính là ý tưởng sử dụng phần bù đã đề cập ở trên.

Vấn đề bây giờ là làm sao ta đếm được các số không nguyên tố cùng nhau với N trong đoạn [1, R]. 

Một số không nguyên tố cùng nhau với N khi nó chia hết cho một trong những ước nguyên tố của N.

Ví dụ: 

Với N = 12, ta phân tích 12 thành thừa số nguyên tố: 12 = 2^2*3, vậy 12 có hai ước nguyên tố là 2 và 3:

• từ 1 -->10: có 5 số chia hết cho 2 là 2, 4, 6, 8, 10

• từ 1 -->10: có 3 số chia hết cho 3 là 3, 6, 9

• Từ 1-->10: Có 1 số vừa chia hết 2 vừa chia hết cho 3 là 6

--> Số các số không nguyên tố cùng nhau với N được tính theo nguyên lý bao hàm loại trừ giống ví dụ 1 là: 5+3-1 = 7

--> Số các số nguyên tố cùng nhau với N = 10 - 7 =3

Độ phức tạp:

• Phân tích thừa số nguyên tố: O(sqrt(N))

• Nguyên lý bao hàm loại trừ: O(2^k) với k là số ước nguyên tố của N, Với N khoảng 10^18 thì chỉ có tối đa 16 ước nguyên tố.

• Tổng độ phức tạp: O(sqrt(N) + 2^k), với k <=16, vậy tương đương 6.5*10^5, hoàn toàn chạy được trong thời gian chỉ 0.1 giây.

Vấn đề còn lại là triển khai code, bước tính số số không nguyên tố cùng nhau với N ở bài này là phiên bản mở rộng của ví dụ 2. Ở vd2 chúng ta biết chắc có ba tập hợp A, B, C đại diện cho các bội của 2, 3 và 5. Ở bài toán này chúng ta có K tập hợp từ A1 đến Ak . Như vậy chúng ta phải triển khai được công thức tổng quát của nguyên lý cho k tập hợp.

Có hai bài toán con mà chúng ta cần giải quyết:

Bài toán 1: Tìm tập các ước nguyên tố của số N, ví dụ nếu N = 30 thì ta phải ra được tập A =  {2, 3, 5}

Bài toán 2: Duyệt qua tất cả tập con của tập A, trong trường hợp này là 8 tập: {}, {2}, {3}, {5}, {2, 3}, {2, 5}, {3, 5} và {2, 3, 5}

Ở bài toán 2 này ta phải sử dụng quay lui (backtracking) hoặc bitmask để duyệt, trong quá trình đó đồng thời phải nhân các giá trị của tập con và đếm số phần tử của tập con. Kỹ thuật duyệt tập con bằng bitmask các em có thể tham khảo tại đây.

Nhiệm vụ 3. Thử thách code hoàn chỉnh ví dụ 3

Như đã giới thiệu ở phần đầu, nguyên lý bao hàm loại trừ có thể ứng dụng để giải quyết nhiều bài toán thuộc các lĩnh vực khác nhau từ lý thuyết xác suất đến lý thuyết độ thị (tô màu đồ thị, đồ thị hai phía, ...) và các bài toán đếm thuộc loại NP-hard. Chúng ta sẽ thảo luận đến lớp các bài toán này sau. 

Để luyện tập khả năng ứng dụng nguyên lý này vào một số bài toán còn ở mức đơn giản, các em hãy thức sức với contest sau nhé.

Nhiệm vụ 4. Thực hiện Contest ngắn Bao hàm - loại trừ 1