Ứng dụng phương pháp đếm bằng hai cách thông thường qua bảng các ô vuông trong các bài toán tổ hợp

(1)

1

ỨNG DỤNG PHƯƠNG PHÁP ĐẾM BẰNG HAI CÁCH THÔNG QUA BẢNG CÁC Ô VUÔNG TRONG CÁC BÀI TOÁN TỔ HỢP

Đậu Hoàng Hưng-Trường THPT chuyên Phan Bội Châu-NA

Chúng ta biết rằng kỹ thuật tính bằng hai cách là một kỹ thuật khá thông dụng trong toán học dựa trên nguyên lý cơ bản: “một đại lượng luôn có nhiều cách tính khác nhau, tùy theo cách ta nhìn nhận đối tượng”. Điều quan trọng là tất cả các cách tính đó đều cho ra một kết quả như nhau. Sau đây là một số hướng mới cho phép ta tiếp cận lời giải bài toán tổ hợp thông qua phương pháp tính bằng hai cách trên bảng các ô vuông. Trước hết ta xét bài toán: Cho F S( ) là họ tất cả các tập con khác rỗng của tập hữu hạn S . Với mỗi xS, gọi d x( ) là số các tập con thuộc F S( )chứa x . Chứng minh rằng:

( )

x S A F S

d x A

 







. (0.1)

Chứng minh

Giả sử S 



x x1, 2,...,x_n



, với mỗi x_iS có 2^n¹ tập con thuộc F S( ) chứa xi, suy ra

( ) .2ⁿ 1 x S

d x n ^





 . (0.0.1) Mặt khác, với mỗi ^k^



^{1, 2,...,}ⁿ



^cóCn^k tập con gồm k phần tử của S, suy ra

 

( ) 0

.

n

k n

A F S k

A k C

 







n.2ⁿ^¹. (0.0.2) Từ (0.0.1) và (0.0.2) ta có:

( )

x S A F S

d x A

 







^.



(2)

2

Trong bài toán trên thì ( )F S là họ tất cả các tập con khác rỗng của tập hữu hạn S. Vấn đề đặt ra là nếu ta thay giả thiết đó bới F S( ) là họ bất kỳ các tập con của tập hữu hạn S thì:

(i) Kết quả có còn đúng nữa không?.

(ii) Phương pháp chứng minh bài toán có còn giá trị cho kết quả mở rộng nữa hay không? Hướng khắc phục hạn chế đó?

(iii) Ngoài kết quả đó ra có thể xây dựng được các kết quả khác nữa không?.

Câu trả lời cho những vấn đề đặt ra là kết quả đó vẫn đúng cho trường hợp F S( ) là họ bất kỳ các tập con của tập hữu hạn S . Tuy nhiên, trong phương pháp chứng minh bài toán trên, chúng ta đã sử dụng tính chất cơ bản của họ tất cả các tập con của tập hữu hạn để xây dựng đẳng thức (0.0.1) và phương pháp chứng minh này có thể không áp dụng được cho họ bất kỳ.

Điều này đòi hỏi chúng ta phải xây dựng và đưa ra kỹ thuật chứng minh mới để khác phục hạn chế đã nếu. Một trong những kỹ thuật đó là đếm bằng hai cách trên bảng các ô vuông. Cụ thể ta có định lý sau:

Định lý. Cho F S( ) là họ các tập con khác rỗng của tập hữu hạn S . Với mỗi xS, gọi d x( ) là số các tập con thuộc F S( )chứa x . Khi đó ta có:

a)

( )

x S A F S

d x A

 







, (0.1.1) b) ²

( ) ( )

( )

x S A F S B F S

d x A B

  





 

^ . (0.1.2) Chứng minh. Không mất tính tổng quát, ta giả sử tập hợp S 



x x1, 2,...,x_n



và F S( )



A A1, 2,...,A_k



(k 2ⁿ). Xét bảng n k ô vuông (gồm n hàng, k cột) sao cho tại mỗi ô vuông thứ ( , )i j (hàng thứ i, cột thứ j) ta đặt một số

,

ai j xác định bởi

(3)

3

,

1 0

i j

i j

i j

x A

a x A

 

 

 



.

a1,1 a_1,2 ... a_1,_k_₁ a_1,k a2,1 a_2,2 ... a_2,_k_₁ a_2,k .

