Ứng dụng phương pháp Song ánh trong giải toán Tổ hợp

(1)

1

Phương pháp song ánh A. Mở đầu

Tổ hợp là một trong những nội dung bắt buộc trong các đề thi HSG Quốc gia và Quốc Tế. Nhưng đây là một vấn đề khó và ít có tài liệu viết đầy đủ. Do vậy trong chuyên đề này tôi xin đưa ra thảo luận và trao đổi với các thầy cô một chuyên đề tổ hợp đó là phương pháp song ánh.

Nội dung cơ bản các chuyên đề là nhắc lại khái niệm về song ánh, cách vận dụng song ánh trong một số dạng toán thi học sinh giỏi thường gặp, từ đó giúp cho các học sinh có được những kiến thức cơ bản về phương pháp song ánh trong các bài toán tổ hợp

B. Nội dung

I. Khái niệm về song ánh 1. Định nghĩa

Cho 2 tập hợp X và Y (khác rỗng). Một ánh xạ f từ X lên Y là một quy tắc cho tương ứng mỗi phần tử x X∈ với 1 và chỉ 1 phần tử y Y∈

Ký hiệu

: f

( )

X Y

x y f x

→

 =

Tập X gọi là tập nguồn, tập Y là tập đích

Ánh xạ f được gọi là đơn ánh nếu mọi x x₁, ₂∈X, f x( )1 = f x( )2 x1=x2 Khi đó ta có X ≤ Y

Ánh xạ f được gọi là toàn ánh nếu ∀ ∈ ∃ ∈y Y x X, sao cho ( ) yf x = Ánh xạ f được gọi là song ánh nếu nó vừa là đơn ánh, vừa là toàn ánh II. Phương pháp song ánh trong các bài toán tổ hợp

1. Phương pháp song ánh để đếm số phần tử của một tập hợp và chứng minh hai tập có cùng số phần tử

Nội dung cơ bản: Để đếm số phần tử của một tập nhất định, ta có thể thay nó bởi một tập hợp khác có cùng số phần tử và số phần tử của tập hợp mới có cách đếm dễ

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

(2)

2

Cho m n, ∈^*, hỏi phương trình x₁+ + + =x₂ ... x_n m (*) có bao nhiêu nghiệm nguyên không âm.

Hướng dẫn: Kí hiệu T là tập các nghiệm của (*) trên tập số tự nhiên.

Gọi A là tập tấ cả các dãy nhị phân gồm (m n+ −1) chữ số trong đó có (n−1) chữ số 0 và m chữ số 1

Xét tương ứng:

  

1 2

1

1 1 1

:

( ,..., ) 1...101...10...01...1

n

x so x so x so

F T A

x x

→



Dễ thấy F là một song ánh. Vậy số nghiệm của (*) = số dãy nhị phân của A. Số dãy nhị phân của A bằng số cách xếp n−1 chữ số 0 vào trong (m n+ −1)chữ số của các dãy nhị phân (trong A) và bằng C_{m n}ⁿ⁻_{+ −}¹ ₁ . Vậy số nghiệm của (*) là C_{m n}ⁿ⁻_{+ −}¹ ₁

Bài 2 [VMO 2012_ câu 5]:

Cho một nhóm có 5 cô gái, kí hiệu là G G₁, ₂,...,G₅ và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đó chỉ ngồi vào các chiếc ghế đó sao cho các điều kiện sao cho đồng thời thỏa mãn:

1. mỗi ghế có duy nhất 1 người ngồi

2. Thứ tự ngồi của các cô gái, xét từ trái qua phải là G G G G G₁, , , ,₂ ₃ ₄ ₅ 3. Giữa G₁ và G₂ có ít nhất 3 chàng trai

4. Giữa G₄ và G₅ có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.

Hỏi có tất cả bao nhiêu cách sắp xếp như vậy

(Hai cách xếp được coi là khác nhau nếu tồn tại 1 chiếc ghế mà người ngồi ở chiếc ghế đó trong 2 cách xếp là khác nhau)

Hướng dẫn:

Bổ đề (bài toán chia kẹo của Euler): cho k n, là các số nguyên dương.

Số nghiệm nguyên không âm của pt x₁+ + + =x₂ ... x_k n

Áp dụng vào bài toán: đánh số thứ tự các ghế từ trái sang phải là 1,2,…,17. Gọi x₁ là số chàng trai được xếp bên trái G₁, x₂ là số chàng trai ở giữa G₁ và G₂; x₃ là số chàng trai ở giữa G₂ và G₃; x₄ là số chàng trai ở giữa G3 và G₄; x₅ là số chàng trai ở giữa G₄ và G₅; x₆ là số chàng trai ngồi bên phải G₅. Khi đó bộ số ( , ,..., )x x₁ ₂ x₅ hoàn toàn xác định vị trí các cô gái và ta có:

1. x₁+ + + =x₂ ... x₆ 12 2. 3≤x₂

(3)

3 3. 1≤ ≤x₅ 4

Đổi biến y₂ = −x₂ 3 và y₅ = −x₅ 1 ta được x₁+ y₂ + + + + =x₃ x₄ y₅ x₆ 8 với các Nn không âm và có thêm điều kiện y₅≤3.

Tiếp theo, áp dụng bài toán chia kẹo ở dạng

1 2 3 4 6 8 5

x + + + + = −y x x x y

Ta được số cách phân ghế cho các cô gái là

4 4 4 4

12 11 10 9 1161

C +C +C +C =

Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp t/m ycbt là 12!.1161

Bài 3 [VMO 2014_ câu 3]:

Cho đa giác đều có 103 cạnh. Tô màu đỏ cho 79 đỉnh của đa giác và tô màu xanh cho các đỉnh còn lại. Gọi A là số cặp đỉnh đỏ kề nhau và B là số cặp đỉnh xanh kề nhau.

a. Tìm tất cả các giá trị có thể nhận được của cặp ( , )A B

b. xác định số cách tô màu các đỉnh của đa giác để B=14. Biết rằng, hai cách tô màu được xem là như nhau nếu chúng có thể nhận được từ nhau thông qua 1 phép quay quanh tâm đường tròn ngoại tiếp đa giác.

Hướng dẫn:

a. Số đỉnh màu xanh là 24 đỉnh (103-79). Nếu tất cả các đỉnh đỏ chia thành một cụm thì A=78. Nếu bị cắt thành 2 cụm thì A=77. Và cứ thế tiếp tục, tức là nếu có k cụm (mỗi cụm là các đỉnh cùng màu đỏ đứng sát nhau) thì

79

A= −k. Nếu có k cụm đỏ thì cũng có k cụm xanh nên có B=24−k. Các giá trị có thể của k là từ 1 đến 24, nên có 24 khả năng tất cả

b. Để có B=14 thì k=10 (phải chia quân xanh thành 10 cụm, quân đỏ thành 10 cụm). Đếm số cách chia như thế nào ?

