Tài liệu Học một bài toán như thế nào

Học một bài toán như thế nào? Trần Nam Dũng ĐH KHTN Tp HCM Quý hồ tinh bất quý hồ đa Tôn Vũ Để cải thiện trí óc, ta cần học ít, thấu hiểu nhiều Rene Descartes Đi chậm, tiến xa Ngạn ngữ Nga Mỗi một bài toán tôi giải đều trở thành quy tắc mà sau này được dùng để giải những bài toán khác Hãy chia những khó khăn thành những thành phần đủ nhỏ để có thể giải quyết chúng Rene Descartes Làm thế nào để học tốt môn toán luôn là câu hỏi mà nhiều bạn học sinh trăn trở. Tại sao có nhiều bạn bỏ rất nhiều thời gian cho việc học toán, nhưng tiến bộ thì rất chậm, nhiều lúc còn đứng yên tại chỗ và thụt lùi? Có nhiều bạn nhìn học rất thoải mái, nhưng học đâu hiểu đó, áp dụng được những điều mình đã học vào các tính huống khác nhau. Vấn đề là ở cách học. Khi học một bài toán, có bạn chỉ học qua loa, nắm được lời giải là thôi, chuyển ngay qua bài toán khác. Không đào sâu khai thác, không so sánh với những bài toán khác để tìm những cái chung, không tóm tắt lại để biết đâu là điểm chính yếu, không mở rộng để xem phương pháp giải sẽ còn áp dụng được đến đâu. Vì thế, một lời giải chỉ đơn thuần là một lời giải. Không phải là phương pháp, không có sự kết nối đa chiều với những bài toán khác. Chúng ta cứ tưởng tượng, nếu cần thuộc đường ở Tp Hồ Chí Minh. Với hàng trăm con đường như thế, chúng ta có nhớ nổi không? Và nếu bỏ công sức ra học thì bao giờ mới nhớ hết? Nhưng nếu ta học một cách có hệ thống, đầu tiên là các trục ngang, trục dọc lớn, sau đó là các cụm theo quận, theo phường. Ta không cần nhớ hết, chỉ cần biết ở quận nào, phường nào, gần đường lớn nào. Khi cần chi tiết ta sẽ nghiên cứu sau, vì khi đã khoanh vùng được thì đó không còn là việc khó. Học giải toán cũng vậy. Nếu chúng ta học các bài toán một cách riêng rẽ thì biết bao nhiêu là đủ. Và ta có đủ thời gian để nhớ được bao nhiêu bài toán. Và nếu ta biết rằng khó hy vọng cho sự trúng tủ, mà chỉ có thể là những bài toán gần, tương tự, có mối liên hệ với những bài toán mình biết. Vậy thì khi cần vận dụng mối liên hệ với những bài toán đó, trong kho tàng vài nghìn bài toán được sắp xếp lộn xộn, không có lớp lang thì ta có đủ thời gian mà đem ra mà dùng không? Nói một cách hình ảnh, giả sử ta có 100 bài toán, thay vì học cả 100 bài một cách riêng lẻ, ta có thể chọn ra 10-15 bài chốt. 1 3 4 2 13 5 15 14 6 7 8 9 10 11 12 Lúc đó, mỗi một bài toán chốt (ta biết rõ cách giải) hay thường (là những bài toán ta chưa biết nhưng có thể gặp) đều có những mối liên hệ hàng ngang, cột dọc hay đường chéo với những bài toán khác. Từ đó, khi cần ta sẽ có thể phục hồi lại, y như ta giải Sudoku vậy. Dưới đây ta xem xét một số ví dụ về khai thác phương pháp giải toán từ những chứng minh và lời giải kinh điển. 1. Chứng minh của G.Polya cho bất đẳng thức AM-GM và bài học về sử dụng hằng số trong bất đẳng thức không thuần nhất. Chúng ta đều biết bất đẳng thức AM-GM và rất nhiều các cách chứng minh của nó: dùng quy nạp lùi, dùng hàm lồi, dùng khai triển, dùng dồng biến ... Tuy nhiên cách chứng minh dưới đây của G.Polya rất đẹp đẽ và đem đến cho ta nhiều bài học bổ ích. Bất đẳng thức AM-GM. Nếu a1, a2, ..., an là n số thực dương thì ta có a1  a2  ...  an n  a1a2 ...an n Chứng minh. Trước hết ta chứng minh bổ đề Bổ đề. Nếu x1, x2, ..., xn là các số thực dương có tích bằng 1 thì x1 + x2 + ... + xn ≥ n. Ta chứng minh bổ đề bằng quy nạp theo n. Với n = 1 mệnh đề hiển nhiên đúng. Giả sử mệnh đề đã đúng với n số. Ta chứng minh mệnh đề đúng với n+1 số. Xét n+1 số x1, x2, ..., xn, xn+1 có tích bằng 1. Nếu tất cả các số bằng nhau (và bằng 1) thì bất đẳng thức trở thành đẳng thức. Trong trường hợp ngược lại, phải có 1 số > 1 và 1 số < 1. Không mất tính tổng quát, giả sử đó là xn < 1 và xn+1 > 1. Khi đó ta có (xn - 1)(xn+1-1) < 0, suy ra xn + xn+1 > xnxn+1 + 1. Từ đó ta có x1 + ... + xn-1 + xn + xn+1 > x1 + ... + xn-1 + xnxn+1 + 1 (1) Áp dụng giải thiết quy nạp cho n số x1, ..., xn-1, xnxn+1 có tích bằng 1, ta có x1 + ... + xn-1 + xnxn+1 ≥ n (2) Từ (1) và (2) ta suy ra x1 + ... + xn-1 + xn + xn+1 > n+1 Như vậy bổ đề đúng đến n+1. Theo nguyên lý quy nạp toán học, bổ đề đúng với mọi n. Quay trở lại bài toán, ta đặt x1  x1... xn  a1 an thì ,..., xn  n a ...a n a ...a 1 n 1 n a1 an a ...a ...  1 n 1 n a ...a n a ...a a1...an 1 n 1 n Áp dụng bổ đề ta có x1  ...  xn  n  n a1 an a  ...  an n  ...  n 1  a1...an . n n a1...an a1...an Bất đẳng thức AM-GM được chứng minh. Trong lời giải này, có 2 ý tưởng chính, thứ nhất là bước đưa bài toán về bài toán với điều kiện chuẩn hóa x1...xn = 1 và thứ hai là bước sử dụng hằng số 1 để "dồn" xn, xn+1 thành xnxn+1 (cụ thể là thay xn + xn+1 bằng xnxn+1 + 1). Nhờ bước thay thế này mà ta áp dụng được giả thiết quy nạp. Ta sẽ tiếp tục phân tích ý tưởng chuẩn hóa ở bước 1 trong mục sau. Ở đây ta khai thác ý tưởng sử dụng hằng số để so sánh các đại lượng không cùng bậc. Bài toán 1. Cho x, y, z là các số thực dương. Chứng minh rằng ta có bất đẳng thức x2 + y2 + z2 + 2xyz + 1 ≥ 2(xy+yz+zx) (1) 2 2 2 Phân tích. Ở đây x + y + z và xy + yz + zx là cùng bậc, có thể so sánh được, nhưng xyz là đại lượng khác bậc. Ta muốn dùng hằng số 1 để so sánh xyz với các đại lượng vế trái, làm đơn giản bớt thành phần này. Giải. Trong 3 số x, y, z luôn có hai số cùng lớn hơn hay bằng 1 hoặc cùng nhỏ hơn hay bằng 1. Giả sử đó là x, y thì ta có (x-1)(y-1) ≥ 0, suy ra xy + 1 ≥ x + y Từ đó 2xyz + 2z ≥ 2xz + 2yz (2) Như vậy, để chứng minh (1), ta chỉ cần chứng minh x2 + y2 + z2 + 1 ≥ 2xy + 2z Nhưng bất đẳng thức cuối này là hiển nhiên vì nó tương đương với (x-y)2 + (z-1)2 ≥ 0. Bài toán 1 là một bổ đề có nhiều ứng dụng hiệu quả, đặc biệt là trong các bất đẳng thức không thuần nhất chứa xyz. Bạn đọc có thể sử dụng bài toán 1 để giải 2 bài toán song sinh sau: Bài tập 1. (Hello IMO 2007) Cho x, y, z là các số thực dương. Chứng minh rằng ta có bất đẳng thức xyz + 2(x2+y2+z2) + 8 ≥ 5(x+y+z). Bài tập 2. (Ninh Thuận 2014) Cho x, y, z là các số thực dương. Chứng minh rằng ta có bất đẳng thức xyz + x2+y2+z2 + 5 ≥ 3(x+y+z). Hằng số 1 trong áp dụng nói trên, về nguyên tắc, có thể thay bằng hằng số bất kỳ. Điều quan trọng trong việc chọn hằng số nào là nó phải liên quan đến các đại lượng ở hai vế và phải giúp ta giải quyết được bài toán. 1 b 1 c 1 a Bài toán 2. Cho a, b, c > 0, x  a  , y  b  , z  c  . Chứng minh rằng ta có bất đẳng thức xy + yz + zx ≥ 2(x + y + z). (1) Phân tích. Trong ví dụ này, ta cũng dùng kỹ thuật chuồng và thỏ, nhưng vách ngăn là số 2. Điều này có thể thấy rõ từ hai vế của BDT cần chứng minh. Giải. Trong 3 số x, y, z luôn có hai số cùng lớn hơn hay bằng 2 hoặc cùng nhỏ hơn hay bằng 2. Giả sử đó là x, y thì ta có (x-2)(y-2) ≥ 0, suy ra xy + 4 ≥ 2(x + y) (2) Như vậy, để chứng minh (1), ta chỉ cần chứng minh yz + zx ≥ 2z + 4 hay là z(y+x-2) ≥ 4 Thật vậy, ta có (3) 1  1 1 1  1 c a    z  x  y  2    c   a   b   2    c   a    2 .2 4 a  b c a  c a c    1 (Ở đây ta đã sử dụng đánh giá b   2 và 2 lần dùng AM-GM ở cuối). Tức là (3) đúng. b Cộng với (2) vế theo vế, ta có đpcm. Bài toán 3. (VMO 1996) Cho x, y, z là các số thực dương thỏa mãn điều kiện xy + yz + zx + xyz = 4. Chứng minh rằng x + y + z ≥ xy + yz + zx (1). Phân tích. Các đại lượng ở đây ngược chiều so với ví dụ 1, 2. Do đó ta không đi theo cách chuồng và thỏ mà đi theo cách của Polya. Giải. Giả sử x ≥ y ≥ z. Vì xy + yz + zx + xyz = 4 nên không thể tất cả các số đều > 1, cũng không thể tất cả các số đều < 1. Từ đây suy ra x ≥ 1 và z ≤ 1. Đặt s = x + z và p = xz thì ta có y(s+p) = 4 - p và ta cần chứng minh s + y ≥ sy + p Ta có (s+p)(s+y-sy-p) = s2 + sp + 4 - p - 4s + ps - sp - p2 = (s - 2)2 + p(s - p - 1). Mặt khác thì s - p - 1 = x + z - xy - 1 = (x-1)(1-z) ≥ 0 nên từ đây suy ra (s+p)(s+y-sy-p) ≥ 0, có nghĩa là s+y-sy-p ≥ 0 (đpcm). Bài tập 3. (PTNK 2014) Cho a, b, c là các số thực dương thỏa mãn điều kiện (a+1)(b+1)(c+1) = 1 + 4abc Chứng minh rằng ta có bất đẳng thức a  b  c  1  abc . 2. Bài học từ Polya về chuẩn hóa trong chứng minh bất đẳng thức. Trong các bài toán ở trên, ta thấy rằng sử dụng các hằng số một cách thích hợp, ta đã rút gọn được các bất đẳng thức cần chứng minh để đưa về các bất đẳng thức đơn giản hơn. Với bất đẳng thức thuần nhất thì không thể có những hằng số như thế (vì khi nhân tất cả các biến với cùng một đại lượng thì bất đẳng thức không thay đổi, trong khi hằng số bị thay đổi). Những hằng số đó sẽ xuất hiện nếu ta đưa ra các điều kiện chuẩn hóa. Ngoài ra, chuẩn hóa còn giúp chúng ta đơn giản các biểu thức cồng kềnh, đặc biệt là các biểu thức chứa căn. Ta bắt đầu bằng một ví dụ kinh điển. Cho a = (a1, a2, ..., an) là bộ gồm n số thực dương. Với số thực r, ta đặt 1 r  a  ...  a  M r (a )    (trung bình bậc r của bộ a) n   r 1 r n Ta có bất đẳng thức trung bình lũy thừa nổi tiếng sau: Nếu r > s thì Mr(a) ≥ Ms(a). Rất thú vị là bất đẳng thức cực mạnh này (từ đây suy ra AM-GM, Cauchy-Schwarz, bất đẳng thức trung bình điều hòa) lại được chứng minh chỉ dùng BDT Bernoulli. Dưới đây ta xét trường hợp chính của bất đẳng thức này. Bài toán 4. Nếu r > s > 0 thì Mr(a) ≥ Ms(a). Giải. Biểu thức của Mr(a) và Ms(a) là khá cồng kềnh và ta chưa biết sẽ xử lý thế nào. Sử dụng ý tưởng từ chứng minh của G.Polya, ta giải bài toán "đã được chuẩn hóa sau". Bổ đề. Cho r > s. Nếu a1s + a2s + ... + ans = n thì a1r + a2r + ... + anr ≥ n. Chứng minh bổ đề. Do r > s > 0 nên r/s > 1. Áp dụng bất đẳng thức Bernoulli ta có r air  1  ais  1 s  1  r s  ai  1 s Cho i chạy từ 1 đến n rồi cộng lại vế theo vế, ta có đpcm. Bài tập 4. Hãy từ bổ đề suy ra kết quả bài toán 4. Bài toán 5. Cho x, y, z là các số thực dương thỏa mãn điều kiện  1 1 1 ( x  y  z )      10. x y z Tìm giá trị lớn nhất, giá trị nhỏ nhất của biểu thức  1 1 1 P  ( x2  y 2  z2 )  2  2  2 . y z  x Lời giải bài toán này có thể chia nhỏ thành các bước sau. Bước 1. Dùng tư tưởng chuẩn hóa, đưa bài toán về bài toán tương đương (vì sao?) như sau: Cho x, y, z > 0, x + y + z = 10, 1/x + 1/y + 1/z = 1. Tìm GTLN và GTNN của  1 1 1 P  ( x2  y 2  z2 )  2  2  2 . y z  x Bước 2. Đặt t = xyz = xy + yz + zx. Tính P theo t. Bước 3. Đánh giá x, y, z bằng phương pháp điều kiện có nghiệm của hệ phương trình. Bước 4. Đánh giá t bằng khảo sát hàm số hoặc phương pháp sử dụng hằng số. Bước 5. Đánh giá P. Bài tập 5. (VMO 2004) Cho x, y, z là các số thực dương thoả mãn điều kiện (x+y+z)3 = 32xyz. Tìm giá trị lớn nhất và giá trị nhỏ nhất của x4  y4  z4 P ( x  y  z) 4 Bài tập 6. (British MO) Cho x, y, z là các số thực thoả mãn điều kiện x + y + z = 0, x2 + y2 + z2 = 6. Tìm giá trị lớn nhất và giá trị nhỏ nhất của P = x2y + y2z + z2x. 3. Loạt bài toán liên quan đến bài PTNK 2014 và Sóc Trăng 2014. Trong kỳ thi chọn đội tuyển của các trường và các tỉnh vừa qua, có hai bài toán sau đây Bài toán 6. (PTNK 2014) Cho X = {1, 2, ..., 19}. Chứng minh rằng tồn tại tập hợp F gồm ít nhất 2600 tập con 7 phần tử của X sao cho với mọi A khác B thuộc F thì | A  B | ≤ 5. Bài toán 7. (Sóc Trăng 2014) Một nhóm học sinh có n người. Họ tổ chức 10 cuộc gặp mặt, mỗi cuộc gặp mặt có 20 học sinh tham dự. Hai học sinh bất kỳ tham gia chung không quá một cuộc gặp. Tìm giá trị nhỏ nhất của n. Bài toán 6 thuộc về dạng xây dựng ví dụ. Những bài này luôn rất khó và không thể làm thủ công được. Lời giải bài này dựa vào ý tưởng sau. Với mỗi k = 0, 1, 2, ..., 18, nếu đặt P(k) = {A  X| | A | = 7, S(A)  k mod 19} (ở đây ta ký hiệu S(A) là tổng các phần tử của A) thì P(k) thỏa mãn điều kiện nếu A khác B thuộc P(k) thì | A  B | ≤ 5 (vì nếu | A  B | = 6 thì A = {a1, ..., a6, a}, B = {a1, ..., a6, b} và S(A) - S(B) = a - b  0 mod 19). Mặt khác ta có |P(0)| + |P(1)| + ... + |P(18)| = C197 . Từ đó suy ra tồn tại k sao cho | P(k) |  C197  2652 . 19 Bài toán 7 thuộc dạng cực trị rời rạc, bao gồm cả đánh giá và xây dựng ví dụ. Và hóa ra, bước đánh giá là khá đơn giản. Cách 1. Ta lập danh sách của 10 chuyến đi. Cho chuyến đi đầu tiên, ta cần 20 học sinh. Cho chuyến đi thứ hai, ta cần ít nhất 19 học sinh mới (tức là học sinh chưa từng đi chuyến trước, do chỉ có nhiều nhất 1 học sinh đi chuyến trước). Cho chuyến đi thứ ba, ta cần ít nhất 18 học sinh mới (do chỉ có nhiều nhất 2 học sinh đi các chuyến trước). Cứ như vậy đến chuyến thứ 10, ta cần ít nhất 11 học sinh mới. Như vậy số học sinh không ít hơn 20 + 19 + 18 + .... + 11 = 155. Cách 2. Ta mô hình hóa bài toán như sau: Cho X = {1, 2, ..., n}. Giả sử tồn tại 10 tập con A1, A2, ..., A10 của X thỏa mãn các điều kiện i) |Ai | = 20, với mọi i = 1, 2, ..., 10 ii) | Ai  Aj | ≤ 1 với mọi 1 ≤ i < j ≤ 10. Tìm giá trị nhỏ nhất của n. Áp dụng bất đẳng thức bao hàm và loại trừ (hay BĐT Bonferroni), ta có n | 10 i 1 10 Ai | | Ai |  i 1  1i  j 10 | Ai  Aj |  10.10  45.1  155 . Cách 3. Cách 3 này phức tạp hơn cả, nhưng, như chúng ta sẽ thấy về sau, là cách có khả năng mở rộng xa nhất và sâu nhất. Trước tiên, ta mô hình hóa bài toán như ở cách 2. Ta lập bảng thành viên gồm 10 dòng và n cột, dòng đại diện cho 10 chuyến đi (các tập Ai) và cột đại diện cho n học sinh (phần tử của X) 1 2 3 ... n-1 n A1 A2 ... A10 Ở dòng i cột j ta sẽ viết số 1 nếu j  Ai (học sinh j dự cuộc gặp mặt thứ i). Trong trường hợp ngược lại, ta viết số 0. Khi đó, tổng số các số 1 trên mỗi dòng, theo giả thiết, bằng 20. Do đó tổng số các số 1 trong toàn bảng bằng 200. Nhưng điều kiện |Ai  Aj| ≤ 1 sẽ được thể hiện như thế nào trên ngôn ngữ của bảng thành viên? Đó là không có 4 số 1 tạo thành đỉnh của một hình chữ nhật. Nói cách khác, mỗi cặp số 1 trên dòng sẽ xuất hiện không quá 1 lần trên 2 cột tương ứng và mỗi cặp số 1 trên cột sẽ xuất hiện trên 2 dòng tương ứng không quá 1 lần. Ta thử dùng ý này để đánh giá n. Nếu đếm số cặp số 1 trên dòng thì trên mỗi dòng có 2 C20  190 cặp số 1. Mặt khác, mỗi cặp cột chứa nhiều nhất 1 cặp số 1 trên dòng, do đó số cặp số 1 trên dòng không lớn hơn Cn2 . Từ đây ta suy ra n(n-1) ≥ 3800. Từ đó n ≥ 63. Đánh giá này quá không chặt. Ta cũng có thể nhận ra ngay điều này khi bắt tay xây dựng ví dụ dấu bằng xảy ra. Ta đổi lại tính số cặp số 1 trên cột. Để làm điều này, ta gọi cj là số số 1 trên dòng j. Ta dễ thấy c1 + c2 + ... + cn bằng tổng số số 1 trong toàn bảng, do đó bằng 200. Ta đếm số cặp số 1 trên cột bằng 2 cách. Cách 1 là đếm theo cột. Cột thứ j có cj số 1 do đó có Cc2  j n  j 1 c j ( c j  1) 2 c j ( c j  1) cặp số 1. Như vậy tổng số cặp số 1 trên cột của toàn bảng bằng 2 Mặt khác, ta có C102  45 cặp dòng, mỗi cặp dòng chứa không quá 1 cặp số 1 trên cột. Do đó toàn bảng có không quá 45 cặp số 1 trên cột. Từ đây ta suy ra bất đẳng thức n c j (c j  1) j 1 2  n n j 1 j 1  45   c 2j   c j  90  290 Làm thế nào để từ đây đánh giá n? Ở đây, do ta biết tổng n c j 1 j nên ta có thể dùng BĐT Cauchy-Schwarz để đánh giá: 2  n   cj  n j 1 2   n  40000  137.9 290   c j   n 290 j 1 Suy ra n ≥ 138. Theo như những lời giải ở trên thì ta đã biết n = 138 không phải là đáp số. Nhưng nếu ta chưa biết đáp số 155 thì sao? Suy nghĩ 1 chút, ta thấy nếu n = 138 thì gần như dấu bằng đã xảy ra, tức là các cj gần như bằng nhau. Nhưng không thể có 138 số nguyên không âm gần như bằng nhau có tổng bằng 200 được. Như vậy đánh giá bằng Cauchy-Schwarz là không chặt. Ta nhận thấy rằng do tổng các cj bằng 200 và có hơn 138 số như vậy nên cj sẽ bằng 1, hoặc 2. Như vậy nếu ta dùng bất đẳng thức (cj-1)(cj-2) ≥ 0 (bất đẳng thức này đúng với mọi cj nguyên) thì có khả năng dấu bằng xảy ra với mọi j, tức là ta có một bất đẳng thức chặt. Áp dụng bất đẳng thức này, ta có đánh giá n n n j 1 j 1 j 1 290   c2j   (3c j  2) 3 3c  2n  600  2n Suy ra 2n ≥ 310, tức là n ≥ 155. Ta cũng đi đến kết quả như 2 cách 1, 2. Tuy cồng kềnh hơn nhưng là một mô hình có thể mở rộng tốt hơn. Điều này sẽ được nhấn mạnh trong phần sau. Nhưng trước hết, thông tin cj = 1 hoặc 2 (cụ thể có 45 số bằng 2 và 110 số bằng 1) giúp ta dễ dàng hơn trong việc xây dựng ví dụ cho n = 155: A1 = {1, 2, ..., 20} A2 = {1, 21, 22, ..., 39} A3 = {2, 21, 40, 41, ..., 57} A4 = {3, 22, 40, 58, ..., 74} A5 = {4, 23, 41, 58, 75, ..., 90} A6 = {5, 24, 42, 59, 75, 91, ..., 105} A7 = {6, 25, 43, 60, 76, 91, 106, ..., 119} A8 = {7, 26, 44, 61, 77, 92, 106, 120, ..., 133} A9 = {8, 27, 45, 62, 78, 93, 107, 120, 134, ..., 144} A10 = {9, 28, 46, 63, 79, 94, 108, 121, 134, 145, ..., 155} Các bài toán 6, 7 đã được giải quyết trọn vẹn. Tuy nhiên, câu chuyện chỉ mới bắt đầu. Sau đây là những bình luận tiếp theo về hai bài toán này. Bình luận 1. Trong lời giải bài 6, ta sử dụng lý luận tổng các |P(k)| bằng C197 nên tồn tại k sao cho | P(k ) | C197  2652 . Nhưng liệu ta có thể làm mạnh kết quả này bằng cách tính 19 các |P(k)| và chọn số lớn nhất? Hóa ra là ta có thể chứng minh tất cả các |P(k)| đều bằng nhau và bằng 2652. Ta chứng minh bằng phương pháp song ánh như sau. Ta chứng minh mẫu là |P(1)| = |P(2)|. Bài toán không thay đổi khi ta thay X = {0, 1, 2, ..., 18}. Giả sử A = {a1, a2, ..., a7} là tập con 7 phần tử của X sao cho a1 + a2 + ... + a7  1 mod 19. Ta đặt bi = 2ai mod 19 thì b1, b2, ..., b7 cũng thuộc X, đôi một phân biệt và b1 + b2 + ... + b7  1 mod 19. Ánh xạ rõ ràng là song ánh, từ đây suy ra |P(1)| = |P(2)|. Một song ánh khác cũng có thể sử dụng là bi = ai + k mod 19 với k được chọn sao cho 7k  1 mod 19. Trong lời giải này, ta sử dụng tính chất 0, 1, 2, ..., 18 vừa đủ một hệ thặng dư đầy đủ mod 19. Nhưng nếu X = {0, 1, 2, ..., 18, 19} thì sao? Phương pháp song ánh như trên không còn khả thi. Thế nhưng ta vẫn có cách. Ta tiếp tục gọi P(k) là họ các tập con 7 phần tử của X = {0, 1, ..., 18} sao cho tổng các phần tử đồng dư k mod 19, còn Q(k) là họ các tập con 6 phần tử của X = {0, 1, ..., 18} sao cho tổng các phần tử đồng dư k mod 19. Lại gọi P*(k) là họ các tập con 7 phần tử của X = {0, 1, ..., 18,19} sao cho tổng các phần tử đồng dư k mod 19. Thế thì vẫn bằng cách chứng minh tương tự như ở trên, ta có tất cả các |P(k)| bằng nhau và tất cả các |Q(k)| bằng nhau. Nhưng rõ ràng |P*(k)| = |P(k)| + |Q(k)| nên ta tiếp tục vẫn có tất cả các |P*(k)| bằng nhau. Bằng cách này, ta có thể tiếp tục chứng minh các |P(k)| vẫn bằng nhau với X = {0, 1, 2, ..., 19, 20}. Nhưng quá trình này có thể kéo dài tiếp được không? Thoạt nhìn ta nghĩ là có thể, nhưng suy nghĩ 1 chút, ta thấy điều kiện cần để các |P(k)| bằng nhau là số tập con 7 phần tử của X phải chia hết cho 19. Mà với |X| = 26 thì rõ ràng điều này không đúng. Vậy với X = {0, 1, 2, ..., 25} thì các |P(k)| bằng bao nhiêu. Nếu làm thủ công tỷ mỉ từ dưới lên thì ta cũng có thể tính được các |P(k)| nhưng cách thủ công cũng không thể đi xa hơn nữa. Ta đề xuất một phương pháp tổng quát hơn để giải các bài toán tương tự, sử dụng số phức, cụ thể là căn của đơn vị. Ta xét trường hợp X = {0, 1, ..., 25} và tập con 7 phần tử. Như thường lệ, gọi a là căn nguyên thủy bậc 19 của 1. Khi đó 1 + a + a2 + ... + a18 = 0 và x19 - 1 = (x-1)(x-a)...(x-a18). Xét đa thức P(x) = (x-1)(x-a)(x-a2)...(x-a25). Ta tính hệ số của x19 trong P(x) bằng 2 cách. Một mặt, nếu khai triển P(x) ra thì để được ta cần lấy x từ 19 dấu ngoặc, còn 7 dấu ngoặc khác sẽ lấy các số có dạng ak với k thuộc {0, 1, ..., 25}. Như thế, ta sẽ có tổng các số có dạng aS(A) với A chạy qua tất cả các tập con 7 phần tử của X. Chú ý rằng aS(A) chỉ phụ thuộc vào số dư khi chia s(A) cho 19 (đó là lý do tại sao ta lấy căn bậc 19 của đơn vị) nên từ đây dễ dàng suy ra tổng nói trên bằng -(|P(0)| + P(1)a + ... + P(18)a18). Mặt khác P(x) = (x19-1)(x-1)(x-a)...(x-a6). Suy ra hệ số của x19 bằng -1.a.a2...a6 = -a2. Từ đây suy ra |P(0)| + |P(1)|a + (|P(2)| -1)a2 + ... + |P(18)|a18 = 0. Điều này đúng với mọi a là nghiệm của phương trình 1 + x + x2 + ... + x18 = 0. Suy ra đa thức |P(0)| + |P(1)|x + (|P(2)| -1)x2 + ... + |P(18)|x18 tỷ lệ với đa thức 1 + x + ... + x18 và vì thế |P(0)| = |P(1)| = |P(2)| - 1 = ... = |P(18)|. Suy ra tất cả các |P(i)|, i 2, bằng nhau và bằng C197  1 . Riêng |P(2)| lớn hơn đúng 1 đơn 19 vị! Lời giải cho bài tính |P(k)| với X = {0, 1, 2, ..., 25} mà không dùng số phức như sau. Đặt X1 = {0, 1, 2, ..., 18}, X2 = {19, 20, ..., 25} Đặt P1(k, s) = {A  X1| |A| = s, S(A)  k mod 19} Với B  X2 đặt P(k, B) = {A  X| |A| = 7, A  X2 = B, S(A)  k mod 19} Khi đó rõ ràng ta có P(k )  P(k , B) . B X 2 Do đó, để so sánh các P(k), ta so sánh các P(k, B). Bổ đề 1. Với mọi 1 ≤ s ≤ 7 thì các |P1(k, s)| bằng nhau với k = 0, 1, 2, ..., 18. Chứng minh bổ đề này bằng phương pháp song ánh như ở trên. Bổ đề 2. Với mọi B  X2, B  X2 thì các |P(k, B)| bằng nhau với k = 0, 1, 2, ..., 18. Chứng minh. Nếu A thuộc P(k, B) thì A  X2 = B, |A| = 7, do đó |A  X1| = 7 - |B| = s ≥ 1. S(A) = k suy ra S(A  X1) = k - S(B) mod 19. Vậy |P(k, B)| = |P1(k - S(B) mod 19, s)| Theo bổ đề 1, các số cuối bằng nhau với k = 0, 1, 2, ..., 18 nên các số ở trước cũng thế. Ta có đpcm. Riêng trường hợp B = X2 thì |P(k, B)| = 0 với k  2 và bằng 1 với k = 2. Tổng hợp lại ta có các |P(k)| bằng nhau với mọi k  2 và |P(2)| lớn hơn các |P(k)| khác đúng 1 đơn vị. (Một lời giải rất gọn cho thấy nếu dùng ký hiệu một cách bài bản có thể diễn đạt các lý luận chính xác và ngắn gọn) Bình luận 2. Ta sẽ thử lửa các phương pháp đã sử dụng trong lời giải bài toán 7 bằng cách thay đổi điều kiện một chút. Bài toán 7'. Một nhóm học sinh có n người. Họ tổ chức 10 cuộc gặp mặt, mỗi cuộc gặp mặt có 7 học sinh tham dự. Hai học sinh bất kỳ tham gia chung không quá một cuộc gặp. Tìm giá trị nhỏ nhất của n. Làm theo cách 1, ta sẽ có đánh giá: n ≥ 7 + 6 + ... + 2 + 1 = 28. Làm theo cách 2, ta sẽ có đánh giá: n ≥ 70 - 45 = 25. Làm theo cách 3, ta có đánh giá: n c j 1 2 j  160 với n c j 1 j  70 . Bây giờ áp dụng BĐT Cauchy Schwarz thì ta được 2  n   cj  n j 1 2   4900  n  4900  30.625 160   c j   n n 160 j 1 Ta có thể làm mạnh hơn bằng cách dùng bất đẳng thức cj2 ≥ 3cj - 2? n n j 1 j 1 160   c 2j  3 c j  2n  210  2n  n  50  25 . 2 Đánh giá này, trái với mong muốn, còn yếu hơn đánh giá trước đó! Tại sao vậy? Bởi vì ở đây ta có khoảng 30 số có tổng bằng 70, như vậy các số này nằm giữa 2 và 3 chứ không phải 1 và 2. Vì thế ta phải sử dụng bất đẳng thức (cj-2)(cj-3) ≥ 0, tức là cj2 ≥ 5cj - 6 thì sẽ chặt hơn. Áp dụng đánh giá này, ta có n n j 1 j 1 160   c 2j  5 c j  6n  350  6n  n  190  31.667 6 Suy ra n ≥ 32. Đây là đánh giá tốt nhất. Việc còn lại của chúng ta là xây dựng ví dụ dấu bằng xảy ra. Hai bài toán 6 và 7 có thể phát biểu thành một dạng toán tổng quát như sau. Cho X = {1, 2, ..., n}. Các tập con A1, A2, ..., Am của X có tính chất i) |Ai| = k với mọi i = 1, 2, ..., m. ii) |Ai  Aj| ≤ p với mọi i  j. Trong bài toán này có 4 tham số, là n, m, k, p. Nếu biết 3 tham số kia, có thể đánh giá các tham số còn lại. 1. Cho biết m, k, p, tìm min n. Bài Sóc Trăng cho m = 10, k = 20, p = 1. 2. Cho biết n, k, p, tìm max m. 3. Cho biết n, k, p, chứng minh có thể tìm ít nhất m tập con thỏa mãn (bài PTNK là n = 19, k = 7, p = 1, m = 2600). 4. Cho biết n, k, m. Tìm min p. Sau đây là một số bài tập tương tự chúng tôi dành cho bạn đọc ở dưới dạng bài tập. Bài tập 7. a) Có 8 cái hộp, mỗi cái hộp có 6 viên bi thuộc một trong n màu. Biết rằng không có hai viên bi cùng màu trong 1 hộp và không có hai màu xuất hiện trong quá 1 hộp. Tìm giá trị nhỏ nhất của n. b) Trong quốc hội có n thành viên. Người ta tổ chức 8 cuộc họp (tiếp nối nhau), mỗi cuộc họp có 6 người tham dự. Biết rằng 2 thành viên bất kỳ không họp chung với nhau quá 1 lần, tìm GTNN của n. c) Trong Duma quốc gia có 1600 đại biểu, lập thành 16000 ủy ban, mỗi ủy ban có 80 đại biểu. Chứng minh rằng có ít nhất hai ủy ban có không dưới 4 thành viên chung. Bài tập 8. Sau khi khai trương được đúng 10 ngày, một nhân viên thư viện cho biết : 1) Mỗi ngày có đúng 8 người đến đọc sách ; 2) Không có người nào đến thư viện 1 ngày quá 1 lần ; 3) Trong hai ngày bất kỳ của 10 ngày đó thì có ít nhất là 15 người khác nhau cùng đến thư viện. Căn cứ đồng thời cả 3 điều kiện mà nhân viên thư viện cung cấp hãy cho biết số người tối thiểu đã đến thư viện trong 10 ngày nói trên là bao nhiêu? Bài tập 9. (Mông Cổ 2014) Một lớp học có n học sinh. Thầy giáo muốn tổ chức các tổ trực gồm 3 học sinh sao cho hai học sinh bất kỳ cùng trực với nhau không quá 1 buổi. Gọi k là số ngày nhiều nhất mà thầy giáo có thể phân công trực. Chứng minh rằng n( n  3) n( n  1) k . 6 6