. .

. . .

1,1

an_ a_n__1,2 ... a_n__1,_k_₁ a_n__1,_k

,1

an a_n_,2 a_{n k}_, _₁ a_{n k}_,

a) Với mỗi ⁱ^



^1,2,...,ⁿ



, đếm theo hàng thứ i ta có:

, 1

( )

k

i i j

j

d x a





^,

suy ra

_,

1 1 1

( )

n n k

i i j

i i j

d x a

  







^.

Tương tự, với mỗi ^j^



^{1, 2,...,}^k



, đếm theo cột thứ j ta có:

, 1 n

j i j

i

A a





^,

suy ra

_,

1 1 1

k k n

j i j

j j i

A a

  







^.

Do

, ,

1 1 1 1

n k k n

i j i j

i j j i

a a

   







nên

(4)

4

1 1

( )_i _j

i j

d x A

 







hay

( )

x S A F S

d x A

 







^.

b) Với mỗi ⁱ^



^1,2,...,ⁿ



^{ta đặt}

d x( )_i k_i, suy ra

2

2 2

,

1 1 1 1

( )

n n k n

i i j i

i i j i

d x a k

   

 

   

 

   

. (0.1.3) Xét họ tập hợp ( )P S xác định bởi:

^{P S}^{( )}^



^{( , ) : ,}^{A B} ^{A B}^^{F S A}^{( );} ^^{B A}^, ^^B^{ }



(ở đây ( , )A B không kể thứ tự). Do P S( ) là số cặp (1,1) trong mỗi hàng của bảng nên ta có

²

1

( ) j

n k j

P S C





^,

suy ra

( ) ( ) 1

2 ( )

n j

A F S B F S j

A B P S k

  

 

 

^



²

1 1

2 j

n n

k j

j j

C k

 









hay

2

( ) ( ) 1

n j

A F S B F S j

A B k

  

 

^ 



. (0.1.4) Từ (0.1.3) và (0.1.4) ta có:

2

( ) ( )

( )

x S A F S B F S

d x A B

  





 

^ ^.



Nhận xét: Từ đẳng thức (0.1.1) và (0.1.2) và bằng kỹ thuật chứng minh tương tự ta có:

 ( )

x X A F

d x X A

 







^ ^,^^X ^^S. (0.1.5)



( ) ( ) ( )

( )

A F S x A A F S B F S

d x A B

   

 



 

^ . (0.1.6)

(5)

5



 

₁

1,..., ( )

( ) ...

s

i is

s

i i

x S A A F S

d x A A

 







^{ } ⁽¹^{ }^s ^{F S}^{( )} ). (0.1.7)



Để củng cố định lí vừa được phát biểu và chứng minh, chúng ta cho học sinh thực hiện các hoạt động nhận dạng và thể hiện định lí bằng cách xem xét để tìm kiếm lời giải cho một số bài toán tổ hợp nâng cao sau:

Bài toán 1. Cho tập hợp S gồm 7 phần tử và A A₁, ₂,...,A₇ là các tập con khác nhau của S thoả mãn A_i 3 ^{ }ⁱ



^1,2,...,7



, với hai phần tử bất kỳ

,

a bS tồn tại duy nhất ^j^



^{1, 2,...,7}



^{sao cho}a b^, Aj. Chứng minh rằng với mọi ^{i j}^, ^



^{1, 2,...,7}



^màⁱ^ ^j^thì ^A_i ^ ^A_j ^¹^.

Bài giải

Giả sử S 



x x1, 2,...,x7



và F S( )



A A1, 2,...,A7



. Xét bảng 7 7 ô vuông (gồm 7 hàng, 7 cột) sao cho tại mỗi ô vuông thứ ( , )i j (hàng thứ i, cột thứ j) ta đặt một số a_{i j}_, xác định bởi:

,

1 0

i j

i j

i j

x A

a x A

 

 

 



a1,1 a_1,2 ... a_1,6 a_1,7

a2,1 a_2,2 ... a_2,6 a_2,7

. . .

a6,1 a_6,2 ... a_6,6 a_6,7

a7,1 a_7,2 a_7,6 a_7,7

Khi đó, với mỗi ⁱ^



^{1, 2,...,7}



