Tài liệu Skkn các bài toán tổ hợp trong các kỳ thi học sinh giỏi

BM 01-Bia SKKN SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI Đơn vị THPT chuyên Lương Thế Vinh Mã số: ................................ (Do HĐKH Sở GD&ĐT ghi) SÁNG KIẾN KINH NGHIỆM CÁC BÀI TOÁN TỔ HỢP TRONG CÁC KỲ THI HỌC SINH GIỎI Người thực hiện: Phạm Doãn Lê Bình Lĩnh vực nghiên cứu: - Quản lý giáo dục  - Phương pháp dạy học bộ môn: Toán  - Lĩnh vực khác: .......................................................  Có đính kèm: Các sản phẩm không thề hiện trong bản in SKKN  Mô hình  Phần mềm  Phim ảnh  Hiện vật khác Năm học: 2015 - 2016 BM02-LLKHSKKN SƠ LƯỢC LÝ LỊCH KHOA HỌC I. THÔNG TIN CHUNG VỀ CÁ NHÂN 1. Họ và tên: Phạm Doãn Lê Bình 2. Ngày tháng năm sinh: 23/04/1986 3. Nam, nữ: Nam 4. Địa chỉ: 1123, KP7, P. Long Bình, TP. Biên Hòa, Đồng Nai 5. Điện thoại: 0613930245 (nhà riêng) ; ĐTDĐ: 01683531100 6. Fax: E-mail: [email protected] 7. Chức vụ: Giáo viên 8. Đơn vị công tác: Trường THPT chuyên Lương Thế Vinh. II. TRÌNH ĐỘ ĐÀO TẠO - Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ - Năm nhận bằng: 2012 - Chuyên ngành đào tạo: Đại số và lý thuyết số III. KINH NGHIỆM KHOA HỌC - Lĩnh vực chuyên môn có kinh nghiệm: Sư phạm Toán Số năm có kinh nghiệm: 8 - Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: + Phương pháp đại lượng bất biến, đơn biến trong các bài toán tổ hợp. (2014) CÁC BÀI TOÁN TỔ HỢP TRONG CÁC ĐỀ THI HỌC SINH GIỎI Phạm Doãn Lê Bình Giáo viên trường THPT chuyên Lương Thế Vinh Tháng 4 năm 2016 Mục lục 1 Lý do chọn đề tài 2 Nội 2.1 2.2 2.3 2.4 2 dung đề tài Bài toán chia kẹo Euler . . . . . Bài toán sử dụng bất biến - đơn Bài toán cực trị tổ hợp . . . . . Bài tập rèn luyện thêm . . . . . . . . biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 7 10 12 3 Hiệu quả của đề tài 15 4 Tài liệu tham khảo 15 Trang 1 1 Lý do chọn đề tài Các bài toán tổ hợp thường xuất hiện trong các kỳ thi học sinh giỏi quốc gia và quốc tế. Qua quá trình bồi dưỡng đội tuyển học sinh giỏi tôi nhận thấy học sinh thường yếu phần toán này. Các em học sinh thường lúng túng trong việc làm bài do các bài toán khá đa dạng và thường không mẫu mực. Do đó tôi tổng hợp một số bài tập tổ hợp trong các đề thi chọn đội tuyển học sinh giỏi quốc gia của các tỉnh, đề thi học sinh giỏi quốc gia và quốc tế theo một số phương pháp quen thuộc mà học sinh đã được học là: quy tắc đếm, phương pháp đơn biến, bất biến và phương pháp cực hạn nhằm tạo nguồn tài liệu cho học sinh quen thuộc hơn với một số bài toán tổ hợp trong các kỳ thi để có kết quả thi tốt hơn. 2 Nội dung đề tài 2.1 Bài toán chia kẹo Euler Có n chiếc kẹo giống nhau chia cho m em bé. Hỏi có tất cả bao nhiêu cách chia kẹo? Số nghiệm của bài toán trên cũng là số nghiệm của bài toán: Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + · · · + xm = n (m, n ∈ N). m−1 Đáp số cho hai bài toán trên đều là Cm+n−1 . Từ bài toán này, ta có thể phát triển cho các trường hợp khác như sau: 1) Số nghiệm nguyên dương của phương trình x1 + x2 + · · · + xm = n (m, n ∈ N và m ≤ n) m−1 là Cn−1 . 2) Cho các số tự nhiên n, λ1 , λ2 , . . . λm . Số nghiệm nguyên của phương trình x1 + x2 + · · · + xm = n thỏa mãn xi ≥ λi , ∀i = 1, m bằng với số nghiệm nguyên không âm của phương trình (x1 − λ1 ) + (x2 − λ2 ) + · · · + (xm − λm ) = n − (λ1 + λ2 + · · · + λm ). m Điều kiện có nghiệm là n − λi ≥ 0. i=1 Trang 2 3) Số nghiệm nguyên không âm của bất phương trình x1 + x2 + · · · + xm ≤ n (m, n ∈ N) bằng với số nghiệm nguyên không âm của phương trình x1 + x2 + · · · + xm + xm+1 = n (m, n ∈ N) m là Cm+n . Ví dụ 1. (Chọn đội tuyển QG của Đồng Nai 2014 - 2015, ngày thứ nhất) Một số tự nhiên được gọi là “số may mắn” nếu tổng các chữ số của nó là 7. Gọi a1 , a2 , . . . , an , . . . là dãy tất cả các “số may mắn” được sắp xếp theo thứ tự tăng dần. Hỏi : a) Số 2014 là số hạng thứ mấy của dãy? b) Số hạng a325 là số nào? Giải: Xét dãy số may mắn a1 , a2 , . . . , an , trong đó a1 = 7 và an là số lớn nhất có k chữ số. Khi đó ta coi các số có ít hơn k chữ số trong dãy là số có k chữ số với các chữ số đầu tiên bằng 0. Ví dụ 7 = 00 . . . 0 7 ; 16 = 00 . . . 0 16 k−1 chữ số 0 k−2 chữ số 0 Vậy số các số có trong dãy chính là số nghiệm nguyên không âm của phương trình x1 + x2 + · · · + xk = 7. a) Để biết 2014 là số hạng thứ mấy của dãy thì ta xét dãy số may mắn a1 , a2 , . . . , an , trong đó a1 = 7 và an = 1600. Khi đó n bằng số nghiệm nguyên không âm của phương trình x1 + x2 + · · · + x4 = 7 x1 ≤ 1 Ta giải phương trình trên trong hai trường hợp x1 = 0 và x1 = 1 thì được 2 2 n = C9 + C8 = 64. Từ đó suy ra số 2005 là số hạng thứ 65 và số 2014 là số hạng thứ 66 của dãy. b) Ta nhận thấy với k = 5 thì n = 330. Do đó số hạng thứ 330 là số 70000. Từ đó đếm ngược tại ta có a329 = 61000; a328 = 60100; a327 = 60010; a326 = 60001; a325 = 52000. Ví dụ 2. (Chọn đội dự tuyển QG của Đồng Nai 2015 - 2016) Một xâu nhị phân có độ dài n là một dãy có dạng a1 a2 . . . an , trong đó ai ∈ {0; 1} với i = 1, n. Hỏi có bao nhiêu xâu nhị phân có độ dài bằng 40, đồng thời trong xâu nhị phân đó có ít nhất 3 chữ số 0 và sau mỗi chữ số 0 có ít nhất 7 chữ số 1. Trang 3 Giải: Nếu trong xâu có k số 0 thì sẽ có ít nhất 7k số 1. Do đó ta có k + 7k ≤ 40, suy ra k ≤ 5. Giả sử trong xâu có k số 0 (3 ≤ k ≤ 5). Đặt x0 là số các số 1 đứng bên trái số 0 đầu tiên, xi là số các số 1 đứng giữa số 0 thứ i và thứ i + 1 với i = 1, 2, . . . , k − 1 và xk là số các số 1 đứng bên phải số 0 thứ k. Khi đó ta có x0 + x1 + · · · + xk = 40 − k (∗) x1 , x2 , . . . xk ≥ 7. Đặt yi = xi − 7 với i = 1, k. Khi đó số nghiệm nguyên không âm của (*) chính là số nghiệm nguyên không âm của phương trình x0 + y1 + y2 + · · · + yk = 40 − 8k(1). k Số nghiệm nguyên không âm của (1) là C40−7k . Vậy số các xâu nhị phân thỏa yêu cầu bài toán là: 5 k 3 4 5 C40−7k = C19 + C12 + C5 = 1465. k=3 Ví dụ 3. (VMO-2012) Cho một nhóm gồm 5 cô gái, kí hiệu là G1 , G2 , G3 , G4 , G5 và 12 chàng trai. Có 17 chiếc ghế được sắp thành một hàng ngang. Người ta xếp nhóm người đã cho ngồi vào các chiếc ghế đó sao cho các điều kiện sau được đồng thời thỏa mãn: a) Mỗi ghế có đúng một người ngồi; b) 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 ; c) Giữa G1 và G2 có ít nhất 3 chàng trai; d) 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 xếp như vậy? (Hai cách xếp được coi là khác nhau nếu tồn tại một chiếc ghế mà người ngồi ở chiếc ghế đó trong hai cách xếp là khác nhau). Giải: Gọi số chàng trai ngồi bên trái của cô gái G1 là B1 ; số chàng trai ngồi giữa cô gái Gi và Gi+1 là Bi+1 với i = 2, 5 và số chàng trai ngồi bên phải của cô gái G5 là B6 . Theo đề bài, ta có hệ phương trình sau:   B1 + B2 + B3 + B4 + B5 + B6 = 12 B2 ≥ 3  1 ≤ B5 ≤ 4 Trang 4 Đặt B3 = B3 − 3 và B5 = B5 − 1, ta có hệ phương trình mới như sau: B1 + B2 + B3 + B4 + B5 + B6 = 8 B5 ≤ 3 Số cách xếp chỗ ngồi của các cô gái bằng với số nghiệm nguyên không âm của hệ phương trình trên. Áp dụng bài toán chia kẹo Euler với các trường hợp B5 nhận lần lượt các giá trị 0, 1, 2, 3 ta sẽ có kết quả là 4 4 4 4 C12 + C11 + C10 + C9 = 1161 (cách). Tuy nhiên, ứng với mỗi trường hợp ngồi của các cô gái thì 12 chàng trai có thể đổi vị trí cho nhau, do đó số cách xếp cho ngồi cho tất cả mọi người thỏa yêu cầu bài toán sẽ là 12!.1161 cách. Ví dụ 4. (Trường Đông Toán học miền Nam, 12-2013) Cho n > 2 là một số nguyên dương. Xét tập hợp các đường đi ngắn nhất trên lưới nguyên từ điểm A(0; 0) đến điểm B(n; n). Một đường đi như thế sẽ tương ứng với một dãy gồm n lệnh T (lên trên) và n lệnh P (sang phải). Trong dãy đó, một cặp lệnh (T, P) kề nhau được gọi là một bước chuyển (lưu ý, cặp (P, T) không được gọi là bước chuyển). Ví dụ dãy PTTPTPPT có 2 bước chuyển. Hãy tìm số các đường đi ngắn nhất từ A đến B có đúng a) 1 bước chuyển; b) 2 bước chuyển. Giải: a) Đường đi ngắn nhất trên lưới nguyên từ điểm A(0; 0) đến điểm B(n; n) là n bước T và n bước P. Đường đi ngắn nhất từ A đến B có đúng 1 bước chuyển thì phải có dạng PP ...P TT ...T PP ...P TT ...T x1 x2 x3 x2 trong đó x1 , x2 , x3 , x4 là nghiệm nguyên không âm của hệ phương trình   x2 + x4 = n (1)   x1 + x3 = n (2)  x3 ≥ 1   x2 ≥ 1 Áp dụng bài toán chia kẹo Euler, ta có số nghiệm nguyên không âm của 1 1 phương trình (1), (2) lần lượt là Cn , Cn . Do đó, số các đường đi có thể 1 2 lập được thỏa yêu cầu bài toán là Cn . Trang 5 b) Đường đi ngắn nhất từ A đến B có đúng 1 bước chuyển thì phải có dạng PP ...P TT ...T PP ...P TT ...T PP ...P TT ...T x1 x2 x3 x4 x5 x6 trong đó x1 , x2 , x3 là nghiệm nguyên không âm của hệ phương trình   x2 + x4 + x6 = n (3) x1 + x3 + x5 = n (4)  xi ≥ 1 với i = 2, 5 Rõ ràng hệ phương trình trên chỉ có nghiệm khi n ≥ 2. Áp dụng bài toán chia kẹo Euler, ta có số nghiệm nguyên không âm của phương trình (3), 2 2 (4) lần lượt là Cn , Cn . Do đó, số các đường đi có thể lập được thỏa yêu 2 2 cầu bài toán là Cn . Ví dụ 5. (VMO - 2014) Trong một đa giác đều có 103 cạnh, 79 đỉnh của đa giác được tô màu đỏ, 24 đỉnh còn lại của nó được tô màu xanh. Gọi A là số đỉnh màu đỏ kề nhau, B là số đỉnh màu xanh kề nhau. Tìm a) tất cả các giá trị có thể của cặp (A, B); b) số cách tô màu các đỉnh của đa giác sao cho B = 14 , biết rằng hai cách tô được coi là giống nhau nếu chúng có thể nhận được từ nhau qua phép quay quanh tâm đường tròn ngoại tiếp của đa giác. Giải: a) Giả sử có tất cả k đoạn mà mỗi đoạn gồm các toàn đỉnh màu đỏ liên tiếp. Ký hiệu x1 , x2 , . . . , xk là số các đỉnh màu đỏ trong mỗi đoạn này. Khi đó ta có k xi = 79, xi ≥ 1. i=1 Như vậy cũng phải có đúng k đoạn màu xanh nằm giữa những đoạn màu đỏ này. Ký hiệu y1 , y2 , . . . , yk là số các đỉnh màu xanh trong mỗi đoạn này. Khi đó ta có k yi = 24, yi ≥ 1. i=1 k Khi đó A = k (xi − 1) = 79 − k và B = i=1 (yi − 1) = 24 − k. Vậy giá trị i=1 của A và B chỉ phụ thuộc vào k. Ta thấy k có thể nhận bất cứ giá trị nào từ 1 đến 24, do đó A và B có thể nhận 24 cặp giá trị tương ứng. Trang 6 b) Để B = 14 thì theo câu a) ta cần tô màu sao cho có đúng 10 đoạn gồm toàn các đỉnh đỏ nằm xen kẽ với 10 đoạn gồm toàn các đỉnh xanh. Xét hệ phương trình 10 10 xi = 79, i=1 yi = 24, i=1 trong đó xi , yi là các số nguyên dương. Ta cố định một đỉnh của đa giác, ví dụ gọi đỉnh đó là O. Với mỗi bộ nghiệm (x1 , x2 , . . . , x10 ) và (y1 , y2 , . . . , y10 ) của hệ, ta tô màu bắt đầu từ đỉnh O, x1 đỉnh liên tiếp màu đỏ (bao gồm cả đỉnh O) tiếp theo là y1 đỉnh màu xanh, rồi đến x2 đỉnh đỏ và y2 đỉnh xanh, ... Dễ thấy tập S gồm tất cả các cách tô màu như trên vét hết các cách tô màu mà B = 14. Ta cần xét xem trong số các cách tô màu thuộc S có bao nhiêu cách tương đương với nhau (tức là nhận được bằng cách quay quanh tâm). Ta có một nhận xét quen thuộc: số đỉnh đa giác 103 là số nguyên tố nên khi quay đa giác quanh tâm luôn có ít nhất 1 đỉnh được quay đến 1 đỉnh có màu khác với nó. Như vậy mỗi cách tô màu trong S tương đương với 9 cách tô màu khác, tương ứng với việc hoán vị vòng quanh cả hai bộ nghiệm (x1 , x2 , . . . , x10 ) và (y1 , y2 , . . . , y10 ). Số phần tử của tập S là 1 9 9 9 9 C78 .C23 . Do đó tổng số cách tô màu thỏa mãn đề bài là C78 .C23 . 10 2.2 Bài toán sử dụng bất biến - đơn biến Ví dụ 6. (IMO Shortlist 2014 - Iran) Cho 2m tờ giấy. Trên mỗi tờ giấy đều ghi số 1. Ta thực hiện hoạt động sau: rút ra 2 tờ giấy bất kỳ, nếu số được ghi trên hai tờ giấy là a, b thì ta xóa 2 số đó đi và thay vào là a + b ở cả hai tờ giấy đó. Chứng minh sau m2m−1 bước thực hiện như vậy thì tổng các số trên các tờ giấy là một số lớn hơn hoặc bằng 4m . Giải: Cho Pk và Sk lần lượt là tích và tổng của các số trên các tờ giấy ở bước thứ k. Giả sử tại bước thứ k + 1, số a và b được thay thế bằng a + b. Trong tích của các số, số ab đã được thay bằng (a + b)2 , còn những thừa số còn lại không thay đổi. Do (a + b)2 ≥ 4ab nên ta có Pk+1 ≥ 4Pk . Bắt đầu với P0 = 1, ta dùng quy nạp thì suy ra Pk ≥ 4k với mọi số nguyên k ≥ 0. Từ đó suy ra m−1 Pm2m−1 ≥ 4m2 m = (2m )2 . Áp dụng bất đẳng thức AM - GM, ta có: Sm2m−1 ≥ 2m . 2m Pm2m−1 ≥ 2m .2m = 4m . Ví dụ 7. (IMO Shortlist 2011) Cho n là một số nguyên dương. Cho 1 cái cân thăng bằng và n quả cân có khối lượng lần lượt là 20 , 21 , . . . , 2n−1 . Đầu Trang 7 tiên ta lấy 1 quả cân và đặt lên đĩa cân bên trái. Sau đó, ta lần lượt lấy từng quả cân và đặt lên đĩa cân bên trái hoặc bên phải sao cho đĩa cân bên phải không bao giờ nặng hơn đĩa cân bên trái. Đến khi các quả cân được sắp hết lên cân thì dừng lại. Tính số cách sắp có thể. Giải: Gọi f (n) là số cách xếp n quả cân lên đĩa thỏa yêu cầu bài toán, với n ≥ 1. Đầu tiên, chúng ta cần để ý: • Nếu lần sắp thứ nhất, ta lấy quả cân nặng 20 thì ta chỉ có 1 cách sắp duy nhất là để nó lên đĩa cân bên trái. • Nếu quả cân nặng 20 được sắp vào một lần bất kì nào khác lần thứ nhất thì ta có thể bỏ nó vào đĩa cân bên trái hoặc bên phải đều được vì khối lượng của các quả cân ở đĩa trái luôn lớn hơn đĩa phải ít nhất là 2. Do đó, ứng với một cách xếp với bộ các quả cân 21 , 22 , . . . , 2n−1 thì ta có 2n − 1 cách xếp quả cân 20 vào một lượt bất kì nào đó. Đồng thời, ta cần để ý rằng, số cách xếp của bộ các quả cân 21 , 22 , . . . , 2n−1 bằng với số cách xếp của bộ các quả cân 20 , 21 , . . . , 2n−2 . Vậy f (n) = (2n − 1)f (n − 1). Do f (1) = 1 và dùng truy hồi, ta có f (n) = (2n − 1).(2n − 3) . . . 5.3.1 với mọi n ≥ 1. Ví dụ 8. (Đề thi chọn đội tuyển tham dự VMO 2014 THPT chuyên Khoa Học Tự Nhiên, vòng 1) Ta xếp một hoán vị của (1, 2, 3, . . . , 2014) lên vòng tròn và kí hiệu các số bởi a1 , a2 , a3 , . . . , a2014 theo chiều kim đồng hồ. Quy ước a2015 = a1 và a0 = a2014 . Gọi N là số các chỉ số 1 ≤ i ≤ 2014 sao cho hoặc ai−1 > ai > ai+1 hoặc ai−1 < ai < ai+1 . Tìm tất cả các giá trị có thể có của N. Giải: Gọi tập các chỉ số thỏa mãn là T , tập còn lại là S. Xét 2 bộ số (ai−2 , ai−1 , ai , ai+1 , ai+2 ) và (aj−2 , aj−1 , ai , aj+1 , aj+2 ) với i, j = 1, 2014 và quy ước a2015 = a1 , a2016 = a2 , a−1 = a2013 và a0 = a2014 . Khi đó ta đổi ai thành aj thì sẽ có các tình huống sau xảy ra: • Nếu hai bộ số (ai−1 , ai ), ai , ai+1 cùng đổi dấu so sánh (>, <) thì chỉ số i không thay đổi tập hợp của nó, còn chỉ số i − 1 và i + 1 sẽ thay đổi tập hợp của nó. Suy ra hiệu của T và S sẽ thay đổi 2 hoặc −2. • Nếu bộ số (ai−1 , ai ) đổi dấu so sánh còn bộ số ai , ai+1 không đổi dấu so sánh thì chỉ số i + 1 không thay đổi tập hợp của nó, còn chỉ số i, i − 1 sẽ thay đổi tập hợp của nó. Suy ra hiệu của T và S sẽ thay đổi 2 hoặc −2. Trang 8 • Nếu bộ số (ai−1 , ai ) không đổi dấu so sánh còn bộ số ai , ai+1 đổi dấu so sánh thì chỉ số i − 1 không thay đổi tập hợp của nó, còn chỉ số i, i + 1 sẽ thay đổi tập hợp của nó. Suy ra hiệu của T và S sẽ thay đổi 2 hoặc −2. • Nếu cả hai bộ số (ai−1 , ai ), ai , ai+1 cùng không đổi dấu so sánh thì các chỉ số i − 1, i, i + 1 vẫn giữ nguyên trong tập hợp của nó. Suy ra hiệu của T và S không thay đổi. Lí luận tương tự cho bộ số (aj−2 , aj−1 , ai , aj+1 , aj+2 ) ta cũng thu được kết quả như trên. Qua các trường hợp trên ta thấy hiệu của T và S là bất biến mod 2. Ban đầu xếp các số sao cho ai = i với i = 1, 2014 thì ta thấy |T | = 2012 và |S| = 2 do đó |T | luôn là số chẵn. Dễ thấy |T | không thể bằng 2014 vì nếu ai = 1 thì i ∈ T . / Giả sử |T | = k là một số chẵn trong đoạn [2; 2012] thì ta có thể xếp các số theo thứ tự như sau: 1, 2, 3, . . . , k, k + 3, k + 2, k + 5, k + 4, k + 7, . . . , 2012, 2013, 2014, k + 1 thì ta thấy có đúng k nhóm số thỏa yêu cầu bài toán là (1, 2, 3), (2, 3, 4), . . . , (k − 1, k, k + 3), (2014, k + 1, 1). Nếu ta sắp xếp các số theo thứ tự sau 1, 2013, 3, 2011, 5, 2009, . . . 1009, 1007, 1008, 1006, . . . , 6, 2010, 4, 2012, 2, 2014 thì rõ ràng không có nhóm số nào thỏa mãn yêu cầu bài toán. Từ đó suy ra các giá trị mà N có thể nhận được là các số chẵn thuộc đoạn [0, 2012]. Ví dụ 9. (IMO Shortlist 2014 - Croatia) Cho số dương n. Xét bàn cờ kích thước n × n được chia thành n2 hình vuông đơn vị. Ta gọi trạng thái của n quân xe trên bàn cờ là "hạnh phúc" nếu mỗi dòng và mỗi cột chỉ chứa đúng một quân xe. Tìm số nguyên dương k lớn nhất sao cho với mỗi trạng thái hạnh phúc của các quân xe ta đều có thể tìm được 1 hình vuông kích thước k × k mà không chứa bất cứ quân xe nào trong k 2 hình vuông đơn vị của nó. Giải: Cho k là một số nguyên dương. • Giả sử k 2 < n. Ta sẽ chứng minh tồn tại một hình vuông k × k mà không chứa bất cứ một quân xe nào. Thật vậy, ở một trạng thái hạnh phúc thì bàn cờ chứa đúng n quân xe. Ta loại đi n − k 2 dòng nằm tận cùng bên trên và n − k 2 cột nằm ở tận cùng bên trái. Khi đó phần còn lại sẽ là một ô vuông kích thước k 2 × k 2 có chứa đúng 2k 2 − n quân xe. Ta chia hình vuông trên thành k 2 hình vuông kích thước k × k. Do 2k 2 − n = k 2 + (k 2 − n) < k 2 − 1 Trang 9 nên trong k 2 hình vuông kích thước k × k sẽ có ít nhất 1 hình không chứa bất kì quân xe nào cả. • Giả sử k 2 = n. Ta sẽ chứng minh mọi hình vuông kích thước k × k đều chứa ít nhất một quân xe với một trường hợp hình vuông n × n có trạng thái hạnh phúc của các quân xe. Ta đánh số các cột và dòng như hình minh họa dưới đây Khi đó, kí hiệu (r; c) là tọa độ của một ô vuông nhỏ trong hình với r là tọa độ dòng và c là tọa độ cột. Ta sẽ xếp các quân xe vào các ô có tọa độ sau: (0; 0), (1; k), . . . , (k − 1; k(k − 1)), (k; 1), (k + 1; 1 + k), . . . , (k + (k − 1); 1 + k(k − 1)), . . . (k(k − 1); k − 1), (k(k − 1) + 1; k − 1 + k) . . . , (k 2 − 1; k 2 − 1) Khi đó hình vuông n × n sẽ có trạng thái hạnh phúc và một hình vuông k × k bất kì luôn có chứa 1 quân xe. Vậy số k lớn nhất đạt được chính là n − 1 , trong đó kí hiệu n là phần nguyên của n. 2.3 Bài toán cực trị tổ hợp Ví dụ 10. (BxMO 1 2015) An arithmetic progression is a set of the form {a, a + d, . . . , a + kd}, where a, d, k are positive integers and k ≥ 2. Thus an arithmetic progression has at least three elements and the successive elements have difference d, called the common difference of the arithmetic progression. Let n be a positive integer. For each partition of the set {1, 2, . . . , 3n} into arithmetic progressions, we consider the sum S of the respective common 1 BxMO = Benelux Mathematical Olympiad. Benelux là vùng gồm ba nước Bỉ (Belgium), Hà Lan (Netherlands) và Luxembourg và Benelux là tên viết tắt các ký tự đầu của ba nước trong vùng này Trang 10 differences of these arithmetic progressions. What is the maximal value S that can attain? (A partition of a set A is a collection of disjoint subsets of A whose union is A.) Một cấp số cộng là một tập hợp có dạng {a, a + d, . . . , a + kd}, với a, d, k là các số nguyên dương và k ≥ 2. Vì vậy một cấp số cộng có ít nhất ba phần tử và các phần tử liên tiếp nhau có sự sai khác là d, số được gọi là công sai của cấp số cộng. Cho n là một số nguyên dương. Với mỗi phần của tập hợp {1, 2, . . . , 3n} đối với cấp số cộng, ta xét tổng của các công sai riêng của những cấp số cộng này. Giá trị lớn nhất của S có thể thu được là bao nhiêu? (Một phần của tập hợp A là tập hợp các tập con rời nhau của A và hợp của chúng là A). Giải: Giả sử ta chia cấp số trên thành N cấp số cộng có độ dài li và N công sai là di , trong đó 1 ≤ i ≤ N và li ≥ 3. Do li = 3n và li ≥ 3 nên i=1 N ≤ n. Ký hiệu ai , bi lần lượt là phần tử lớn nhất, nhỏ nhất của cấp số thứ i. Ta có N N N di ≤ 2 i=1 N (li − 1)di ≤ i=1 ai − i=1 bi i=1 Ta lại có N bi ≥ 1 + 2 + · · · + N = i=1 N (N + 1) , 2 N ai ≤ (3n − N + 1) + · · · + 3n = i=1 và do đó N (6n − N + 1) , 2 N di ≤ N (3n − N ) ≤ 2n2 2 i=1 hay N di ≤ n2 . i=1 Dấu bằng xảy ra khi ta chia dãy cấp số cộng ban đầu thành n dãy cấp số cộng {1, n + 1, 2n + 1}, . . . , {n, 2n, 3n} với công sai của mỗi dãy là n. Ví dụ 11. (BxMO 2014) Let k ≥ 1 be an integer. We consider 4k chips, 2k of which are red and 2k of which are blue. A sequence of those 4k chips can be transformed into another sequence by a so-called move, consisting of interchanging a number (possibly one) of consecutive red chips with an equal number of consecutive blue chips. For example, we can move from rbbbrrrb Trang 11 to rrrbrbbb where r denotes a red chip and b denotes a blue chip. Determine the smallest number n (as a function of k) such that starting from any initial sequence of the 4k chips, we need at most n moves to reach the state in which the first 2k chips are red. Cho k ≥ 1 là một số nguyên. Xét 4k thẻ trong đó 2k thẻ được sơn màu đỏ, 2k thẻ được sơn màu xanh. Một dãy của 4k thẻ này có thể được được chuyển thành dãy mới bằng cách di chuyển một nhóm (có thể bằng 1) các thẻ liên tiếp màu đỏ với một nhóm (có cùng số lượng) các thẻ liên tiếp màu xanh. Ví dụ, chúng ta có thể chuyển dãy rbbbrrrb thành dãy rrrbrbbb với r là ký hiệu một thẻ màu đỏ và b là ký hiệu một thẻ màu xanh. Xác định số n nhỏ nhất (như là một hàm theo k) sao cho từ một dãy ban đầu bất kỳ của 4k thẻ, chúng ta cần nhiều nhất n bước di chuyển sang trạng thái là 2k thẻ đầu tiên màu đỏ. Giải: Đầu tiên chúng ta sẽ chứng minh n ≥ k. Gọi C là số thẻ màu đỏ ở ngay bên phải một thẻ màu xanh. Xét trạng thái brbr . . . brbr thì C = 2k và ở trạng thái cuối cùng cần đạt được thì C = 0. Ta thấy rằng ở mỗi lần di chuyển thì C giảm đi nhiều nhất là 2. Do đó, số lần di chuyển ít nhất để 2k = k. Do đó chuyển từ trạng thái brbr . . . brbr sang trạng thái cuối cùng là 2 n ≥ k. Bây giờ ta chứng minh n ≤ k. Chia 4k thẻ ở một trạng thái bất kì nào đó thành 2 nhóm, mỗi nhóm 2k thẻ. Nếu 2k thẻ đầu tiên có nhiều nhất là k thẻ màu xanh, còn lại là các thẻ màu đỏ thì ta chỉ cần di chuyển mỗi lần một thẻ đỏ ở nhóm bên phải và một thẻ xanh ở nhóm bên trái thì số lần đưa 2k thẻ đỏ lên vị trí đầu tiên là ít hơn k. Nếu trong 2k thẻ đầu tiên có ít nhất k + 1 thẻ màu xanh và nhiều nhất k − 1 thẻ màu đỏ thì ta di chuyển mỗi lần một thẻ màu đỏ từ nửa nhóm bên trái với một thẻ màu xanh ở nửa nhóm bên thì đến một lúc ta sẽ thu được 2k thẻ cuối cùng màu đỏ, 2k thẻ đầu tiên màu xanh và khi đó ta chỉ cần thêm 1 lần chuyển 2k thẻ đỏ từ cuối lên đầu thì sẽ thu được trạng thái cần đạt được. Rõ ràng số lần di chuyển không lớn hơn k. Vậy ta có n ≤ k. Ta đã chứng minh được n ≥ k và n ≤ k nên suy ra n = k. 2.4 Bài tập rèn luyện thêm Bài 1. (Đề chọn đội tuyển Quảng Bình 2013 - 2014, câu 9) Cho các số nguyên dương n, k, p với k ≥ 2 và k(p + 1) ≤ n. Cho n điểm phân biệt cùng nằm trên 1 đường thẳng. Tô n điểm đó bằng 2 màu xanh, đỏ (mỗi điểm chỉ tô đúng 1 màu). Tìm số cách tô màu khác nhau, sao cho các điều kiện đồng thời xảy ra: a) Có đúng k điểm được tô bởi màu xanh. b) Giữa hai điểm màu xanh liên tiếp (tính từ trái qua phải) có ít nhất p điểm được tô màu đỏ. Trang 12 c) Ở bên phải điểm tô màu xanh cuối cùng có ít nhất p điểm được tô màu đỏ. (Hai cách tô màu được gọi là khác nhau nếu có ít nhất một điểm được tô màu khác nhau trong hai cách đó). Bài 2. (Đề chọn đội tuyển chuyên Nguyễn Du, Đắk Lắk (vòng 2) 2013 - 2014, câu 6) Cho đa giác lồi 2014 đỉnh. Một điểm P nằm trong đa giác mà không thuộc bất kì đường chéo nào của đa giác. Chứng minh rằng số tam giác có đỉnh thuộc 2014 đỉnh trên mà chứa được P (P thuộc miền trong tam giác đó) là số chẵn. Bài 3. Cho n hộp có B1 ; B2 ; . . . ; Bn nằm trên 1 hàng ngang. Tổng số bóng trong n hộp này là n quả bóng. Mỗi bước, ta có thể sử dụng 1 trong 3 quy tắc sau: 1) Nếu có ít nhất 1 quả bóng trong B1 , ta có thể chuyển 1 quả bóng từ B1 sang B2 . 2) Nếu có ít nhất 1 quả bóng trong Bn , ta có thể chuyển 1 quả bóng từ Bn sang Bn−1 . 3) Với mỗi 2 ≤ k ≤ n − 1, nếu hộp Bk có ít nhất 2 quả bóng, ta có thể chuyển 2 quả bóng từ Bk sang Bk−1 ; Bk+1 mỗi hộp 1 quả (quy ước: B0 = Bn ; Bn+1 = B1 ). Chứng minh rằng: sau một số hữu hạn bước chuyển bóng, ta có thể đưa về mỗi hộp đúng 1 quả bóng. Bài 4. Cho một bộ gồm 3 số. Ở mỗi bước, người ta chọn ra hai trong ba số của bộ, giả sử là a và b. Sau đó thay hai số a; b thành hai số a + b |a − b| √ ; √ . Hỏi sau một số hữu hạn bước, ta có thể chuyển bộ 2 2 √ √ √ 1 1; 2; 1 + 2 thành bộ 2; 2; √ được không? 2 Bài 5. Cho tập S có 2016 phần tử. Mỗi bước, ta sử dụng phép biến đổi sau: {a1 ; a2 ; . . . ; an } −→ a1 + a2 a2 + a3 an−1 + an an + a1 ; ;··· ; ; 2 2 2 2 · Giả sử rằng sau 2016 bước, ta lại thu được tập S ban đầu. Hãy chứng minh rằng mọi phần tử trong tập S là bằng nhau. Bài 6. Có 2016 quả bóng trắng trong một cái hộp. Và bên ngoài hộp đó có vô hạn quả bóng có màu là một trong ba màu: trắng, xanh hoặc đỏ. Tại mỗi bước, người ta chuyển hai quả trong hộp ra và đưa một hoặc hai quả ngoài hộp vào, theo nguyên tắc sau: Trang 13 • hai quả trắng đổi cho một quả xanh; • hai quả đỏ đổi cho một quả xanh; • hai quả xanh đổi cho một quả trắng và một quả đỏ; • một quả trắng và một quả xanh đổi cho một quả đỏ; • một quả xanh và một quả đỏ đổi cho một quả trắng; a) Giả sử rằng, sau một số hữu hạn bước, trong hộp có đúng ba quả. Chứng minh rằng: trong ba quả này có ít nhất một quả màu xanh. b) Có tồn tại hữu hạn bước mà sau bước cuối, hộp còn đúng một quả? Bài 7. Cho một bộ gồm 4 số nguyên dương. Người ta tiến hành thực hiện thuật toán sau: Tại mỗi bước, từ bộ (x; y; u; v), nếu có x > y thì thay thành bộ (x − y; y; u + v; v), nếu có x < y thì thay thành bộ (x; y − x; u; v + u). Thuật toán này dừng lại khi bộ (x; y; u; v) có x = y. Người ta bắt đầu bằng bộ (m; n; m; n) (m; n ∈ N∗ ). Chứng minh rằng: sau khi thuật toán kết thúc, ta có: trung bình cộng của hai số sau không nhỏ hơn bội chung nhỏ nhất của m; n. Bài 8. Cho a; b; c; d là bộ bốn số nguyên đôi một khác nhau. Ta định nghĩa phép biến đổi T là biến đổi bộ (x; y; z; t) có thứ tự thành bộ (x − y; y − z; z − t; t − x). Chứng minh với bộ ban đầu bất kỳ thì sau một số hữu hạn bước, ta có thể thu được bộ mới mà có ít nhất một số trong bốn số mới này lớn hơn 2016. Bài 9. Bắt đầu một bộ gồm 4 số nguyên bất kỳ, người ta thực hiện quy tắc T sau: T (a; b; c; d) − (|a − b|; |b − c|; |c − d|; |d − a|) . → Chứng minh rằng: sau một số hữu hạn bước, ta có thể thu được bộ (0; 0; 0; 0). Bài 10. Cho một số số nguyên dương trên bảng (nhiều hơn một số). Chọn ra hai số nguyên phân biệt trong chúng và thay thế bởi USCLN và BSCNN của hai số đó. Chứng minh rằng: sau một số hữu hạn bước, các số đó không thay đổi. Bài 11. Cho hai dãy số (xn ) và (yn ) có x1 = a; y1 = b; xn+1 = xn + y n 2xn .yn ; yn+1 = 2 xn + yn trong đó 0 < a < b. Tìm giới hạn của các dãy số (xn ), (yn ). Trang 14 Bài 12. Mỗi số trong dãy 20 ; 21 ; 22 ; 23 ; . . . ; 22013 ; 22014 đều được thay bằng tổng các chữ số của nó cho đến khi các số nhận được trong dãy có 1 chữ số. Chứng minh rằng trong dãy số thu được: số chữ số chẵn nhiều hơn số chữ số lẻ. 3 Hiệu quả của đề tài Học sinh có thêm kinh nghiệm trong việc xử lý các bài toán tổ hợp bằng phương pháp sử dụng nguyên lí cực hạn. 4 Tài liệu tham khảo 1. Nguyễn Thị Ngọc Ánh , “Xung quanh bài toán chia kẹo của Euler”, báo Toán học tuổi trẻ số 424 (tháng 10 năm 2012). 2. Các đề thi học sinh giỏi sưu tầm trên internet. Người thực hiện Phạm Doãn Lê Bình Trang 15 BM04-NXĐGSKKN SỞ GD&ĐT ĐỒNG NAI Đơn vị THPT chuyên Lương Thế Vinh CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc ................................, ngày tháng năm PHIẾU NHẬN XÉT, ĐÁNH GIÁ SÁNG KIẾN KINH NGHIỆM Năm học: 2015 - 2016 ––––––––––––––––– Tên sáng kiến kinh nghiệm: CÁC BÀI TOÁN TỔ HỢP TRONG CÁC KỲ THI HỌC SINH GIỎI ............................................................................................................................................... Họ và tên tác giả: Phạm Doãn Lê Bình Chức vụ: Giáo viên Đơn vị: THPT chuyên Lương Thế Vinh. Lĩnh vực: (Đánh dấu X vào các ô tương ứng, ghi rõ tên bộ môn hoặc lĩnh vực khác) - Quản lý giáo dục  - Phương pháp dạy học bộ môn: ...............................  - Phương pháp giáo dục  - Lĩnh vực khác: ........................................................  Sáng kiến kinh nghiệm đã được triển khai áp dụng: Tại đơn vị  Trong Ngành  1. Tính mới (Đánh dấu X vào 1 trong 2 ô dưới đây) - Có giải pháp hoàn toàn mới  - Có giải pháp cải tiến, đổi mới từ giải pháp đã có  2. Hiệu quả (Đánh dấu X vào 1 trong 4 ô dưới đây) - Hoàn toàn mới và đã triển khai áp dụng trong toàn ngành có hiệu quả cao  - Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng trong toàn ngành có hiệu quả cao  - Hoàn toàn mới và đã triển khai áp dụng tại đơn vị có hiệu quả cao  - Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng tại đơn vị có hiệu quả  3. Khả năng áp dụng (Đánh dấu X vào 1 trong 3 ô mỗi dòng dưới đây) - Cung cấp được các luận cứ khoa học cho việc hoạch định đường lối, chính sách: Tốt  Khá  Đạt  - Đưa ra các giải pháp khuyến nghị có khả năng ứng dụng thực tiễn, dễ thực hiện và dễ đi vào cuộc sống: Tốt  Khá  Đạt  - Đã được áp dụng trong thực tế đạt hiệu quả hoặc có khả năng áp dụng đạt hiệu quả trong phạm vi rộng: Tốt  Khá  Đạt  Phiếu này được đánh dấu X đầy đủ các ô tương ứng, có ký tên xác nhận của người có thẩm quyền, đóng dấu của đơn vị và đóng kèm vào cuối mỗi bản sáng kiến kinh nghiệm. XÁC NHẬN CỦA TỔ CHUYÊN MÔN (Ký tên và ghi rõ họ tên) THỦ TRƯỞNG ĐƠN VỊ (Ký tên, ghi rõ họ tên và đóng dấu)