Sử dụng đa thức và số phức trong một số bài toán tổ hợp

Nội dung tài liệu: Sử dụng đa thức và số phức trong một số bài toán tổ hợp

1. SỞ GIÁO DỤC ĐÀO TẠO TỈNH BẮC GIANG TRƢỜNG THPT CHUYÊN BẮC GIANG TRẦN ANH ĐỨC SỬ DỤNG ĐA THỨC VÀ SỐ PHỨC TRONG MỘT SỐ BÀI TOÁN TỔ HỢP Tổ: Toán – Tin học Năm học: 2023 - 2024 Mã số: Bắc Giang, tháng 3 năm 2024 1
2. PHẦN I: MỞ ĐẦU I. LÍ DO CHỌN ĐỀ TÀI Các bài toán tổ hợp là một phần quan trọng của chuyên ngành toán rời rạc và là một mảng khó trong chương trình toán THPT chuyên. Chính vì thế trong các kì thi học sinh giỏi quốc gia, thi Olympic Toán quốc tế và khu vực, những bài toán tổ hợp cũng hay được đề cập và thường được xem là những dạng toán khó, những câu phân loại của kì thi. Các em học sinh bậc Trung học phổ thông thường gặp một số khó khăn khi tiếp cận các dạng toán liên quan đến tư duy tổ hợp, đặc biệt là kỹ năng ứng dụng các kiến thức số học và một số kiến thức cơ bản khác vào việc giải bài tập tổ hợp. Những học sinh mới bắt đầu làm quen một số dạng toán tổ hợp thường chưa hiểu tường tận tư tưởng cũng như phương pháp tiếp cận bài toán, đặc biệt là khâu vận dụng kiến thức tổ hợp liên quan đến các phân môn khác vào giải toán tổ hợp trong những tình huống khác nhau. Để hiểu và vận dụng tốt một số dạng toán cơ bản và vận dụng kiến thức tổ hợp vào giải toán thì thông thường học sinh phải có kiến thức nền tảng tổ hợp tương đối đầy đủ và chắc chắn trên tất cả các lĩnh vực của ngành toán rời rạc. Đó là một khó khăn rất lớn đối với giáo viên và học sinh khi giảng dạy và học tập phần các kiến thức cần thiết trong tổ hợp. Trong các kiến thức cũng như dạng toán trong tổ hợp thì phép đếm sử dụng đa thức và số phức có nhiều ứng dụng trong việc giải các bài toán tổ hợp và trong các kì thi học sinh giỏi số lượng các bài toán liên quan đến việc sử dụng các phương pháp này khá nhiều. Các bài toán khi giải bằng phương pháp sử dụng một số phương pháp trên trong các kì thi học sinh giỏi thường khá hay và đặc sắc, thể hiện khả năng sáng tạo của học sinh. Bằng cách giải bằng cách sử dụng phương pháp này giúp học sinh thấy được bản chất của bài toán và phát hiện ra các tính chất thú vị khác của bài toán. Tuy nhiên khó khăn lớn nhất của giáo viên khi dạy phần này là làm sao để học sinh hứng thú học và có khả năng vận dụng các phương pháp này vào giải các bài toán tổ hợp, do đó vấn đề đặt ra là cần trang bị cho các em những kiến thức gì? Cần bắt đầu từ những bài toán nào? Cần phân dạng các bài tập áp dụng từng phương pháp giải toán tổ hợp theo mức độ từ thấp đến cao và những dấu hiệu của các bài toán như thế nào thì dùng phương pháp tương ứng? Với tất cả những khó khăn và thuận lợi trên chúng tôi chọn đề tài “Sử dụng đa thức và số phức trong một số bài toán tổ hợp” để trao đổi và đưa ra một số dạng bài tập đặc trưng để góp phần nâng cao tư duy tổ hơp của học sinh. Nội dung chuyên đề gồm ba phần chính: – Cơ sở lí thuyết của phương pháp. – Một số bài toán vận dụng phương pháp sử dụng đa thức và số phức trong các bài toán tổ hợp. – Bài tập luyện tập. 2
3. II. MỤC ĐÍCH NGHIÊN CỨU Đề tài “Sử dụng đa thức và số phức trong một số bài toán tổ hợp” được chọn để giới thiệu với các thầy cô giáo và các em học sinh những kinh nghiệm của chúng tôi khi giảng dạy một số chủ đề tổ hợp trong chương trình THPT chuyên, và đồng thời thông qua đề tài này chúng tôi muốn nhấn mạnh tầm quan trọng của phương pháp này trong các bài toán tổ hợp và một số bài toán khác xuất hiện trong các kì thi Quốc tế, khu vực và Olympic quốc gia của một số nước những năm gần đây. Các bài toán tổ hợp trong các kì thi học sinh giỏi olimpic thường là những bài tập khó, các bài tập chúng tôi đưa ra đều là các đề thi Olympic Quốc tế, khu vực và một số nước có truyền thống về toán, trong các bài tập này chúng tôi có phân tích dấu hiệu của bài toán mà có thể sử dụng để giải bằng cách dùng những kiến thức cơ sở nào nhanh nhất và hiệu quả nhất. Những bài toán này nếu không sử dụng các kiến thức tổ hợp tương ứng với giả thiết của nó thường rất khó trình bày và rất dễ ngộ nhận. Thông qua đề tài “Sử dụng đa thức và số phức trong một số bài toán tổ hợp” chúng tôi cũng rất mong muốn nhận được góp ý trao đổi của các bạn đồng nghiệp, các bậc cha mẹ học sinh và các em học sinh. Chúng tôi mong muốn đề tài này góp một phần nhỏ để việc dạy phần toán tổ hợp một cách hiệu quả nhất và giúp các em học sinh có khả năng vận dụng một số phương pháp cơ bản vào giải các bài toán tổ hợp một cách tốt nhất. III. NHIỆM VỤ NGHIÊN CỨU Đưa ra hướng tiếp cận cho một số dạng bài toán đếm được xử lý bằng đa thức và số phức và ví dụ minh họa phong phú. Để đáp ứng yêu cầu về việc học tập và nghiên cứu cho học sinh chuyên, góp phần nâng cao số lượng và chất lượng HSG môn toán tại các ký thi học sinh giỏi cấp Quốc gia. Tuy nhiên, do giới hạn về chương trình, điều kiện về giáo viên, cơ sở vất chất nên đề tài chưa được triển khai rộng trong các trường THPT trong phạm vi rộng. IV. ĐỐI TƢỢNG NGHIÊN CỨU Đối tượng nghiên cứu của đề tài là học sinh các lớp chuyên Toán 10, 11, 12; đội tuyển HSG tham dự kỳ thi chọn HSG QG lớp 12 môn Toán học của các trường THPT Chuyên. Ngoài ra còn có thể là tài liệu tham khảo cho học sinh, giáo viên và phụ huynh học sinh có nhu cầu tìm hiểu sâu hơn về phân môn tổ hợp. V. PHƢƠNG PHÁP NGHIÊN CỨU Trong đề tài sử dụng các phương pháp nghiên cứu chủ yếu sau: - Phương pháp nghiên cứu lí luận: Nghiên cứu các tài liệu chuyên về tổ hợp đặc biệt là các tài liệu liên quan đến số học, đại số, dãy số, ... và các tạp chí trong và ngoài nước; tài liệu từ Internet... - Phương pháp trao đổi, tọa đàm (với giáo viên, học sinh các lớp chuyên toán). - Phương pháp tổng kết kinh nghiệm. 3
4. VI. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI Đưa ra được hệ thống cơ sở lí thuyết cơ bản và nâng cao về phương pháp sử dụng đa thức và số phức trong các bài toán đếm giúp ích cho việc tiếp cận lời giải các bài toán tổ hợp, ví dụ minh họa phong phú, từ đơn giản đến phức tạp khá đầy đủ. Tạo thêm niềm tin và một cách tiếp cận cho học sinh trước các bài toán tổ hợp. 4
5. PHẦN II: NỘI DUNG I. Cơ sở lý thuyết I.1. Căn bậc n của đơn vị I.1.1. Định nghĩa. Số phức z được gọi là căn bậc n của đơn vị nếu nó thỏa mãn đẳng thức zn 10. kk22 Tập hợp các căn bậc n của đơn vị là tập hợp cos i sin k 0,1,..., n 1 nn I.1.2 Tính chất +) Nếu z 1 là căn bậc n của đơn vị suy ra z là nghiệm của phương trình znn 12 z ... z 1 0 +) Phương trình có n 1 nghiệm là kk22 cos i sin , kn 1,..., 1 nn I.2. Đa thức bất khả quy I.2.1. Định nghĩa. Đa thức P x A x , trong đó A  và có bậc ( nn ,0) được gọi là đa thức bất khả quy trên tập A nếu Px không phân tích được thành tích của hai đa thức với hệ số đều thuộc A và có bậc nhỏ hơn . I.2.2. Định lí. Đa thức với hệ số nguyên và có bậc ( ) bất khả quy trên . Khi đó đa thức cũng bất khả quy trên . I.3. Tiêu chuẩn Eisenstein. n Cho đa thức P x a01 a x ... an x  x , n , n 1. Giả sử tồn tại số nguyên tố p thỏa mãn đồng thời các điều kiện sau (1) a0, a 1 ,..., ap 1 đều chia hết cho p ; (2) an không chia hết cho p ; 2 (3) a0 không chia hết cho p . Khi đó đa thức bất khả quy trên . 5
6. I.4. Một số định lí 22 I.4.1. Định lí . Cho p là một số nguyên tố,  cosi sin và a, a ,..., a thỏa mãn pp0 1p 1 đẳng thức 21p a0 a 1 a 2  ... ap 1  0 Khi đó a0 a 1 ... ap 1 . Chứng minh. Xét các đa thức 21p P x a0 a 1 x a 2 x ... ap 1 x 21p n Q x 1 x x ... x Trước hết ta chứng minh bổ đề sau Bổ đề. Đa thức bất khả quy trên . 11 y p Thật vậy, đặt x 11 y R y Q y 11 y 1 2p 1 p 2 p p 1 Cp C p y ... C p y C p y k p Do Cp p,1 k p 1 và Cp 1 không chia hết cho p nên theo tiêu chuẩn Eisenstein ta được Ry bất khả quy trên hay đa thức Qx bất khả quy trên suy ra Qx bất khả quy trên . Vậy bổ đề được chứng minh. +) Nếu P x ,1 Q x thì tồn tại các đa thức q12 x , q x  x sao cho 1 q12 x P x q x Q x 10 q12  P  q  Q  Vô lí vì PQ  0. +) Nếu P x , Q x d x , vì Qx bất khả quy trên nên điều này chỉ xảy ra khi Px chia hết cho Qx . Mặt khác P x , Q x có cùng bậc nên . Vậy định lí được chứng minh. 22 I.4.2. Định lí (định lí Root of unity filter). Cho số nguyên dương ,  cosi sin và nn đa thức 2 m P x a0 a 1 x a 2 x ... am x 6
7. Khi đó 1 a P1 P ... P n 1  k kn n Chứng minh. Ta có các đẳng thức sau P 1 a01 a ... am m P  a01 a  ... am  ............... k k mk P  a01 a  ... am  ............... nn 11mn 1 P  a01 a  ... am  Cộng từng vế các đẳng thức trên ta được n 1 n 1 n 1 n 1 j j jlm j P  na01 a   ... alm   ... a   j 0 j 0 j 0 j 0 Chú ý n 1 0khi k mod n j k   j 0 n khi k mod n Do đó n 1 j nP   j 0 Từ đó suy ra đẳng thức cần chứng minh. II. Bài tập minh họa phƣơng pháp Trong tất cả các bài tập trong chuyên đề này ta kí hiệu SXX , lần lượt chỉ tổng các phần tử, số phần tử của tập hợp X. Bài II.1 (China TST 2017). Tìm số bộ sắp thứ tự x1, x 2 ,..., x 100 thỏa mãn đồng thời các điều kiện sau: 7
8. (i) x1, x 2 ,..., x 100 1,2,...,2017 ; (ii) 2017x1 x 2 ... x 100 ; 2 2 2 (iii) 2017x1 x 2 ... x 100 . Lời giải. Đây là một bài toán rất khó và hay mặc dù phát biểu hết sức đơn giản. Cái khó nhất là khi sử dụng công cụ số phức thì ta sẽ dùng thông qua đại lượng trung gian nào. Nếu ta dùng 2 2 2 100 đa thức theo hướng xét P x x1 1 x 2 2 ... x 2017 2017 . Khi khai triển đa thức này ta 2017 2 2 2 thấy có dạng P x  xx1 x 2 ... x 100 x 1 x 2 ... x 100 . Tuy nhiên rất khó để sử dụng định lí RUF x1, x 2 ,..., x 100 1 và hai điều kiện (ii) và (iii). Sau đây chúng ta đưa ra một cách tiếp cận bài toán này theo hướng như sau: 22 Để thuận tiện trong trình bày ta đặt pp 2017  1 mod 4 . Gọi  cosi sin , pp p 1 aa12 ap với mỗi hệ thặng dư đầy đủ mod p a12, a ,..., ap ta có 1, ,...,   ,  ,...,   . Dựa vào nhận xét trên ta được nếu a12, a ,..., ap là hệ thặng dư đầy đủ mod p thì suy ra p a  1 aa12  ... p 1 1  2 ...  p 1 0 .  1 Dựa vào kết quả trên ta thu được bổ đề sau: p 1 2 2 2 a x1 x 2 ... x 100 b x 1 x 2 ... x 100 2 2 2 Bổ đề 1.   bằng 0 khi x1 x 2 ... x 100 , x 1 x 2 ... x 100 không đồng ab,0 thời chia hết cho p và bằng p2 khi đồng thời chia hết cho p . Chứng minh. Nếu hai số không đồng thời chia hết cho , chẳng hạn x2 x 2 ... x 2 a x2 x 2 ... x 2 a 0,1,..., p 1 1 2 100 không chia hết cho p suy ra 1 2 100  là hệ thặng p 1 2 2 2 a x1 x 2 ... x 100 dư đầy đủ mod p  0. Do đó a 0 pp 112 2 2 b x x ... x a x1 x 2 ... x 100 1 2 100 0 . ba 00 Nếu hai số đồng thời chia hết cho thì 8
9. pp 112 2 2 a x1 x 2 ... x 100 b x 1 x 2 ... x 100 2  1.p a, b 0 a , b 0 Từ bổ đề 1 ta thấy nếu cho các biến x1, x 2 ,..., x 100 thay đổi trên tập 1,2,..., p thì số bộ sắp thứ tự thỏa mãn yêu cầu bài toán là pp 1 2 2 2 1 a x1 x 2 ... x 100 b x 1 x 2 ... x 100  2  . p x1, x 2 ,..., x 100 1 a , b 0 Tiếp theo ta thu gọn tổng trên pp 1 2 2 2 1 a x1 x 2 ... x 100 b x 1 x 2 ... x 100  2  p x1, x 2 ,..., x 100 1 a , b 0 pp 1 100 1 ax2 bx 2   p a, b 0 x 1 p 11 p100 p p 100 11 bx ax2 bx 22    ppb 0 x 1 a , b 0 x 1 a 0 p100 p 11 p 100 p p 100 1 0.x 1 bx 1 ax2 bx 2  2    2    p x 1 p b 1 x 1 p a , b 0 x 1 a 0 p 11 p100 p p 100 98 11 bx ax2 bx p 22    ppb 1 x 1 a , b 0 x 1 a 0 p 11 p100 p p 100 98 11 k ax2 bx p 22    ppb 1 k 1 a , b 0 x 1 a 0 (Do b không chia hết cho nên bx x 1,2,..., p là hệ thặng dư đầy đủ mod p ) pp 1 100 98 1 ax2 bx p 2   p a, b 0 x 1 a 0 p 2 100 pp 1 2ax b b2 1 p98 44aa. 2  p a, b 0 x 1 a 0 2 100 pp 1 2ax b2 1 p98 44aa. 2  p a, b 0 x 1 a 0 9
10. (Do 2a , p 1 2 ax b x 1,2,..., p , 2 ax x 1,2,..., p là các hệ thặng dư đầy đủ mod p ) 100 pp 1 b2 2 98 1 ax 4a p 2  . p a, b 0 x 1 a 0 100 pp 1 25b2 1 2 p98 a ax 2  . p a, b 0 x 1 a 0 Suy ra 100 p 1 2 2 2 1 a x1 x 2 ... x 100 b x 1 x 2 ... x 100  2  p x1, x 2 ,..., x 100 1 a , b 0 Đặt 2 p p p 22 ax222 ax a x y AA      x 1 x 1 x , y 1 Để tính tổng trên ta sẽ tìm số nghiệm nguyên dương x, y ; x , y 1,2,..., p của phương trình x22 y  t mod p , t 1,2,..., p 1 . Ta xét bổ đề 2 dưới đây Bổ đề 2. Số nghiệm nguyên dương của phương trình x22 y  t mod p , t 1,2,..., p 1 bằng p 1. Từ đó suy ra số nghiệm nguyên dương của phương trình x22  y0 mod p bằng 21p . Chứng minh. Do p1 mod 4  a 1,2,... p 1 thỏa mãn ap2  1 mod suy ra x2 y 2  x 2 a 2 y 2 mod p . Như vậy x22 y  t mod p x ay x ay  t mod p . Đặt uv x 2 u x ay, v x ay . Chú ý phương trình vu a u v yp  mod 22a uv t mod p , t 1,2,..., p 1 có p 1 nghiệm nguyên dương u, v ; u , v 1,2,..., p 1 . Ta thấy mỗi nghiệm nguyên dương cho ta một nghiệm nguyên dương được xác định theo u x ay, v x ay . Tiếp theo mỗi nghiệm 10
11. nguyên dương cho ta một nghiệm nguyên dương uv xp mod 2 được xác định theo . a u v yp mod 2 Số nghiệm nguyên dương của phương trình bằng p2 p 1 p 1 2 p 1. Do đó bổ đề 2 được chứng minh. Áp dụng bổ đề 2 ta được p2 p100 p 1 p 11 p 22 a x2 x 2 ... x 2 b x x ... x 2 ax2 1 a x y 1 2 100 0 1 2 100 a . t t A 2  2 p 1 .  p 1 .  2 p 1 p 1 .  p    x 1x1 x, x, 2y ,..., 1 x 100 1 a , b 0 t 1 t 1 2p 1 p 1 1  ...p 1 1 2 p 1 p 1 p . Suy ra p 1 25b2 981 a 50 pp2   . (1). x, y ;p x ,ab y,0 1,2,..., p a 0  Do a không chia hết cho nên tồn tại mp 1,2,..., 1 sao cho 1 25b2 ma1 mod p  m mod p  25 b2 m mod p . Kết hợp với (1) ta được aa 22 x  ypp0 11 mod25b p2 2 981 a 50 98 48 48 25bm p 2 .1 p p p p p p a, b 0 m , b 1 a 0 Với mỗi số b 1,2,..., p 1 25 b22 , p 1 25 b x x 1,2,..., p 1 lập thành hệ thặng dư thu gọn mod p . Do đó p 1 p 1 p 1 p98 p 49 p 48 k p 98 p 48 p 1 p 48 1 p 98 .  p  b 1 k 1 b 1 u, v ; u , v 1,2,..., p 1 Vậy số bộ sắp thứ tự thỏa mãn yêu cầu bài toán là 201798 . Bài II.2 (VMO 2015). Cho số nguyên dương k . Tìm số các số tự nhiên n không vượt quá k 10 thỏa mãn đồng thời các điều kiện sau: a) n chia hết cho 3; x1, x 2 ,..., x 100 b) Các chữ số trong biểu diễn thập phân của n thuộc tập hợp 2,0,1,5 . 11
12. Lời giải. 22 Cách 1 (Sử dụng định lí I.4.1).Đặt  cosi sin , x là số các số tự nhiên có chữ số, 33j mỗi chữ số được lấy từ các chữ số 2, 0, 1, 5 và có tổng các chữ số  j mod3 . Khi đó ta có 2 k j x12 x ... xk 2 0 1 5 x j      j 0 x12 , x ,..., xk 2,0,1,5 kk 2 1   2  2  2k Ta xét các trường hợp sau +) k  0 mod 3 ta có 2 jk2  x j 1 j 0 Do đó theo định lí I.4.1 ta có x x x 1 41k 42k x 1 x x x 1 0 1 2 x 0 1 2 0 330 3 +) k 1 mod 3 ta có 2 jk22  x j   j 0 Do đó theo định lí I.4.1 ta có x x x 1 41k 41k x x x 1 x 0 1 2 x 0 1 2 0 330 3 +) k  2 mod 3 ta có 2 jk2  x j   j 0 Do đó theo định lí I.4.1 ta có 41k x x 1 x x . 0 1 2 0 3 22 k Cách 2 (Sử dụng định lí I.4.2) Đặt  cosi sin , xét đa thức 33 k P x x2 x 0 x 1 x 5 12
13. Ta có 5k j P x  aj x , j 0 trong đó a j là số các số tự nhiên có chữ số, mỗi chữ số được lấy từ các chữ số 2, 0, 1, 5 và có tổng các chữ số bằng j . Theo định lý I.4.2 ta có 3 1 h aPj  31jh3 Với 12 h , ta có kk P h 2 h  0  h  5 h  2 h  0  h  2 h  2 h . k Ta xét các trường hợp sau +) k  0 mod 3 ta có Ph h 5. h k 1, 1 2, 3 k 1h 4 2 aPj  31jh33 +) k 1 mod 3 ta có Ph h 5 h . k  2 h , 1 2 , 3 k2 4 k 2 k 1h 4   4   4 1 aPj  31jh3 3 3 3 +) k  2 mod 3 ta có Ph h 5. h k  h , 1 2 , 3 k2 4 k 2 k 1h 4   4   4 1 aPj  31jh3 3 3 3 Nhận xét. Đây là một bài toán quen thuộc và đã xuất hiện nhiều dạng toán quen thuộc với cách giải tương tự như vậy. k Bài II.2.1 (Rumania 2003). Cho tập hợp X 2;3;7;9 và n là số nguyên dương. Hỏi từ tập X ta có thể lập được bao nhiêu số nguyên dương, mỗi số có n chữ số và chia hết cho 3 ? 13
14. Bài II.2.2 (PTNK TPHCM 2009). Cho số nguyên dương . Có bao nhiêu số chia hết cho 3, có chữ số và các chữ số đều thuộc tập hợp 3,4,5,6 ? x j Bài II.3 (Hong Kong MO 2017) Cho k là một số nguyên dương. Tìm số các số nguyên không âm n không vượt quá 10k thỏa mãn các điều kiện sau: (i) n chia hết cho 3; (ii) Mỗi chữ số của n khi viết trong hệ thập phân là một trong các chữ số 2,0,1,7. Lời giải. Tương tự bài II.2. Bài II.4 Cho n là số nguyên dương lớn hơn 1. Tìm số tập con A của tập hợp Xn 1,2,3,...,  sao cho tổng các phần tử của A chia hết cho 7 Lời giải 22 Cách 1 (Sử dụng định lí I.4.1). Đặt  cosi sin , là số tập con của tập hợp X có 77 tổng các phần tử  j mod7 . Khi đó ta có 6 jnSB 2 x j  1  1  ... 1  (1) j 0 B 1,2,..., n Ta có x7 1 x  x  2 ... x  7 x7 1 x  x  2 ... x  7 x7 1 x  x  2 ... x  7 1  1 27 ... 1  2 (2) Ta xét các trường hợp sau +) n  0 mod7 , từ (1) và (2) ta được 6 n j 7  x j 2 j 0 Do đó theo định lí I.4.1 ta được n 7 x0 2 x 1 ... x 6 n n n n x x ... x 27 22n 7 x 27 0 1 6 0 77 14
15. n 2n 6.27 x 0 7 +) n 1 mod7 , từ (1) và (2) ta được 6 nn 11 jn77  x j 2 1  2 1  j 0 Do đó theo định lí I.4.1 ta được nn 11 77 x0 2 x 1 2 ... x 6 n 1 n 1 n 1 x x ... x 2.2 7 2n 2.2 7 x 2 7 0 1 6 0 77 22  cosi sinn 1 277n 5.2 7 x 0 7 Tương tự cho các trường hợp nn2 mod 7 ,..., 6 mod 7 . Cách 2 (Sử dụng định lí I.4.2). Đặt , xét đa thức P x 1 x 1 x2 ... 1 xn Ta có nn 1 2 k P x  ak x , k 0 trong đó ak chỉ số tập con có tổng các phần tử bằng k . Theo định lý I.4.2 ta có 7 1 j aPk  71kj7 Mặt khác ta lại có x7 1 x j x  2 j ... x  7 j x7 1 x j x  2 j ... x  7 j x7 1 x j x  2 j ... x  7 j 15
16. 1 j 1 27 j ... 1  j 2 Ta xét các trường hợp sau x j +) ta có n n j j27 j j 7 7 Pj  1  1  ... 1  2 ,1 6 , n 7 n 7 1j 2 6.2 aPk  71kj77 +) n 1 mod7 ta có n 1 n 1 Pj j 1  j 1 27 j ...1  j 7 1  nj 217  j ,1 6 , 22  cosi sin 77n 1 7 n 7  j mod7 1j 2 5.2 aPk  71kj77 nn2 mod 7 ,..., 6 mod 7 Tương tự cho các trường hợp . Bài II.5. Có bao nhiêu số tự nhiên có tổng các chữ số chia hết cho 7, có n chữ số và mỗi chữ số được lấy từ các chữ số 1, 3, 4, 6, 7, 9. Lời giải Cách 1 (Sử dụng định lí I.4.1). Đặt , là số các số tự nhiên có n chữ số, mỗi chữ số được lấy từ các chữ số 1, 3, 4, 6, 7, 9 và có tổng các chữ số . Khi đó ta có 6 n j x12 x ... xn 3 4 6 7 9 x j        j 0 x12 , x ,..., xn 1,3,4,6,7,9 n  0 mod7 nn 1  2  3  4  5  6  5  5 Ta xét các trường hợp sau +) ta có 6 j 5 n n  x j 1 j 0 Do đó theo định lí I.4.1 ta có 16
17. n x0 1 x 1 ... x 6 nnn n x x ... x 1 6 1 x 1 0 1 6 0 77 6n 6. 1 n x 0 7 +) n 1 mod7 ta có 6 j 55n n  x j  1  j 0 Do đó theo định lí I.4.1 ta có n x x ... x x 1 x 0 1 422 5 6  cosi sin 77 x x ... x 1 nn 6n 1 x 0 1 6 0 77 nn2 mod 7 ,..., 6 mod 7 6n 6. 1 n x 0 7 Tương tự cho các trường hợp . Cách 2 (Sử dụng định lí I.4.2) Đặt , xét đa thức n P x x x3 x 4 x 6 x 7 x 9 Ta có a 9n k k k P x  ak x , k 0 trong đó là số các số tự nhiên có n chữ số, m7ỗi chữ số được lấy từ các chữ số 1, 3, 4, 6, 7, 1 j 9 và có tổng các chữ số bằng . aPk  71kj7 Theo định lý I.4.2 ta có Với 16 j , ta có n P j  j 3 j  4 j  6 j  7 j  9 j 17
18. n 11 j 2 j  3 j  4 j  5 j  6 j  5 j n  5 nj Ta xét các trường hợp sau +) n  0 mod7 ta có Pj j 1 nn5 nj 1 ,1 6 , n 7 n 1 j 6 6. 1 aPk  71kj77 Tương tự cho các trường hợp . Bài II.6 (IMO 1995). Cho p là một số nguyên tố lẻ và tập hợp Ap 1,2,...,2  . Tìm số tập hợp con của tập hợp A mà mỗi tập con đó có k phần tử và tổng các phần tử chia hết cho p , trong đó k 12 k p là số nguyên dương cho trước. Lời giải nn2 mod 7 ,...,22 6 mod 7 Cách 1 (Sử dụng định lí I.4.1). Đặt  cosi sin , kí hiệu x ( jp 0,1,..., 1) là số tập pp j hợp con X của A sao cho S X  j mod p và Xk . Ta có p 1 j SX c12 c ... ck x j     j 0 X  A , X k 1 c12 c ... ck 2 p Ta nhận thấy   c12 c ... ck bằng hệ số của x2 pk trong khai triển thành đa thức của 1 c12 c ... ck 2 p x  x 22 ... x  p . Mặt khác ta có xpp 1 x  x 2 ... x  xpp 1 x 12 x  ... x  xpp 1 x 12 x  ... x  Do đó ta được x  x 22 ... x  p 2 1 x p Ta xét các trường hợp sau TH1. Nếu kp thì hệ số của xx2 p k p bằng 2. Do đó ta được 18
19. p 1 j c12 c ... ck x j 2 j 0 1 c12 c ... ck 2 p Kết hợp với định lí I.4.1 ta có x0 2 x 1 ... xp 1 x x ... x 2 C p 2 x 2 0 1pp 1 2 0 pp C p 2 x 2 p 2 0 p TH2. Nếu kp thì hệ số của x2 pk bằng 0. Do đó ta được Kết hợp với định lí I.4.1 ta có x0 x 1 ... xp 1 x x ... x C k x 0 1pp 1 2 0 pp C p 2 Ck Vậy x 2 p 2 nếu kp và x 2 p nếu . 0 p 0 p Cách 2 (Sử dụng định lí I.4.2) Xét đa thức P x, y 1 xy 1 x22 y ... 1 xp y Ta có nm ank, x y nm, Trong đó anm, là số các tập con có m phần tử và tổng của m phần tử này bằng n. Theo định lí I.4.2 ta được p 1 mj1 anm, y F  , y n pp j 0 Ta có F 1, y 1 y 2 p và với 11 jp thì 19
20. F j, y 1  j y 1 22 j y ... 1  pj y 2 j2 j pj 1 y 1  y ... 1  y 2 22p 1 j 1 j 1 pj y   ...  y y y 2 p 2 pp 1 2 yy 11 y Suy ra p 1 112 p 2 a ym F j, y 1 y p 1 1 y p nm, n ppp j 0 Do đó 1 1 p k  an,2 m C p 21 p nếu kp và  aCn,2 m p nếu kp . n p, m k p n p, m k p Bài II.7 (IMO Shortlist 2007).Tìm tất cả các số nguyên dương n sao cho mỗi phần tử của tập Sn 1;2;3;...;  được tô bởi màu đỏ hoặc xanh, sao cho các điều kiện sau đồng thời xảy ra: Tập hợp SSS chứa đúng 2007 bộ thứ tự x;; y z và thỏa mãn: (i) các số x;; y z được tô cùng một màu, (ii) số x y z chia hết cho n . Lời giải. Kí hiệu M là số bộ thứ tự thỏa mãn yêu cầu bài toán. Gọi A, B 1,2,3,..., n là các tập hợp các số tương ứng với màu đỏ, xanh và A u, B v . Ta xét các đa thức sau: f x  xab, g x x a A b B 33 a1 a 2 a 3 b 1 b 2 b 3 n P x f x g x  x x axn ; 33 a1,,,, a 2 a 3 A b 1 b 2 b 3 B n trong đó an là số bộ x,, y z thỏa mãn x,, y z cùng màu và x y z chia hết cho n .Đặt 22  cosi sin , theo định lí I.4.2 ta được: nn 20