^đặt:

(6)

6

, 1

i i j

j

r a





và mỗi ^j^



^{1, 2,...,7}



^đặt:

7 , 1

j i j

i

l a





^.

Ta có r_i là số các tập hợp thuộc F S( ) chứa x_i, l_j là số các phần tử thuộc Aj. Từ giả thiết Ai ³  i



^{1, 2,...,7}



nên:

7 7 7

1 1 1

i ij

i i j

r a

  







7 7

1 1

ij

j i

a

 





7

1 j 21

j

A





 . (1.1)

Mặt khác, do mỗi bộ gồm 2 phần tử

1, 2

j j

x x của S luôn tồn tại duy nhất tập hợp A_iF S( ) để

1, 2

j j i

x x A nên

i j 1

A  A  ^^{i j}^, ^



^1,2,...,7



^:ⁱ^ ^j^,

suy ra

2

7 21

i j

i j

A A C



 



^ ^.

Kết hợp với đẳng thức:

7 2 1

i j rk

i j k

A A C

 



^ 



7 2

1 2

k k

k

r r





 ^. Ta có

7 2

1

2 21

k k

k

r r



 



. (1.2) Theo bất đẳng thức Cauchy’s

7 2 7 7

2

1 1 1

1

2 2

k k

k k k

r r

  

  

   

 

  

(7)

7

7 2

7 1

1

2 7

k k

r

 r



  

  

 

 

 

 

 



hay

7 2 7 7

1 1 1

1 7

2 2.7

k k

k k k

r r

  

   

    

  

  

^.

Kết hợp với (1.1) ta có:

7 2

1

2 21

k k

k

r r



 



. (1.3) Từ (1.2) và (1.3) ta suy ra được:

7 2

1

2 21

k k

k

r r



 



_i _j 21

i j

A A







^ 

 A_i  A_j 1 (1 i j7).



Bài toán 2. Cho S 



A A1, 2,...,A11



là họ các tập hợp thoả mãn đồng thời hai điều kiện:

(i) A_i  A_j     1 i j11; (ii) A_j 5 1  i 11.

Đặt A A₁ A₂ ... A₁₁, với mỗi xA ký hiệu d x( ) là số các tập hợp thuộc S chứa x và ^d ^^max



^{d x}^{( ) :}^x^^A



. Tìm giá trị nhỏ nhất của d.

(Romania MO 1994) Bài giải

Giả sử A



x x1, 2,...,x_m



, xét bảng m11 ô vuông (gồm m hàng, 11 cột) sao cho tại mỗi ô vuông thứ ( , )i j (hàng thứ i, cột thứ j) ta đặt một số

,

ai j xác định bởi:

,

1 0

i j

i j

i j

x A

a x A

 

 

 



. Khi đó:

(8)

8

, 1

( )_i _{i j}

j

d x a





^,^{ }ⁱ



^1,2,...,^m



^;

, 1 m

j i j

i

A a





^, j



1, 2,...,11



và

11 ,

1 1 1

( )

m m

i i j

i i j

d x a

  







11 ,

1 1

m i j

j i

a

 





11

1 j j

A





hay

1

( ) 55

m i i

d x





 . (2.1) Ta có:

²₍ ₎

1

k

m

i j d x

i j k

A A C

 



^ 



 

1

1 ( ) ( ) 1

2

m

k k

k

d x d x







1

1( 1) ( )

2

m k k

d d x



 



. (2.2) Từ (2.1) và (2.2) suy ra:

⁵⁵⁽ ¹⁾

i j 2

i j

A A d



 



^ . (2.3) Mặt khác, từ giả thiết A_i A_j   nên với mỗi cặp



^{A A}ⁱ^, ^j



luôn tồn tại

k i j

x A A hay cặp



^{A A}ⁱ^, ^j



được tính ít nhất một lần trong biểu thức

i j

i j

A A





^ , do đó ta có:

2

11 55

i j

i j

A A C



 



^ . (2.4)

(9)

9

Từ (2.3) và (2.4) ta suy ra d3. Nếu d 3 thì với mỗi x_iS ta có

( )_i 3

d x d  . Ta chứng minh không tồn tại x_jS để d x( _j)2. Thật vậy, giả sử tồn tại x_jS để d x( _j) 2, khi đó

 

