Mình đăng lại bài viết của bạn Nguyễn Tiến Hoàng gửi cho Tập san Star Education số 10.
Nếu bạn đang tự hỏi rằng tên bài viết này có nhầm lẫn gì không, thì không hề đâu, bạn đã đọc đúng rồi đấy. Trước khi bắt đầu đọc, hãy lưu ý rằng, bài viết này rất nhiều chữ.
Một trong những vấn đề muôn thuở của học sinh Việt Nam, theo quan sát của người viết bài, là một nỗi sợ vô hình đối với các bài toán tổ hợp trong bất kỳ một kỳ thi lớn hay nhỏ. Tổ hợp ở đây không giới hạn trong phạm vi các bài toán đếm mà mang một nét nghĩa rộng hơn thế, tập trung vào khả năng diễn giải và suy luận. Mỗi bài toán dù trong quá trình luyện tập tại nhà, hay là bước vào thực tế thi cử, đều là một vấn đề hoàn toàn mới lạ với các bạn học sinh. Thông thường có hai hình thức để xoay sở:
a) Giải càng nhiều bài tập càng tốt để thu nhận kinh nghiệm. Đây thực ra không phải điều xấu, nhưng việc lạm dụng quá đà sẽ khiến học sinh chỉ trông đợi vào việc gặp lại những thứ quen thuộc, và thậm chí biến tướng thành việc học thuộc lòng.
b) Tuỳ cơ ứng biến và tin tưởng vào trực giác của bản thân. Điều này cũng thú vị bởi xét cho cùng thì một bài toán trong một kỳ thi ở bậc trung học, dù thi gì đi nữa, cũng chỉ là một vấn đề có thể được giải quyết trong thời gian ngắn, thành ra khả năng lớn là mỗi người sẽ tìm được một cách tiếp cận riêng mang tính sáng tạo. Thế nhưng trong một ngày xấu trời, sự nhạy bén không đồng hành, thì phải làm sao ?
Trong bài viết này, người viết muốn giới thiệu một hướng tiếp cận mang tính chất trung hoà và tập trung vào một khâu mà các bạn học sinh thường bỏ quên: phân tích bài toán. Các phân tích cẩn thận và rõ ràng để dần gỡ rối vấn đề được đặt ra đóng vai trò quan trọng tương tự như dàn ý trong việc viết văn. Điều này trở nên then chốt với các vấn đề phức tạp.
Sự phân tích nên tiến hành ra sao ? Bốn câu hỏi cơ bản sau nên được trả lời:
a) “Có gì ?” Bước đầu tiên không khác việc đọc hiểu là bao. Cần chú ý đến từng câu chữ dù là nhỏ nhất. Việc đọc kỹ các giả thiết được đưa ra giúp người giải toán hình dung được những đối tượng đã xuất hiện trong bài toán.
b) “Cần gì ?” Đây là bước giúp hiểu được yêu cầu của bài toán.
c) “Khó khăn gì ?” Bước này quan trọng nhất và đòi hỏi sự kiên nhẫn. Khi thực hiện cẩn thận hai bước đầu tiên, một số vấn đề sẽ phát sinh rất tự nhiên. Các đối tượng được đưa ra đã rõ ràng hay chưa ? Những giả thiết trong bài toán để làm gì ? Tại sao đề bài lại hỏi như thế ? Liệu các đối
tượng có liên kết gì với nhau ? Cấu trúc của từng thành phần hay cả tổng thể là thế nào ? Và còn nhiều thứ phải chú ý nữa.
d) “Giải quyết thế nào ?” Đây là việc trả lời các câu hỏi trên một cách trực tiếp. Việc đặt ra các câu hỏi tự nhiên trong bước trên sẽ giúp người giải toán nhận ra những gì cần thực hiện. Một nguyên tắc chung là, hãy phân tích và liên tục đặt câu hỏi để giảm sự phức tạp, đến khi mọi thứ có thể diễn giải được thật dễ hiểu. Việc gõ rối cần đi từ nội tại từng đối tượng (chẳng hạn như cấu trúc và tính chất của chúng), cho đến liên hệ giữa các đối tượng với nhau, để tránh bỏ sót thông tin quan trọng.
Trong những bài toán phức tạp gồm nhiều công đoạn, các bước trên sẽ phải thực hiện nhiều lần cho mỗi phần của bài toán. Việc tiếp cận có định hướng thế này, ban đầu có thể sẽ hơi tốn thời gian và mệt mỏi trong suy nghĩ, nhưng khi đã thành thạo thì cho thấy hiệu quả lớn, hơn nữa còn rèn luyện được khả năng giải quyết vấn đề một cách độc lập. Người viết bài đã liên tục sử dụng định hướng trên trong việc giảng dạy tại lớp Chuyên đề Toán 9 năm học 2022-2023 và nhận thấy hiệu quả tương đối rõ rệt.
Ví dụ 1. Chứng minh rằng trong 39 số tư nhiên liên tiếp, luôn tìm được một số mà tổng các chứ số của nó chia hết cho 11.
Phân tích. Khi đọc kỹ bài toán, một số câu hỏi sau về các khó khăn là tự nhiên:
a) Tại sao đối tượng được quan tâm là tồng các chữ số ?
b) Dưới điều kiẹn gi thì tồng đó sẽ là bội của 11 ?
c) Tại sao phải cần 39 số tự nhiên liên tiếp? Như thế là ít hay nhiều?
Để đưa được một lập luận trực tiếp nhằm giải quyết các câu hỏi trên, nhìn chung là việc khó hình dung. Các yêu cầu trên có sự liên quan mật thiết với nhau, và hơn nữa tồng các chũ số là một đại lượng không quen thuộc cho lắm, nên một cách tiếp cận khả dũ là việc làm mọi thứ trở nên rõ ràng, từ tính chất của tổng các chữ số hay là quan hệ trong nội bộ của đối tượng, cho đến quan hệ giũa các đối tượng đã xuất hiện.
Một cách tìm hướng giải quyết là đưa ra ví dụ. Khi nhìn vào trường hợp đơn giản nhất cho 39 số tự nhiên liên tiếp chính là các số từ 1 đến 39, chúng ta có thề quan sát được sự biến động của tổng các chũ̃ số và khảo sát được tính chia hết cho 11. Có gì thú vị?
a) Dường như tồng các chư số là tăng dần, nhưng có lúc tổng đó sẽ bị giảm. Vậy khi nào tổng ấy tăng và khi nào tổng ấy giảm ? Quan sát kỹ sẽ thấy rằng: Khi bắt đầu từ số chia hết cho 10 , chẳng hạn là $10 x$ với $x \in \mathbb{Z}^{+}$, thì các số từ $10 x$ đến $10 x+9$ có tổng các chữ số là 10 số tự nhiên liên tiếp. Tổng các chũ số sẽ giảm khi ta “chuyển” tù̀ $10 x+9$ lên $10(x+1)$.
b) Việc chia hết cho 11, nếu nhìn lại ý đầu tiên, thì chúng ta nhận ra rằng vì đã có cách tạo ra 10 giá trị liên tiêp của tổng các chữ số, chỉ cần cố gắng “kéo dài” để tạo ra 11 giá trị liên tiếp của tổng đó thì bài toán sẽ được hoàn tất, bởi trong 11 số tự nhiên liên tiêpp, thế nào cũng có số chia hết cho 11. Do đó việc quan sát vị trí mà tổng các chũ số bị giảm trở nên quan trọng, và đại lượng đó sẽ giảm thế nào ?
- Có vẻ nhu khi từ $10 x+9$ lên $10(x+1)$ thì tổng các chũ số sẽ giảm 9 đơn vị. Nếu được nhu thê, chúng ta chỉ cần lấy 20 số là $10 x, 10 x+1, \cdots, 10 x+19$ là xong, vì sẽ thu được 11 giá trị liên tiếp cho tổng các chữ sô.
- Nhưng tại sao bài toán lại cần đến 39 số ? Nếu hình dung một bộ gồm 20 số liên tiếp, bắt đầu từ số chia hết cho 10, là ứng viên tiềm năng để giải quyết bài toán, thì chúng ta không cần đến 39 số để chắc chắn chọn được, mà cần quãng 30 số là đủ. Nghĩa là nhận xét về sự thay đổi được đưa ra phía trên có thể không đúng.
- Vậy chúng ta tiếp tục kiểm tra khi nào nhận xét “giảm 9 đơn vị” đúng và khi nào điều đó sai, hay có thể tạm gọi là chú ý đến sự xuất hiện của những thứ “ngoài quy luật”. Thử với các giá trị tiếp theo của $x$, rất đáng chú ý khi nhận ra rằng, nhận xét sẽ sai khi có bước chuyển từ 99 lên 100, hay từ 199 lên 200,… Nói cách khác, miễn là $10(x+1)$ không chia hết cho 100 thì nhân xét đúng.
Có thể rút ra được gì từ các nhận định trên?
a) Nếu trong 39 số mà không có số nào chia hết cho 100, thi chọn được bộ 20 số liên tiếp từ $10 x$ đến $10 x+19$, mà có thể hoàn toàn yên tâm về tính “liên tiếp” của tổng các chưu số trong nhũ̃ng số đang được xét, và bài toán sê xong.
b) Lỡ nhu trong 39 số ban đầu, có số chia hết cho 100 thì sao ? Như đã chỉ ra, chúng ta chỉ cần 20 số có dạng $10 x$ đến $10 x+19$, mà trong chúng sẽ không có số nào chia hết cho 100. Có thể hiểu rằng số chia hết cho 100, mà tạm gọi là a, sê “phân đôi” 39 số mà bài toán cho thành 2 phần: một phần gồm các số từ a trở lên, và một phần gồm các số từ a-1 trở xuống. Vì ban đầu chúng ta có 39 số, theo Nguyên lý Dirichlet, phải có một phần được tạo ra gồm ít nhất 20 số.
Và thế là xong. Bây giờ chỉ là sắp xếp và viết lại các nhận định trên thành một lời giải ngắn gọn. Khi viết thành văn thì các suy luận trên có vẻ dài dòng, nhưng trên thực tế khi suy nghĩ, mọi thứ chỉ ở dạng ý tưởng, nên việc triển khai có thề diễn ra rất nhanh.
Chứng minh. Với mỗi số nguyên dương $n$, gọi $S(n)$ là tổng các chữ số của $n$. Trước hết chúng ta chứng minh rằng, với $x$ là số nguyên dương sao cho $100 \nmid 10(x+1)$, có một trong các số $10 x, 10 x+1, \cdots, 10 x+19$ có tổng các chữ số chia hết cho $11 .$. Thật vậy, đặt $S(10 x)=a$ thì với $0 \leq k \leq 9$, ta có $S(10 x+k)=a+k$ và $S(10 x+10+k)=$ $a+1+k$. Do đó tổng các chữ số nhận giá trị trong ${a, a+1, a+2, \cdots, a+10}$, là tập hợp gồm 11 số tự nhiên liên tiếp, và trong tập hợp đó có một giá trị chia hết cho 11 . Quay trở lại bài toán. Gọi 39 số tự nhiên của đề bài lần lượt là là $a, a+1, \cdots, a+38$. Xét các khả năng sau:
- Trong 39 số này không có số nào là bội của 100. Bởi vì tập hợp ${a, a+1, \cdots, a+9}$ gồm 10 số tự nhiên liên tiếp, trong đó phải có một số chia hết cho 10. Khi đó tồn tại $0 \leq k \leq 9$ để $10 \mid a+k$. Xét các giá trị trong ${S(a+k), S(a+k+1), \cdots, S(a+$ $k+19)}$ thì theo nhận xét ở đầu bài toán, tồn tại một giá trị trong đó là bội của 11.
- Tồn tại một giá trị $0 \leq k \leq 38$ để $100 \mid a+k$. Khi đó trong các số còn lại, không còn số nào chia hết cho 100 . Có hai khả năng sau:
- Nếu $k \leq 18$, xét tập hợp ${S(a+k), S(a+k+1), \cdots, S(a+k+19)}$ thì theo nhận xét ở đầu bài toán, tồn tại một giá trị trong đó là bội của 11 .
- Nếu $k \geq 19$, xét tập hợp ${S(a+k), S(a+k-1), \cdots, S(a+k-19)}$ thì theo nhận xét ở đầu bài toán, tồn tại một giá trị trong đó là bội của 11 .
Tóm lại, trong 39 số tự nhiên liên tiếp, luôn có số mà tổng các chữ số là bội của 11.
Ví dụ trên cũng cho thấy được một hiện tượng rất thú vị và hầu như luôn đúng, đó là khi quá trình phân tích đủ cẩn thận, việc trình bày lời giải chỉ là một cách sắp xếp và viết ngược lại những ý tưởng chính trong mạch suy luận mà thôi. Để kết thúc bài toán này một cách trọn vẹn, bây giờ là một câu hỏi dành cho các bạn.
Ví dụ 2. Thay vì 39 số, chúng ta chỉ xét 38 số thôi. Liệu bài toán còn đúng không ?
Một gợi ý cho các bạn là hãy đọc lại thật cẩn thận từng bước suy luận, và xem vấn đề diền ra ở đâu. Chú ý rằng nếu như bài toán vần đúng, các bạn phải cung cấp một chứng minh, còn nếu kết quả trở nên sai thì hãy chỉ ra một phản ví dụ. Bây giờ chúng ta đến với một bài toán khác cũng tương đối cổ điển.
Ví dụ 3. Cho sáu số nguyên dương đôi một phân biệt và đều nhỏ hơn 10. Chứng minh rằng luôn tìm được ba số trong đó, mà có một số bằng tồng hai số còn lại.
Phân tích. Một số câu hỏi có thể được đặt ra:
a) Tại sao lại xét 6 số trong ${1,2, \cdots, 9}$ ?
b) Việc có một số bằng tổng hai số còn lại có ý nghĩa gì ? Số nào sẽ bằng tổng của hai số nào ? Khó khăn tại đây đến từ việc chúng ta không xác định được điều trên.
Mà nếu đã không xác định được rõ ràng mọi thứ ngay lập tức, thì tốt nhất là lấy ví dụ cu thể để quan sát thôi. Khi lấy thử một vài ví dụ đề khảo sát, dù có ít bộ ba số hay nhiều bộ ba số thoả mãn yêu cầu bài toán, luôn có một nhận xét quan trọng xuất hiện: tồn tại hai số có tổng bằng số lớn nhất.
Vậy từ đây một hướng đi khả dĩ là tìm hiểu xem số lớn nhất như thế nào, đồng thời làm thế nào có thề viết được số đó thành tổng của hai số tự nhiên phân biệt khác. Khi đã làm được điều đó, hãy xem các thông tin vừa nhận được liên hệ gì với giả thiết ban đầu, mà cụ thể là những số nào xuất hiện trong các cách phân tích thành tổng ấy. Thực ra cũng không quá nhiều trường hợp để giải quyết, vì số lớn nhất thì cũng phải không nhỏ hơn 6.
Chứng minh. Gọi 6 số đã cho là $1 \leq a_1<a_2<\cdots<a_6 \leq 9$. Theo giả thiết trên và đề bài thì $a_k \geq k$ với $1 \leq k \leq 6$. Xét các khả năng sau:
- Nếu $a_6=9$ thì $1 \leq a_k \leq 8$ với $1 \leq k \leq 5$. Phân các số nguyên dương từ 1 đến 8 thành bốn tập hợp ${1,8},{2,7},{3,6},{4,5}$. Theo nguyên lý Dirichlet, trong các số từ $a_1$ đến $a_5$, có ít nhất hai số thuộc vào cùng một tập hợp. Tổng hai số đó bằng 9 , nên tồn tại $1 \leq i<j \leq 5$ để $a_i+a_j=9$.
- Nếu $a_6=8$ thì $1 \leq a_k \leq 7$ với $1 \leq k \leq 5$. Phân các số nguyên dương từ 1 đến 8 thành bốn tập hợp ${1,7},{2,6},{3,5},{4}$. Theo nguyên lý Dirichlet, trong các số từ $a_1$ đến $a_5$, có ít nhất hai số thuộc vào cùng một tập hợp. Tổng hai số đó bằng 8 , nên tồn tại $1 \leq i<j \leq 5$ để $a_i+a_j=8$.
- Nếu $a_6=7$ thì $1 \leq a_k \leq 6$ với $1 \leq k \leq 5$. Phân các số nguyên dương từ 1 đến 7 thành ba tập hợp ${1,6},{2,5},{3,4}$. Theo nguyên lý Dirichlet, trong các số từ $a_1$ đến $a_5$, có ít nhất hai số thuộc vào cùng một tập hợp. Tổng hai số đó bằng 7 , nên tồn tại $1 \leq i<j \leq 5$ để $a_i+a_j=7$.
- Nếu $a_6=6$ thì $1 \leq a_k \leq 5$ với $1 \leq k \leq 5$. Phân các số nguyên dương từ 1 đến 5 thành ba tập hợp ${1,5},{2,4},{3}$. Theo nguyên lý Dirichlet, trong các số từ
- $a_1$ đến $a_5$, có ít nhất hai số thuộc vào cùng một tập hợp. Tổng hai số đó bằng 6 , nên tồn tại $1 \leq i<j \leq 5$ để $a_i+a_j=6$.
- Tóm lại thì luôn có hai số bằng tổng của số lớn nhất. Bài toán kết thúc.
Khai thác thêm bài toán này có thể thấy nhiều điều thú vị sau:
a) Câu hỏi đầu tiên vẫn chưa được giải quyết triệt để khi phân tích. Tuy nhiên, với trường hợp $a_6=9$, nhận thấy rằng việc chọn ra 6 số là để vừa đủ cho việc sử dụng Nguyên lý Dirichlet. Một câu hỏi tự nhiên là nếu bài toán chỉ xét 5 số thay vì 6 số, thì các lập luận sẽ biến đổi thế nào, và liệu kết luận của bài toán còn đúng ?
b) Phát biểu khác đi một chút, liệu số lượng số nhỏ nhất cần chọn để chắc chắn có một số bằng tổng hai số khác, là bao nhiêu? Hơn nữa thay vì giải quyết bài toán như trường hợp ban đầu, khi các số không lớn hơn 9 , điều gì sẽ xảy ra khi thay 9 bởi một số nguyên dương $n$ bất kỳ ? Liệu các câu hỏi tương tự có thể được giải quyết ?
Từ đó có thể thu được bài toán sau, xin dành cho các bạn tự luyện tập.
Ví dụ 4. Cho số nguyên dương $n \geq 3$. Tìm số nguyên dương $k$ nhỏ nhất sao cho với mọi cách chọn ra $k$ số nguyên dương đôi một phân biệt từ tập hợp ${1,2, \cdots, n}$, luôn chọn được ba số trong đó, mà có một số bằng tổng hai số kia.
Ví dụ 5. Với n là số nguyên dương, chọn ra $n+1$ số từ tập hợp ${1,2, \cdots, 2 n}$.
a) Chứng minh rằng có hai số nguyên tố cùng nhau.
b) Chứng minh rằng có hai số mà thương của chúng là số nguyên.
Phân tích. Một số câu hỏi có thể được đặt ra như sau:
a) Tại sao phải cần chọn ra $n+1$ số ?
b) Sự nguyên tố cùng nhau, và việc thương là số nguyên, có ý nghĩa số học gì ? Nếu định nghĩa một cách số học, thì hai số được gọi là nguyên tố cùng nhau khi và chỉ khi chúng không có ước nguyên tố chung. Khi thử tiếp cận theo việc khảo sát các ước nguyên tố của $n+1$ số, mọi chuyện sẽ trở nên rất phức tạp vi chúng ta không biết những số nào được chọn ra, hơn nữa bài toán chỉ yêu cầu một sự tốn tại, nên nếu đi khảo sát toàn bộ cấu trúc của tập hợp ước nguyên tô, thì đó có vè là một yêu cầu quá sức. Hơn nũa, một vấn đề khác làm hướng tiếp cận này trở nên không khả thi, đó là trong bài toán không hề có dấu hiệu gì cho thấy nên tìm hiểu một cách chi tiết về các cấu trúc số $h o c$.
Do đó chúng ta sẽ thử một góc nhìn khác. Tập trung vào câu hỏi đầu tiên, một vấn đề được đặt ra nhu sau: nếu như chỉ lấy $n$ số thì sao? Có thể tìm ngay được phản ví dụ với việc chọn $n$ số chã̃n, thì hai số nào cũng có ước nguyên tố chung là 2. Vậy trong trường hợp tạm gọi là xấu nhất, thế nào cũng có ít nhất một số lẻ. Và liệu số lẻ này có vai trò và quan hệ thế nào với các số chã̃n, khi cần khảo sát sự nguyên tố cùng nhau?
Viết một vài trường hợp nhỏ, chúng ta nhận ra rằng khi số lẻ ấy được kết hợp với số liền trước hay số liền sau, thi sẽ tạo ra một cặp số nguyên tố cùng nhau. Từ đó một câu hỏi
nảy sinh: nếu như chọn $n+1$ số bất kỳ, thi liệu luôn có hai số tự nhiên liên tiếp ? Điều này có thể được kiểm chứng dễ dàng, nên ý đầu tiên của bài toán đến đây là hoàn thành. Sự kiện “chia hết” là một yếu tố khó kiểm soát. Bây giờ chẳng hạn như đã chọn trước một số nguyên dương a, các số chia hết cho a sẽ là ka, hoặc các ước của a thì luôn có dạng $a / k$. Vấn đề là, chúng ta không xác định được khi chọn ra $n+1$ số bất kỳ, sẽ có các số nào liên quan đến a xuất hiện, hơn nữa không chắc chắn việc thương của chúng liệu có phải số nguyên. Vậy thì chúng ta sẽ thử làm mạn đánh giá lên để khử được sự ngẫu nhiên ấy: nếu như chọn ra được một bộ càng nhiều số càng tốt mà liên quan đến a, đồng thời hai số nào trong đó cũng có thương là số nguyên, thì bộ số ấy chỉ nên được chọn tối đa một phần tử nhằm tránh việc chia hết.
Làm rõ ý tưởng này, chúng ta sẽ nhận ra $a, 2 a, 4 a, \cdots$ là lựa chọn tốt nhất có thể nếu xét các số tù̀ a trở lên. Khi chú ý đến các số tù̀ a trở xuống và hiệu chỉnh, lưa chọn phù hợp cho bộ số cần tìm chính là $a, 2 a, 4 a, \cdots$ với a là số lẻ. Có n bộ như thê, và thế là xong.
Chứng minh.
a) Chia tập hợp ${1,2, \cdots, 2 n}$ thành $n$ tập hợp ${2 k-1,2 k}$ với $1 \leq k \leq n$. Vì ban đầu có $n+1$ phần tử được chọn ra, theo Nguyên lý Dirichlet, phải có hai phần tử nào đó thuộc cùng một tập hợp con được nêu ra phía trên. Đây là hai số tự nhiên liên tiếp nên chúng nguyên tố cùng nhau.
b) Với $a$ là số lẻ và $1 \leq a \leq 2 n$, ta định nghĩa
$$
S_a=\left\{x \in \mathbb{Z}^{+}, 1 \leq x \leq 2 n \mid \exists k \in \mathbb{Z}^{+}: x=2^k a\right\}
$$
Mỗi số nguyên dương không vượt quá $2 n$ đều thuộc về một tập hợp $S_a$ nào đó. Có $n$ tập hợp như thế, mà ban đầu có $n+1$ số được chọn, nên Nguyên lý Dirichlet cho thấy rằng phải có hai số cùng nằm trong một tập hợp $S_a$ nào đó. Gọi hai số đó là $2^s a$ và $2^t a$ với $0 \leq s<t$ thì thương của chúng là $2^{t-s} a$, là một số nguyên.
Như thường lệ, bài toán chưa kết thúc ngay tại đây, mà chúng ta đặt ra thêm một vài quan sát nữa. Việc chọn $n+1$ số trong tập hợp ${1,2, \cdots, 2 n}$, như đã phân tích, là vừa đủ để vượt qua ngưỡng “lớn nhất” của sự kiện không có hai số nào nguyên tố cùng nhau. Một lẽ dĩ nhiên là chúng ta muốn xác lập một ngưỡng tương tự cho sự kiện chia hết: liệu có thể chọn được tối đa bao nhiêu sô, mà không có hai số nào có thương là số nguyên ?
Hơn nữa, nếu như kết hợp cả hai vấn đề, nghĩa là có thể chọn được tối đa bao nhiêu số để không có hai số nào nguyên tố cùng nhau và đồng thời không có hai số nào có thương là số nguyên, chúng ta thu được bài toán sau trong đề thi chọn Đội tuyển năm 2017 của Trường Phổ thông Năng khiếu để tham dự Kỳ thi Học sinh giỏi Quốc gia môn Toán bậc THPT.
Ví dụ 6 (PTNK 2017). Xét tập hợp $S={1,2, \cdots, 2017}$. Liệu có thể chọn ra tôi đa bao nhiêu số nguyên dương từ $S$, sao cho không có hai số nào nguyên tố cùng nhau và đồng thời không có hai số nào có thương là số nguyên ?
Theo trí nhớ của người viết bài cũng tham dự kỳ thi năm ấy, không có thí sinh nào giải quyết được bài toán trên. Mặc dù vậy, khi phân tích kỹ, đặc biệt là về sự kiện chia
hết, các bạn có thể tìm được ngay đáp số và thậm chí là một ví dụ thoả mãn yêu cầu bài toán.
Các bài toán trên đều minh hoạ cho một bước chuyển đổi quan trọng từ những phân tích dài dòng bằng chữ thành các suy diễn gãy gọn được diễn đạt bằng ký hiệu. Vì mỗi tình huống mỗi khác, điều quan trọng nhất vẫn là đọc thật kỹ những giả thiết được đưa ra và nắm chắc những yêu cầu cẩn thiết. Một điều tối kỵ là không được bịa ra thêm giả định vô căn cứ để ép vào mạch suy luận. Chúng ta kết thúc bằng một bài toán thú vị, mặc dù trông có vẻ nhiều khó khăn, và phương châm vẫn là… nghĩ đơn giản thôi
Ví dụ 7. Cho các số tự nhiên tù 1 đến 2023. Hỏi có thể chọn ra được nhiều nhất bao nhiêu số sao cho tổng của hai số bất kì trong chúng không chia hết cho hiệu của nó ?
Phân tích. Một số câu hỏi sau được đặt ra khi đọc kỹ đề bài.
a) Giả định chia hết của bài toán rất kỳ quặc. Có cách nào diễn đạt lại mọi thứ cho rồ ràng hơn hay không, và làm sao để khai thác được điều kiện ấy ?
b) Liệu có thể tìm được một ví dụ với tương đối nhiều số ?
Chúng ta tập trung giải quyết yêu cầu đầu tiên. Viết rõ lại bằng ký hiệu, đó là với $a>b$ là hai số nguyên dương phân biệt được chọn, ta phải có $a-b \nmid a+b$. Vì các số này được chọn bất kỳ và các biểu thức xuất hiện đẹ̀u là bậc nhất, việc tìm kiếm một quan hệ số học giũ̃a a và b chỉ bằng giả định trên là không khả thi. Nếu không tin, các bạn có thể thư!
Xoay sang câu hỏi thứ nhì. Thử tiếp cận vấn đề một cách tương đối ngây thơ như sau: cứ lần lượt bắt đầu tù số 1, liệu có thề lấy được những số nào tiểp theo? Dĩ nhiên không phải lúc nào việc xử lý vấn đè̀ theo cách tham lam cũng cho một kết quả tối u’u, nhung ít nhất vẫn có thêm định hướng và một vài quan sát hữu ích để hiệu chỉnh khi cần thiết.
- Không lấy được số 2 và số 3, vì ảnh hưởng của số 1 .
- Lấy được số 4. Cũng bởi thế mà không lấy được số 5 và số 6 .
- Lấy được số 7, rồi lại bỏ qua số 8 và số 9. Cứ như thế…
Một quan sát về các số được thu nhận cho thấy chúng phải cách nhau ít nhất 3 đơn vị. Liệu điều này có luôn đúng ? Có thề quay về giả định của bài toán để kiểm tra.
Mọi thứ quy về việc chọn ra càng nhiều số càng tốt, mà hai số bất kỳ có hiệu từ 3 trở lên. Để chọn được nhiều số nhất, một lê dĩ nhiên là phải khởi đầu từ số nhỏ nhất, và các khoảng cách giữa các số cũng phải nhỏ nhất có thể. Bây giờ chỉ là xếp lại thành lời giải, và nhớ rằng vì đây là bài toán cực trị, hãy chỉ ra ví dụ.
Chứng minh. Gọi các số được chọn là $1 \leq a_1<a_2<\cdots<a_k \leq 2023$. Trước hết, ta chứng minh rằng với $1 \leq i \leq k-1$ thì $a_{i+1}-a_i \geq 3$. Thật vậy:
Nếu có chỉ số $1 \leq i \leq k-1$ để $a_{i+1}-a_i=1$ thì $a_{i+1}-a_i \mid a_{i+1}+a_i$, mâu thuẫn.
Nếu có chỉ số $1 \leq i \leq k-1$ để $a_{i+1}-a_i=2$ thì chú ý rằng $a_{i+1}+a_i=2 a_i+2$, ta cũng thu được $a_{i+1}-a_i \mid a_{i+1}+a_i$, lại là một mâu thuẫn.
Do đó nhận xét được chứng minh. Từ đó thì
$$
2023 \geq a_k \geq a_{k-1}+3 \geq a_{k-2}+3 \cdot 2 \geq \cdots \geq a_1+3(k-1) \geq 1+3(k-1)
$$
hay là $2022 \geq 3(k-1)$. Điều này cho thấy $k \leq 675$. Để chọn được 675 số thoả mãn yêu cầu bài toán, với $1 \leq i \leq 675$, chọn $a_i=3 i-2$. Thật vậy, với $1 \leq i<j \leq 675$ thì:
- $a_j-a_i=3(j-i)$ là một bội của 3 ,
- $a_j+a_i=3(j+i)-4$ không là một bội của 3 , nên ta luôn có $a_j-a_i \nmid a_j+a_i$. Vậy có thể chọn được tối đa 675 số nguyên dương đôi một phân biệt không vượt quá 2023 mà không có tổng hai số nào chia hết cho hiệu của chúng.
Hi vọng rằng những trình bày phía trên có thể giúp các bạn phần nào đó tự tin và vững vàng hơn trong việc suy luận để giải toán. Dưới đây là một số bài toán để luyện tập.
Bài tập rèn luyện.
Bài 1. Xét bảng ô vuông $10 \times 10$. Mỗi ô vuông của bảng được điền một số nguyên tuỳ ý sao cho hiệu hai số được điền ở hai ô chung một cạnh bất kì đều không vượt quá 1 . Chứng minh rằng tồn tại một số nguyên xuất hiện trên bảng ít nhất 6 lần.
Bài 2. Cho $A B C$ là một tam giác tuỳ ý. Mỗi điểm trên mặt phẳng được tô bởi một trong hai màu xanh hoặc đỏ. Chứng minh rằng tồn tại hai điểm màu đỏ có khoảng cách bằng 1, hoặc tồn tại một tam giác có ba đỉnh màu xanh mà đồng dạng với tam giác $A B C$.
Bài 3. Có 20 viên bi được xếp thành một hàng ngang trên bàn, trong đó có 10 viên bi màu xanh và 10 viên bi màu đỏ. Chứng minh rằng có thể chọn ra một bộ gồm 10 viên bi liên tiếp mà trong đó số viên bi màu xanh bằng số viên bi màu đỏ.
Bài 4. Cho $A={1,2,3, \cdots, 100}$. Lấy $S$ là tập hợp con của $A$ sao cho các tồng hai phần tử phân biệt bất kỳ của $S$ thì có các số du đôi một phân biệt khi chia cho 100. Chứng minh rằng $S$ có không quá 14 phần tử, và chỉ ra một tập hợp $S$ có 10 phần tử.
Bài 5. Có một bộ các quả cân có tính chất sau:
i) Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau.
ii) Với hai quả cân bất kỳ, tìm được hai quả cân khác có tồng trọng lượng bằng với tổng trọng lượng của hai quả cân đó.
Bộ quả cân này có ít nhất là bao nhiêu quả cân?
Bài 6. Chọn ra $k$ số nguyên dương phân biệt là ước của $6^{2023}$.
a) Chứng minh rằng nếu $k=5$ thì tồn tại hai số có tích là số chính phương.
b) Chứng minh rằng nếu $k=21$ thì tồn tại sáu số có tích là một luỹ thừa bậc 6.
Bài 7. Cho số nguyên dương $n \geq 2$. Chứng minh rằng khi chọn ra $n+2$ số nguyên dương từ tập hợp $S={1,2, \cdots, 3 n}$, luôn tồn tại hai số $x, y$ đề $n<x-y<2 n$.
Bài 8. Cho tập hợp $S={1,2, \cdots, 2023}$. Xét tập hợp con $T \subseteq S$. Nếu $T$ không chứa hai phần tử nào có hiệu trong $E$ thì có tối đa bao nhiêu phần tứ, với:
a) $E={3 ; 6 ; 9}$
b) $E={4 ; 7}$
Bài 9. Lớp $9 A$ có 6 học sinh tham gia kỳ thi chọn đội tuyển môn Toán, và nhận được 6 điểm số khác nhau là các số tự nhiên không vượt quá 20. Gọi m là trung bình cộng các điểm số của 6 học sinh trên. Hai học sinh được gọi là lập thành một cạ̣p hoàn hảo nếu như trung bình cộng điểm số của hai em đó lớn hơn $m$.
a) Chứng minh rằng không thề chia 6 học sinh thành 3 cặp mà mỗi cặp đều hoàn hảo.
b) Trong 6 học sinh trên, có thể có nhiều nhất bao nhiêu cặp hoàn hảo ?
Bài 10. Có 8 kì thủ thi đấu giải cờ vua Candidates 2023 theo thể thức vòng tròn một lượt. Tại mỗi trận đấu phân định thắng thua, người thắng được 1 điểm còn người thua được 0 điểm; tại mỗi trận hòa thì mỗi người được 0.5 điểm.
a) Chứng minh rằng sau 3 vòng đầu tiên, luôn tìm được hai người có số điểm bằng nhau.
b) Giả sử rằng sau khi kết thúc giải, tất cả các kì thủ đều có số điểm khác nhau. Tìm số điểm ít nhất có thể của người chiến thắng.
c) Giải lại bài toán khi giải đấu diễn ra theo thể thức vòng tròn hai lượt.