Tài liệu Tài liệu tập huấn phát triển chuyên môn giáo viên trường thpt chuyên môn toán

www.VNMATH.com BỘ GIÁO DỤC VÀ ĐÀO TẠO VỤ GIÁO DỤC TRUNG HỌC CHƯƠNG TRÌNH PHÁT TRIỂN GIÁO DỤC TRUNG HỌC TÀI LIỆU TẬP HUẤN PHÁT TRIỂN CHUYÊN MÔN GIÁO VIÊN TRƯỜNG THPT CHUYÊN MÔN TOÁN (Tài liệu lưu hành nội bộ) Hà Nội, tháng 7 năm 2012 www.VNMATH.com Chủ trì biên soạn: Vụ Giáo dục Trung học Chương trình phát triển giáo dục trung học NHÓM TÁC GIẢ BIÊN SOẠN TÀI LIỆU: 1. GS.TSKH Hà Huy Khoái 2. GS.TSKH Nguyễn Văn Mậu 3. GS.TSKH Đặng Hùng Thắng 4. PGS.TSKH Vũ Đình Hòa 5. PGS.TS Nguyễn Vũ Lương 6. TS Phạm Văn Quốc 7. TS Lê Anh Vinh 8. TS Trịnh Đào Chiến www.VNMATH.com ��������������������������������������������������������������������������� ��������������������������������������������������������������������������������� ����������������������������������������������������� www.VNMATH.com Mục lục Lời nói đầu 4 Hà Huy Khoái Một số bài toán Số học - Tổ hợp 5 Nguyễn Văn Mậu Lớp các phương trình hàm Cauchy, d’Alembert và dạng toán liên quan 22 Đặng Hùng Thắng Một số lớp phương trình Diophant cơ bản 66 Vũ Đình Hoà Bài toán tô màu đồ thị 105 Nguyễn Vũ Lương Một cách tiếp cận tới bài toán tổ hợp 134 Trịnh Đào Chiến Một số dạng bất phương trình hàm 188 Phạm Văn Quốc Phương trình Pell 207 Lê Anh Vinh Bất biến và nửa bất biến 220 3 www.VNMATH.com Lời nói đầu Hoạt động bồi dưỡng theo các bộ môn, phân theo các cụm, khu vực theo địa hình và đặc thù văn hoá, ... đã trở thành sinh hoạt chuyên môn truyền thống và ngày càng đi vào nề nếp trong hệ thống các trường trung học chuyên và năng khiếu bậc phổ thông. Nhờ đó, các đơn vị, các trường THPT chuyên chủ động xây dựng chương trình hành động và lựa chọn cách thức triển khai. Đặc biệt chương trình tập huấn phát triển năng lực chuyên môn giáo viên trường THPT chuyên gắn với các hoạt động bồi dưỡng chuyên môn nghiệp vụ và năng lực tổ chức các hoạt động xã hội cho giáo viên đang giảng dạy ở các đội tuyển các trường THPT Chuyên. Ban tổ chức đã xây dựng nội dung, chương trình kế hoạch cho các hoạt động bồi dưỡng chuyên môn nghiệp vụ; liên hệ mời các giáo sư, các nhà khoa học có kinh nghiệm và tâm huyết trực tiếp giảng bài và tổ chức các semina khoa học. Sản phẩm của chương trình tập huấn là đã xây dựng một tập san (tài liệu tập huấn) trong đó lưu giữ các nội dung gồm các bài viết, bài giảng, các đề thi Olympic đề xuất kèm theo lời giải và giới thiệu những xu hướng mới cập nhật với olympic khu vực và quốc tế. Vì thời gian rất gấp gáp, nên các khâu chế bản và nội dung cuốn tài liệu tập huấn này chắc chắn còn nhiều khiếm khuyết. Mong nhận được sự góp ý của các thầy, cô và các đồng nghiệp. Ban Tổ chức 4 www.VNMATH.com Một số bài toán Số học - Tổ hợp Hà Huy Khoái Viện Toán học Bài giảng này nhằm mục tiêu giới thiệu một số bài toán có thể gọi là thuộc loại "số học - tổ hợp". Thực ra không có một "định nghĩa" nào cho loại bài toán đó, nên ở đây chỉ giới hạn ở việc đưa ra một số ví dụ về loại bài toán thường gặp trong những kỳ thi học sinh giỏi, mà việc giải chúng đòi hỏi những phương pháp của số học và tổ hợp. Để tiện theo giõi, chũng tôi tạm chia bài giảng thành bốn phần: Tỷ số vàng, Các dãy nhị phân, Tính chia hết và Trò chơi. Khi trình bày các lời giải, trong chừng mực có thể, chúng tôi cố gắng mô tả quá trình hình thành nên lời giải đó, hơn là đưa ra một lời giải ngắn gọn. §1. Tỷ số vàng. Chúng ta đều biết "tỷ số vàng" sau đây thường xuất hiện trong khoa học, nghệ thuật và đời sống √ 1+ 5 . 2 Tỷ số vàng đó cũng thường bắt gặp trong lời giải của những bài toán số học - tổ hợp. Trước tiên ta xét ví dụ sau: Bài toán 1. Giả sử γ, δ là những số vô tỷ dương, thỏa mãn 1 1 + = 1. γ δ 5 www.VNMATH.com Chứng minh rằng nếu đặt an = [nγ], bn = [nδ] thì mỗi số nguyên dương xuất hiện đúng một lần trong một trong hai dãy an , bn . Phân tích - Lời giải Rõ ràng yêu cầu của bài toán tương đương với việc chứng minh rằng, các số trong mỗi đoạn hữu hạn tùy ý [1, 2, · · · , N ] có mặt ở một trong hai dãy, và xuất hiện đúng một lần. Như vậy vấn đề chỉ còn là đếm xem trong N − 1 số nguyên dương nhỏ hơn N , có bao nhiêu số thuộc một trong hai dãy nói trên. Xét mọi số nguyên dương n thỏa mãn [nγ] < N , tức là n < N γ. Như vậy, các số n thỏa mãn là n = 1, 2, · · · , [ Nγ ]. Tương tự, các số m sao cho [mδ] < N là m = 1, 2, · · · , [ Nδ ]. Như vậy, trong các số nguyên dương nhỏ hơn N , số các số thuộc một trong hai dãy an , bn là [ Nγ ] + [ Nδ ]. Do γ; δ là các số vô tỷ nên [ Nγ ]; [ Nδ ] 6∈ Z. Từ đó ta có: N N N −1<[ ]< , γ γ γ N N N −1<[ ]< , δ δ δ suy ra 1 1 N N 1 1 N ( + ) − 2 = N − 2 < [ ] + [ ] < N ( + ) = N. γ δ γ δ γ δ Do đó [ N N ] + [ ] = N − 1. γ δ Như vậy trong N − 1 số nhỏ hơn N có đúng N − 1 số thuộc một trong hai dãy đang xét, đ.p.c.m. Bài toán trên đây là một "thành phần" của rất nhiều bài toán tổ hợp. Trong bài giảng này, chúng ta sẽ xem xét hai bài thuộc loại đó. Bài toán 2. 6 www.VNMATH.com Tìm các dãy tăng các số nguyên dương {an }; {bn } thỏa mãn những tính chất sau: 1/ a1 = 1. 2/ Với mọi n ≥ 1, bn = an + n. 3/ an là số nguyên dương nhỏ nhất không thuộc tập hợp {a1 , a2 , · · · , an−1 ; b1 , b2 , · · · , bn−1 }. Rõ ràng ba điều kiện nói trên xác định một cách duy nhất các dãy {an }, {bn }. Hơn nữa, đối với hai dãy tăng, việc thỏa mãn các điều kiện 1/ , 2/, 3/ tương đương với việc thỏa mãn các điều kiện 1/, 2/ , và 3’/ như sau: 3’/ Mỗi số nguyên dương đều thuộc một và chỉ một trong hai dãy đang xét. Do tính xác định duy nhất của các dãy thỏa mãn 1/, 2/, 3’/, ta chỉ cần chứng minh sự tồn tại, bằng cách chỉ ra ví dụ cụ thể. Bài toán 1 cho ta cách tìm hai dãy thỏa mãn điều kiện 3’/: đó chính là các dãy an = [nγ], bn = [nδ], trong đó γ, δ là những số vô tỷ dương, thỏa mãn 1 1 + = 1. γ δ Vấn đề chỉ là tìm γ để các điều kiện 1/ và 2/ được thỏa mãn. Để ý rằng n = n + [nγ] − [nγ] = [n + nγ] − [nγ] = [(1 + γ)n] − [nγ]. Như vậy chỉ cần chọn γ vô tỷ, thỏa mãn: 1 1 + = 1. γ γ+1 Nghiệm của phương trình trên là "tỷ số vàng" √ 1+ 5 2 . Các dãy an , bn cần tìm là: √ √ 1+3 5 1+ 5 n]; bn = [ n]. an = [ 2 2 7 www.VNMATH.com Bài toán 1 và Bài toán 2 lại có thể làm "thành phần" cho bài toán phức tạp hơn sau đây: Bài toán 3 Lập dãy số theo cách sau: lấy x1 = 1, với i ≥ 2 số xi nhận được từ xi−1 bằng cách đổi (trong cách viết số xi−1 ) số 1 thành 01, số 0 thành 1. Làm như vậy, ta nhận được dãy số 1, 01, 101, 01101,...Trong dãy này, gọi an là vị trí của chữ số 1 thứ n, bn là vị trí của chữ số 0 thứ n (như vậy a1 = 1, a2 = 3, a3 = 4, b1 = 2, b2 = 5, · · · ). Tìm công thức xác định an , bn . Phân tích - Lời giải Trước tiên ta cần tìm một công thức xác định mối liên hệ giữa an và bn . Gọi kn là số chữ số 0 đứng trước chữ số 1 thứ n. Theo định nghĩa hai dãy đang xét ta có an = n + kn . Theo bài ra, chữ số 0 thứ n được "sinh ra" từ chữ số 1 thứ n. Mặt khác, chữ số 1 biến thành hai chữ số 01, chữ số 0 biến thành một chữ số 1. Trước chữ số 1 thứ n có kn chữ số 0, và "biến thành kn chữ số; còn n chữ số 1 "biến thành" 2n chữ số. Từ đó suy ra: bn = kn + 2n. Từ hai công thức trên đây, ta có bn = an + n. Vì an và bn đều là các "số thứ tự" nên hai dãy là dãy tăng, đồng thời mỗi một số nguyên dương xuất hiện đúng một lần trong một trong hai dãy. Các Bài toán 1 và Bài toán 2 cho ta đáp số: √ √ 1+ 5 1+3 5 an = [ n]; bn = [ n]. 2 2 8 www.VNMATH.com Trong phần các bài toán về trò chơi, ta sẽ gặp lại "tỷ số vàng". §2 Các dãy nhị phân Trong rất nhiều bài toán tổ hợp, đặc biệt là các bài toán "đếm", ta thường gặp những tình huống mà tại đó có hai khả năng xẩy ra: được tô bởi hai màu; đường đi chỉ được phép sang phải hoặc đi lên; học sinh nam hay nữ, số chẵn hoặc lẻ; ...Về thực chất, những bài toán như vậy luôn luôn có thể đưa về cùng một dạng phát biểu, trong đó thông thường nhất là dùng các dãy nhị phân (các dãy gồm hai chữ số 0 và 1). Để hiểu rõ hơn điều đó, ta xét bài toán sau đây. Bài toán 4. Sau giờ học, các em học sinh xếp hàng để nhận xe đạp ở nhà gửi xe. Giá tiền gửi mỗi xe là 1000 đồng. Giả sử có k em học sinh có tờ 1000 đồng, m em có tờ 2000 đồng. Hỏi có bao nhiêu cách xếp hàng lấy xe sao cho không em nào phải chờ để lấy tiền trả lại? (Với giả thiết người giữ xe không có đồng tiền lẻ nào). Phân tích - Lời giải Đây là một bài toán thuộc loại "hai khả năng": mỗi em học sinh hoặc có tờ 1000 đồng, hoặc có tờ 2000 đồng. Như vậy, để dễ thấy bản chất bài toán, ta có thể lập tương ứng mỗi hàng học sinh với một dãy gồm hai chữ số 0, 1. Giả sử ứng với mỗi học sinh có tờ 1000 đồng trong hàng, ta viết số 0; ứng với học sinh có tờ 2000 đồng, ta viết số 1. Như vậy, mỗi hàng học sinh tương ứng một dãy gồm k chữ số 0, m chữ số 1. Để tồn tại cách xếp mà không có em nào phải chờ lấy tiền trả lại, điều kiện cần là k ≥ m. Cũng tương tự như trong nhiều bài toán tổ hợp khác, khi việc đếm số phần tử thỏa mãn bài ra là khó, ta đếm "phần bù" của nó, tức là những phần tử không thỏa mãn bài ra. Như vậy, ở đây ta sẽ xét xem có bao nhiêu hàng mà 9 www.VNMATH.com có học sinh nào đó đến lượt mình phải chờ lấy tiển trả lại. Theo cách tương ứng của chúng ta, một hàng như vậy sẽ tương ứng một - một với một dãy gồm k số 0, m số 1, trong đó tồn tại vị trí 2s + 1 sao cho tại đó có số 1, đồng thời ở 2s vị trí đầu, số số 0 và số số 1 là như nhau. Ta gọi một hàng như vậy là "hàng xấu". Nếu bạn là người giữ xe thì bạn sẽ làm thế nào trong tình huống đó? Hiển nhiên là gọi thêm một bạn nào đó có tờ 1000 đồng lên đứng trước hàng! Phương pháp "thực tiễn" này gợi cho ta lập tương ững mỗi hàng xấu gồm k chữ số 0, m chữ số 1 với một hàng gồm k + 1 chữ số 0, m chữ số 1, với chữ số 0 đứng đầu. Đồng thời, trong 2s + 2 vị trí đầu tiên, số chữ số 0 và số chữ số 1 là như nhau. Nếu ta đổi số 0 thành số 1, số 1 thành số 0 ở 2s + 2 vị trí đầu, một hàng như trên sẽ tương ứng với một hàng gồm k + 1 chữ số 0, m chữ số 1, nhưng với số 1 đứng đầu tiên. Lại bỏ đi số 1 đầu tiên này, ta được một hàng gồm k + 1 chữ số 0, m − 1 chữ số 1. Như vậy, mỗi hàng xấu gồm k chữ số 0, m chữ số 1 sẽ được tương ứng với một hàng gồm k + 1 chữ số 0, m − 1 chữ số 1 theo cách trên đậy. Dễ thấy rằng, tương ứng như trên là một - một. Thật vậy, xét một hàng tùy ý gồm k + 1 chữ số 0, m − 1 chữ số 1. Ta thêm số 1 vào đầu hàng, để được hàng gồm k + 1 chữ số 0, m chữ số 1. Do điều kiện k ≥ m nên trong hàng này phải tồn tại vị trí (2s + 2) mà từ đó trở lên, số số 0 bằng số số 1. Ta đổi số 0 thành số 1 và ngược lại ở các vị trí từ đó trở lên, để được hàng gồm k + 1 chữ số 0, m chữ số 1, với số 0 đứng đầu. Bỏ số 0 đầu tiên này, ta nhận được một hàng xấu. Từ những tương ứng trên suy ra rằng, số các hàng xấu gồm k chữ số 0, m chữ số 1 bằng số các hàng (tùy ý) với k + 1 chữ số 0, m − 1 chữ số 1, tức là k+1 bằng Cm+k . Như vậy, số cách xếp hàng sao cho không học sinh nào phải chờ lấy tiền 10 www.VNMATH.com trả lại là: k+1 k Cm+k − Cm+k . Bài toán 5. Có 2k học sinh chiều cao khác nhau đôi một. Người ta muốn xếp họ thành hai hàng ngang, sao cho trong mỗi hàng, chiều cao của học sinh giảm dần, và ở mỗi vị trí, em đứng hàng trước cao hơn em đứng hàng sau. Hỏi có bao nhiêu cách xếp hàng thỏa mãn yêu cầu? Phân tích - Lời giải Thoạt nhìn thì đây là bài toán khác hẳn với bài toán trên. Tuy nhiên, nếu ta đã nắm vững nguyên tắc "hai khả năng" thì thấy cả hai bài chỉ cùng một loại. Thật vậy, vấn đề ở đây chỉ là xếp học sinh vào một trong hai hàng. Với quan niệm như trên, ta cho mỗi em đứng hàng trước cầm một tấm biển ghi số "0", mỗi em hàng sau cầm tấm biểm ghi số "1". Sau đó gọi tất cả 2k em xếp lại thành một hàng dọc theo thứ tự chiều cao giảm dần. Làm như vậy, ta được một dãy gồm k chữ số 0, k chữ số 1. Dễ thấy rằng, một cách xếp hàng thỏa mãn bài ra chính là một cách xếp hàng sao cho tại mỗi vị trí 2s + 1, số số 0 từ vị trí đầu tiên đến đó phải ≥ s + 1. Theo Bài toán 4, số cách xếp hàng hỏa mãn bài ra là: k+1 k C2k − C2k = (2k)! . k!(k + 1)! §3. Tính chia hết Ta bắt đầu với bài toán đơn giản sau. Bài toán 6. Tìm tất cả các tập hợp A = {a1 , a2 , · · · , an ; n > 2012} gồm những số nguyên và có tính chất sau: 2012 ∈ A, đồng thời mỗi tập con tùy ý gồm 2012 số thuộc 11 www.VNMATH.com A đều có thể chia thành 4 nhóm có số phần tử bằng nhau và tổng các phần tử trong mỗi nhóm bằng nhau. Phân tích - Lời giải. Điều kiện của bài toán cho ta thấy rằng, tổng của 2012 số tùy ý thuộc A là một số chia hết cho 4. Thay từ tập hợp 2012 phần tử một phần tử bất kỳ bởi một phần tử khác tùy ý không thuộc tập đã chọn, tính chất tổng chia hết cho 4 không hề thay đổi. Như vậy có thể thấy ngay rằng, mọi phần tử thuộc A đều đồng dư nhau modulo 4. Dĩ nhiên ta nẩy ra ngay dự đóan rằng, các phần tử của A đều bằng nhau. Để có thể kiểm chứng dự đoán này, ta xét phần tử nhỏ nhất của A : ā. Khi đó tập hợp B = {a1 − ā, a2 − ā, · · · , an − ā} rõ ràng cũng thỏa mãn những tính chất đã nêu trong bài toán như đối với tập hợp A. Do đó, mọi phần tử của B cũng đồng dư nhau modulo 4,và vì B chứa phần tử bàng 0 nên suy ra mọi phần tử của B đều chia hết cho 4. Từ đây, suy luận "quy nạp lùi" quen thuộc cho ta lời giải: tập hợp nhận được từ B bằng cách thay mọi phần tử b ∈ B bởi b 4 cũng có tính chất nêu trong bài ra; và do đó các phần tử của tập hợp này cũng chia hết cho 4. Tiếp tục quá trình,dễ suy ra mọi phần tử của B đều bằng 0. Như vậy, mọi số thuộc A đều bằng 2012. Bài toán 7 Với mỗi số nguyên dương d, gọi f (d) là số nguyên dương nhỏ nhất có đúng d ước số dương. Chứng minh rằng với mọi k ≥ 0, f (2k+1 ) chia hết cho f (2k ). Phân tích- Lời giải. Để giải bài này, rõ ràng ta cần biết những số nào sẽ có 2k ước dương, sau đó mới tìm số nhỏ nhất trong những số như vậy. Lẽ tự nhiên là ta nghĩ ngay đến việc phân tích một số nguyên dương n ra thừa số nguyên tố. Vì cần có công thức cho n tổng quát (khi chưa có thông tin gì 12 www.VNMATH.com về các ước nguyên tố của nó), ta viết n = Πp pα(p) , trong đó α(p) là các số nguyên không âm, đồng thời chỉ có hữu hạn số khác 0. Nếu gọi d(n) là số ước dương của n thì d(n) = Πp (α(p) + 1). Như vậy, d(n) là một lũy thừa của 2 khi và chỉ khi với mọi p, tồn tại b(p) ≥ 0 sao cho α(p) = 2b(p) − 1. Để có thể nhìn rõ hơn"cấu trúc" của n, ta viết số mũ thành tổng (và có n dưới dạng tích) α(p) = 2b(p) − 1 = 1 + 2 + 22 + · · · + 2b(p)−1 , b(p)−1 2i n = Πp Πi=0 p . Khi đó d(n) = 2k , với k = Σp b(p). Như vậy các số n cần tìm là tích của những r số nào đó có dạng p2 , với p nguyên tố và r nguyên không âm. Từ phân tích r trên đây ta thấy rằng nếu số p2 có mặt trong biểu diễn n dưới dạng tích, thì m những số p2 với m < r cũng có mặt trong tích đó. Nghĩa là nếu một số nào đó có mặt trong biểu diễn n thì mọi ước số của nó cũng đều tham gia trong r biểu diễn. Do đó ta có kết luận sau đây: nếu gọi S là tập hợp các số dạng p2 , với p nguyên tố và r nguyên không âm, thì d(n) là một lũy thừa của 2 khi và chỉ khi n là tích các phần tử thuộc một tập con hữu hạn T của S có tính chất sau: với mọi t ∈ T , s ∈ S , mà s|t thì s ∈ T. Hơn nữa, nếu d(n) = 2k thì tập hợp T gồm k phần tử. 13 www.VNMATH.com Dễ thấy rằng, với mọi k nguyên dương, tập hợp Tk gồm k phần tử nhỏ nhất của S thỏa mãn tính chất trên, suy ra f (2k ) chính là tích các phần tử thuộc Tk . Từ đó suy ra ngay kết luận của bài toán. Nhận xét: có thể thấy S = {2, 3, 4, 5, 7, 9, 11, 13, 16, 17, · · · }, suy ra f (2) = 2; f (4) = 2.3 = 6; f (8) = 2.3.4 = 24; f (16) = 2.3.4.5 = 120; f (32) = 2.3.4.5.7 = 840, ... Biểu diễn số Có rất nhiều bài toán liên quan đến việc biểu diễn số nguyên (dương) dưới một dạng nào đó. Nhìn chung, lời giải thường xuất phát từ việc xem xét kỹ những trường hợp riêng rẽ, đặc biệt là khi các số đang xét tương đối nhỏ. Ta xét ví dụ sau đây. Bài toán 8. Tìm số k nguyên dương lớn nhất có tính chất sau: tập hợp các số nguyên dương phân hoạch được thành k tập con A1 , A2 , · · · , Ak sao cho với mọi n ≥ 15 , với mọi i ∈ {1, 2, · · · , k} tồn tại hai phần tử khác nhau của Ai có tổng bằng n. Phân tích - Lời giải Ta bắt đầu với trường hợp k = 2. Rõ ràng có thể phân hoạch tập hợp các số nguyên dương thành hai tập con: A1 = {2n, n ≥ 3} ∪ {1, 2}; A2 = {2n − 1, n ≥ 3} ∪ {3, 4} có tính chất: mọi số nguyên dương ≥ 7 biểu diễn được dạng tổng hai số thuộc A1 và tổng hai số thuộc A2 . Khi k = 3, dĩ nhiên việc phân hoạch thành "chẵn, lẻ" như trên được thay bởi phân hoạch theo modulo 3, và cũng như trước, cần thêm vào mỗi lớp đồng dư modulo 3 một số số đầu tiên để bảo đảm mỗi tập đều biểu diễn được mọi số lớn hơn hoặc bằng 15 dưới dạng tổng hai số. Có thể chọn phân hoạch sau đây: A1 = {1, 2, 3} ∪ {3m; m ≥ 4}, 14 www.VNMATH.com A2 = {4, 5, 6} ∪ {3m − 1; m ≥ 4}, A3 = {7, 8, 9} ∪ {3m − 2; m ≥ 4}. Dễ thử lại rằng, phân hoạch trên đây thỏa mãn bài ra. Hơn nữa, có thể nhận thấy rằng, điều kiện biểu diễn được mọi số ≥ 15 đối với phân hoạch trên đây đã rất "chặt", chẳng hạn số 14 không thể biểu diễn dạng tổng hai số thuộc A2 hoặc hai số thuộc A3 . Từ đó có thể dự đoán rằng, k = 3 là giá trị lớn nhất có thể để tồn tại phân hoạch thỏa mãn bài ra. Ta sẽ chứng minh dự đoán trên, nghĩa là với k ≥ 4 không thể phân hoạch tập các số tự nhiên thành k tập hợp con thỏa mãn bài ra. Rõ ràng nếu với k ≥ 4 nào đó mà tồn tại phân hoạch thỏa mãn, thì phân hoạch như vậy cũng tồn tại với k = 4: chỉ cần lấy phân hoạch A1 , A2 , A3 , A4 ∪ A5 ∪ · · · ∪ Ak ta được phân hoạch gồm 4 tập hợp thỏa mãn bài ra. Như vậy chỉ cần chứng minh không thể tồn tại phân hoạch gồm 4 tập hợp con thỏa mãn bài ra. Giả sử tồn tại một phân hoạch như vậy: A1 , A2 , A3 , A4 . Như ta đã thấy trong các ví dụ khi k = 2, 3, các tập hợp Ai phải chứa những số nào đó trong những số tự nhiên đầu tiên. Xét 10 số nhỏ nhất mà mỗi một tập hợp Ai đều phải biểu diễn được: 15, 16, ..., 24. Mỗi số trong 10 số này đều là tổng của hai số nào đó thuộc tập hợp B = {1, 2, · · · , 23}. Như vậy, mỗi tập hợp Ai cần chứa ít nhất 5 số thuộc B . Do bốn tập Ai rời nhau mà B chỉ có 23 phần tử nên phải tồn tại tập Aj nào đó chứa đúng 5 số thuộc B, giả sử đó là các số {x1 , x2 , x3 , x4 , x5 }. Năm số này biểu diễn được đúng 10 số trong các số từ 15 đến 24, tức là 10 số đó chính là 10 tổng có thể {xk + xl , k 6= l; 1 ≤ k, eq5}. Từ đó suy ra: 15 + 16 + · · · + 24 = 4(x1 + x2 + x3 + x4 + x5 ), 15 www.VNMATH.com vì mỗi số xi tham gia trong đúng 4 cặp số. Đẳng thức trên đây cho ta mâu thuẫn vì tổng ở vế trái là 195, trong khi vế phải chia hết cho 4. Bài toán 9. Với mỗi số nguyên dương m, ký hiệu C(m) là số nguyên dương k lớn nhất để tồn tại tập hợp S gồm m số nguyên sao cho mỗi số nguyên từ 1 đến k đều thuộc S , hoặc là tổng của hai số thuộc S (không nhất thiết khác nhau). Ví dụ : C(3) = 8; S = {1, 3, 4}. Chứng minh bất đẳng thức sau đây: m(m + 3) m(m + 6) ≤ C(m) ≤ . 4 2 Phân tích - Lời giải Điều kiện bài toán gợi cho ta thấy cần phải tính số phần tử của tập hợp S ∪ (S + S), trong đó S + S = {x + y|x, y ∈ S}. Nếu với mỗi tập hợp A, ký hiệu qua |A| số phần tử của nó, thì ta có bất đẳng thức hiển nhiên sau: |S ∪ (S + S)| ≤ |S| + |S + S|. Mỗi phần tử của S + S nhận được bằng cách lấy tổng một cặp số (bằng nhau hoặc khác nhau) của S , suy ra bất đẳng thức sau: 1 2 |S + S| ≤ |S| + C|S| = |S|(|S| + 1). 2 Trong hai bất đẳng thức cần chứng minh, bất đẳng thức bên phải tương đối dễ thấy. Số C(m) là số nguyên dương k lớn nhất sao cho tồn tại tập S gồm m số nguyên dương thỏa mãn {1, 2, · · · , k} ⊂ S ∪ (S + S). 16 www.VNMATH.com Từ chứng minh trên ta có 1 k ≤ |S ∪ (S + S)| ≤ |S|(|S| + 3). 2 Từ đó suy ra C(m) ≤ m(m + 3) . 2 Ta chứng minh bất đẳng thức bên trái. Trước tiên, tập hợp S cần tìm chứa một số số tự nhiên liên tiếp nào đó 1, 2, · · · , t; t < m. Với những số này, tập hợp S ∪ (S + S) chứa các số 1, 2, · · · , 2t. Như vậy, để biểu diễn được những số tiếp theo, cần thêm số 2t + 1. Các số 1, 2, · · · , t, 2t + 1 cho phép biểu diễn các số tự nhiên cho đến số 3t + 1, vì thế muốn biểu diễn các số lớn hơn, ta cần thêm số 3t + 2. Lý luận trên đây chỉ ra rằng tập hợp S gồm m phần tử cần tìm có dạng {1, 2, · · · , t} ∪ {(k + 1)t + k; k = 1, 2, · · · , m − t.} Khi đó dễ thấy rằng {1, 2, · · · , m + (m + 1)t − t2 } ⊂ S ∪ (S + S). Ta cần tìm giá trị t < m sao cho số các số biểu diễn được là lớn nhất, tức là tìm t sao cho m+)m + 1)t − t2 đạt cực đại. Dễ chứng mỉnh rằng đại lượng này đạt cực đại khi t = [ m+1 m(m + 6) ], và giá trị cực đại là [ ]. 2 4 Từ đó ta có bất đẳng thức cần chứng minh. §4. Trò chơi Bài toán 10. Trên bàn có n > 1 que diêm. Có hai người lần lượt lấy diêm. Mỗi người đến lượt mình được lấy một số que diêm tùy ý trong những que còn lại trên bàn, nhưng không vượt quá số que diêm mà người đi trước vừa lấy, và người 17 www.VNMATH.com đi đầu tiên không lấy quá n − 1 que. Người nào lấy que diêm cuối cùng được xem là chiến thắng. Tìm các số n sao cho người đi trước có chiến lược thắng. Phân tích -Lời giải. Dễ thấy rằng nếu n lẻ thì người đi trước luôn luôn thắng, bằng cách ở nước đi đầu tiên, người đó chỉ lấy một que diêm, do đó ở những nước đi tiếp theo, mỗi người chỉ được lấy một que diêm. Xét trường hợp n chẵn. Rõ ràng người nào lấy một số lẻ que diêm đầu tiên sẽ thua, vì để lại cho người đi nước tiếp theo một số lẻ que diêm: trở về trường hợp trên. Do đó, người chiến thắng phải luôn lấy một số chẵn que diêm. Như vậy, có thể hình dung các que diêm được gắn thành từng cặp, và mỗi người đến lượt sẽ lấy một số cặp nào đó. 1/ Nếu chỉ có một cặp (n = 2): người đi trước thua, vì chỉ được lấy một que. 2/ Nếu số cặp lẻ và > 1 (n ≡ 2 mod 4): ta trở về trường hợp n lẻ (vì các que diêm đã được gắn thành cặp), và người đi trước thắng. 3/ Nếu số cặp chẵn (n ≡ 0 mod 4): mỗi người muốn thắng thì luôn phải lấy một số chẵn cặp (nếu ngược lại thì ta trở về trường hợp 2/). Khi đó có thể hình dung các que diêm được gắn thành từng nhóm 4 que. Tương tự trường hợp 1/ và 2/ ta thấy nếu số nhóm là một (n = 4) thì người đi trước thua; nếu n > 4 và số nhóm lẻ (n ≡ 4 mod 8) thì người đi trước thắng. Nếu số nhóm là chẵn (n ≡ 0 mod 8), ta lại gắn các que diêm thành từng nhóm 8 que,... Như vậy, người đi trước có chiến lược thắng khi và chỉ khi n không phải là một lũy thừa của 2 (n 6= 2k .) Trên đây là một bài về trò chơi, mà lời giải đơn giản dựa vào việc xét modulo 2k . Trong phần còn lại của mục này, chúng ta sẽ xem xét một bài toán trò chơi rất tổng quát. Sở dĩ chúng tôi đưa ra ví dụ này vì lời giải của nó 18 www.VNMATH.com hội tụ đầy đủ những vấn đề thường gặp trong bài toán về trò chơi: tập hợp có chiến lược thắng, đồ thị, số học. Hơn nữa, chúng ta lại một lần nữa tìm thấy sự tham gia của "tỷ số vàng" Bài toán 11. Cho hai đống đá, một đống có a hòn đá, đống kia có b hòn. Hai người chơi, mỗi người đến lượt mình được lấy một số tùy ý hòn đá từ một trong hai đống, hoặc lấy từ hai đống số hòn đá như nhau. Người lấy được hòn cuối cùng là người chiến thắng. Tìm tất cả các cặp (a, b) sao cho người đi sau có chiến lược thắng. (Ví dụ: (1,2) là cặp có tính chất đó). Phân tích - Lời giải. Việc cho phép lấy hoặc một số đá tùy ý từ một trong hai đống, hoặc lấy số đá như nhau từ mỗi đống gợi cho ta hình ảnh: hoặc giảm theo chiều ngang, theo chiều dọc, hoặc theo đường chéo. Để mô tả tình hình đó, tốt nhất là dùng một đồ thị có hướng. Xét đồ thị mà các đỉnh là các điểm trên mặt phẳng với tọa độ nguyên không âm, các cạnh là những đoạn nối hai điểm, nằm trên những đường song song các trục tọa độ và trên những đường song song với đường thẳng y = x. Các cạnh có hướng từ phải sang trái, từ trên xuống dưới. Với bài toán có hai đống đá với số đá là a, b, ta có một đồ thị có hướng mà điểm xuất phát là điểm có tọa độ (a, b). Trong quá trình chơi, mỗi người đến lượt mình sẽ đi theo một trong ba hướng (phải-trái, trên-dưới hoặc giảm theo đường chéo) đến một đỉnh mới của đồ thị. Người chiến thắng là người đến điểm (0,0) đầu tiên. Như vậy, một cặp (a, b) thỏa mãn bài ra ứng với một vị trí thắng theo định nghĩa sau: Định nghĩa Ta gọi điểm (a, b) là một vị trí thắng nếu người chơi nào đến được vị trí đó thì họ sẽ có chiến lược thắng, không phụ thuộc bước tiếp theo 19