1

55 1 ( ) ( ) 1

2

m

i i

i

d x d x









¹ ^{( )}



^{( ) 1}



¹ ^{( )}



^{( ) 1}



2 _{i j} d xⁱ d xⁱ 2d x^j d x^j







  

1 ^{( )}



^{( ) 1}



2 ( ) 2

j j

i i j

d x d x

n d x



 







Mà

   

1

( ) ( ) 1 ( ) ( )

1 1

( ) ( )

2 2 2 2

j j m j j

i i

i j i

d x d x d x d x d

n n

d x d x

 

 

  

 

(3 1)55 2(2 3)

2 2 54

 

   .

Điều này dẫn đến vô lý hay ta có d x( )_i 3  x_i S, suy ra 3m55(không thoả mãn). Vậy d 4 và ta chỉ ra có 11 tập hợp thoả mãn yêu cầu bài toán là:

 

1 1, 2,3, 4,5

A  , A2 



1, 2,3, 4,5



, A3 



1,6,7,8,9



,

A4 



1,10,11,12,13



, A5 



2,6,9,10,14



,A6 



3,7,11,14,15



,

 

7 4,8,9,12,15

A  ,A8 



3,6,8,10,13



,A9 



4,5,6,11,14



,

 

10 2,7,11,12,13

A  , A11 



5,9,13,14,15



.



Bài toán 3 Cho A A₁, ₂,...,A_k là các tập con của S 



1, 2,...,10



sao cho

i 5

A  ,i1, 2,...,k và A_i A_j 2,1 i j k. Tìm giá trị lớn nhất của k?.

Bài giải Giả sử F S( )



A A1, 2,...,A_k



, xét bảng 10k ô vuông (gồm 10 hàng, k cột) sao cho tại mỗi ô vuông thứ ( , )i j (hàng thứ i, cột thứ j) ta đặt một số a_{i j}_, xác định bởi:

,

1 0

i j

i j

i j

x A

a x A

 

 

 



. Khi đó:

, 1

( )

k i j j

d i a





^, i



1, 2,...,10



;

(10)

10

, 1

j i j

i

A a





^,^{ }^j



^{1, 2,...,}^k



và

10 10

,

1 1 1

( )

k i j

i i j

d i a

  







10 ,

1 1

k

i j

j i

a

 





1

5

k j j

A k





 . (3.1) Ta có

10 2

( ) 1

i j d j

i j j

A A C

 



^ 



 

1

1 ( ) ( ) 1

2

m

j

d j d j





 . (3.2) Mặt khác, từ giả thiết bài toán ta có

_i _j 2 _k² ( 1)

i j

A A C k k



  



^ . (3.3)

Từ (3.2) và (3.3) suy ra:

 

1

1 ( ) ( ) 1 ( 1)

2

m

j

d j d j k k



  



²

1 1

1 ( ) ( ) ( 1)

2

m m

j j

d j d j k k

 

 

    



 



2

1 1

( ) ( ) ( 1)

2 10

m m

j j

d j d j k k

 

   

 

      

 

1 1

1 ( ) ( ) 10 ( 1)

20

m m

j j

d j d j k k

 

  

     









 ^.

Kết hợp với (3.1) ta có:

1 .5 .(5 10) ( 1) 20 k k k k   k 6.

Ta chứng minh k6 là giá trị lớn nhất bằng cách chỉ ra 6 tập con của S thoả mãn điều kiện bài toán là:

(11)

11

 

1 1, 2,3, 4,5

A  , A2 



1,2,6,7,8



, A3 



1,3,6,9,10



,

 

4 2, 4,7,9,10

A  , A5 



3,5,7,8,10



, A6 



4,5,6,8,9



.



Bên cạnh những bài toán được cho trực tiếp dưới dạng tập hợp như trên, còn có những bài toán được cho dưới dạng gián tiếp thông qua một hình thức, ngôn ngữ khác. Để giải quyết được nó, trước hết người giải toán phải thực hiện việc chuyển đổi từ ngôn ngữ bài toán về ngôn ngữ tập hợp.

Điều này đòi hỏi phải nắm được bản chất của bài toán. Chúng ta tiếp tục xét một số bài toán sau:

Bài toán 4. Trong một kỳ thi có 11 thí sinh tham gia giải 9 bài toán. Với hai thí sinh bất kỳ, có nhiều nhất một bài toán cùng giải được. Tìm giá trị lớn nhất của k để mỗi bài toán đều có ít nhất k thí sinh giải được.

Bài giải. Với bài toán này, trước hết phải phải thực hiện việc chuyển ngôn ngữ bài toán về ngôn ngữ tập hợp bằng cách giả sử tập hợp các bài toán là



1, 2,..., 9



S  x x x và A_i (1 i 11) là tập hợp các bài toán giải bởi thí sinh thứ i, theo bài ra ta có:

A_i  A_j 1 (1 i j9).

Trên cơ sở các tập hợp vừa xây dựng, ta có thể tiến hành giải bài toán như sau. Gọi d x( )_i là số tập A_j chứa x_i, ta có:

9 11

1 1

( )_i _j

i j

d x A

 







và

11 11

2

1 1

i j ( )

i j x S

A A d x

  



^ 



^,

suy ra

11

2

1 1

2 ( )

i i j

i i j m x S

A A A d x

    

 

 

^



11 2

1 1 11

( ) _i 2 _i _j

x S i i j

d x A A A

    













^

²

1 11

( ) ( ) 2 _i _j

x S x S i j

d x d x A A

    













^

(12)

12



²



1 11

( ) ( ) 2 _i _j

x S i j

d x d x A A

   





 



^

2C₁₁² 110 ^⁹



^k² ^^k



^¹¹⁰

 k 4.

Với k4, giả sử tồn tại x_iSđể d x( )_i 5, ta có:

 

9 2 1

( )_j ( )_j 8.12 20 116 110

j

d x d x



    



^{(vô lý ).}

Do đó

1 2 9

( ) ( ) ... ( ) 4

d x d x  d x 

1 11

i j 54

i j

A A

  





^ 

₁₁²

1 11

i j 1

i j

A A C

  





^   ^,

suy ra tồn tại duy nhất cặp ( , )i j để A_i A_j 0. Không mất tính tổng quát ta giả sử cặp đó là (1, 2), suy ra A₁A₂   và A_i  A_j 1, ( , )i j (1; 2) và i j. Nếu tồn tại i



3, 4,...,11



để A_i 3, từ giả thiết A_i  A_j 1,



1, 2,...,11 \

  

j i

  nên tồn tại một phần tử của A_i thuộc ít nhất

10 1 4

3

 

  

  tập A_j( ji), suy ra tồn tại một phần tử thuộc ít nhất 5 tập Ak (vô lý). Như vậy, ta có A_i 4, ^{ }ⁱ



^3,4,...,11



^{, suy ra}

11

1 2

1

36 36

i i

A A A



   



^,

điều này không thể xảy ra. Do đó k4 không thoả mãn.

Với k 3, ta chỉ ra trường hợp sau thoả mãn bằng cách lập bảng các ô vuông 11 9 (11 hàng, 9 cột) trong đó nếu thí sinh A_i giải được bài x_j thì ở ô vuông ( , )i j ta điền số 1, ngược lại ta điền số 0.

(13)

13

x1 x₂ x₃ x₄ x₅ x₆ x₇ x₈ x₉ A1 1 0 0 1 0 0 1 0 0 A2 1 0 0 0 1 0 0 0 1 A3 0 1 1 0 0 1 0 1 0 A4 0 1 0 1 1 0 0 0 0 A5 0 0 0 1 0 0 0 1 1 A6 0 0 1 0 0 0 1 0 1 A7 0 0 0 0 1 1 0 0 0 A8 1 1 0 0 0 0 0 0 0 A9 0 0 1 0 0 0 0 0 0 A10 0 0 0 0 0 1 1 0 0 A11 0 0 0 0 0 0 0 1 0



Bài toán 5. Trong một kỳ thi Toán học có 8 thí sinh tham gia và có n câu hỏi (mỗi câu hỏi có 2 cách chọn là đúng hoặc sai). Tìm giá trị lớn nhất của n biết rằng với mỗi cặp hai câu hỏi bất kỳ ( , )A B (ở đây cặp ( , )A B là một cặp có thứ tự) có đúng hai thí sinh trả lời là (đúng, đúng), hai thí sinh trả lời là (đúng, sai), hai thí sinh trả lời là (sai, đúng) và hai thí sinh trả lời là (sai, sai).