Gọi X là số cụm các điểm đỏ liền nhau, thì B=24−X . Do vậy B=14 thì X =10. Áp dụng công thức chia kẹo của pt chia kẹo, ta suy ra được số cách chia 24 điểm xanh vào 10 cụm là C₂₃⁹ . Tiếp theo, ta sẽ xem xét việc xếp các điểm xanh- đỏ như là vệc có sẵn 79 điểm đỏ ở trên đường tròn, và ta bỏ đi 10 cụm điểm xanh và các khoảng trống giữa 2 điểm đỏ liên tiếp, mỗi khoảng có tối đa 1 cụm. Như vậy thì số cách chọn ra 10 khoảng trống trong 79 khoảng là C₇₉¹⁰. Sự trùng lặp theo phép quay là ở chỗ ta chọn 10 vị trí trong 79 vị trí theo đường tròn. Nhờ có (79,10)=1 mà ta không phải lo về “các cấu hình lộn xộn”, mỗi cách tô bị lặp đúng 79 lần, do vậy đáp số là

10 9 79 23

79 C C

Định lý 4.1:

(4)

4

Cho A và B là 2 tập hợp hữu hạn, và f là 1 ánh xạ đơn ánh từ A vào B.

Khi đó số phần tử của B ít nhất là bằng số phần tử của A. Và nếu f là song ánh thì A và B có cùng số phần tử

Bài 4: Với mỗi đỉnh của đa giác đều 9 đỉnh (cửu giác) được tô bởi màu đỏ hoặc xanh da trời. Chứng minh rằng tồn tại 2 tam giác đơn sắc đồng dạng , trong đó tam giác đơn sắc là tam giác có tất cả các đỉnh là cùng 1 màu

Lg: Ta gọi đơn giác đỏ (xanh) nếu tất các đỉnh của tam giác là đỏ hoặc xanh.

Vì đa giác có 9 đỉnh, mỗi đỉnh chỉ tô 2 màu xanh hoặc đỏ nên có ít nhất 5 đỉnh có dùng 1 màu. Không mất tính tổng quát, giả sử đó là màu đỏ. Suy ra có it nhất C₅² =10 đơn giác đỏ. Giờ ta chứng minh có 2 tam giác đỏ đồng dạng.

Hình 1

Đặt A A A₁, ,₂ ₉ là các đỉnh của đa giác (Hình 1) và ω là đường tròn ngoại tiếp đa giác. 9 đỉnh đa giác chia đường tròn này thành 9 cung bằng nhau. Gọi mỗi cung trong 9 cung này là 1 mảnh. Gọi A A A_i _j _k là tam giác thỏa mãn

i j j k k i

A A ≤ A A ≤ A A^.Định nghĩa a_{i j}_, là số mảnh của cung A A_i _j không chứa điểm A_k. Ta định nghĩa tương tự với a_{j k}_, và a_{k i}_, . Khi đó ΔA A A_i _j _k ^{được xác} định bởi bộ ba

(

^{a a}^{i j}^, ^, ^{j k}^, ^,^a^{k i}^,

)

. Do 1 tam giác có 3 đỉnh, nên ta dễ thấy

, , ,

1≤a_{i j} ≤a_{j k} ≤a_{k i} ≤7 (trường hợp góc lớn nhất là 3 đỉnh nằm kề nhau trên đường tròn). Do A A_i _j +A A_j _k + A A_k _i =180⁰, do đó a_{i j}_, +a_{j k}_, +a_{k i}_, =9^{. Ví dụ} với tam giác ΔA A A₂ ₄ ₈ ta xác định được bộ ba tương ứng là (2,3,4). Dễ thấy

(5)

5

các tam giác đồng dạng cho cùng 1 bộ ba, trong khi 2 tam giác không đồng dạng có các bộ ba khác nhau. Từ đó ta xây dựng song ánh A →B như sau:

A: tập các tam giác đồng dạng

B: tập các số tự nhiên a, b, c thỏa mãn 1≤ ≤ ≤ ≤a b c 7 và a+b+c=9.

Ta có thể liệt kê ra các phần tử của B là (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4), (3,3,3) có tất cả 7 phần tử.

Suy ra A cũng có 7 phần tử hay có tất cả 7 dạng tam giác khác nhau.

Trong khi đó ta có 10 tam giác đơn sắc, nên tồn tại ít nhất 2 tam giác đơn sắc đồng dạng.

Bài 5: Cho n nguyên dương. Hỏi có bao nhiêu các biểu diễn n thành tổng của ít nhất 2 số nguyên dương.

(Ví dụ có 3 cách biểu diễn số 3 thành tổng của các số nguyên dương:

3=1+1+1=1+2=2+1) Lời giải:

Ta viết n dưới dạng sau:

(1_1_..._1) gồm n số 1. Xét n-1 khoảng trống trong đó là a a a_{1 2}... _n₋₁ , khi đó các khoảng trống sẽ có 2 trạng thái là 0 hoặc 1. Nếu trạng thái là 0, thì ta sẽ thay khoảng trống bởi dấu “+”, nếu trạng thái là 1 thì thay bởi “)+(“. Ví dụ như 4=(1_1_1_1)=( , , )a a a₁ ₂ ₃ . Khi đó nếu ( , , ) (0,0,1)a a a₁ ₂ ₃ = thì 4=(1+1+1)+(1)=3+1 là một cách biểu diễn.

Ta có tất cả 2^n-1 cách biểu diễn cho dãy nhị phân (n-1) bit a a a_{1 2}... _n₋₁ và mỗi dãy nhị phân cho một cách biểu diễn duy nhất của n.

Trong dãy nhị phân này, chỉ có trường hợp duy nhất là dãy 00…0 là không biểu diễn dưới dạng tổng của ít nhất 2 số. Do đó có 2^n-1-1 cách biểu diễn n dưới dạng tổng của ít nhất 2 số nguyên dương

Bài 6 [AHSME 1992]:

Cho 10 điểm đặt trên phần dương trục x(X⁺), 5 điểm đặt trên phần dương trục y (Y⁺). Khi đó ta có tất cả 50 đoạn thẳng nối giữa 10 điểm trên X⁺ với 5 điểm trên trục Y⁺. Khi đó có tối đa bao nhiêu giao điểm của 50 đoạn thẳng nằm trong góc phần tư thứ nhất? (Hình 2)

(6)

6 Hình 2 Lời giải:

Ta có, cứ 2 điểm trên X⁺ và 2 điểm trên Y⁺ thì tạo thành 1 tứ giác và khi đó chỉ xác định được duy nhất 1 giao điểm. Khi đó số giao điểm lớn nhất có thể tạo được là C C₁₀² ₅² =45.10 450= . Dấu bằng xảy ra ⇔ không có 3 đường nào cùng cắt nhau tại một điểm trong góc phần tư thứ nhất

Bài 7 [China 1991, by Weichao Wu]:

Cho n là số tự nhiên với n≥2 , và đặt dãy ^S ⁼

(

^1,2,...,ⁿ

)

. Một dãy con của S được gọi là dãy con số học nếu nó có ít nhất 2 phần tử và nó là 1 cấp số cộng. Dãy con số học được gọi là cực đại nếu dãy này không thể kéo dài bằng cách thêm vào một phần tử khác của S. Xác định số dãy con số học cực đại

Lời giải:

Ta có công sai a₂ −a₁ phải lớn hơn a₁ để không thể điền thêm phần tử nào vào bên trái dãy con( phía trước a₁ ), nên a₂ ≥2a₁. Lại có a₂ ≤2m nên a1≤m. Khi đó để một dãy con là cực đại thì1≤ ≤a₁ m và 2a₁≤ ≤a₂ n (1). Ta cũng có, với mỗi bộ ( , )a a₁ ₂ thỏa mãn điều kiện trên thì cũng cho ra duy nhất 1 dãy con cực đại có phần tử ban đầu a₁ và công sai a₂ −a₁. Suy ra dãy số con cực đại và bộ ( , )a a₁ ₂ thỏa mãn đk (1) là song ánh. Ta có, với mỗi cách chọn a1 thì có n−2a₁+1 cách chọn a2. Do có m cách chọn a1 nên số bộ ( , )a a₁ ₂ thỏa mãn đk (1) là:

( )

1

1 1

2 2 2

( 1)

2 1 2

2 2

m

a

n a mn m m m

m m m

=

− + = − + +

= − =



Vậy có m² dãy con cực đại với n=2m

(7)

7

Xét với n=2m+1, với m là số nguyên dương.

Tương tự ta có: a₂≥2a₁, suy ra a₁≤m . Lý luận tương tự, ta có số dãy con cực đại là:

( )

1 1 1

2 2

( 1)

2 1 2

2 (2 1)

m

a

n a mn m m m

m m m m m

=

− + = − + +

= + − = +



Vậy, với mỗi số tự nhiên n, ta có

2

4

 n

   dãy con số học cực đại

Song ánh có thể được sử dụng giữa các tập hợp mà các tập hợp này không cần hữu hạn. Dưới đây là 1 ví dụ.

Bài 8 [PEA Math Materials]

Giả sử rằng có 2 quản trị PEA, là những người duy nhất có quyền quay số truy cập vào tệp tài liệu Internet của học viện, biết rằng tại một thời điểm tệp này chỉ xử lý cho một yêu cầu truy cập. Với 15 phút sử dụng tệp cho 1 lần truy cập và tệp chỉ được sử dụng từ 4h chiều đến 6 giờ chiều trong ngày. Biết rằng không có yêu cầu truy cập nào được thực hiện sau 5h45 chiều, và 1 người không được yêu cầu truy cập quá 1 lần. Ít nhất 1 người trong số họ thực hiện thành công cuộc gọi. Hỏi xác suất là bao nhiêu để cả 2 người đều có thể thực hiện thành công cuộc gọi của mình?

Lời giải:

Gọi An và Giang là 2 quản trị của PEA. Ta biết rằng yêu cầu truy cập vào tệp internet của học viện chỉ được thực hiện trong 105 phút. Giả sử An gọi sau 4h x phút, Giang gọi sau 4h y phút, khi đó ta có thể ánh xạ bộ thời gian gọi của 2 người tới điểm (x,y) trên mp tọa độ (Hình 3). Rõ ràng đây là một song ánh.

(8)

8 Hình 3

Tập hợp các điểm (x,y) là hình vuông OA2PZ2. Rõ ràng một người không thể gửi yêu cầu truy cập thành công nếu người còn lại đang làm việc với tệp, do đó để cả 2 người có thể đều truy cập được tệp tài liệu thì ta phải có

15

x y− > . Xét miền của tập hợp các điểm (x,y) được xác định bởi 15

x y− ≤ . Đây là giao của 2 phương trình đường thẳng với hình vuông, cắt tại các điểm Z1, Z2, A1, A3. Ta xác định được Z1=(0,15), Z3=(90,105), A1=(15,0), A3=(105,90)

Từ đó, xác suất để cả 2 người cùng truy cập được vào tệp là:

1 2 3 1 2 3

2 2

90 36

105 49

Z Z Z A A A

OA PZ

S S

p S

Δ + Δ

= = =

Hệ quả 1

Cho 2 số nguyên dương m và n

a. Có C_n^m₋⁻₁¹ bộ nguyên dương

(

^{x x}¹^{, ,...,}² ^x^m

)

thỏa mãn phương trình

1 2 ... _m

x + + +x x =n

b. Có C_{n m}^m_{+ −}⁻¹₁ bộ nguyên không âm

(

^{x x}¹^{, ,...,}² ^x^m

)

thỏa mãn phương trình

1 2 ... _m

x + + +x x =n

Bài 9: Có 5 con xúc xắc được đổ ra. Hỏi có bao nhiêu xác suất để tổng của 5 mặt trên xúc xắc là 14?

Lời giải:

Gọi 5 xúc xắc lần lượt là d d₁, ,...,₂ d₅ và x_i là con số mặt trên của xúc xắc d_i. Với mỗi x_i ta có 6 khả năng, nên có tất cả 6⁵ khả năng có thể xảy ra đối với cả 5 xúc xắc. Gọi A là tập hợp các khả năng tổng các mặt là 14. Ta cần tính | |₅

6

A . Do đó ta cần tính số bộ 5 số nguyên

(

^{x x}¹^{, ,...,}² ^x⁵

)

^{thỏa mãn}

1≤ ≤x_i 6 và x₁+ + + =x₂ .... x₅ 14

Theo Hệ quả 1 thì có tất cả C_{14 1}^{5 1}⁻₋ =715 bộ 5 số nguyên dương thỏa mãn

1 2 .... 5 14

x + + + =x x .

Gọi B là tập các bộ 5 số nguyên dương có tổng bằng 14 và có ít nhất 1 số lớn hơn 6. Đặt B_i ⊂B thỏa mãn x_i >6 . Ta có B_i∩ = ∅B_j ^vớii≠ j^(do

1 2 ... 5 6 6 1 1 1 15

x + + + > + + + + =x x , suy ra B= ∪B_i . Ta cũng có B_i = B_j , suy ra B =5B₁ . Ánh xạ từ

(

^{x x}¹^{, ,...,}² ^x⁵

)

^∈^B¹^tới

(

^{y y}¹^{, ,...,}² ^y⁵

)

^với^y¹^{= −}^x¹ ⁵

và y_i =x_i với 2≤ ≤i 5. Đây là 1 song ánh giữa tập B1 tới tập các bộ 5

(9)

9

(

^{y y}¹^{, ,...,}² ^y⁵

)

nguyên dương thỏa mãn y₁+y₂ + +... y₅ =8. Suy ra

5 1 4

1 8 1 7 35

B =C₋⁻ =C = . Suy ra B =175 Vậy A =715 175 540− = .

Vậy xác suất xuất hiện 5 mặt có tổng là 14 là 540₅ 5 6 =72 Bài 10 [Aime 2000]

Cho 8 chiếc nhẫn khác nhau, tìm số cách xếp 5 chiếc nhẫn xếp trên 4 ngón tay (không tính ngón cái) trên một bàn tay. Biết rằng thứ tự từng chiếc nhẫn trên một ngón tay là quan trọng và không bắt buộc ngón nào cũng phải có nhẫn.

Lời giải:

Ta có C₈⁵ cách chọn ra 5 chiếc nhẫn bất kỳ để đeo trong 8 chiếc nhẫn đã cho. Đăt a, b, c, d là số chiếc nhẫn trên từng ngón tay. Ta có a+b+c+d=5.

Theo Hệ quả 1 ta có C₈³ cách sắp xếp các chiếc nhẫn vào 4 ngón tay (giả thiết là các chiếc nhẫn ko phân biệt). Lại có với mỗi cách sắp xếp 5 chiếc nhẫn ko phân biệt thì tương ứng có 5! cách sắp xếp đối với 5 chiếc nhẫn phân biệt.

Vậy ta có số cách sắp xếp là:

5 3

8. .5! 3763208

C C =

Bài 11:

Ngân hàng Bảo Hiểm của nước cộng hòa Fatand có 15 nhân viên điều hành cấp cao. Mỗi nhân viên này có 1 thẻ truy cập vào kho của ngân hàng và trên mỗi thẻ bất kỳ đều có 1 bảng gồm m mã hóa khác nhau. Để mở được kho, mỗi người sẽ đặt thẻ của mình vào khóa điện tử của kho. Máy tính sẽ thu thập tất cả các mã khác nhau trên thẻ và hầm sẽ được mở khi và chỉ khi tập các mã hóa có n mã hóa (khác nhau) đặt trước. Vì lý do bảo mật, hầm có thể được mở nếu và chỉ nếu có ít nhất thẻ của 6 nhân viên cao cấp. Tìm n và m thỏa mãn n nhỏ nhất để có thể thực hiện được chính sách bảo mật nêu như trên.

Lời giải:

Dễ thấy với mỗi một nhóm gồm 5 nhân viên cao cấp thì sẽ thiếu ít nhất 1 mã hóa so với n mã hóa đặt trước để mở được hầm. Đặt A là tập hợp các nhóm có 5 nhân viên và B là tập hợp gồm n mã hóa cần để mở hầm. Xét ánh xạ từ A vào 1 trong các mã hóa có thể thiếu trong nhóm 5 người (số mã hóa thiếu có thể nhiều hơn 1, nhưng chỉ xét ánh xạ 1-1 để dễ thực hiện). Gọi ánh xạ này là f, ta sẽ chứng minh nó là đơn ánh. Thật vậy, gọi a a₁, ₂∈A là 2 nhóm khác nhau thỏa mãn f a( )₁ = f a( )₂ =c, c là mã còn thiếu. Do a1 khác a2 nên

(10)

10

tồn tại nhóm 6 người lấy từ 2 nhóm a1 và a2 mà vẫn thiếu ít nhất 1 mã (mã c), (vô lý so với giả thiết). Vậy f là đơn ánh. Rõ ràng f là ánh xạ từ A vào B nên ta có:

5

15 3003

n= B ≥ A C= =

Ta sẽ chứng minh n=3003 thỏa mãn. Khi đó cho mỗi nhóm 5 người 1 nhận được 1 mã c(a) khác nhau trong 3003 mã cho trước (điều này có thể thực hiện được vì ta có tất cả 3003 nhóm). Tiếp theo ta viết mỗi mã c(a) này vào thẻ của các thành viên không nằm trong nhóm . Khi đó, mỗi mã sẽ được viết cho 10 người không trong nhóm, suy ra ta viết tất cả 10.C₁₅⁵ các mã, đồng thời được chia đều cho 15 người nên thẻ mỗi người sẽ có

5

10. 15

15 2002

C = mã khác nhau.

Xét một nhóm gồm 6 người bất kỳ. Theo như cách sắp xếp mã như trên, với nhóm a gồm 5 người bất kỳ sẽ chỉ thiếu duy nhất một mã c(a). Ta sẽ chứng minh nhóm 6 người có đủ n mã khác nhau. Thật vậy, xét 2 nhóm 5 người bất kỳ a1 và a2 từ 6 người được chọn. Khi đó ta có c a( )₁ ≠c a( )₂ . Ta sẽ chứng minh rằng nhóm a2 có mã c(a1). Giả sử trong a2 không có mã c(a1), khi đó theo định nghĩa hàm c như ban đầu, ta có ^{c a}

( ) ( )

¹ ⁼^{c a}² (vô lý). Vậy một nhóm 6 người sẽ có đủ mã để mở kho, hay m=2002

Kết luận: n=3003, m=2002

Bài 12 [AIME 2001, by Richard Parris]:

Cho các số 1,2,3,4,5,6,7,8 được điền bất kỳ lên mặt của 1 bát phương

(11)

11

Hình 4: minh họa 1 bát phương

Sao cho mỗi một mặt là 1 số khác nhau. Tính xác suất để không có 2 số liên tiếp nào (8 và 1 cũng được cho 2 số liên tiếp) được viết trên 2 mặt có chung cạnh.

Lời giải:

Để giải bài toán, ta xét thêm hình lập phương có các đỉnh là A,B,C,D,E,F,G, H như ở Hình 5, trong đó đỉnh hình lập phương là các trọng tâm các mặt của bát phương. Khi đó ta sẽ kí hiệu như sau: các số 1,2,3,4,5,6,7,8 thứ tự tương ứng lần lượt là các đỉnh A,B,C,D,E,F,G,H. Cạnh của lập phương nối 2 đỉnh lập phương( nối 2 số) thể hiện mối liên hệ (chung cạnh) giữa 2 mặt bát phương. Ta thấy rõ ràng liên hệ này là 1-1. Khi đó thay vì đếm số trường hợp không có 2 số liên tiếp trên cùng một mặt, ta đếm số cách điền các đỉnh của hình lập phương để không có 2 đỉnh liền kề nào là lập thành 1 cạnh lập phương.

Hình 5

Ta chia các đỉnh thành 2 nhóm, G₁={ , , , }A C F H và G₂={ , , , }G E B D . Dễ thấy các đỉnh trong cùng 1 nhóm thì không liền kề với nhau.

Bài 13:

Cho 1 lưới tam giác có chiều dài mỗi cạnh bên là n, được phủ bởi n² tam giác con đều có cạnh bằng 1. Xác định có bao nhiêu hình bình hành bị giới hạn bởi các đoạn thẳng của lưới.

Lời giải:

(12)

12 Hình 6

Ta chia tất cả các hình bình hành thành 3 tập. Có các cạnh của 1 hình bình hành bất kỳ phải song song với đúng 2 cạnh của tam giác. Gọi S_YZlà tập các hình bình hành có cạnh song song với 2 cạnh XY và ZX của tam giác.

Các tập S_XY và S_ZX xác định tương tự. Do tính đối xứng nên ta có

XY YZ ZX

S = S = S . Từ đó, đáp án của ta sẽ là 3S_YZ . Mở rộng các cạnh XY và XZ về phí Y và Z thêm 1 đơn vị, ta được các đoạn thẳng mới là XY^’ và XZ^’. Xét một hình bình hành bất kỳ thuộc S_YZ, ta kéo dài các cạnh của hbh đó, cắt đoạn thẳng Y’Z’ tại 4 điểm phân biệt (hiển nhiên). Từ đây ta xác định được rằng, cứ 4 điểm phân biệt trên đoạn thẳng Y’Z’ vẽ song song với XY và ZX, cắt nhau tại 4 điểm sẽ tạo được 1 hbh thuộc S_YZ. Vậy ta có ánh xạ từ S_YZra bộ 4 điểm trên đoạn Y’Z’ là 1 song ánh, mà đoạn Y’Z’ có tất cả n+2 điểm, nên ta có S_YZ =C_n⁴₊₂.

Vậy có tất cả 3C_n⁴₊₂ hbh bị giới hạn bởi các cạnh của tam giác.

Bài 14:

Bart hiện là nhân viên của rạp chiếu phim. Rạp này có sức chứa 200 chỗ ngồi. Trong ngày khởi chiếu phần I Star War: The Phantom Menace, có 200 người đứng xếp hàng để mua vé xem phim. Giá mỗi vé là 5$. Trong 200 người mua vé, 100 trong số họ có hóa đơn loại 5$, nửa còn lại là hóa đơn loại 10$(mỗi người có 1 hóa đơn). Bart vốn bất cNn và vẫn không chịu thay đổi.

200 người đó xếp hàng 1 cách ngẫu nhiên và không ai muốn chờ để thay đổi vé của mình khi họ mua vé. Xác suất là bao nhiêu để Bart có thể bán được hết tất cả các vé có lợi nhất (thành công)

Lời giải:

(13)

13

Để dễ dàng hơn ta thay 100 bằng n. Ta xem xét những người là không phâ biệt được. Ta cân nhắc sự sắp xếp của n người sở hữu hóa đơn 5$ và n người sở hữu hóa đơn 10$ (nói cách khác ta làm phép nhân lên ( !)n ² tới cả hai mẫu số và tử số, việc này không ảnh hưởng tới giá trị của xác suất). Có

2 n

C n cách sắp xếp xác số mà không hạn chế. Bart sẽ thành công khi và chi khi:

ta sắp xếp 2n số vào một hàng ngang và đánh số vị trí của chúng từ trái qua phải từ 1,2,3,...,2 n. Với 1≤ ≤i 2n, đặt ( )a b_i _i là số người có hóa đơn 5$ (10$) đứng trước vị trí thứ i. Ta cần đếm số sự sắp xếp thỏa mãn a_i ≥b_i với 1≤ ≤i 2n. Gọi S là tập hợp tất cả các sắp xếp như vậy. Gọi T là tập hợp các sự sắp xếp khác nhau như trên. Ta sẽ tìm T .

Ta có S =C₂ⁿ_n −T

Một phần tử t T∈ , t =( , ,..., )t t₁ ₂ t₂_n có số i,1≤ ≤i 2nthỏa mãn a_i <b_i. Gọi f t( ) là ký hiệu của số chỉ đầu tiên. Bởi sự xác đinh cả ta,

( ) ( )

( ) 1 ( ) 1

2 , 2

f t f t

a = − b = + và t_{f t}_{( )} =10. Vì vậy có nhiều hơn số hóa đơn 10$ so với 5$ tính đến (tại) thời điểm thứ ( )f t . Ta thay đổi toàn bộ các đồng 5$ thành 10$ và các đồng 10$ thành 5$ sau thời điểm thứ ( )f t , thì khi đó ta thu được một hoán vị g t( ) của n+1 đồng 10$ và n−1 đồng 5$

Ví dụ: với n=6 ta có:

(

5,10,10,5,10,10,10,5,10,5,5,5

)

t=

Ta có

1 2 12

1 2 2

2 2 3

( , ,..., ) (1,1,1,2,2,2,2,3,3,4,5,6) ( , ,..., ) (0,1,2,2,3,4,5,5,6,6,6,6)

( ) 3, 1, 1, 10

( ) (5,10,10,10,5,5,5,10,5,10,10,10) a a a

b b b

f t a b t

g t

=

= = = =

=

Do đó ta xác định một ánh xạ từ T vào U- là tập hợp hoán vị của n+1 đồng 10$ và n−1 đồng 5$. Ta sẽ hứng minh g là một song ánh

Đầu tiên ta chứng minh g là một toàn ánh. Xét u là một phần tử bất kỳ thuộc U. Ta đếm số lần xuất hiện của đồng 5$ và 10$ tính từ trái qua phải với i là các giá trị nguyên nhỏ nhất sao cho tính đến thời điểm thứ i số đồng 10$

là nhiều hơn số đồng 5$. Ta thay đổi toàn bộ các đồng 5$ thành 10$ và toàn bộ các đồng 10$ thành 5$ sau thời điểm thứ i. Vì số đồng 10$ có số lượng lớn hơn 2 so với số đồng 5$ trong U nên sẽ có số đồng 10$ nhiều hơn số đồng 5$ tại trước thời điểm i và số đồng 10$ nhiều hơn số đồng 5$ tại 2n i− thời điểm còn lại. Sau bước đổi 5→10 và 10→5 trên ta thu được số đồng 5$

(14)

14

và 10$ bằng nhau. Không khó để thấy dáy mới này thuộc T, do đó g là một toàn ánh.

Bây giờ ta chứng minh g là đơn ánh. Xét t và t' là 2 phần tử thuộc T. Giả sử rằng tại thời điểm thứ i,1≤ ≤i 2n là thời điểm đầu tiên t và t' có sự khác nhau. Không giảm tính tổng quát g/s t_i =5 và , thì f t( )≠i. Nếu f t( )<i thì f t( ')= f t( ) bởi i−1 vị trí đầu của t và 't là hoàn toàn giống nhau. Khi đó tại thời điểm thứ i, ( )g t và ( ')g t có giá trị là 10 và 5 tương ứng, do đó

( ) ( ')

g t ≠g t . Ta lại xét ( )f t >i . Thì tại thời điểm thứ i của ( )g t là t_i, có

i 5

t = . Bởi vì ( 1)i− vị trí đầu của t và t' như nhau, ( ')f t >i. Dô đó tại thời điểm thứ i của ( ')g t là t', nó bằng 10. Do đó ( )g t ≠g t( '). Suy ra g là song ánh.

Từ đó theo ta có:

1 2

n

T =U =C n⁻ . Vậy ₂ ₂ ₂ ¹ 1 ₂

1

n n n n

S C T C C C

n

= − = − − =

+ Trở lại bài toán, ta có n=200, vậy xác suất là 1

201 Bài 15:

Cho n là số nguyên dương thỏa mãn các tính chất: nếu n cái domino được đặt trên 1 bàn cờ 6x6 với mỗi domino chiếm 2 đơn vị diện tích vuông, thì luôn luôn có thể đặt thêm 1 domino lên trên bàn mà không phải di chuyển bất kỳ domino nào khác. Xác định giá trị lớn nhất của n.

Lời giải:

Ta sẽ chứng minh giá trị lớn nhất của n là 11. Hình 7 là cách sắp xếp 12 domino trên bàn cờ thì không thể để thêm 1 domino nào nữa. Suy ra n≤11.

Hình 7

(15)

15

Ta sẽ chứng minh rằng với 11 domino trên bàn cờ thì luôn đặt thêm được 1 domino nữa. Ta sẽ chứng minh bằng phản chứng. Giả sử rằng tồn tại cách đặt 11 domino trên bàn cờ mà không thể đặt thêm 1 domino nào nữa.

Khi đó số ô vuông trên bàn chưa bị phủ bởi 11 domino là: 36-22=14.

Đặt S1 là phần trên của bàn cở ban đầu có kích thước 5x6 (Hình 8). Đặt A là tập các ô vuông trong S1 mà không bị phủ bởi các domino, và S2 là hàng cuối của bàn cờ (bàn cờ chia làm 2 phần S1 và S2). Vì ta không thể điền thêm 1 domino nào vào bàn cờ, nên một trong 2 ô vuông bất kỳ cạnh nhau sẽ được bao phủ bởi 1 domino, suy ra S2 có nhiều nhất là 3 ô không bị phủ bởi domino (trống), suy ra S1 có ít nhất là 14-3=11 ô trống.

Hình 8

Đặt S3 là phần dưới của bàn cờ và có kích thước 5x6 (Hình 8), B là tập tất cả các domino nằm trong S3. Ta sẽ định nghĩa một ánh xạ f từ A vào B. Ta có, với mỗi ô vuông trống s trong S1, sẽ tồn tại một ô vuông t nằm dưới s. Suy ra ô vuông t nằm trong S3 và được phủ bởi một domino d. Rõ ràng domino d phải nằm trong S3 (vì nếu ko thuộc S3 thì nó sẽ gồm 2 ô t và s-vô lý). Khi đó ta xác định ánh xạ f là ( )f s =d . Ta sẽ chứng minh rằng f là đơn ánh. Thật vậy, giả sử ∃s s₁, ₂∈A sao cho f s( )₁ = f s( )₂ =d. Suy ra d phủ 2 ô vuông ở dưới s₁ và s₂. Suy ra s₁ và s₂ nằm cạnh nhau (Hình 9), như vậy khi đó ta có thể đặt thêm 1 domino phủ lên s₁ và s₂(vô lý). Vậy f là đơn ánh, suy ra A ≤ B hay B ≥11. Nhưng cả bàn cờ chỉ có 11 domino, suy ra B =11. Khi đó thì hàng trên cùng sẽ không bị phủ bởi 1 domino nào, và sẽ đặt được thêm 1 quân domino nữa (vô lý).

(16)

16 Hình 9 Vậy giá trị lớn nhất của n là 11.

Bài 16 [China 2000, by Jiangang Yao]:

Cho số nguyên dương n và xác định ^M ⁼

{

^{( , ) | ,}^{x y x y}^∈^^,1^≤^{x y n}^, ^≤

}

Hỏi có bao nhiêu ánh xạ f xác định trên M thỏa mãn i. f x y( , ) là số tự nhiên với mọi ( , )x y ∈M

ii.

1

( , ) 1

n

y

f x y n

= = −



^{với mọi}^x thỏa mãn 1≤ ≤x n iii. Nếu f x y f x y( , ) ( , ) 0₁ ₁ ₂ ₂ > thì (x₁−x₂)(y₁−y₂) 0≥ Lời giải:

Có kết luận 2 1

1 n

Cn⁻₋ giá trị của hàm f . Ta coi một hàm f trên M như một ma trận M_f =( )s_{i j}_, với n hàng và n cột sao cho f i j( , )=s_{i j}_,

Điều kiện i,ii,iii trở thành

i’. tất cả các thành phần của M_f là các số tự nhiên

ii’. tổng của tất cả các thành phần của M_f theo hàng ngang bằng n−1 iii’. tất cả các thành phần (nhập vào) của M_f có thể đi theo 1 lối đi từ thành phần (nhập vào) trên cùng bên trái s_1,1 tới thành phần bên phải dưới s_{n n}_, bằng các bước dịch chuyển xuống hoặc sang phải một đơn vị mỗi lần. Điều đó là đúng vì nếu s_{i j}_, >0 và s_i₊_1,_k >0 thì j k≤ vì

[

ⁱ^{− +}⁽ⁱ ¹⁾

][

^{j k}^{− ≥}

]

⁰^và

hơn thế nữa mỗi đường đi thỏa mãn xác định duy nhất một ma trận M_f nếu đường đi đó đòi hỏi phải đi qua (xuống) tới s_{i j}_, nếu s_{i j}_, >0 và s_{i k}_. =0 với

1

j+ ≤ ≤k n.

(17)

17

Ta gọi ma trận thỏa mãn i’, ii’, iii’ là ma trận tốt. Rõ ràng có một song ánh giữa tập hợp tất cả các hàm thỏa mãn điều kiện bài toán với tập các ma trận tốt

Ta cần đếm tất cả các ma trận tốt. Do đó ta xét bài toán khác sau: Một công viên bị chia thành một lưới n n× các hình vuông đơn vị. Người làm vườn của công viên phải trồng n−1 cây vào mỗi hàng ngang của lưới. Anh ấy có thể trồng bất kỳ chiếc cây nào (các cây không phân biệt) vào một ô vuông. Và anh ta có thể trồng nhiều hơn 1 cây vào ô vuông . Anh ta làm việc trồng cây bắt đầu từ góc tây bắc( trên cùng bên trái) của công viên xuống góc đông nam (dưới cùng bên phải) của công viên. Anh ta trồng một hàng cây tại một thời điểm và khi hoàn thành 1 hàng, anh ta tự chuyển xuống hàng ngang phía dưới ( phía nam). N gười làm vườn có 3 trạng thái

1. trồng 1 cây ở hình vuông anh ta đang đứng 2. chuyển tới một hình vuông ở phía đông (phải)

3. tự động xuống dưới (phía nam) nếu anh ta trồng đủ n−1 cây ở hàng anh ta đang đứng (trừ hàng cuối)

Chúng ta không phải lo lắng ở trường hợp (3) vì người làm vườn luôn cNn thận đếm số cây đã trồng trong 1 hàng và chỉ chuyển xuống hàng tiếp theo nếu đã trồng đủ (n−1) cây ở hàng đang đứng. Anh ta trồng (n−1) cây ở mỗi hàng ngang nếu tổng số cây đã trồng là (n n−1) cây. Do đó anh ta thực hiện n n( −1) trạng thái loại (1). Với trường hợp chuyển vị trí xuống góc dưới cùng phía bên phải anh ta phải thực hiện (n−1) trạng thái loại (2). Và do đó anh ta có tất cả n n( − + − = −1) n 1 n² 1 trạng thái. Vì anh ta có thể biểu diễn trạng thái theo ý muốn nên số cách anh ta thực hiện công việc là 2

1 1 n

Cn⁻₋ (do phải trồng n−1 cây). Không khó để thấy rằng có sự tương ứng một-một giữa các ma trận tốt và số cách trồng của người làm vườn.

Ví dụ với n=4, nếu 1 và e là ký hiệu tương ứng cho trạng thái (1) và (2) thì coi dãy 11ee11111111e11,e1111111111e1e1,11111111e11e11e tương ứng với các hình vẽ sau:

** * *

**

*

**

* **

(18)

18 *

**

*

**

*

**

* * *

Và có 3 ma trận tương ứng là 2 0 1 0

0 0 3 0 0 0 3 0 0 0 1 0

 

 

 

và

0 3 0 0 0 3 0 0 0 3 0 0 0 1 1 1

 

 

 

Do đó số ma trận M_f bằng số các hàm số f và cùng bằng 2 1

1 n

Cn⁻₋ Bài 17:

Cho số nguyên dương n, và tập A là tập tất cả các dãy con tăng có tổng bằng n. Đặt a=( , ,..., )a a₁ ₂ a_m là phần tử của A. Đặt ( )s a là chỉ số bé nhất thỏa mãn a_{s a}_{( )},a_{s a}_{( ) 1}₊,...,a_m là các số nguyên liên tiếp. Giả sử n không thể viết dưới dạng (3 1)

2

k k− hoặc (3 1) 2

k k+ với mọi số nguyên dương k. Đặt A₁ là tập con của A thỏa mãn a A∈ ₁ khi và chỉ khi a₁≤ −m s a( ) 1+ .

Chứng minh rằng A =2 A₁ Lời giải:

Gọi A₁'là tập con của A thỏa mãn a A∈ ₁' khi và chỉ khi

1 ( ) 1

a > −m s a + . Khi đó ta có A A= ∪₁ A₁'. Ta sẽ chứng minh tồn tại 1 song ánh đi từ A₁ vào A₁'. Thật vậy, ta định nghĩa ánh xạ như sau:

1 1

1 2 2 1

( , ,..., )_m ' ( ,..., _{m a}, _{m a} 1,..., _m 1) a= a a a → =a a a ₋ a _{− +} + a + (*)

(Thực hiện chia đều a₁ cho a₁ phần tử cuối của a, và xóa đi a₁ , ta được phần tử mới a' -giúp đảm bảo tổng các phần tử đều bằng n

Ví dụ với n=42 và a=(3,5,7,8,9,10). Ta có a₁=3,m=6 và ( ) 3s a = , do đó a A∈ ₁. Khi đó qua phép ánh xạ ở trên, ta được ' (5,7,9,10,11)a = . Ta có

(19)

19

thể quan sát dễ dàng trên biều đồ Young (. Như trên hình 12, ta xóa 3 điểm trong cột thứ nhất (vì a₁=3 ) và chia đều số điểm đó cho 3 cột sát bên phải nhất.

Hình 10 Ta cần chứng minh:

i. a'∈A₁'

ii. Phép ánh xạ (*) là đơn ánh iii. Phép ánh xạ (*) là toàn ánh Cm (i):

Ta có m a− + ≥₁ 1 s a( ) (vì a A∈ ₁ ). Do ( )s a là chỉ số nhỏ nhất để

( ), ( ) 1,...,

s a s a m

a a ₊ a là các số tự nhiên liên tiếp, suy ra ta có

1 1 1,..., 1

m a m

a _{− +} + a + là các số tự nhiên liên tiếp.

Nếu m a− + ≥₁ 1 3 thì ánh xạ (*) cho:

1 1

' '

2 1 1 1

' ( ,..., _{m a}, _{m a} 1,..., _m 1) ( ,..., _m ) a = a a ₋ a _{− +} + a + = a a ₋

1 1 1 1

' ' '

1 2 _{m a} 1 _{m a} _{m a} 1 1 _{m a} 2

a = ≤a a _{− −} =a ₋ ≤a _{− +} − =a ₋ − . Suy ra s a( ')= −m a₁.

Khi đó m s a'− ( ') 1 (+ = m− −1) (m a− ₁) 1+ =a₁, lại có a₂>a₁ nên suy ra

'

1 2 ' ( ') 1

a = > −a m s a + . Vậy a'∈A₁^'.

Nếu m a− + =₁ 1 2 thì ánh xạ (*) cho

' '

2 1 1

' ( 1,..., _m 1) ( ,..., _m )

a = a + a + = a a ₋ và s a( ') 1, '= m = −m 1. Khi đó do

'

1 2 1 ' ( ') 1 1 1 1

a = + > −a m s a + = − = +m a . Vậy a'∈A₁^'.

(20)

20

Nếu m a− + =₁ 1 1, suy ra s a( ) 1= . Khi đó ta có a a₁, ,...,₂ a_m là m số tự

nhiên liên tiếp. Khi đó ta có

2 1

( 1) ( 1) (3 1)

2 2 2

m m m m m m

n ma= + − =m + − = − (vô lý với giả thiết).

Vậy a'∈A₁^' và s a( ')= −m a₁ (1)

Chứng minh ii: ta sử dụng pp phản chứng.

Giả sử ∃ ≠a b a b A, , ∈ ₁ sao cho qua phép ánh xạ (*) có ảnh là a b', '∈A₁^' thỏa mãn a'=b'. Do phép ánh xạ (*) làm giảm chiều dài của dãy mới đi 1 so với ban đầu, suy ra a và b có cùng chiều dài. Đặt b=( , ,..., )b b₁ ₂ b_m . Ta có

1 ( ') ( ') 1

m a− =s a =s b = −m b (theo 1). Suy ra a₁ =b₁ , suy ra a b= (mâu thuẫn). Vậy phép ánh xạ (*) là đơn ánh

Để chứng minh ý (iii), ta sử dụng ánh xạ ngược của (*). Đặt

' ' ' '

1 2 1 1

' ( , ,..., _m )

a = a a a ₋ ∈A. Ta thực hiện phép ánh xạ ngược như sau: trừ đi 1 đơn vị ở m s a− ( ') số tự nhiên liên tiếp của a', sau đó thêm vào trước a₁^' số có giá trị bằng m s a− ( '). Gọi phần tử mới này là a, ta sẽ chứng minh a A∈ ₁.

Để ý dạng tổng quát của a như sau:

' ' ' '

1 ( ') 1 ( ') 1

( ( '), ,..., _{s a} , _{s a} 1,..., _m 1)

a= m s a a− a ₋ a − a ₋ − (dễ thấy có cái này thì ( ') 1 1

s a − ≥ để thỏa mãn đk về chỉ số). Ta sẽ xét 2 trường hợp:

Nếu s a( ') 1 1− ≥ . Ta có a'∈A₁^' nên a₁^' >(m− −1) s a( ') 1+ = −m s a( ')và

' '

( ') 1 ( ') 2

s a s a

a ₋ ≤a − . Khi đó ánh xạ ngược của (*):

' ' ' '

1 2 1 ( ') 1 ( ') 1

( , ,..., ) (_m ( '), ,..., _{s a} , _{s a} 1,..., _m 1) a= a a a = m s a a− a ₋ a − a ₋ −

Lại có a^'_{s a}_{( ')},a_{s a}^'_{( ') 1}₊ ,...,a_m^'₋₁ là các số tự nhiên liên tiếp nên a_{s a}_{( ') 1}₊ =a_{s a}^'_{( ')} −1 ,…,a_m =a_m^'₋₁−1 là các số tự nhiên liên tiếp. Khi đó chỉ số ( )s a của a phải nhỏ hơn bằng ( ') 1s a + ( ( )s a ≤s a( ') 1+ )

Kết hợp lại ta có: a₁= −m s a( ')≤ −m s a( ) 1+ , suy ra a A∈ ₁

Nếu ( ') 1s a = . Vì a'∈A₁^' nên a₁^' >(m− −1) s a( ') 1+ = −m 1. Nếu a₁^' =m thì ta có

[ ]

' '

1 1

( 2)( 1)

... ... ( 2) ( 1)

2 ( 1) 3( 1) 1

2

m

m m

n a a m m m m m

m m

−

− −

= + + = + + + − = − +

− − +

=

(vô lý).

(21)

21

Vậy a₁^' ≥ +m 1 suy ra. Khi đó ánh xạ ngược của (*) cho ta có

' 1

1 1

( 1, 1,..., _m 1)

a= m− a − a ₋ − thỏa mãn a₁= − ≤ −m 1 m s a( ) 1+ (do ( ) 2s a ≤ ).

Vậy ánh xạ ngược của (*) cho ra a A∈ ₁

Vậy phép ánh xạ (*) là song ánh, suy ra A₁ = A₁^' , suy ra A =2 A₁ Bài 18 [VMO 1996]:

Cho các số nguyên dương k và n với k n≤ . Hỏi có tất cả bao nhiêu chỉnh hợp

(

^{a a}¹^{, ,...,}² ^a^k

)

^chập ^k^củaⁿ số nguyên dương đầu tiên, mà mỗi chỉnh hợp

(

^{a a}¹^{, ,...,}² ^a^k

)

thỏa mãn ít nhất một trong 2 điều kiện sau:

1. Tồn tại ,s t thuộc

{

^1,2,...,^k

}

^{sao cho}^{s t}^< ^và^a^s ^>^a^t

2. Tồn tại s thuộc

{

^1,2,...,^k

}

^{sao cho}

(

^a^s ⁻^s

)

không chia hết cho 2 Lời giải:

Gọi ^A⁼

{ (a a1, ,...,2 ak) }

^với^{k n}^≤ ^,^aⁱ ⁼

{

^1,2,...,ⁿ

}

^{với mọi}ⁱ⁼^1,2,...,^k^.

Xét tập B⊂ Athỏa mãn nếu

(

^{a a}¹^{, ,...,}² ^a^k

)

^∈^B^thì^aⁱ ^<^aⁱ⁺¹ ^với^{∀ =}ⁱ ^1,2,...,^k⁻¹

và a_i ≡i(mod 2) với ∀ =i 1,2,...,k. Xét tập D⊂ A mà mỗi chỉnh hợp a D∈ thỏa mãn yêu cầu bài toán. Rõ ràng ta có D A B= \ nên số chỉnh hợp cần phải tìm là D = A − B (1)

Để xét số phần tử của tập B ta thấy a_i + ≡ ≡i 2i 0(mod 2) với 1,2,...,

i k

∀ = nên ta lập ánh xạ :f B→E xác định bởi:

( )

(

¹^{, ,...,}² ^k

) ( 1 1, 2 2,..., k ),

f a a a = a + a + a +k i =1,2...,k

Với ^E ⁼

{ (e e1, ,...,2 ek) }

trong đó 2≤ ≤ +e_i n k, 0(mod 2)e_i ≡ với 1,2,...,

i k

∀ = và 1+ <e_i e_i₊₁ với 1,2,...,∀ =i k−1

Dễ dàng thấy nếu , 'b b ∈B mà b b≠ ' thì ( )f b ≠ f b( ')nên f là đơn ánh. Mặt khác từ e_i ≡0(mod 2) thì e i i_i − ≡ (mod 2) và từ e_i <e_i₊₁−1 suy ra

1 1

i i

e − <i e₊ − −i (hay a_i <a_i₊₁ khi đặt a_i = −e_i i a, _i₊₁=e_i₊₁− −i 1), mà 2≤ <e_i e_i₊1≤ +n k nên 1≤ <a_i a_i₊₁≤n với ∀ =i 1,2,...,k−1. Từ đó, với mỗi

(

¹^{, ,...,}² ^k

)

e= e e e ∈E thì tồn tại ^b⁼

(

^{a a}¹^{, ,...,}² ^a^k

)

^∈^B sao cho ( )f b =e, nghĩa là f là toàn ánh. Vậy f là song ánh nên B = E . Với tập E được xác định như trên ta có B = E =C_m^k với

2 m n k+ 

=  (2) Từ (1) và (2) và !

( )!

A n

= n k

− ta có:

(22)

22

!

( )!

k m

D A E n C

= − = n k −

− với

2 m n k+ 

=  Nhận xét:

2. Dùng song ánh để chứng minh các hằng đẳng thức tổ hợp

Bài 1:Chứng minh hằng đẳng thức

( ) ( ) ( )

^Cⁿ⁰ ² ⁺ ^C¹ⁿ ²⁺ ^Cⁿ² ² ^{+ +}^...

( )

^Cⁿⁿ ² ⁼^C²ⁿⁿ

Hướng dẫn:

Ta thấy C₂ⁿ_n bằng số cách chọn ra n đối tượng từ 2n đối tượng đôi một khác nhau.

Mặt khác, chia 2n đối tượng này ra thành 2 nhóm: Nhóm 1 và nhóm 2 đều gồm n đối tượng. Khi đó để chọn ra n phần tử ta thực hiện như sau.

Chọn k phần tử từ nhóm 1: có C_n^k cách chọn, sau đó chọn n k− đối tượng từ nhóm 2: có C_n^{n k}⁻ =C_n^k cách chọn. Theo quy rắc nhân có

( )

^Cⁿ^k ² cách chọn ra n đối tượng mà trong đó có k đối tượng thuộc nhóm 1. Cho k =0,1,...,n và theo quy tắc cộng ta có đpcm

Bài 2:Chứng minh hằng đẳng thức:

( )

² ² ¹¹

0

n k n

n n

k

k C nC ⁻₋

= =



HD:

Xét bài toán có n học sinh nam và n học sinh nữ. Hỏi có bao nhiêu cách chọn ra n học sinh sao cho có 1 học sinh nam làm lớp trưởng.

Bài 3: Chứng minh hằng đẳng thức: <