Ứng dụng phương pháp Song ánh trong giải toán Tổ hợp
Gửi bởi: Phạm Thọ Thái Dương 8 tháng 4 2021 lúc 17:16:35 | Được cập nhật: hôm qua lúc 2:26:12 | IP: 10.1.29.225 Kiểu file: PDF | Lượt xem: 698 | Lượt Download: 11 | File size: 0.844814 Mb
Nội dung tài liệu
Tải xuống
Link tài liệu:
Các tài liệu liên quan
- Các đề luyện thi TNTHPT môn Toán
- Chuyên đề sự đồng biến và nghịch biến
- Chuyên đề cực trị của hàm số
- Test công thức
- 300 câu trắc nghiệm chương Đạo hàm theo chủ đề
- 520 bài tập trắc nghiệm đạo hàm
- Đề luyện tập Chuyên đề 1 - Ứng dụng của đạo hàm để khảo sát và vẽ đồ thị của hàm số
- Đề luyện tập Chuyên đề 2 - Khối đa diện
- Đề luyện tập Chuyên đề 3 - Hàm số lũy thừa, hàm số mũ và hàm lôgarit
- ĐỀ 44-TỔNG HỢP (ĐẾN NGUYÊN HÀM-MẶT CẦU)
Có thể bạn quan tâm
Thông tin tài liệu
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 x1 , x2 ∈ X , f ( x1 ) = f ( x2 ) 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 f ( x) = y
Á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)
1
Cho m, n ∈ * , hỏi phương trình x1 + x2 + ... + xn = 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
F: T →A
Xét tương ứng: ( x ,..., x ) 1...101...10...01...1
1
n
x1
so1
x2
so1
xn
so1
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 Cmn −+1n −1 . Vậy số
nghiệm của (*) là Cmn −+1n −1
Bài 2 [VMO 2012_ câu 5]:
Cho một nhóm có 5 cô gái, kí hiệu là G1 , G2 ,..., G5 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à G1 , G2 , G3 , G4 , G5
3. Giữa G1 và G2 có ít nhất 3 chàng trai
4. Giữa G4 và G5 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 x1 + x2 + ... + xk = 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 x1 là số chàng trai được xếp bên trái G1 , x2 là số chàng trai ở
giữa G1 và G2 ; x3 là số chàng trai ở giữa G2 và G3 ; x4 là số chàng trai ở giữa
G3 và G4 ; x5 là số chàng trai ở giữa G4 và G5 ; x6 là số chàng trai ngồi bên
phải G5 . Khi đó bộ số ( x1 , x2 ,..., x5 ) hoàn toàn xác định vị trí các cô gái và ta
có:
1. x1 + x2 + ... + x6 = 12
2. 3 ≤ x2
2
3. 1 ≤ x5 ≤ 4
Đổi biến y2 = x2 − 3 và y5 = x5 − 1 ta được x1 + y2 + x3 + x4 + y5 + x6 = 8
với các Nn không âm và có thêm điều kiện y5 ≤ 3 .
Tiếp theo, áp dụng bài toán chia kẹo ở dạng
x1 + y2 + x3 + x4 + x6 = 8 − y5
Ta được số cách phân ghế cho các cô gái là
C124 + C114 + C104 + C94 = 1161
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ì
A = 79 − 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à C239 . 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. N hư vậy thì số cách chọn ra 10 khoảng trống trong 79
khoảng là C7910 . 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. N hờ có (79,10)=1 mà ta không phải lo về “các cấu hình
C7910C239
lộn xộn”, mỗi cách tô bị lặp đúng 79 lần, do vậy đáp số là
79
Định lý 4.1:
3
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 C52 = 10 đơn giác đỏ. Giờ ta chứng minh có 2 tam giác đỏ đồng dạng.
Hình 1
Đặt A1 , A2 , A9 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 Ai Aj Ak là tam giác thỏa mãn
A A ≤ A A ≤ A A . Định nghĩa a là số mảnh của cung
A A không chứa
i
j
j
k
k
i
i, j
i
j
điểm Ak . Ta định nghĩa tương tự với a j ,k và ak ,i . Khi đó ΔAi Aj Ak được xác
định bởi bộ ba
(a
i, j
, a j ,k , ak ,i ) . Do 1 tam giác có 3 đỉnh, nên ta dễ thấy
1 ≤ ai , j ≤ a j ,k ≤ ak ,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
Ai Aj +
Aj Ak +
Ak Ai = 1800 , do đó ai , j + a j ,k + ak ,i = 9 . Ví dụ
với tam giác ΔA2 A4 A8 ta xác định được bộ ba tương ứng là (2,3,4). Dễ thấy
4
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à a1a2 ...an−1 ,
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)= (a1 , a2 , a3 ) . Khi đó nếu (a1 , a2 , a3 ) = (0,0,1) thì
4=(1+1+1)+(1)=3+1 là một cách biểu diễn.
Ta có tất cả 2n-1 cách biểu diễn cho dãy nhị phân (n-1) bit a1a2 ...an−1 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ó 2n-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)
5
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à C102 C52 = 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,..., n ) . 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 a2 − a1 phải lớn hơn a1 để 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 a1 ), nên a2 ≥ 2a1 . Lại có a2 ≤ 2m nên
a1 ≤ m . Khi đó để một dãy con là cực đại thì1 ≤ a1 ≤ m và 2a1 ≤ a2 ≤ n (1). Ta
cũng có, với mỗi bộ ( a1 , a2 ) 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 a1 và công sai a2 − a1 . Suy ra dãy số con
cực đại và bộ ( a1 , a2 ) thỏa mãn đk (1) là song ánh. Ta có, với mỗi cách chọn
a1 thì có n − 2a1 + 1 cách chọn a2. Do có m cách chọn a1 nên số bộ ( a1 , a2 )
thỏa mãn đk (1) là:
m
( n − 2a
a1 =1
1
m(m + 1)
+m
2
= 2m 2 − m 2 = m 2
+ 1) = mn − 2
Vậy có m2 dãy con cực đại với n=2m
6
Xét với n=2m+1, với m là số nguyên dương.
Tương tự ta có: a2 ≥ 2a1 , suy ra a1 ≤ m . Lý luận tương tự, ta có số dãy
con cực đại là:
m
( n − 2a
a1 =1
1
m(m + 1)
+m
2
= m(2m + 1) − m 2 = m 2 + m
+ 1) = mn − 2
n2
Vậy, với mỗi số tự nhiên n, ta có dãy con số học cực đại
4
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.
7
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ó
x − y > 15 . Xét miền của tập hợp các điểm (x,y) được xác định bởi
x − y ≤ 15 . Đâ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à:
p=
S ΔZ Z Z + S ΔA A A
1 2 3
1 2 3
SOA PZ
2
2
=
902 36
=
1052 49
Hệ quả 1
Cho 2 số nguyên dương m và n
a. Có Cnm−−11 bộ nguyên dương
x1 + x2 + ... + xm = n
( x , x ,..., x )
1
2
m
thỏa mãn phương trình
b. Có Cnm+−m1−1 bộ nguyên không âm ( x1 , x2 ,..., xm ) thỏa mãn phương trình
x1 + x2 + ... + xm = 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à d1 , d 2 ,..., d 5 và xi là con số mặt trên của xúc
xắc d i . Với mỗi xi ta có 6 khả năng, nên có tất cả 65 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
| A|
cần tính 5 . Do đó ta cần tính số bộ 5 số nguyên ( x1 , x2 ,..., x5 ) thỏa mãn
6
1 ≤ xi ≤ 6 và x1 + x2 + .... + x5 = 14
Theo Hệ quả 1 thì có tất cả C145−−11 = 715 bộ 5 số nguyên dương thỏa mãn
x1 + x2 + .... + x5 = 14 .
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 Bi ⊂ B thỏa mãn xi > 6 . Ta có Bi ∩ B j = ∅ với i ≠ j (do
x1 + x2 + ... + x5 > 6 + 6 + 1 + 1 + 1 = 15 , suy ra B = ∪ Bi . Ta cũng có Bi = B j ,
suy ra B = 5 B1 . Ánh xạ từ ( x1 , x2 ,..., x5 ) ∈ B1 tới ( y1 , y2 ,..., y5 ) với y1 = x1 − 5
và yi = xi với 2 ≤ i ≤ 5 . Đây là 1 song ánh giữa tập B1 tới tập các bộ 5
8
( y , y ,..., y ) nguyên
1
2
5
dương
thỏa
mãn
y1 + y2 + ... + y5 = 8 .
Suy
ra
B1 = C85−−11 = C74 = 35 . 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
=
65
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ó C85 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ó C83 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à:
C85 .C83 .5! = 376320
Bài 11:
N gâ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 a1 , a2 ∈ A là 2 nhóm
khác nhau thỏa mãn f (a1 ) = f (a2 ) = c , c là mã còn thiếu. Do a1 khác a2 nên
9
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ó:
n = B ≥ A = C155 = 3003
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.C155 các mã, đồng
10.C155
thời được chia đều cho 15 người nên thẻ mỗi người sẽ có
= 2002 mã
15
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( a1 ) ≠ c( a2 ) . 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 ( a1 ) = c ( a2 ) (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
10
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, G1 = { A, C , F , H } và G2 = {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 n2
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:
11
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 SYZ là 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ó
S XY = SYZ = S ZX . Từ đó, đáp án của ta sẽ là 3 SYZ . 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 SYZ , 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 SYZ . Vậy ta có ánh xạ từ SYZ ra 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ó SYZ = Cn4+ 2 .
Vậy có tất cả 3Cn4+ 2 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:
12
Để 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!) 2 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ó
C2nn 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 ai (bi ) 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 ai ≥ bi 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 = C2nn − T
Một phần tử t ∈ T , t = (t1 , t2 ,..., t2 n ) có số i,1 ≤ i ≤ 2 n thỏa mãn ai < bi .
Gọi f (t ) là ký hiệu của số chỉ đầu tiên. Bởi sự xác đinh cả ta,
f (t ) − 1
f (t ) + 1
a f (t ) =
, bf (t ) =
và t f ( t ) = 10 . Vì vậy có nhiều hơn số hóa đơn
2
2
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ó:
t = ( 5,10,10,5,10,10,10,5,10,5,5,5)
Ta có
(a1 , a2 ,..., a12 ) = (1,1,1,2,2,2,2,3,3,4,5,6)
(b1 , b2 ,..., b2 ) = (0,1,2,2,3,4,5,5,6,6,6,6)
f (t ) = 3, a2 = 1, b2 = 1, t3 = 10
g (t ) = (5,10,10,10,5,5,5,10,5,10,10,10)
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$
13
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 ≤ 2 n 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 ti = 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à ti , có
ti = 5 . Bởi vì (i − 1) 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ó:
T = U = C2nn−1 . Vậy S = C2nn − T = C2nn − C2nn−1 =
Trở lại bài toán, ta có n = 200 , vậy xác suất là
1
C2nn
n +1
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
14
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ử ∃s1 , s2 ∈ A sao cho f ( s1 ) = f ( s2 ) = d . Suy ra d phủ 2 ô vuông ở
dưới s1 và s2 . Suy ra s1 và s2 nằm cạnh nhau (Hình 9), như vậy khi đó ta có
thể đặt thêm 1 domino phủ lên s1 và s2 (vô lý). Vậy f là đơn ánh, suy ra
A ≤ B hay B ≥ 11 . N hư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ý).
15
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.
ii.
iii.
f ( x, y ) là số tự nhiên với mọi ( x, y ) ∈ M
n
f ( x, y) = n − 1 với mọi
x thỏa mãn 1 ≤ x ≤ n
N ếu f ( x1 , y1 ) f ( x2 , y2 ) > 0 thì ( x1 − x2 )( y1 − y2 ) ≥ 0
y =1
Lời giải:
Có kết luận Cnn −−11 giá trị của hàm f . Ta coi một hàm f trên M như
2
một ma trận M f = ( si , j ) với n hàng và n cột sao cho f (i, j ) = si , 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 s1,1 tới thành phần bên phải dưới sn ,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 si , j > 0 và si +1,k > 0 thì j ≤ k vì [i − (i + 1)][ j − k ] ≥ 0 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 si , j nếu si , j > 0 và si .k = 0 với
j +1≤ k ≤ n .
16
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ị. N gườ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 2 − 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à Cnn −−11 (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.
2
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:
**
*
*
**
*
**
*
**
17
*
**
*
**
*
**
*
*
*
Và có 3 ma trận tương ứng là
2
0
0
0
0 1 0
0
0
0 3 0
và
0
0 3 0
0 1 0
0
3 0 0
3 0 0
3 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 Cnn−−11
2
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 = (a1 , a2 ,..., am ) là phần tử của A . Đặt s(a) là chỉ số bé nhất
thỏa mãn as ( a ) , as ( a )+1 ,..., am là các số nguyên liên tiếp. Giả sử n không thể viết
k (3k − 1)
k (3k + 1)
hoặc
với mọi số nguyên dương k . Đặt A1 là
2
2
tập con của A thỏa mãn a ∈ A1 khi và chỉ khi a1 ≤ m − s ( a ) + 1 .
dưới dạng
Chứng minh rằng A = 2 A1
Lời giải:
thỏa mãn a ∈ A1 ' khi và chỉ khi
Gọi A1 ' là tập con của A
a1 > m − s ( a ) + 1 . Khi đó ta có A = A1 ∪ A1 ' . Ta sẽ chứng minh tồn tại 1 song
ánh đi từ A1 vào A1 ' . Thật vậy, ta định nghĩa ánh xạ như sau:
a = (a1 , a2 ,..., am ) → a ' = (a2 ,..., am−a , am−a +1 + 1,..., am + 1) (*)
1
1
(Thực hiện chia đều a1 cho a1 phần tử cuối của a , và xóa đi a1 , 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ó a1 = 3, m = 6 và s(a) = 3 ,
do đó a ∈ A1 . Khi đó qua phép ánh xạ ở trên, ta được a ' = (5,7,9,10,11) . Ta có
18
thể quan sát dễ dàng trên biều đồ Young (. N hư trên hình 12, ta xóa 3 điểm
trong cột thứ nhất (vì a1 = 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 ' ∈ A1 '
ii.
Phép ánh xạ (*) là đơn ánh
iii.
Phép ánh xạ (*) là toàn ánh
Cm (i):
Ta có m − a1 + 1 ≥ s ( a ) (vì a ∈ A1 ). Do s(a) là chỉ số nhỏ nhất để
as ( a ) , as ( a )+1 ,..., am là các số tự nhiên liên tiếp, suy ra ta có am−a +1 + 1,..., am + 1 là
các số tự nhiên liên tiếp.
1
N ếu m − a1 + 1 ≥ 3 thì ánh xạ (*) cho:
a ' = (a2 ,..., am − a , am −a +1 + 1,..., am + 1) = (a1' ,..., am' −1 )
1
1
a1' = a2 ≤ am' −a −1 = am−a ≤ am−a +1 − 1 = am' −a − 2 . Suy ra s(a ') = m − a1 .
1
1
1
1
Khi đó m '− s ( a ') + 1 = ( m − 1) − ( m − a1 ) + 1 = a1 , lại có a2 > a1 nên suy ra
a = a2 > m '− s (a ') + 1 . Vậy a ' ∈ A1' .
'
1
m − a1 + 1 = 2
thì
ánh
xạ
N ếu
a ' = (a2 + 1,..., am + 1) = (a1' ,..., am' −1 ) và s (a ') = 1, m ' = m − 1 .
a1' = a2 + 1 > m '− s (a ') + 1 = m − 1 = a1 + 1 . Vậy a ' ∈ A1' .
19
(*)
cho
Khi đó do
N ếu m − a1 + 1 = 1 , suy ra s ( a ) = 1 . Khi đó ta có a1 , a2 ,..., am là m số tự
nhiên
liên
tiếp.
Khi
đó
ta
có
m(m − 1)
m(m − 1) m(3m − 1)
n = ma1 +
= m2 +
=
(vô lý với giả thiết).
2
2
2
Vậy a ' ∈ A1' và s(a ') = m − a1 (1)
Chứng minh ii: ta sử dụng pp phản chứng.
Giả sử ∃a ≠ b, a, b ∈ A1 sao cho qua phép ánh xạ (*) có ảnh là a ', b ' ∈ A1'
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 = (b1 , b2 ,..., bm ) . Ta có
m − a1 = s ( a ') = s (b ') = m − b1 (theo 1). Suy ra a1 = b1 , 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
a ' = (a1' , a2' ,..., am' −1 ) ∈ A1' . 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 a1' 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 ∈ A1 .
Để ý dạng tổng quát của a như sau:
a = (m − s (a '), a1' ,..., as' ( a ') −1 , as' ( a ') − 1,..., am' −1 − 1) (dễ thấy có cái này thì
s (a ') − 1 ≥ 1 để 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 ' ∈ A1' nên a1' > (m − 1) − s(a ') + 1 = m − s(a ') và
as' ( a ')−1 ≤ as' ( a ') − 2 . Khi đó ánh xạ ngược của (*):
a = (a1 , a2 ,..., am ) = (m − s (a '), a1' ,..., as' ( a ')−1 , as' ( a ') − 1,..., am' −1 − 1)
Lại có as' ( a ') , as' ( a ')+1 ,..., am' −1 là các số tự nhiên liên tiếp nên as ( a ')+1 = as' ( a ') − 1
,…, am = am' −1 − 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 s (a ') + 1 ( s(a) ≤ s(a ') + 1 )
Kết hợp lại ta có: a1 = m − s ( a ') ≤ m − s ( a ) + 1 , suy ra a ∈ A1
N ếu s ( a ') = 1 . Vì a ' ∈ A1' nên a1' > (m − 1) − s(a ') + 1 = m − 1 . N ếu a1' = m
(m − 2)(m − 1)
n = a1' + ... + am' −1 = m + ... + (m + m − 2) = m(m − 1) +
2
thì ta có
(m − 1) [3(m − 1) + 1]
=
2
(vô lý).
20
Vậy a1' ≥ m + 1 suy ra. Khi đó ánh xạ ngược của (*) cho ta có
a = (m − 1, a1' − 1,..., a1m−1 − 1) thỏa mãn a1 = m − 1 ≤ m − s (a ) + 1 (do s(a) ≤ 2 ).
Vậy ánh xạ ngược của (*) cho ra a ∈ A1
Vậy phép ánh xạ (*) là song ánh, suy ra A1 = A1' , suy ra A = 2 A1
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 ( a1 , a2 ,..., ak ) chập k của n số nguyên dương đầu tiên, mà mỗi
chỉnh hợp ( a1 , a2 ,..., ak ) 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à as > at
2. Tồn tại s thuộc {1, 2,...,k } sao cho ( as − s ) không chia hết cho 2
Lời giải:
Gọi A = {( a1 , a2 ,..., ak )} với k ≤ n , ai = {1, 2,..., n} với mọi i = 1, 2,..., k .
Xét tập B ⊂ A thỏa mãn nếu ( a1 , a2 ,..., ak ) ∈ B thì ai < ai +1 với ∀i = 1,2,..., k − 1
và ai ≡ 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 ai + i ≡ 2i ≡ 0(mod 2) với
∀i = 1, 2,..., k nên ta lập ánh xạ f : B → E xác định bởi:
( ( a , a ,..., a ) ) = ( a + 1, a + 2,..., a
Với E = {( e , e ,..., e )} trong đó
f
1
2
k
1
1
2
2
k
k
+ k ) , i = 1,2..., k
2 ≤ ei ≤ n + k , ei ≡ 0(mod 2) với
∀i = 1, 2,..., k và 1 + ei < ei +1 với ∀i = 1,2,..., 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ừ ei ≡ 0(mod 2) thì ei − i ≡ i(mod 2) và từ ei < ei +1 − 1 suy ra
ei − i < ei +1 − i − 1 (hay ai < ai +1 khi đặt ai = ei − i, ai +1 = ei +1 − i − 1 ), mà
2 ≤ ei < ei +1 ≤ n + k nên 1 ≤ ai < ai +1 ≤ n với ∀i = 1,2,..., k − 1 . Từ đó, với mỗi
e = ( e1 , e2 ,..., ek ) ∈ E thì tồn tại b = ( a1 , a2 ,..., ak ) ∈ 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ư
n + k
(2)
trên ta có B = E = Cmk với m =
2
Từ (1) và (2) và A =
n!
ta có:
(n − k )!
21
D= A−E =
n!
n + k
− Cmk với m =
(n − k )!
2
N hậ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 )
2
0
n
1 2
n
2
n
2
+ ... + ( Cnn ) = C2nn
2
Hướng dẫn:
Ta thấy C2nn 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: N hó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ó Cnk cách chọn, sau đó chọn n − k đối tượng từ
nhóm 2: có Cnn−k = Cnk cách chọn. Theo quy rắc nhân có ( Cnk ) cách chọn ra n
2
đố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:
n
k (C )
k
n
k =0
2
= nC2nn−−11
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:
n
2 C C
k
k =0
k
n
n−k
2
n−k
= C2nn+1
HD:
Xét bài toán “chọn n số từ 2n+1 số khác nhau” theo 2 cách:
Cách 1: chia 2n+1 số thành n cặp gồm 2 số và 1 số x
• Bước 1: chọn ra k cặp, từ mỗi cặp này chọn ra một số. Có Cnk cách
chọn ra k cặp và có 2 cách chọn ra 1 số trong mỗi cặp. Vậy theo quy
tắc nhân có 2 k Cnk cách chọn theo bước 1
22
n−k
• Bước 2: chọn
cặp trong n − k cặp còn lại, ngoài ra số x sẽ
2
được chon nếu n − k lẻ và không chọn được thêm x nếu n − k
chẵn. Khi đó có C
n−k
2
n−k
cách chọn trong bước 2
n−k
2
n−k
Theo quy tắc nhân có C .Cnk .2k cách chọn ra n số trong mỗi lần
chọn. Cho k = 0,1, 2,..., n ta có được tổng ở vế trái đẳng thức.
Cách 2: chọn theo tổ hợp chập n của 2n + 1 phần tử: có C2nn+1 cách chọn
Vậy ta có đpcm
Bài 4:CMR:
n! = n nCn0 − (n − 1) n Cn1 + (n − 2) n Cn2 − (n − 3) n Cn3 + ... + (−1) n−1 Cnn−1
HD:
Xét X là tập toàn ánh từ tập M = {1,2,...,n} vào chính nó.
Mỗi toàn ánh từ M vào chính nó là một hoán vị của M . Suy ra số các
toàn ánh từ M vào M là X = n! (*)
Mặt khác: đặt Hom(M,M)= tập các ánh xạ từ M vào M. Suy ra
Hom( M , M ) = n n
Đặt Ai = { f ∈ Hom( M , M ) | i ∈ f ( M )} với i = 1, 2,..., n . Khi đó:
n
X = Hom( M , M ) \ Ai X = n n −
i =1
Ta có
n
A
i =1
i
n
A
i =1
i
(1)
= Cn1 (n − 1) n − Cn2 (n − 2) n + Cn3 (n − 3) n + ... + (−1) n−1 Cnn−1
(2)
Từ (1) và (2) ta có :
X = n nCn0 − (n − 1)n Cn1 + (n − 2)n Cn2 − (n − 3)n Cn3 + ... + (−1)n−1 Cnn−1
Từ (*) và (**) ta có đpcm
n
2
C C
i =0
i
n
i
n −i
2n−2i = C2nn
3. Dùng song ánh để tính tổng các phần tử của một tập
23
(**)
Bài 1:Cho tập A = {1,2,..., n} . Mỗi tập con không rỗng của A ta xác định duy
nhất một tổng đan dấu như sau: sắp xếp các phần tử của A theo thứ tự tăng
dần sau đó gán luân phiên các dấu + và – sao cho phần tử lớn nhất mang dấu
cộng. Tính tổng các tổng đan dấu trên
HD:
Coi tập rỗng có tổng bằng 0
Với các tập Ai khác rỗng ta chia chúng làm 2 loại: tập A1 chứa các tập
chứa phần tử n , tập A2 chứa các tập không chứa phần tử n . Khi đó tương
ứng sau là song ánh:
f : A2 → A1
Ai = {a1 > a2 > ... > ai } → f ( Ai ) = {n > a1 > a2 > ... > ai }
Khi đó tổng của tổng đan dấu của Ai và f ( Ai ) bằng n. Vì A có 2 n tập
con nên có 2n−1 cặp tập con Ai và f ( Ai ) . Suy ra tổng các tổng đan dấu bằng
n.2n−1
Bài 2: (NMO Việt Nam)
Cho tập S = {1,2,..., n} . Gọi T là tập tất cả các tập con không rỗng của
S . Với mỗi X ∈ T , gọi m( X ) là trung bình cộng các phần tử của X . Tính
m( X )
m=
T
HD:
Xét song ánh f : T → T , f (X) = {n + 1 − x} với x ∈ X
Ta thấy m( X ) + m( f ( X )) = n + 1 . Do đó:
2 m( X ) = ( m( X ) + m( f ( X )) ) = T .(n + 1) m =
n +1
2
Bài 3: Hãy tính trung bình cộng tất cả các số N = a1a2 ...an chia hết cho 99
và các chữ số của N thuộc tập {1,2,3,4,5,6,7,8}
HD:
Gọi T là tập tất cả các số dạng N . Khi đó xét tương ứng
24
f : T →T
a1...an → b1...bn
với bi = 9 − ai , i = 1, 2,..., n
Ta thấy: N + f ( N ) = 99...999 nên f ( N ) ∈ T và f là một ánh xạ. Dễ
chứng minh f là một song ánh. Khi đó:
2 N = N + f ( N ) = T .99...9
N ∈T
N ∈T
n
Suy ra TBC các số N là 99...9
= 10 − 1
n chu so 9
25
Tài liệu tham khảo
[1] TiTu
Andreescu,
Zuming
Feng;
A
path
to
combinatorics
for
undergraduates
[2] Lê Hải Châu, Giới thiệu các bài thi chọn HỌC SINH GIỎI TOÁN phổ
thông trung học toàn quốc (từ năm 1962 ñến năm 2000)
[3] N guyễn Sinh N guyên, N guyễn Văn N ho, Lê Hoàng Phò; Tuyển tập các
bài dự tuyển Olympic toán học quốc tế 1991-2001
[4] Vũ Dương Thụy, N guyễn Văn N ho; 40 năm Olympic toán quốc tế
[5] N guyễn Văn Mậu (chủ biên), Chuyên đề TOÁN RỜI RẠC và một số vấn đề
liên quan (tài liệu dùng cho lớp bồi dưỡng giáo viên THPT Chuyên – hè
2007)
[6] Tủ sách toán học và tuổi trẻ, Các bài thi Olympic toán trung học phổ
thông Việt Nam (1990 – 2006), Nxb Giáo dục (2007).
[7] Đề thi học sinh giỏi quốc gia các năm 2012,2014
[8] tai lieu\CH2.pdf
26