Bài giải Giả sử 8 thí sinh tham dự kỳ thi là p p₁, ₂,...,p₈ và n câu hỏi là

1, 2,..., _n

A A A . Xét bảng 8n ô vuông (gồm 8 hàng, n cột) sao cho tại mỗi ô vuông thứ ( , )i j (hàng thứ i, cột thứ j) ta đặt một số a_{i j}_, với a_{i j}_, 1 nếu với câu hỏi A_j, thí sinh p_i trả lời đúng và a_{i j}_, 0 nếu với câu hỏi A_j, thí sinh

pi trả lời sai. Khi đó:

, 1

( )

n

i i j

j

d p a





^,^{ }ⁱ



^{1, 2,...,8}



^;

8 , 1

j i j 4

i

A a





 ^,^{ }^j



^{1, 2,...,}ⁿ



và

8 8

,

1 1 1

( )

n

i i j

i i j

d p a

  







(14)

14

_,

1 1

i j

j i

a

 





1 n

j j

A





4n . (5.1)

Từ giả thiết ta thấy, nếu trong một cột tất cả số 1 đổi thành số 0 và tất cả số 0 đổi thành số 1 thì tính chất trong bảng vẫn không đổi. Do đó, không mất tính tổng quát ta giả sử tất cả các số trong ô vuông của hàng đầu tiên đều bằng 1, suy ra

(1) d  n và

2

( ) 3

n

i

d i n





 ^.

Số các cặp số (1,1) trong mỗi hàng của bảng là:

8

2 2

( ) 1

d i 2 n

i

C C







n n( 1). Mà

8 8

2 2 2

( ) (1) ( )

1 2

d i d d i

i i

C C C

 

 

 

8 8

2 2

1 ( ) ( )

n 2

i i

C d i d i

 

 

    



 



8 2 8

2 2

( 1) 1 1

( ) ( )

2 2 7 _i _i

n n d i d i

 

 

  

   



 



 Suy ra

8 2 8

2 2

( 1) 1 1

( ) ( ) ( 1)

2 2 7 _i _i

n n d i d i n n

 

 

  

  



 



  ⁽ ¹⁾ ¹



^{(3 )}² ^7.3



⁽ ¹⁾

2 14

n n n n n n

    

 n 7.

Ta chứng minh với n7 thoả mãn yêu cầu bài toán thông qua bảng sau:

(15)

15

A1 A₂ A₃ A₄ A₅ A₆ A₇ p1 1 1 1 1 1 1 1

p2 1 0 0 0 0 1 1

p3 1 0 0 1 1 0 0

p4 1 1 1 0 0 0 0

p5 0 1 0 1 0 1 0

p6 0 1 0 0 1 0 1

p7 0 0 1 1 0 0 1

p8 0 0 1 0 1 1 0



Bài toán 6 (IMO 1998) Trong một cuộc thi có m thí sinh và n giám khảo (m n, ^*;n3, n lẻ). Giả sử k^* là số sao cho hai giám khảo bất kỳ cho không quá k thí sinh đánh giá giống nhau (giám khảo đánh giá thí sinh đạt hoặc không đạt). Chứng minh rằng ¹

2 k n

m n

  . Bài giải

Xét bảng ô vuông m n (m hàng, n cột) trong đó các hàng biểu diễn thí sinh và các cột biểu diễn cho các giám khảo. Mỗi ô sẽ nhận giá trị 1 nếu giám khảo đánh giá thí sinh đạt và nhận giá trị 0 nếu giám khảo đánh giá thí sinh trượt. Gọi S là tập hợp các cặp số 0 hoặc 1 ở cùng một hàng. Do giả thiết hai giám khảo đánh giá giống nhau ở nhiều nhất k thí sinh nên ở hai cột bất kỳ thì có không quá k cặp số 0 hoặc 1 thuộc S, do đó ta có:

2 ( 1)

n 2

S kC kn n

  . (6.1) Mặt khác, xét một hàng nào đó trong bảng ô vuông, giả sử có p số 0 và q số 1 thì số cặp số 0 hoặc số 1 trong hàng đó là

2 2 ( 1) ( 1)

p q 2

p p q q

C C   

  .

Từ pqn và n lẻ nên ta có:

( 1) ( 1) ( 1)2

2 2

p p q q pq



^²



^p² ^^q² ^ ^p^^q

 

^ ^p² ^^q²^{ }^{1 2}^pq^²^p^²^q



 p² q² 2pq1

(16)

16

(pq) 1 (bất đẳng thức này đúng do p q, khác tính chẵn lẻ).

2

2 2 ( 1)

p q 4

C C n

   .

Do có m hàng nên ta có:

( 1)2

4 S m n

 . (6.2) Kết hợp (6.1) và (6.2) ta có:

( 1) ( 1)2

2 4

kn n m n



¹

2 k n

m n

   .



Bên cạnh việc rèn luyện tư duy sáng tạo cho học sinh thông qua ứng dụng phương pháp đếm bằng hai cách bằng bảng các ô vuông để giải các bài toán sơ cấp về Tổ hợp nâng cao, ta có thể rèn luyện tư duy sáng tạo cho các em bằng cách ứng dụng phương pháp đếm này để chứng minh lại, qua đó tiếp cận một số kết quả khác trong lý thuyết Tổ hợp và Đồ thị.

Định lý Corrádi. Cho A A₁, ₂,...,A_n là các tập hợp gồm r phần tử và

1 n

i i

X A





^{. Nếu} ^Aⁱ ^^A^j ^^k ^^{i j}^, ^



^1,2,...,^{n i}



^: ^ ^j^thì

2

( 1) X nr

r n k

   . Chứng minh. Với mỗi ⁱ^



^1,2,...,ⁿ



^{ta có}

1

( )

i

n

i j

x A j

d x A A

 







^

_i _i _j

j i

A A A



 



^

( ) ( 1)

x Ai

d x r n k







  

 

1

( ) ( 1)

i

n

i x A

d x n r n k

 





   . (7.1) Mặt khác, từ đẳng thức

(17)

17

 

²

1

( ) ( )

i

n

i x A x X

d x d x

  









^{( )}



² ¹₂

x X x X

X d x

X

 

 

 









( ) 2

x Xd x

X X

  

  

 



Mà

 

²

2

( ) _i _i

x Xd x A

X X

  

  

 

 

 

 

²

2

nr X

 . Suy ra

 

²

1

( )

i

n

i x A

d x nr

  X



 . (7.2) Từ (7.1) và (7.2) ta có

   

2

( 1)

nr n r n k

X   



2

( 1) X nr

r n k

   .



Định lý Erdos-Ko-Rado. Cho X là tập hợp gồm n phần tử và F X là họ ( ) các tập con gồm k phần tử của X ,

2

kn sao cho với mọi tập hợp

, ( )

A B F X thì AB , khi đó: F X( ) C_n^k_^₁¹. Chứng minh

Không mất tính tổng quát ta giả sử ^X ^



^0,1,...,ⁿ^¹



và với mỗi sX , đặt :



^, ^1,..., ¹



Bs  s s s k  ( trong đó các số modn).

(18)

18

Trong số các tập B_s, có không quá k tập nằm trong ( )F X . Thật vậy, giả sử

0 ( )

B F X , khi đó có đúng 2k2 tập khác là B_i



^⁽^k^¹⁾^{  }ⁱ ^k ¹



^có

giao khác rỗng với B₀(ở đâyB__j B_{n j}_ ) . Tuy nhiên các cặp B_i và B_{i k}_ lại rời nhau nên ngoài B₀ ra, F X( ) chỉ chứa nhiều nhất là k1 tập. Với mỗi hoán vị

   

: 0,1,...,n 1 0,1,...,n 1

   

ta đặt

 

(B_s) ( ), (s s 1),..., (s k 1) (mod )n

        .

Theo lý luận trên ta thấy F X( ) chứa nhiều nhất k tập dạng (B_s)

 ^s^



^0,1,...,ⁿ^¹



^{. Đặt}L



^{( , ) : (} s  Bs⁾F X^{( )}



, do có !n hoán vị  nên ta xét bảng ( !)n n ô vuông (gồm !n hàng, n cột) sao cho tại mỗi ô vuông thứ ( , )i j (hàng thứ i, cột thứ j) ta đặt một số a_{i j}_, xác định bởi

,

1 ( ) ( )

0 ( ) ( )

s i j

s

B F X

a B F X



 

  

.

a1,0 a_1,1 ... a_1,_n_₂ a_1,_n_₁ a2,0 a_2,1 ... a_2,_n_₂ a_2,_n_₁ .

. .

. . .

! 1,0

an_ a_n_{! 1,1}_ ... a_n_{! 1,}_ _n_₂ a_n_{! 1,}_ _n_₁

!,0

an a_n_!,1 a_{n n}_!, _₂ a_{n n}_!, _₁

Từ bảng ta đếm số phần tử của L theo hai cách:

 Đếm theo cột: Với mỗi s và phần tử A F X ( ) cố định, số hoán vị

 mà

(B_s) A

 

là !.(k nk)!, do đó ta có

(19)

19

. !.( )!. ( ) L n k nk F X .

 Đếm theo hàng: Từ mỗi hàng của bảng có không quá k số 1 nên

!.

L n k. Suy ra

. !.( )!. ( ) !.

n k nk F X n k

!.

( ) . !.( )!

F X n k

n k n k

 

  F X( ) C_n^k_^₁¹.



Dưới đây là một số bài tập tổ hợp luyện tập về ứng dụng phương pháp đếm bằng hai cách thông qua bảng các ô vuông.

Bài tập 1. Cho n^*và ( ,a a₁ ₂,...,a_n) là hoán vị của (1,2,..., )n . Với mỗi 1 k n đặt Fk 



a ai ^| i a ik^, k



và Gk 



a ai^| i a ik^, k



. Chứng minh rằng:

1 1

n n

k k

F G

 







^.

Bài tập 2. Cho tập S là tập hữu hạn và F S( )



A A1, 2,...,A_n



là họ các tập con của S sao cho mỗi phần tử của S đều thuộc ít nhất t tập con của ( )F S . Chứng minh rằng:

1 n

i i

A t S





 ^.

Bài tập 3. Cho ,n k là các số nguyên dương thỏa mãn nk²  k 1 và



A A1, 2,...,A_n



là họ các tập hợp thỏa mãn đồng thời hai điều kiện:

(i) Ai k  i



^1,2,...,n



;

(ii) Ai Aj ²k ¹ i j^, 



^1,2,...,n i



^,  j. Tính số phần tử của tập hợp

1 n

i i

A





^?.

Bài tập 4. Cho tập hợp S gồm n phần tử (n6) và A A₁, ₂,...,A_m là các tập con phân biệt của S thỏa mãn Ai   ⁵ i



^1,2,...,m



. Chứng minh rằng nếu

(20)

20

( 1)( 2)( 3)(4 15) 600

n n n n n  m thì tồn tại i i1, ,...,2 i6



1,2,...,m



đôi một khác nhau sao cho

6

1 ik

k

A





chứa đúng 6 phần tử.

Bài tập 5. Cho S là tập hợp hữu hạn và F S( ) là họ các tập con khác rỗng của S thỏa mãn ,A BF S( ) thì ABF S( ). Có tồn tại hay không phần tử

xS sao cho:

( ) ( ) 2 d x  F S .

Bài tập 6. Cho S là tập hợp gồm n phần tử và A A₁, ₂,...,A_k là các tập con của S có cỡ trung bình nhỏ nhất bằng n

r . Chứng minh rằng nếu k 2r² thì tồn tại ^{i j}^, ^



^{1, 2,...,}^k



^, ^j^ⁱ sao cho ₂

i j 2

A A n

 r

 .(Ở đây, cỡ trung bình của các tập A A₁, ₂,...,A_k là

1

1 ^k

i i

k



 A ^).

Bài tập 7. Cho tập hợp S gồm n phần tử và A A₁, ₂,...,A_n là các tập con của S thoả mãn điều kiện | A_i | 2 ^{ }ⁱ



^{1, 2,...,}ⁿ



. Giả sử với mỗi tập con

:| | 2

BS B  , tồn tại duy nhất chỉ số ⁱ^



^{1, 2,...,}ⁿ



^đểB Ai. Chứng minh rằng A_i A_j 1,  i j.

Bài tập 8. Cho tập hợp S gồm n phần tử và A A