Tag Archives: ToHop

Suy luận phản chứng (phần 2)

Phép phản chứng trong toán học còn được gọi là phương pháp chứng minh bằng mâu thuẫn. Nếu ta muốn chứng minh kết luận của bài toán là đúng thì cần phải chứng minh điều ngược lại với giả thiết là sai. Sau đây ta xét một vài ví dụ áp dụng suy luận này, dành cho các bạn hs lớp 8, 9.

1/ Ví dụ:

Ví dụ 1.

Chứng minh rằng $\sqrt{2}$ là một số vô tỷ.

Lời giải

Giả sử $\sqrt{2}$ là số hữu tỉ. Khi đó tồn tại $a,b\in \mathbb{N}^*$ sao cho $\sqrt{2}= \dfrac{a}{b}$ với $(a,b)=1$

Ta có: $(\sqrt{2})^2=\left(\dfrac{a}{b}\right)^{2}$ hay $a^{2}=2 b^{2}\quad (1)$

Suy ra a là số chẵn, ta có: $\mathrm{a}=2 \mathrm{c}$ với $c\in Z$

Thay $\mathrm{a}=2 \mathrm{c}$ vào (1) ta được: $(2 c)^{2}=2 b^{2}$ hay $b^{2}=2 c^{2}$

Do đó, b là số chẵn

Hai số a và $b$ đều số chẵn $\Rightarrow$ Mâu thuẫn với $(1)$

Vậy $\sqrt{2}$ là số vô tỉ.

Ví dụ 2.

Chứng minh rằng tổng của một số hữu tỷ và một số vô tỷ là số vô tỷ.

Lời giải

Giả sử tổng của số hữu tỉ a vs số vô tỉ b là số hữu tỉ c, ta có: $\mathrm{b}=\mathrm{c}-\mathrm{a}$

Mà hiệu của 2 số hữu tỉ phải là số hữu tỉ nên $b$ là số hữu tỉ

$\Rightarrow$ Mâu thuẫn vs giả thiết

Vậy tổng của 1 số hữu tỉ với 1 số vô tỉ là 1 số vô tỉ.

Ví dụ 3. (Nguyên lý Dirichlet)

Có $nk + 1$ viên bi, bỏ vào trong $k$ cái hộp. Chứng minh rằng có ít nhất một hộp có ít nhất là là $n+1$ viên bi.

Lời giải

Giả sử tất cả các hộp đều chứa số bi không vượt quá $n$ viên, khi đó tổng số bi không vượt quá $nk$, mâu thuẫn. Vậy phải có một hộp chứa nhiều hơn $n$ viên bi $\Rightarrow$ đpcm.

2/ Bài tập

Bài 1.

Cho 15 số phân biệt thỏa mãn tổng của 8 số bất kì lớn hơn tổng của 7 số còn lại. Chứng minh tất cả các số đã cho đều dương.

Lời giải

Gọi 15 số đã cho là $a_1<a_2<a_3<\cdots <a_{15}$. Ta chỉ cần chứng minh $a_1 > 0$.

Thật vậy, giả sử $a_1 \leq 0$, khi đó $$a_1 + a_2 + \cdots + a_8 \leq a_2 + a_3 + \cdots a_8 < a_9 + \cdots a_{15}$$ (mâu thuẫn).

Vậy điều giả sử là sai, hay $0<a_1\Rightarrow 15$ số đã cho đều dương.

Bài 2.

Từ 8 số nguyên dương không lớn hơn 20, chứng minh rằng có thể chọn ra 3 số $x, y, z$ là độ dài 3 cạnh của một tam giác.

Lời giải

Gọi 8 số nguyên dương không lớn hơn 20 là $a_{1}, a_{2}, a_{3}, \ldots, a_{8}$

$$ \text { với } 1 \leq a_{1} \leq a_{2} \leq a_{3} \leq a_{4} \leq \ldots \ldots \leq a_{8} \leq 20 $$

Nhận thấy rằng với ba số nguyên dương $a, b, c$ thỏa mãn $a \geq b \geq c$ và $b+c>a$ thì khi đó $a, b, c$ là độ dài 3 cạnh tam giác.

Giả sử trong các số $a_{1}, a_{2}, a_{3}, a_{4}, \ldots . a_{8}$ không chọn được 3 số nào là độ dài 3 cạnh của tam giác thì ta có:

$$a 3 \geq a 1+a 2 \geq 1+1=2$$

$$a 4 \geq a 2+a 3 \geq 1+2=3$$

$$a 5 \geq a 3+a 4 \geq 2+3=5$$

$$a 6 \geq a 4+a 5 \geq 3+5=8$$

$$a 7 \geq a 5+a 6 \geq 5+8=13$$

$$a 8 \geq a 6+a 7 \geq 13+8=21$$

$\Rightarrow$ Trái với giả thiết

Vậy điều giả sử là sai

$\Rightarrow$ đpcm.

Bài 3.

Cho tập $B = {1, 2, 3, …, 16}$. Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:

a/ Tổng của hai số kề nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?

b/ Tổng của ba số kề nhau bất kì lớn hơn 24 được không? Tại sao?

Lời giải

a/ Giả sử tồn tại cách ghi thỏa mãn. Khi đó, gọi 2 số kề với 1 là a và b.

Theo giả thiết, ta có:

$\left\{\begin{array}{l} 1 + a \geqslant 17 \\1 + b \geqslant 17 \end{array} \right. \Rightarrow \left\{\begin{array}{l} a \geqslant 16 \\ b \geqslant 16 \end{array} \right. \Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách ghi thỏa mãn.

b/ Giả sử tồn tại cách ghi thỏa mãn.

Khi đó, ta tách số 16 ra và chia 15 số còn lại thành 5 bộ 3 số kề nhau. Và tổng của 16 số này phải lớn hơn hoặc bằng: $16+5\cdot 25=141$

Mà $1+2+3+\cdots 16=136 \Rightarrow $ Mâu thuẫn

Vậy không tồn tại cách ghi thỏa mãn.

Bài 4.

Có thể chia tập $X = \{1, 2, …, 2023\}$ thành hai tập rời nhau sao cho tổng các phần tử thuộc tập này bằng 2 lần tổng các phần tử thuộc tập kia?

Lời giải

Giả sử có thể chia tập $X$ thành hai tập rời nhau $A$ và $B$ sao cho tổng các phần tử thuộc A bằng 2 lần tổng các phần tử thuộc B.

Khi đó, tổng các phần tử của 2 tập hợp này phải chia hết cho 3.

Mà ta có: $1+2+3+\cdots +2023=\dfrac{2023\cdot 2024}{2}=1012\cdot 2023 \not \vdots \ 3 \Rightarrow$ Mâu thuẫn

Vậy không thể chia tập $X$ thành hai tập rời nhau $A$ và $B$ sao cho tổng các phần tử thuộc $A$ bằng 2 lần tổng các phần tử thuộc $B$.

Bài 5.

Một bảng vuông $8 \times 8$ khuyết các ô vuông ở hai góc đối diện. Hỏi có thể phủ các ô của bảng vuông bằng các hình Domino $1 \times 2$ mà không có quân Domino nào chồng lên nhau được không? Tại sao?

Lời giải

Giả sử có thể phủ các ô của bảng vuông bằng các hình Domino $1 \times 2$ mà không có quân Domino nào chồng lên nhau.

Mỗi quân Domino lát vào bàn cờ luôn chiếm một ô trắng và một ô đen. Do đó, để lát được phần còn lại của bàn cờ thì số ô trắng và số ô đen bằng nhau. Mà số ô màu trắng và số ô màu đen trong phần còn lại của bàn cờ không bằng nhau. Điều này mâu thuẫn.

Vậy không thể lát được phần còn lại của bàn cờ bằng các quân Domino.

Giải toán như … viết văn

Leave a reply

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.

Bất biến và đơn biến – Phần 1

Leave a reply

Lê Anh Vinh

ĐH Giáo dục, ĐHQGHN

1/ Khởi động:

Chúng ta sẽ bắt đầu bằng một ví dụ đơn giản. Giáo viên yêu cầu học sinh làm một thí nghiệm nhỏ – viết lên bảng $a+b$ số gồm $a$ số 0 và $b$ số 1 . Sau đó thực hiện $a+b-1$ lần phép biến đổi sau: xoá hai số bất kỳ trên bảng. Nếu chúng bằng nhau thì viết số 0 lên bảng và nếu khác nhau thì viết số 1 lên bảng. Sau khi học sinh làm thử trên vở, giáo viên có thể nói ngay số còn lại trên bảng là số 1 hay số 0 .

Học sinh sẽ thắc mắc một cách tự nhiên: làm thế nào giáo viên biết được số còn lại trên bảng? Rõ ràng các phép biến đổi có thể thực hiện theo nhiều cách khác nhau, nhưng sau các phép biến đổi, tổng các số trên bảng là không đổi theo modulo $2 .$ Do đó, số còn lại trên bảng sẽ là 1 nếu $b$ lẻ và 0 trong trường hợp ngược lại.

Chúng ta tiếp tục với các ví dụ sau.

Bài toán 1.1. Khối $A0$ có một ngôn ngữ riêng chỉ gồm hai chữ cái $A$ và $0$ , đồng thời thỏa mãn hai điều kiện sau:

Nếu xóa hai chữ cái kề nhau $\mathrm{A} 0$ trong bất kì một từ nào, ta không làm thay đổi nghĩa của từ đó.
Nếu thêm tổ hợp 0A hoặc AA00 vào vị trí bất kì nào trong một từ, ta cũng không làm thay đổi nghĩa của từ đó.

Liệu hai từ A00 và 0AA có cùng nghĩa không ?
Giải

Dễ thấy sau mỗii phép biến đổi, số lượng $\mathrm{A}$ và 0 thêm vào hay bớt đi là như nhau. Vì vậy, xuất phát từ $\mathrm{A} 00$ với nhiều chữ cái 0 hơn, ta không thể thu được $0 \mathrm{AA}$ với nhiều chữ cái $\mathrm{A}$ hơn. Đại lượng bất biến ở đây có thể chọn là sai khác giữa số chữ cái ${A}$ và chữ cái 0 trong một từ.

Lời giải trên đã chỉ ra ý tưởng cơ bản nhất của bất biến. Cho trước một số cấu hình, chúng ta có thể thực hiện một số phép biến đổi trên chúng. Câu hỏi đật ra là có thể thu được một cấu hình này từ một câu hình khác không? Tính bất biến thường được dùng để chỉ ra rằng từ một cấu hình không thể đạt tới một cấu hình khác. Để làm được điều đó, chúng ta xây dựng một đại lượng không đổi (hoặc thay đổi đơn điệu – khi đó ta có khái niệm nửa bất biến) dưới các phép biến đổi sao cho giá trị của đại lượng này là khác nhau ở hai cấu hình trong cần hỏi. Tuy nhiên, đối với các bài toán bất biến, phần khó nhất thường là chỉ ra đại lương bất biến. Trong bài giảng này, chúng ta sẽ hệ thống một số dạng bất biến thường gặp qua một loạt các ví dụ từ đơn giản đến nâng cao.

Bài toán 1.2. Một hình tròn được chia làm 6 ô dẻ quạt bằng nhau và đặt một quân tốt vào mỗi ô. Trong mỗi bước, cho phép chuyển hai quân tốt bất kỳ vào ô kề với nó. Hỏi có thể chuyển tất cả quân cờ vào một ô hay không?

Giải

Đánh số các ô từ 1 đến 6 theo chiều kim đồng hồ. Với mỗi cách sắp xếp, xét $S$ là tổng các ô có chứa quân cờ (tính cả bội). Khi đó, tính chẵn lẽ của $S$ không thay đổi.

Trong một số trường hợp, bất biến không chỉ được dùng để chứng minh ta không thể thu được cấu hình này từ một cấu hình khác mà còn có thể sử dụng để tìm hiểu cấu hình nào có thể thu được từ một cấu hình cho trước. Ta có ví dụ sau.

Bài toán 1.3. Các số $1,2,3, \ldots, 20$ được viết lên bảng. Mỗi phép biến đổi, ta xóa hai số $a, b$ và thêm vào số $a+b-1$. Số nào sẽ còn lại trên bảng sau 19 bước?

Giải

Với bộ $n$ số trên bảng ta xét đại lượng $X$ bằng tổng các số trên bảng trừ đi $n$. Khi đó $X$ không thay đổi trong các phép biến đổi. Lúc đầu $X=(1+2+\ldots+20)-20=190$. Sau 19 bước, $X=190$ hay số còn lại sẽ là $191 .$

Sẽ không ngạc nhiên nếu như một số học sinh đưa ra lập luận như sau: tại mỗi bước, tổng các số giảm đi 1 . Lúc đầu tổng là 210 và sau 19 bước, số còn lại sẽ là $210-19=191$. Cách giải này hiển nhiên đúng nhưng không làm rõ được ý tưởng của “bất biến”. Chúng ta sẽ đưa cho học sinh một bài toán tương tự, mà ở đây, những lập luận “rút gọn” như vậy là khó có thể thực hiện được.

Bài toán 1.4. Các số $1,2,3, \ldots, 20$ được viết lên bảng. Mỗi phép biến đổi, ta xóa hai số $a, b$ và thêm vào số $ab+a+b$. Số nào sẽ còn lại trên bảng sau 19 bước?

Sau đây là một số bài toán khá thú vị sử dụng y tưởng của bất biến.

Bài toán 1.5. Trong bàn cờ $8 \times 8$, một ô bị tô màu đen và các ô còn lại được tô màu trắng. Liệu có thể làm cho cả bảng màu trắng bằng cách tô lại các hàng và cột không? Ở dây, tô lại một hàng hay cột được hiểu như là một phép đổi màu tất cả các ô trên hàng hoặc cột đó.

Bài toán 1.6. Giải Bài 5 cho bảng $3 \times 3$.

Bài toán 1.7. Giải Bài 5 cho bảng $8 \times 8$ với bốn ô ở góc được tô màu đen và các ô khác được tô màu trắng.

Lưu ý rằng Bài 5 , khác với Bài 6 và Bài 7 , có thể giải chỉ sử dụng tính chã̃n lẻ của số ô đen trên bảng. Để giải Bài 6 , ta có thể xét tính chã̃n lẻ của số ô đen trong bốn ô ở góc. Để giải Bài 7 , ta phải xét tính chẵn lẻ của số ô đen trong bốn ô cụ thể, ví dụ bốn ô ở góc phải trên.

Bài toán 1.8. Các số $1,2, \ldots, 2013$ được viết lên bảng. Cho phép xóa đi hai số và thay bởi hiệu của chúng. Liệu có thể thu được một bảng gồm toàn số 0 không?

Có nhiều cách để giải bài toán trên, một trong những bất biến có thể sử dụng là tính chẵn lẻ của tổng các số viết trên bảng. Lưu ý rằng tổng và hiệu của hai số bất kỳ là cùng tính chẵn lẻ.

Bài toán 1.9. Có 13 con tắc kè xanh, 15 con tắc kề đỏ và 17 con tắc kè vàng trên một hòn đảo. Khi hai con tắc kè khác màu gặp nhau, chúng đổi sang màu còn lại. Liệu có thể đến một lúc nào đó tất cả các con tắc kè có cùng màu hay không?

Giải

Mỗi “trạng thái” trên đảo gồm $a$ con tắc kè xanh, $b$ con tắc kè đỏ và $c$ con tắc kè vàng với $a+b+c=45$. Phép biến đổi màu sẽ chuyển từ trạng thái $(a, b, c)$ sang một trong ba trạng thái $(a-1, b-1, c+2),(a-1, b+2, c-1)$ hoặc $(a+2, b-1, c-1)$. Dễ thấy $(a-1)-(b-1) \equiv(a-1)-(b+2) \equiv(a+2)-(b-1) \equiv a-b$ mod $3 .$ Bất biến $X=$ sai khác giữa số tắc kè xanh và số tắc kề đỏ theo modulo 3. Lúc đầu $X \equiv 2 \bmod 3$ và khi tất cả các tắc kè cùng màu thì $X \equiv 0 \bmod 3$. Vì vậy, trường hợp tất cả các con tắc kè có cùng màu không thể xảy ra.

Bài toán 1.10. Viết 11 số $+1$ và 01 số $-1$ lên đỉnh của 12 giác đều. Cho phép đổi dấu của các số trên $k$ đỉnh bất kỳ của đa giác. Có thể hay không luôn chuyển số $-1$ sang đỉnh kề của nó nếu

a) $k=3$

b) $k=4$;

c) $k=6 ?$

Giải

Câu trả lời là phủ định trong cả ba trường hợp. Chứng minh cho cả ba trường hợp có thể thực hiện như sau: chúng ta chọn các đỉnh cách đều nhau đúng $k-1$ dỉnh (ví dụ khi $k=3$ ta chọn được 4 dỉnh, khi $k=4$ ta chọn được 3 điểm và $k=6$ ta chọn được 2 điểm). Bất biến của chúng ta là tích các số trên các đỉnh được chọn. Chúng ta xếp số – 1 vào một trong các điểm được chọn. Dễ kiểm tra rằng nếu số $-1$ được chuyển sang đỉnh kề thì tích các số trên các điểm được chọn lúc đó sẽ là $1 .$

Lưu ý rằng khái niệm bất biến là khá trừu tượng và phức tạp đối với phần lớn học sinh trong lần tiếp cận đầu tiên. Chúng ta nên lưu ý phân tích các lập luận logic của việc sử dụng các đại lượng bất biến trong giải các bài toán cụ thể. Ở đây, chúng tôi chỉ đưa ra những gợi ý tóm tắt cho các bài toán nhưng khi hướng dẫn cho học sinh, có thể sử dụng các ví dụ minh họa khiến lời giải trở nên trực quan và dễ hiểu hơn. Ngoài ra, chúng ta chỉ nên giới thiệu khái niệm và phương pháp sử dụng bất biến sau khi mỗi học sinh đã tự tìm tòi và giải quyết độc lập một vài ví dụ minh họa đơn giản nhất, thậm chí đã sử dụng bất biến mà không hề ý thức được điều đó. Rõ ràng, bước khó nhất khi giải các bài toán sử dụng bất biến là phát hiện ra được đại lượng bất biến phù hợp. Đây là một nghê thuật mà chúng ta chỉ có thể thành thạo được thông qua việc giải một loạt các bài toán trong cùng một chủ đề.

2/ Cơ bản:

Chúng ta đã gặp một số bất biến trong phần Khởi động. Tiếp theo chúng ta sẽ xem xét một số dạng bất biến cơ bản khác, ví dụ như tính chẵn lẻ, tô màu, công thức đại số, cặp nghịch đối của hoán vị,… Đối với mỗi bài toán, giáo viên có thể bắt đầu bằng việc thảo luận với học sinh dạng bất biến có thể sử dụng là gì.

Bài toán 2.1. Trên bảng viết các số $1,2, \ldots, 1000$. Ở mỗi bước cho phép thay một số bằng tổng các chữ số của nó. Quá trình dừng lại khi có toàn các số có một chữ số. Hỏi số số 1 còn lại trên bảng nhiều hơn hay số số 2 còn lại trên bảng nhiều hơn?

Giải

Nếu chúng ta viết tất cả các số trên bảng theo modulo 9 thì các số này sẽ là bất biến trong các phép biến đổi. Do số các số đồng dư 1 mod 9 nhiều hơn số các số đồng dư $2 \bmod 9$ trong tập $\{1, \ldots, 1000\}$, số các số 1 còn lại trên bảng sẽ nhiều hơn số số 2 còn lại trên bảng.

Bài toán 2.2. Vào năm 3000, ở Việt Nam, một nhân dân tệ (RMB) đổi được 10 đồng Việt Nam (VNĐ). Trong khi đó, ở Trung Quốc, một VNĐ đổi được $10 \mathrm{RMB}$. Một du khách người Nhật lúc đầu có $01 \mathrm{VND}$. Ông này có thể đi lại tùy ý giữa hai nước VN và TQ. Hỏi ông ta có thể làm cho số VNĐ và RMB ông ta có là bằng nhau hay không?

Giải

Xét $X=$ số VNĐ $-$ số RMB của du khách. Khi đó $X \bmod 11$ sẽ là bất biến trong các bước đổi tiền. Nếu số VNĐ và RMB bằng nhau thì $X \equiv 0 \bmod 11$. Lúc đầu $X \equiv 1 \bmod 11$, do đó không thể thu được $X \equiv 0$ mod 11. Ta có câu trả lời phủ định.

Bài toán 2.3. Hình vuông $8 \times 8$ bỏ đi hai ô ở góc đối nhau. Có thể phủ phần còn lại bởi 31 quân đômino $1 \times 2$ không? Nếu bỏ hai ô bất kì thì sao?

Giải

Chúng ta tô màu hình vuông đen trắng như bàn cờ vua. Hai ổ ở góc đối nhau luôn cùng mau nên sau khi bỏ chúng đi, số ô đen khác số ô trắng. Mỗi quân đômino phủ đúng một ô đen, một ô trắng nên phần còn lại của hình vuông không thể phủ kín được bởi các quân đômino. Bất biến ở đây chính là hiệu số giữa số ô trắng và số ô đen trên bảng.

Bài toán 2.4. Cho đa thức $P(x)=a x^{2}+b x+c$, có thể thực hiện một trong hai phép biến đổi:

a) Đổi chỗ $a$ và $c$.

b) Đổi biến $x$ bởi $x+t$ với $t \in \mathbb{R}$.

Hỏi từ $x^{2}-31 x-3$ có thu được $x^{2}-20 x-12$ không? Tìm mối liên hệ của hai đa thức bậc hai $P(x)$ và $Q(x)$ sao cho từ đa thức này có thể thu được đa thức kia bởi hai phép biến đổi nói trên.

Giải

Bất biến của chúng ta là định thức $\Delta=b^{2}-4 a c$ của đa thức $P(x)=a x^{2}+b x+c$. Dễ kiểm tra rằng hai phép biến đổi a) và b) không làm thay đổi định thức của đa thức. Định thức $\Delta_{1}$ của $x^{2}-31 x-3$ và định thức $\Delta_{2}$ của $x^{2}-20 x-12$ là khác nhau. Ta có câu trả lời phủ định! Chúng tôi để lại câu hỏi tìm mối liên hệ giữa hai đa thức bậc hai nhận được từ nhau qua hai phép biến đổi trong đề bài cho bạn đọc.

Bài toán 2.5. Tô đen 09 ô của hình vuông $10 \times 10$. Mỗi lần tô màu đen một ô chưa tô nếu nó kề với ít nhất hai ô đen (kề được hiểu là chung cạnh). Có thể tô màu hết bàn cờ hay không? Nếu là 10 ô thì sao? Nếu là hình vuông $n \times n$ thì lúc đầu cần tô đen ít nhất bao nhiêu ô để có thể tô đen cả bàn cờ?

Giải

Nếu tô 10 ô thì câu trả lời là khẳng định. Ví dụ ta có thể bắt đầu với 10 ô đen trên đường chéo chính của hình vuông.

Nếu tô 9 ô thì câu trả lời là phủ đinh. Xét $X$ là tổng chu vi của phần tô đen trên hình thì lúc đầu $X \leq 36$. Dễ kiểm tra $X$ là nửa bất biến, cụ thể, $X$ là không tăng. Nếu cả bàn cờ được tô màu thì lúc này $X=40$ – mâu thuẫn. Vậy, không thể tô đen được cả bàn cờ nếu xuất phát với 9 ô màu đen.

Bài toán 2.6. Cho một hoán vị của các số $1,2, \ldots, 2012$. Mỗi lần cho đổi chỗ hai số bất kì. Sau 2011 bước có thể quay về hoán vị ban đầu không?

Giải

Bài toán này liên quan đến số cặp nghịch đối của một hoán vị. Cặp nghịch đối của hoán vị $\pi$ của $\{1, \ldots, n\}$ là số cặp $1 \leq i<j \leq n$ sao cho $\pi(i)>\pi(j)$. Bạn đọc hãy tự kiểm tra rằng tính chẵn lẻ của số cặp nghịch đối thay đổi khi chúng ta hoán vị một cặp trong dãy. Sau 2011 bước, số cặp nghịch đối sẽ bị thay đổi tính chẵn lẻ và chúng ta không thể quay trở về hoán vị ban đầu.

Bài toán 2.7. Trên bảng viết các số $1,2,3,4,5$. Mỗi bước cho phép chọn hai số $a, b$ và thay bởi $a+b, a b$. Hỏi có thu được $21,27,64,180,540$ hay không?

Giải

Bài toán này thoạt nhìn khá đơn giản nhưng để tìm được bất biến không phải là điều dễ dàng. Trước hết ta kiểm tra rằng số các số chia hết cho 3 không giảm và số lượng này tăng khi và chỉ khi từ hai số chia 3 dư 1 và chia 3 dư 2 chúng ta thu được một số chia hết cho 3 và một số chia hết cho 2 . Vì vậy, khi chúng ta lần đầu tiên chuyển sang trạng thái có 4 số chia hết cho 3 thì số còn lại chia 3 dư 2 , nhưng 64 chia 3 dư 1 nên câu trả lời sẽ là phủ định.

Bài toán 2.8. Trên bảng viết số $99 \ldots 99$ (2012 lần). Mỗi bước cho phép chọn một số $a$, phân tích $a$ thành tích hai số $m, n$ và viết lên bảng $m \pm 2, n \pm 2$ tùy ý. Ví dụ: $a=15, a=3.5$ có thể viết lên bảng $1=3-2$ và $7=5+2$. Hỏi sau một số bước như vậy, có thể thu được trên bảng toàn các số 9 không?

Giải

Đây cũng không phải là một bài toán “dễ” như cách phát biểu cũng như lời giải của nó. Bất biến là trên bảng luôn có ít nhất một số chia 4 dư 3 .

Bài toán 2.9. Một túi gồm 1001 viên đá. Mỗi bước chọn một túi có nhiều hơn 01 viên. Bỏ đi một viên và chia các viên còn lại thành 02 túi. Hỏi có thể làm như vậy để thu được tất cả các túi đều có 03 viên?

Giải

Xét $X$ là tổng số đá và số túi tại mỗi bước. Dễ thấy $X \bmod 4$ không đổi. Lúc đầu $X=1002$ không chia hết cho 4 . Nếu tất cả các túi có 3 viên thì $X$ lúc đó chia hết cho 4, mẫu thuẫn. Vậy câu trả lời là phủ định.

Bài toán 2.10. Chúng ta xét một quân cờ đặc biệt, được gọi là quân “lạc đà”, di chuyển trên bàn cờ $10 \times 10$ như là một quân mã $(1,3)$. Có nghĩa là di chuyển sang ô kề và sau đó di chuyển ba ô theo hướng vuông góc với hướng vừa di chuyển. Quân mã thông thường di chuyển theo hướng $(1,2)$. Liệu quân lạc đà có thể di chuyển từ một ô sang ô kề nó không?

Giải

Câu trả lời là không. Xét các tô màu đen trắng của bàn cờ thông thường. Dễ dàng kiểm tra được rằng quân lạc đà luôn di chuyển trong các ô cùng màu và hai ô kề nhau lại là khác màu.

Bài toán 2.11. Một bảng hình chữ nhật có thể phủ kín không đè lên nhau bởi các hình $1 \times 4$ và $2 \times 2$. Khi bỏ các hình này ra ngoài, chúng ta làm mất một hình $2 \times 2$ và thay vào đó một hình $1 \times 4$. Liệu có có thể dùng các hình lúc này phủ kín hình chữ nhật được không?

Giải

Câu trả lời là phủ định. Hãy tìm một cách tô màu các ô của hình chữ nhật bởi các màu $1,2,3,4$ sao cho mỗi hình $2 \times 2$ có một ô mỗi màu và hình $1 \times 4$ hoặc không có ô màu $i$ hoặc có 2 ô màu $i$ với mỗi $i=1,2,3,4$.

Bài toán 2.12. Có thể hay không một quân mã đi qua tất cả các ô của bàn cờ $4 \times N$, mỗi ô đúng một lần và quay lại ô xuất phát ban đầu?

Giải

Tô màu hàng thứ nhất $1,2,1,2, \ldots$. Tô màu hàng thứ hai $3,4,3,4, \ldots . .$ Tô màu hàng thứ ba $4,3,4,3, \ldots$, và tô màu hàng thứ tư $2,1,2,1, \ldots$.. Giả sử tồn tại một chu trình bởi quân mã trên bàn cờ. Dẽ̃ kiểm tra rằng với cách tô của chúng ta, nếu quân mã đứng ở ô màu 1 hoặc 2 thì bước tiếp theo sẽ là ô màu 3 hoặc 4 , tương ứng. Do số ô mỗi màu là như nhau, các cập màu sẽ thay đổi luân phiên trong chu trình. Bạn đọc hãy tự chỉ ra rằng lúc này ta phải luân phiên giữa các ô màu 1 và màu 3 hoặc luân phiên giữa các ô màu 2 và màu 4 . Hay nói một cách khác, chúng ta không thể đi hết được cả bàn cờ.

Bài toán 2.13. Có ba máy in thẻ trong đó các thẻ là một cặp các số tự nhiên (không sắp thứ tự). Máy thứ nhất nhận một thẻ với hai số $a, b$ và cho ra thẻ với hai số $a+1, b+1$. Máy thứ hai chỉ nhận các thẻ với hai số chẵn $a, b$ và cho ra thẻ với hai số $a / 2, b / 2$. Máy thứ ba nhận thẻ gồm hai $a, b$ và thẻ gồm hai $b, c$ và cho ra thẻ gồm hai số $a, c$. Các máy cũng sẽ trả lại các thẻ được đưa vào. Có thể nhận được thẻ gồm hai số 1 và 2012 chỉ từ một tấm thẻ gồm hai số 5 và 19 được không? Tổng quát, từ thẻ gồm hai số 5 và 19 có thể nhận được những thẻ như thế nào?

Giải

Ba phép toán có thể viết lại dưới dạng $(a, b) \rightarrow(a+1, b+1)$, $(a, b) \rightarrow(a / 2, b / 2)$ và $(a, b),(b, c) \rightarrow(a, c)$. Trong phép biến đổi thứ nhất, hiệu giữa hai số trên thẻ không đổi. Trong phép biến đổi thứ hai, hiệu giữa hai số trên thẻ giảm một nửa. Và trong phép biến đổi thứ ba, hiệu hai số trên thẻ mới bằng tổng hiệu các số trên hai thẻ cũ. Như vậy, hiệu các số trên thẻ không phải là bất biến! Tuy nhiên, nếu nhìn kĩ, có thể tính chia hết cho một số bất kì sẽ được bảo toàn. Kiểm tra được rằng $19-5=14$ chia hết cho 7 nhưng $2012-1$ thì không. Câu trả lời là phủ định. Phần còn lại của bài toán được dành cho độc giả với gợi ý là tất cả các thẻ gồm hai số $\mathrm{a}, \mathrm{b}$ thỏa mān $a-b$ chia hết cho 7 đều nhận được.

Bài toán 2.14. Một quân cờ di chuyển trên bàn cờ $n \times n$ theo một trong ba cách: đi lên một ô, sang bên phải một ô, đi xuống về bên trái một ô. Hỏi quân cờ có thể đi qua tất cả các ô, mỗi ô đúng một lần và quay lại ô kề bên phải ô xuất phát được không?

Giải

Sau mỗi bước, tổng thứ tự của hàng và cột chứa quân cờ hoặc giảm đi 2 hoặc tăng lên 1 . Như vậy, khi xét theo modulo 3 thì tổng này tăng 1 mỗi bước. Do có $n^{2}-1$ bước, nếu kết thúc ở ô kề bên phải ô xuất phát thì tổng này tăng 1 đơn vị. Do đó $n^{2}-2$ chia hết cho 3 , mẵu thuẫn. Vậy câu trả lời lại là phủ định.

Bài toán 2.15. Có bảy số 0 và một số 1 được điền vào các đỉnh của khố lập phương. Mỡi bước cho phép cộng thêm 1 vào các số ở một cạnh nào đó. Có thể thu được khối lập phương với tất cả các số bằng nhau không? Có thể thu được khối lập phương với tất cả các số chia hết cho 3 không?

Giải

Chúng ta đánh dấu 4 đỉnh của khối lập phương sao cho các đỉnh này không kề nhau. Xét hiệu giữa tổng các số được đánh dấu và các số không được đánh dấu thì tổng này không đổi. Sử dụng bất biến này, chúng ta dễ dàng chứng minh được rằng câu trả lời trong cả hai trường hợp là phủ định.

Bài toán 2.16. Hình tròn được chia thành 06 hình dẻ quạt, trong đó điền các số $1,0,1,0,0,0$ theo thứ tự chiều kim đồng hồ. Cho phép thêm 1 vào các số trong hai ô kề nhau. Có thể làm cho tất cả các số bằng nhau được không?

Giải

Tương tự như Bài 25 , đánh số các dẻ quạt $1,2, \ldots, 6$ và tô màu đỏ các dẻ quạt $1,3,5$. Xét hiệu giữa tổng các số trên các dẻ quạt được tô màu và tổng các số trên các dẻ quạt còn lại thì tổng này không đổi.

Bài toán 2.17. Chúng ta thực hiện phép biến đổi trên các bộ ba số như sau: thay hai số trong chúng, ví dụ $a$ và $b$, bời $(a+b) / \sqrt{2}$ và $(a-b) / \sqrt{2}$. Hỏi có thể nhận được $1, \sqrt{2}, 1+\sqrt{2}$ từ $2, \sqrt{2}, 1 / \sqrt{2}$ không?

Giải

Tổng bình phương của các số trong mọi cấu hình là không đổi. Sử dụng bất biến này, dễ dàng đưa ra câu trả lời phủ định cho bài toán.

Bài toán 2.18. Các số thực được viết lên vòng tròn. Nếu bốn số liên tiếp $a, b, c, d$ thỏa mān $(a-d)(b-c)>0$ thì có thể đổi chỗ $b$ và $c$. Chứng minh rằng quá trình sẽ phải kết thúc.

Giải

Giả sử các số trên vòng tròn theo thứ tự là $a_{1}, a_{2}, \ldots, a_{n}$. Xét $X=\sum_{i=1}^{n} a_{i} a_{i+1}$ với $a_{n+1}=a_{1} .$ Khi đó trong mối phép biến đổi $X$ tăng thực sự. Nếu quá trình kéo dài vô hạn thì tổng này có vô hạn giá trị, nhưng tổng chỉ có tối đa $n !$ giá trị. Suy ra quá trình buộc phải kết thúc.

Bài toán 2.19. Cho một đồ thị $n$ đỉnh, bậc của mỗi đỉnh không quá 5. Chứng minh rằng các đỉnh có thể tô bởi ba màu sao cho không quá $n / 2$ cạnh có các đỉnh mút cùng màu.

Lời giải của Bài 29 được dành cho bạn đọc!

Bất biến và nửa bất biến – Phần 2

Leave a reply

(Bài viết của GS Lê Anh Vinh)

3/ Nâng cao:

Trong phần này chúng ta sẽ thảo luận một số bài toán nâng cao có sử dụng phương pháp bất biến. Trong 29 bài toán chúng ta đã đề cập từ đầu đến giờ, các bài toán gần như được giải quyết ngay lập tực khi đã chỉ ra được bất biến phù hợp. Các bài toán trong phần này, ngoài ý tưởng chính là bất biến, sẽ yêu cầu thêm một số bước biến đổi khác làm tăng độ khó và thú vị của chúng.

Bài toán 3.1. Các ô vuông được xếp kề nhau tạo thành một dải hình chữ nhật vô hạn về cả hai phía. Ta xếp vào các ô vuông một số hữu hạn các viên đá. Mỗi bước, chọn hai viên đá ở cùng ô và chuyển chúng sang hai ô bên cạnh khác hướng nhau.

a) Có thể sau một số hũ̃u hạn bước quay lại ví trí ban đầu không?

b) Có thể thực hiện vô hạn bước như vậy không?

c) Nếu quá trình dừng lại thì trạng thái sắp xếp cuối cùng có phụ thuộc vào quá trình thực hiện các bước không?

Giải

Gán cho viên đá ở ô thứ $n$ số $n^{2}$. Xét tổng tất cả các số thu được. Rõ ràng mỗi phép biến đổi ta thay hai số $n^{2}$ bởi số $(n-1)^{2}$ và $(n+1)^{2}$. Do đó tổng này tăng 2 đơn vị trong mỗi phép biến đổi. Suy ra sau một số hữu hạn bước không thể quay lại vị trí ban đầu.

Tiếp theo, chúng ta đi chứng minh rằng tổng không thể tăng vô hạn bằng phương pháp quy nạp. Lưu ý rằng nếu tổng tăng vô hạn, có nghĩa là một số viên đá sẽ phải tiến ra xa vô hạn. Viên đá cuối cùng bên phải nhất luôn tăng chỉ số và viên đá cuối cùng bên trái luôn giảm chỉ số. Do đó khoảng cách giữa hai viên đá này tăng vô hạn. Và đến một lúc nào đó, sẽ có một viên không chịu tác động của các viên còn lại! Lập luận hoàn chỉnh của phần b và lời giải của phần $c$ được dành cho bạn đọc.

Bài toán 3.2. Hình tròn được chia thành 2011 hình dẻ quạt. Xếp 2012 viên kẹo vào các phằn dẻ quạt. Mỗi bước, cho phép chuyển hai viên ở cùng một phần sang hai phần kề khác hướng. Chứng minh rằng đến một lúc nào đó có ít nhất 1006 phần có chứa kẹo.

Giải

Trước hết, chúng ta có 03 nhận xét quan trọng:

a) Do số kẹo lớn hơn một nửa số ô, quá trình ở đây thực hiện được vô hạn lần;

b) Bài toán sẽ được giải quyết xong nếu ta chứng minh được một lúc nào đó hai ô kề nhau bất kì có kẹo. Thật vậy, lúc đó số ô có chứa kẹo sẽ $\geq 2011 / 2$ và do là số nguyên nên số ô có chứa kẹo ít nhất là 1006 .

c) Đến một lúc nào đó, nếu hai ô kề nhau có ít nhất một viên kẹo thì kể từ đó, hai ô này luôn luôn có kẹo. Điều này là hiển nhiên từ phép chuyển.

Theo Nhận xét c) nếu tại mọi thời điểm đều tồn tại hai ô liền nhau không có kẹo thì sẽ tồn tại hai ô liền nhau không bao giờ có kẹo trong tất cả các phép biến đổi. Ta đánh số các dẻ quạt bởi $1,2, \ldots, 2011$ sao cho hai ô đó là 1 và 2011 . Gán cho mỗi chiếc kẹo một số tương ứng với số của ô chứa nó và xét $X$ là tổng bình phương các số đó.

Tương tự như bài trên, $X$ tăng trong mỗi phép biến đổi. Theo Nhận xét a), $X$ tăng vô hạn. Nhưng lại có $X \leq 1006 \times 2010^{2}$, dẫn đến mâu thuẫn. Vậy, đến một lúc nào đó hai ô kề nhau bất kì luôn có kẹo. Bài toán được suy ra từ Nhận xét b).

Bài toán 3.3. Giả thiết và câu hỏi như ở Bài 30 , chỉ khác cách chuyển viên đá được thực hiện như sau:

a) Bỏ một viên ở ô thứ $n-1$ và một viên ở ô thứ $n$, thêm vào một viên ở ô thứ $n+1$.

b) Bỏ hai viên ở ô thứ $n$ và thêm một viên vào ô thứ $n-2$, một viên vào ô thứ $n+1$.

Giải

Nhận xét rằng viên đá ở ô phải nhất sẽ luôn di chuyển về bên phải và viên đá ở bên trái nhất sẽ luôn đi về bên trái. Nếu như quay lại trạng thái ban đầu sau hữu hạn bước thì chúng ta sẽ không được tác động đến hai viên này. Khi đó, có thể bỏ đi hai viên này và lặp lại lập luận trên để suy ra mâu thuẫn. Do đó, không thể quay lại trạng thái ban đầu sau hữu hạn bước.

Chọn $\alpha>1$ là nghiệm của $\alpha^{2}-\alpha-1=0$. Gán cho viên đá ở ô thứ $n$ số $\alpha^{n}$ và xét $X$ là tổng các số này. Khi đó tổng $X$ không đổi. Giả sử có thể chuyển viên đá vô hạn lần thì theo nhận xét trên, các viên đá sẽ tiến ra vô cùng và khi đó tổng $X$ cũng vậy $(\operatorname{do} \alpha>1)$. Điều này mâu thuẫn với tính bất biến của $X$.

Để chứng minh trạng thái sắp xếp cuối cùng không phụ thuộc vào quá trình các bước chuyển, ta chỉ cần chứng minh nếu từ một trạng thái thu được hai trạng thái khác nhau thì tổng $X$ sẽ khác nhau. Chi tiết của lập luận này (thật ra là một bài toán bất đẳng thức đơn giản) được dành cho bạn đọc.

Bài toán 3.4. Có 119 người ở trong 120 căn hộ. Một căn hộ được gọi là quá tải nếu có nhiều hơn 14 thành viên. Mỗi ngày, các thành viên của một căn hộ quá tải xảy ra mẫu thuẫn và chuyển sang các căn hộ khác nhau. Hỏi quá trình có buộc phải kết thúc không?

Giải

Trước khi chuyển nhà cho các thành viên ở căn hộ quá tải bắt tay nhau. Có thể chứng minh được rằng tổng số cái bắt tay sẽ giảm thực sự. Và do đó quá trình sẽ buộc phải kết thúc sau hữu hạn bước.

Bài toán 3.5. Trên vòng tròn có 20 số. Cho phép chọn 3 số liên tiếp $X, Y, Z$ và thay bởi $X+Y,-Y, Z+Y$. Có thể từ

$$ [1,2, \ldots, 10,-1,-2, \ldots,-10] $$

thu được $[10,9, \ldots, 1,-10, \ldots,-1]$ hay không?

Giải

Chọn $x_{1}, \ldots, x_{20}$ sao cho $x_{1}-x_{2}, \ldots, x_{20}-x_{1}$ là bộ 20 số ban đầu. Khi đó dễ dàng kiểm tra được rằng, phép biến đổi đã cho trên bộ 20 số $x_{1} – x_{2}, \ldots, x_{20}-x_{1}$ sẽ tương ứng với việc đổi chỗ hai số cạnh nhau trên bộ $x_{1}, \ldots, x_{20}$. Từ $x_{1}, \ldots, x_{20}$ tương ứng với $[1,2, \ldots, 10,-1,-2, \ldots,-10]$, đổi chỗ liên tiếp các số cạnh nhau ta thu được $x_{20}, \ldots, x_{1}$ ương ứng với bộ $[10,9, \ldots, 1,-10, \ldots,-1]$. Do đó, câu trả lời là khẳng định.

Bài toán 3.6. Giả sử tổng của 20 số là dương. Cho phép biến đổi như ở bài trên, liệu có thể thu được một bộ gồm 20 số không âm hay không?

Giải

Y tưởng chứng minh tương tự như trên. Chỉ có điều chúng ta không điền các số trên vòng tròn mà điền trên đường thẳng vô hạn $\ldots, x_{-n}, \ldots, x_{n}, \ldots$ sao cho chọn 21 số liên tiếp trên đường thẳng thì hiệu các cặp giữa chúng sẽ là 20 số tương ứng. Ta chỉ cần chỉ ra rằng với các đồi chỗ như trong giả thuyết của đề bài, ta có thể sắp xếp lại dãy theo thứ tự tăng. Khi đó, ta sẽ có câu trả lời khẳng định cho bài toán.

Bài toán 3.7. Trên vòng tròn có một số điểm Xanh, Đỏ. Cho phép thêm vào một điểm $Đ$ và đổi màu hai điểm kề nó, hoặc bớt đi một điểm $D$ và đổi màu hai điểm kề nó. Lúc đầu có hai điểm $\mathrm{D}$ và quá trình ko được phép làm cho có ít hơn hai điểm. Hỏi có thể thu được:

a) 2 điểm $\mathrm{X}$, Đ.

b) 8 điểm $\mathrm{D}$.

c) 1 điểm $Đ, 6$ điểm $X$.

d) 2 điểm X.

Giải

a) Không thể thu được 2 điểm $\mathrm{X}, \mathrm{D}$ do tính chẵn lẻ của số điểm X không thay đổi.

b) c) Xây dựng được cụ thể.

d) Không được thể thu được 2 điểm $\mathrm{X}$. Do lúc đầu không có điểm $\mathrm{X}$ nào nên số điểm X luôn là chã̄n. Đánh số các điểm xanh bởi $x_{1}, \ldots, x_{2 n}$ và gọi $d_{1}, \ldots, d_{2 n}$ là số điểm đỏ giữa các điểm $\mathrm{X}$. Bất biến là tính chia hết cho 3 của

$$ S=\left|d_{1}-d_{2}+\ldots+d_{2 n-1}-d_{2 n}\right| $$

Nếu không có điểm $X$ nào thì đặt $S$ là số điểm đỏ. Đây là một bài toán rất khó và chúng tôi khuyến khích bạn đọc tìm hiểu xem với các cấu hình nào thì có thể nhận được từ một cặp điểm $Đ$ ? Gợi ý rằng đại lượng $S$ sẽ giúp xác định chính xác các cấu hình như vậy.

Hết

Giải bài toán bằng đại lượng cực biên – Phần 2

Leave a reply

(Bài viết dành cho các em học sinh lớp 8, 9, 10)

Ví dụ 1. Tìm $n$ lớn nhất sao cho tồn tại $n$ điểm mà 3 điểm bất kì đều tạo thành tam giác vuông.

Lời giải.

Ta thấy $n=3, n=4$ đều tồn tại. Ta chứng minh $n\geq 5$ thì không tồn tại. \
Giả sử ngược lại, tồn tại 5 điểm, sao cho 3 điểm bất kì đều tạo thành tam giác vuông. Khi đó ta chọn hai điểm sao cho có độ dài lớn nhất. Khi đó các điểm còn lại đều nằm trên đường tròn đường kính là đoạn thẳng này. Khi đó 3 điểm thuộc 2 nửa đường tròn, khi đó có ít nhất 2 điểm cùng thuộc một nửa, từ đó tồn tại một tam giác khác vuông có đỉnh là 2 điểm này cùng một điểm thuộc đường kính. Do đó không thỏa đề bài.

Nhận xét. Đây là một bài toán cực trị dạng tìm số nhỏ nhất, lớn nhất của n để thỏa điều kiện nào đó. Những kiểu bài tập này thường ta cứ xét các trường hợp nhỏ và cố gắng xây dựng cấu hình thỏa, đối với bài này cấu hình rất dễ tìm, với trường hợp $ n = 5$, để chứng minh không tồn tại, ta sử dụng cực biên, kết hợp với phản chứng để cho lời giải trọn vẹn, chọn độ dài lớn nhất giúp mình gôm hết các điểm vào thành một đường tròn, từ đó giúp giải được bài toán.

Ví dụ 2. Trên một mặt bàn đặt một số các đồng xu với kích cỡ không giống nhau đôi một (các đồng xu không được đè lên nhau và phải nằm sấp hoặc ngửa trên bàn). Chứng minh rằng dù ta đặt như thế nào đi nữa, cũng luôn tồn tại một đồng xu chỉ tiếp xúc được với nhiều nhất 5 đồng xu khác.

Lời giải. Đồng xu càng to thì nhiều đồng xu có thể tiếp xúc với nó, còn ngược lại thì càng nhỏ, do đó để càng ít đường tròn tiếp xúc nó, ta chọn đồng xu nhỏ nhất.

Chọn đồng xu có bán kính nhỏ nhất, thì đồng xu này chỉ tiếp xúc không quá 5 đồng xu khác. Giả sử nó có thể tiếp xúc với 6 đồng xu khác. Khi đó $A$ là tâm đường tròn, tâm các đường tròn còn lại là $A_1, \cdots, A_6$. Khi đó tồn tại $A_iA_{i+1} \leq 60^\circ$, suy ra $A_iA_{i+1} < AA_i$ vô lý, vì bán kính của $(A)$ là nhỏ nhất.

Ví dụ 3. Cho $n$ điểm trong mặt phẳng biết rằng cứ 3 điểm bất kì tạo thành một tam giác có diện tích không lớn hơn 1. Chứng minh rằng $n$ điểm thuộc một hình tam giác có diện tích không lớn hơn 4.

Lời giải. Gọi $A, B, C$ là 3 điểm tạo thành tam giác sao cho $ABC$ có diện tích lớn nhất. Từ $A, B, C$ vẽ các đường song song với các cạnh đối diện, các đường thẳng cắt nhau tại $A’, B’, C’$ ta chứng minh các điểm thuộc cạnh hoặc miền trong tam giác $A’B’C’$. \
Thật vậy, nếu có điểm nào nằm ngoài tam giác $A’B’C’$ thì điểm đó kết hợp với hai trong 3 điểm $A, B, C$ sẽ có diện tích lớn hơn diện tích tam giác $ABC$, vô lý. \
Do $S_{A’B’C’} = 4S_{ABC} \leq 4$.

Ví dụ 4. (Sylvester) Trong mặt phẳng cho $n$ điểm phân biệt, sao cho mỗi đường thẳng đi qua hai điểm thì đi qua ít nhất một điểm khác. Chứng minh rằng $n$ điểm này cùng thuộc một đường thẳng.

Lời giải. Giả sử không phải tất cả các điểm cùng thuộc một đường thẳng. Khi đó ta xét khoảng cách từ một điểm đến đường thẳng qua ít nhất 3 điểm, trong các khoảng cách này có khoảng cách nhỏ nhất. Giả sử $P$ là điểm có khoảng cách từ $P$ đến $d$ là nhỏ nhất, với $d$ là đường thẳng qua các điểm $A, B, C$ theo thứ tự. \
Gọi $H$ là hình chiếu của $P$ trên $d$, $D, E$ là hình chiếu của $A, B$ trên $B$ trên $PA, PC$. Nếu $H$ thuộc tia $BA$ thì $BE < PH$, nếu $H$ thuộc đoạn $BC$ thì $BD < PH$. Mâu thuẫn với $PH$ là nhỏ nhất. \
Vậy tất cả các điểm cùng thuộc một đường thẳng.

Việc chọn phần tử lớn nhất, nhỏ nhất thể hiện ưu thế của của các phần tử đó so với các đối tượng khác, đó chưa chắc là cái thỏa, nhưng cũng cũng có ưu thế hơn, giống khi xét tuyển, các thí sinh có điểm trung bình cao chưa chắc là giỏi nhất, nhưng là những người có ưu thế hơn điểm thấp, khi chọn trong nhóm đó sẽ tìm được nhiều người giỏi hơn là chọn trong nhóm thấp điểm, do đó vượt trội một khía cạnh nào tính ra là một lợi thế để so sánh.

Ta tiếp tục với việc chứng minh các bài toán về tồn tại các đối tượng thỏa yêu cầu nào đó.

Ví dụ 5. Cho 3 trường, mỗi trường có $n$ học sinh, biết rằng cứ mỗi học sinh thì quen ít nhất $n + 1$ học sinh của hai trường khác. Chứng minh rằng có thể chọn được từ mỗi trường một bạn sao cho 3 bạn này đôi một quen nhau.

Lời giải. Giả sử 3 trường là $X, Y, Z$. Tồn tại một người có số người quen ở cùng một trường khác là nhiều nhất, giả sử $A$ thuộc $X$ có số người quen ở trường $Y$ nhiều nhất là $k$. Khi đó số người quen của $A$ ở $Z$ ít nhất là $n+1-k$. Nếu nhóm người quen $A$ ở $Z$ quen với số người quen $A$ ở $X$ có hai người quen nhau thì ta có điều chứng minh.\
Ngược lại xét người quen $A$ ở $Z$, đặt là $B$ quen số người ở $Y$ tối đa là $n-k$, khi đó $B$ quen ở $X$ ít nhất là $n+1 – (n-k) = k+1$, mâu thuẫn với cách chọn $A$. (Mâu thuẫn).

Ví dụ 6. Một bảng $2n \times 2n$ ô, người ta đánh dấu bất kì $3n$ ô trong bảng. Chứng minh rằng tồn tại $n$ dòng và $n$ cột sao cho $3n$ ô được đánh dấu thuộc $n$ dòng và $n$ cột này.

Lời giải. Chọn $n$ dòng sao cho số ô được tô là lớn nhất, ta chứng minh rằng số ô được tô trong $n$ dòng này là không ít hơn $2n$ ô.
Thực vậy giả sử số ô được tô là ít hơn $2n$, khi đó $n$ dòng còn lại có nhiều hơn $n$ ô được tô, nên có ít nhất một một dòng có 2 ô được tô.

Do đó $n$ dòng đã chọn, mỗi dòng ít nhất 2 ô được tô nên tổng số ô hơn hoặc bằng $2n$ (mâu thuẫn).
Vậy ta chỉ cần chọn $n$ cột chứa các ô được tô màu nhưng chưa được chọn trong $n$ dòng trên thì sẽ có điều cần chứng minh.

Ví dụ 7. Một bữa tiệc có 10 học sinh tham gia, biết rằng mỗi học sinh quen với ít nhất là 5 người. Chứng minh rằng có thể sắp xếp 10 học sinh ngồi vào một bàn tròn sao cho hai người kế nhau thì quen nhau.

Lời giải. Giả sử chuỗi người quen dài nhất có độ dài là $k$, $A_1A_2…A_k$, ta thấy các người còn lại không ai quen $A_1, A_k$ nên suy ra $k \geq 6$. \
Nếu $k = 6$, suy ra $A_1$ và $A_6$ quen nhau, khi đó trong các người còn lại $A_7$ quen một trong cái người giả sử là $A_i$, khi đó ta có chuỗi $A_7A_iA_{i-1}A_1A_6A_{i+1}$ có độ dài hơn 6, vô lý.\
Nếu $k =7$, khi đó $A_1$ quen từ $A_2$ đến $A_6$ và $A_7$ quen $A_2$ tới $A_6$, khi đó có một vòng $A_2A_7A_6A_5A_4A_3A_1A_2$. Khi đó sẽ có một người trong nhóm còn lại thì ta sẽ có chuỗi dài hơn, mâu thuẫn.\
Nếu $k=8,9$ xét tương tự, ta sẽ có $k=10$. Giả sử có chuỗi $A_1\cdots A_{10}$. Khi đó tồn tại $k>i$ sao cho $A_1$ quen $A_k$ và $A_{10}$ quen $A_i$, khi đó có cách xếp thỏa đề bài là $A_1A_k\cdot A_iA_{10}A_9…A_k$.

Bài tập Bài tập nguyên lý cực biên

Tài liệu tham khảo.

Problems – Solving Stretagies – Arthur Hegel
Giải bài toàn bằng đại lượng cực biên – Nguyễn Hữu Điển

Trắc nghiệm phép đếm

Leave a reply

[WpProQuiz 20]

Phương pháp chứng minh phản chứng (P2)

Leave a reply

Bài 1.

Cho tập $B = {1, 2, 3, …, 16}$. Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:

a/ Tổng của hai số kế nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?

b/ Tổng của ba số kế nhau bất kì lớn hơn 24 được không? Tại sao?

Lời giải

a/ Giả sử tồn tại cách ghi thỏa mãn. Khi đó, gọi 2 số kề với 1 là a và b.

Theo giả thiết, ta có:

Vậy không tồn tại cách ghi thỏa mãn.

b/ Giả sử tồn tại cách ghi thỏa mãn.

Khi đó, ta tách số 16 ra và chia 15 số còn lại thành 5 bộ 3 số kề nhau. Và tổng của 16 số này phải lớn hơn hoặc bằng: $16+5\cdot 25=141$

Mà $1+2+3+\cdots 16=136 \Rightarrow $ Mâu thuẫn

Vậy không tồn tại cách ghi thỏa mãn.

Bài 2.

Có tồn tại hay không một cách điền các số $0,1, 2, 3, \cdots , 9$ vào các đỉnh của một đa giác 10 đỉnh sao cho hiệu hai số ở hai đỉnh kề nhau chỉ có thể nhận một trong các giá trị sau: $-5, -4, -3, 3, 4, 5$.

Lời giải

Giả sử có cách xếp thỏa mãn.

Xét các số $0,1,2,8,9$ không thể đứng kề nhau và có đúng 10 số nên 5 số còn lại phải đứng xen kẽ với 5 số $0,1,2,8,9$.

Xét số 7:

Khi đó hai số kề số 7 phải thuộc tập hợp $\left\{0,1,2,8,9\right\}$

Mà theo giả thiết 2 đỉnh kề nhau bất kì nhận một trong các giá trị – 3, – 4, – 5, 3, 4 hoặc 5 nên 2 số kề nhau với 7 đều bằng 2 $\Rightarrow$ Mâu thuẫn.

Vậy không có cách xếp nào thỏa mãn.

Bài 3.

Trong mặt phẳng tọa độ thì một điểm mà hoành độ và tung độ đều là các số nguyên được gọi là điểm nguyên. Chứng minh rằng không tồn tại tam giác đều nào mà các đỉnh đều là điểm nguyên.

Lời giải

Giả sử tồn tại tam giác đều có các đỉnh là các điểm nguyên.

Xét hình chữ nhật có các đỉnh là các điểm nguyên, sao cho đỉnh của tam giác đều thuộc cạnh của hình chữ nhật. Khi đó dễ dàng suy ra diện tích tam giác đều là số hữu tỷ.

Ta có diện tích tam giác đều $S=\dfrac{a^{2} \sqrt{3}}{4}$ với $a^2=x^2+y^2$ là số nguyên, $\sqrt{3}$ là số vô tỷ

Do đó, S là số vô tỉ $\Rightarrow$ Mâu thuẫn $\Rightarrow$ đpcm.

Bài 4.

Điền các số 1,2,3,…,121 vào một bảng ô vuông kích thước $11 \times 11$ sao cho mỗi ô chứa một số. Tồn tại hay không một cách điền sao cho hai số tự nhiên liên tiếp sẽ được điền vào hai ô có chung một cạnh và các tất cả các số chính phương thì nằm trong cùng một cột?

Lời giải

Giả sử tồn tại một cách điền số vào các ô thỏa yêu cầu đặt ra.

Khi đó bảng ô vuông được chia thành hai phần ngăn cách nhau bởi cột điền các số chính phương. Một phần chứa $11n$ ô vuông $1 \times 1$, và phần còn lại chứa $110-11n$ ô vuông $1 \times 1$ , với $0 \le n \le 5.$

Nhận thấy rằng các số tự nhiên nằm giữa hai số chính phương liên tiếp $a^2$ và $(a+1)^2$ sẽ cùng nằm về một phần và các số tự nhiên nằm giữa $(a+1)^2$ và $(a+2)^2$ sẽ nằm ở phần còn lại.

Ta có số lượng các số tự nhiên nằm giữa 1 và 4, 4 và 9, 9 và 16,…,100 và 121 lần lượt là $2,4,6,8,…,20$.

Do đó một phần sẽ chứa $2+6+10+14+18=50$ số, phần còn lại chứa $4+8+12+16+20=60$ số.

Cả 50 và 60 đều không chia hết cho 11 $\Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách điền số thỏa yêu cầu đề bài.

Bài 5.

Mỗi phần tử của bảng vuông $ 25 \times 25 $ hoặc là $ + 1 $ hoặc $ -1 $. Gọi $ a_{i} $ là tích của tất cả các phần tử của hàng thứ $ i $ và $ b_{j} $ là tích của tất cả các phần tử của cột thứ $ j $. Chứng minh rằng $ a_ {1} + b_ {1} + \cdots + a_ {25} + b_ {25} \neq 0 $

Lời giải

Giả sử $ a_ {1} + b_ {1} + \cdots + a_ {25} + b_ {25} = 0 $.

Vì mỗi ô vuông chứa -1 hoặc 1 nên $a_i,b_i\in \left\{1,-1\right\}$

Do đó trong 50 tích $a_i,b_i\quad (i=\overline{1,25})$ sẽ có 25 tích có giá trị -1 và 25 tích có giá 1.

Khi thay thế một phần tử -1 trong bảng bằng 1 thì số các tích ngang dọc có giá trị -1 sẽ tăng 2 hoặc giảm 2 hoặc không thay đổi. Như vậy số các tích $a_i,b_i$ có giá trị -1 luôn là số lẻ (1)

Ta sẽ tiếp tục thay thế các phần tử -1 trong bảng bằng 1 cho đến khi tất cả các phần tử trong bảng đều bằng 1 thì khi đó số các tích ngang dọc $a_i,b_i$ có giá trị -1 là 0 $\Rightarrow$ Mâu thuẫn với (1) $\Rightarrow$ đpcm.

Phương pháp ánh xạ trong các bài toán tổ hợp

Leave a reply

Thầy Nguyễn Tăng Vũ

1/ Lý thuyết:

Cho $A$ và $B$ là hai tập hợp hữu hạn.

Nếu có một đơn ánh $f: X \longrightarrow Y$ thì $|X| \le |Y|.$
Nếu có một toàn ánh $f: X \longrightarrow Y$ thì $|X| \ge |Y|.$
Nếu có một song ánh $f: X \longrightarrow Y$ thì $|X| = |Y|.$

2/ Bài tập:

Bài 1.

Cho $X={ 1,2,..,n}$. Một tập con $S={s_1,s_2,…,s_k }$ của X ($s_1<s_2<…<s_k$) được gọi là \textit{m- tách được} $(m \in \mathbb{N})$ nếu $s_i-s_{i-1} \ge m; i=1,2,…,k$. Có bao nhiêu tập con m- tách được gồm $k$ phần tử của X, trong đó $0 \le k \le n-(m-1)(k-1)$.

Lời giải

Gọi A là tập tất cả các tập con m- tách được gồm $k$ phần tử của X và B là tập tất cả các tập con gồm k phần tử của tập $Y=\{1,2,…, n-(k-1)(m-1) \}$.

Ta xây dựng song ánh từ A đến B như sau: Với $S=\{s_1,s_2,…,s_k \} \in A$ ($s_1<s_2<…<s_k$) lấy tương ứng $f(S)=\{s_1, s_2-(m-1), s_3-2(m-1),…, s_k-(k-1)(m-1) \}$. Dễ chứng minh đây là một song ánh. Từ đó có $C^k_{n-(k-1)(m-1)}$ tập thoả yêu cầu đề bài.

Bài 2.

Cho $X={1,2,…,n}$, với mỗi tập con khác rỗng $A_i={a_1,a_2,…,a_i }$ (không mất tổng quát giả sử $a_1>a_2>…>a_i$) ta định nghĩa tổng hỗn tạp của $A_i$ là số $m(A_i)=a_1-a_2+a_3-… \pm a_i$. Tính $\sum \limits_{A_i \subset X} m(A_i)$.

Lời giải

Gọi B là tập tất cả các tập con không chứa phần tử n của X và C là tập tất cả các tập con có chứa phần tử n của X.

Ta xây dựng song ánh từ B đến C như sau: Với $S=\{s_1,s_2,…,s_k \} \in B$ ($s_1<s_2<…<s_k<n$) lấy tương ứng $f(S)=\{s_1,s_2,…,s_k,n \} ,$ nhận thấy $f(S)\in C$. Dễ chứng minh đây là một song ánh.

Ta có: $|B|=|C|=2^{n-1};B\cup C= \emptyset;B\cap C=X$

Và $m(S)+m(f(S))=n$

Do đó: $$\sum \limits_{A_i \subset X} m(A_i) =\sum \limits_{B_i \subset B} m(B_i) +\sum \limits_{C_i \subset C} m(C_i)=n\cdot 2^{n-1}$$

Bài 3.

Cho $X={1,2,…,n}$. Một tập con A của X được gọi là tập béo nếu mỗi phần tử của A đều không nhỏ hơn số phần tử của nó. Tập rỗng cũng là một tập béo. Đặt $a_n$ là số các tập béo của X mà trong mỗi tập không chứa hai số liên tiếp, $b_n$ là số các tập con của X mà hai phần tử bất kỳ hơn kém nhau ít nhất 3 đơn vị. Chứng minh $a_n=b_n.$

Lời giải

Gọi A là họ các tập béo thỏa yêu cầu đề bài, B là họ các các tập con của X có tính chất hai phần tử bất kỳ hơn kém nhau 3 đơn vị. Ta thiết lập một ánh xạ $f$ đi từ A đến B như sau: giả sử $x=\{a_1,a_2,…,a_k\} \in A$, ta có thể giả sử $k \le a_1<a_2<a_3<…<a_k \le n$. Đặt $b_1=a_1-k+1, b_2=a_2-k+2,…,b_k=a_k$. Khi đó $$ a_{i+1} \ge a_i+2, i=1,2,…,k-1. $$

Suy ra $a_{i+1}-a_i \ge 2$ do đó $b_{i+1}-b_i \ge 3$ và $b_1 \ge 1, b_k \le n.$ Định nghĩa $f(x)=y=\{b_1,b_2,…,b_k\}$, suy ra $y \in B$. Vậy $f$ là một ánh xạ, hơn nữa dễ thấy $f$ là một song ánh do đó ta có điều cần chứng minh.

Bài 4.

Cho số nguyên dương $n$ và $d$ là một ước dương của $n$. Gọi S là tập tất cả những bộ $(x_1,x_2,…,x_n)$ nguyên dương thỏa $0 \le x_1 \le x_2 \le… \le x_n \le n$ và $d| x_1+x_2+…+x_n$. Chứng minh rằng có đúng một nửa các phần tử của S có tính chất $x_n=n$.

Lời giải

$(x_1,x_2,…,x_{n-1},x_n) \in S$ mà $x_n \ne n$ ta cho tương ứng với bộ $(x_1+1,x_2+2,…,x_{n-1}+1,x_n+1)$, với $(x_1,x_2,…,x_{n-1},n) \in S$ ta cho tương ứng với bộ $(0,x_1,…,x_{n-1}).$ \

Dễ chứng minh $f$ là một song ánh, $f$ hoán vị S và $f(S)=S.$ Vì tổng tất cả các phần tử của các bộ trong S và $f(S)$ là như nhau trong khi tương ứng thứ nhất tăng tăng tổng này lên $n$ đơn vị, tương ứng thứ hai giảm tổng này đi $n$ đơn vị nên số lần xuất hiện của hai tương ứng này là như nhau. Từ đó suy ra điều cần chứng minh

Bài 5.

Gọi $a_n$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_n$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n+1}=2a_n$ với mọi số nguyên dương $n$.

Lời giải

Gọi $A_n, B_n$ lần lượt là tập các xâu nhị phân độ dài $n$ thỏa điều kiện thứ nhất và thứ hai. Với mỗi xâu nhị phân $(x_1,x_2,…,x_n)$ ta cho tương ứng với một xâu nhị phân $(y_0,y_1,…,y_n)$ xác định bởi $y_0=0$ và $$ y_i=x_1+x_2+…+x_i \ mod \ 2, i=1,2,…,n. \ \ \ (*)$$

Khi đó $$ x_i=y_i+y_{i-1} \ mod \ 2, i=1,2,…,n. $$

Dễ thấy (*) là một song ánh giữa tập tất cả các xâu nhị phân độ dài $n$ và tập tất cả các xâu nhị phân độ dài $n+1$ trong đó có bit đầu tiên là 0. Hơn nữa xâu nhị phân $(x_1,x_2,…,x_n)$ có 3 bit 0,1,0 liên tiếp theo thứ tự này khi và chỉ khi xâu nhị phân tương ứng $(y_0,y_1,…,y_n)$ có 4 bit liên tiếp theo thứ tự là 0,0,1,1 hoặc 1,1,0,0. Nói cách khác một xâu nhị phân thuộc $A_n$ sẽ tương ứng với một xâu nhị phân thuộc $B_{n+1}$ và bắt đầu bằng bit 0. Vì số xâu nhị phân thuộc vào $B_{n+1}$ bắt đầu bằng bit 0 đúng bằng một nửa số xâu nhị phân thuộc vào $B_{n+1}$ do đó ta có $b_{n+1}=2a_n$ (điều phải chứng minh).

Các bài toán tổ hợp trong kì thi Junior Bankan – P1

Leave a reply

Lê Phúc Lữ – Phạm Khánh Vĩnh

(Bài viết trích từ Tập san Star Education – Số 5)

Bài 1. (JBMO 1998)
Hỏi có tồn tại hay không $16$ số có ba chữ số tạo thành từ ba chữ số phân biệt cho trước mà không có hai số nào có cùng số dư khi chia cho $16$?

Lời giải

Câu trả lời là phủ định.
Giả sử tồn tại các số thỏa mãn đề bài thì vì chúng có số dư đôi một khác nhau nên sẽ có đầy đủ các số dư $0,1,2,3,\ldots ,15$. Điều này có nghĩa là trong đó, có $8$ số chẵn và $8$ số lẻ. Suy ra, ba chữ số $a,b,c$ để tạo thành các số đã cho không thể có cùng tính chẵn lẻ. Ta có hai trường hợp:

Trong các số $a,b,c$, có hai số chẵn là $a,b$ và số $c$ lẻ. Ta có tất cả $9$ số lẻ tạo thành từ các chữ số này là:
$aac,abc,acc,bac,bbc,bcc,cac,cbc,ccc$.
Gọi ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{9}}$ là số có hai chữ số tạo thành bằng cách xóa đi chữ số cuối từ dãy trên.
Rõ ràng số $\overline{{{a}_{i}}k}$ và $\overline{{{a}_{j}}k}$ với $i\ne j$ khác số dư với nhau theo modulo $16$ nếu như hiệu của chúng không chia hết cho $16$, suy ra ${{a}_{i}}-{{a}_{j}}$ không chia hết cho $8.$ Tuy nhiên, ta lại có đến $9$ số nên điều này không thể xảy theo nguyên lý chuồng bồ câu.
Trong các số $a,b,c$, có hai số lẻ là $a,b$ và số $c$ chẵn: cũng dẫn đến mâu thuẫn tương tự.

Vậy không tồn tại các số thỏa mãn đề bài.

Bài 2: (JBMO 2000)

Trong một giải thi đấu tennis, số lượng nam gấp đôi số nữ. Mỗi cặp vận động viên thi đấu với nhau đúng một lần và không có trận hòa, chỉ có thắng – thua. Tỷ số giữa trận thắng của nữ và của nam là $\frac{7}{5}$. Hỏi có bao nhiêu vận động viên trong giải thi đấu?

Lời giải

Gọi số nam là $2n$, số nữ là $n$ và tổng số vận động viên là $3n.$ Tổng số trận đấu là

$\frac{3n(3n-1)}{2}.$ \medskip

Theo giả thiết thì số trận thắng bởi nam là $$\frac{5}{12}\cdot \frac{3n(3n-1)}{2}=\frac{5n(3n-1)}{8}.$$

Số trận đấu giữa các nam là $\frac{2n(2n-1)}{2}=n(2n-1)$ và rõ ràng số trận này không vượt quá số trận thắng của các nam.

Suy ra $$\frac{5n(3n-1)}{8}\ge n(2n-1)\Leftrightarrow n\le 3.$$ Mặt khác, $5n(3n-1)$ phải chia hết cho $8$ nên $n=3.$ Do đó, số vận động viên của giải đấu là $9.$

Bài 3: (JBMO 2006)

Xét bảng ô vuông kích thước $2n\times 2n$ với $n$ nguyên dương. Người ta xóa đi một số ô của bảng theo quy tắc sau đây:

Nếu $1\le i\le n$ thì ở dòng thứ $i$, xóa $2(i-1)$ ô ở giữa.
Nếu $n+1\le i\le 2n$ thì ở dòng thứ $i,$ xóa đi $2(2n-i)$ ô ở giữa.

Hỏi có thể phủ được bảng bởi tối đa bao nhiêu hình chữ nhật kích thước $2\times 1$ và $1\times 2$ (không nhất thiết phải phủ kín toàn bộ) sao cho không có hai hình chữ nhật nào chồng lên nhau?

Lời giải

Với mọi bảng kích thước $2n\times 2n,$ tổng số ô bị xóa đi là $$2\times 2\times (1+2+3+\cdots +n-1)=2n(n-1).$$

Bảng sẽ còn lại ${{(2n)}^{2}}-2n(n-1)=2n(n+1)$ ô, tức là phủ được tối đa $n(n+1)$ ô vuông.

Với $n=1,2,3,4,$ ta có thể kiểm tra trực tiếp được rằng kết quả lần lượt sẽ là $2,6,12,20$ bởi khi đó ta có thể phủ kín toàn bộ bảng. Còn với $n\ge 4$, ta xét hai trường hợp:

Nếu $n$ lẻ, khi đó ta chia bảng $2n\times 2n$ đã cho thành $4$ hình vuông nhỏ thì rõ ràng, mỗi hình sẽ có $\frac{n(n+1)}{2}$ ô còn trống. Tiếp theo, ta tô màu theo dạng bàn cờ cho bảng này (ô ở góc thì tô đen), ta sẽ có tất cả $\frac{{{(n+1)}^{2}}}{4}$ ô đen và $\frac{{{n}^{2}}-1}{4}$ ô trắng. Rõ ràng mỗi hình chữ nhật khi đặt lên bảng sẽ chứa một ô đen và một ô trắng nên số cặp ô trắng – đen tối đa trong hình vuông con là $\frac{{{n}^{2}}-1}{4}$, và tương ứng sẽ có tối đa $$4\cdot \frac{{{n}^{2}}-1}{4}={{n}^{2}}-1$$ hình chữ nhật $1\times 2,2\times 1$ phủ được trên bảng.

Ngoài ra, giữa các hình vuông con cạnh nhau, ta còn có hai ô màu đen cạnh nhau nên ta có thể lát thêm vào đó tổng cộng $4$ hình chữ nhật nữa, tổng cộng là ${{n}^{2}}-1+4={{n}^{2}}+3$.

Nếu $n$ chẵn, bằng cách tương tự trên, ta phủ được hình bởi tối đa ${{n}^{2}}+4$ ô.

Tóm lại,

Với $n=1,2,3,4$, đáp số lần lượt là $2,6,12,20.$
Với $n>4$ và $n$ lẻ thì đáp số là ${{n}^{2}}+3.$
Với $n>4$ và $n$ chẵn thì đáp số là ${{n}^{2}}+4.$

Bài 4: (JBMO 2008)

Một bảng $4\times 4$ được chia thành $16$ ô vuông con và tất cả đều được tô màu trắng. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh. Một thao tác hợp lệ bao gồm việc chọn một ô vuông và đổi màu tất cả các ô kề với nó (kể cả nó): trắng sang đen, đen sang trắng. Sau $n$ thao tác, tất cả ô vuông của bảng chuyển sang màu đen. Tìm tất cả các giá trị có thể có của $n.$

Lời giải

Ta thấy mỗi lần đổi màu không quá $5$ ô nên số lần đổi màu phải ít nhất là $4.$Hơn nữa, ta cũng có thể đổi màu tất cả sang đen như hình bên dưới, các ô được đánh dấu là các ô được chọn trong các thao tác.

Mặt khác, với $n$ chẵn lớn hơn $4$, ta có thể chọn một trong các điểm trên hai lần và khi đó, màu của chúng sẽ đổi từ trắng sang đen, đen sang trắng, tức là không bị ảnh hưởng. Điều này có nghĩa là ta cũng có thể chuyển tất cả các ô sang màu đen như trường hợp $n=4.$ \medskip

Cuối cùng, ta sẽ chứng minh rằng $n$ lẻ không thỏa mãn đề bài.

Tô màu xanh các ô vuông như hình vẽ. Ta thấy rằng ở mỗi lần thao tác thì có số lẻ ô xanh bị thay đổi ($1$ hoặc $3$) nên sau mỗi lần thao tác, số lượng ô trắng – đen trong vùng màu xanh bị thay đổi một số đồng dư $2$ modulo $4.$

Ban đầu chênh lệch đó là $10$ và nếu muốn đổi tất cả sang màu đen thì chênh lệch đó là $-10$; tức là thay đổi $-20$, chia hết cho $4$. Điều này không thể xảy ra nên $n$ lẻ không thỏa mãn đề bài.

Vậy các giá trị $n$ cần tìm là $n$ chẵn và $n\ge 4.$

Bài 5: (JBMO 2008)

Lời giải

Cuối cùng, ta sẽ chứng minh rằng $n$ lẻ không thỏa mãn đề bài.

Vậy các giá trị $n$ cần tìm là $n$ chẵn và $n\ge 4.$

Bài 6:

(JBMO 2010)

Một hình chữ nhật $9\times 7$ được lát bởi hai loại gạch như hình bên dưới: chữ $L$ và hình vuông.

Tìm tất cả các giá trị có thể có của số lượng các viên gạch hình vuông đã được dùng.

Lời giải

Câu trả lời là $0$ hoặc $3.$

Gọi $x$ là số viên gạch chữ $L$ và $y$ là số viên gạch hình vuông $2\times 2.$ Đánh dấu chéo $20$ hình vuông của hình chữ nhật như sơ đồ bên dưới.

Rõ ràng mỗi viên gạch sẽ chứa không quá một dấu chéo. Suy ra $x+y\ge 20.$

Ngoài ra ta cũng có $3x+4y=63.$

Từ đó suy ra $y\le 3$ và $y$ chia hết cho $3$, dựa theo điều kiện thứ hai.

Do đó $y=0$ hoặc $y=3.$ Dưới đây là các cách lát thỏa mãn điều kiện đó.

Bài 7: (JBMO 2013)

Cho $n$ là một số nguyên dương. Có hai người chơi là Alice và Bob chơi một trò chơi như sau:

Alice chọn $n$ số thực, không nhất thiết phân biệt.
Alice viết tất cả các tổng theo cặp của tất cả các số lên giấy và đưa nó cho Bob (rõ ràng có tất cả $\frac{n(n-1)}{2}$ cặp và không nhất thiết phân biệt).
Bob sẽ thắng nếu như có thể tìm lại được $n$ số ban đầu được chọn bởi Alice.

Hỏi Bob có thể có cách chắc chắn thắng hay không với

$n=5?$
$n=6?$
$n=8?$

Lời giải

1) Câu trả lời là khẳng định.

Giả sử các số Alice đã chọn là $a\le b\le c\le d\le e$. Rõ ràng mỗi số xuất hiện trong các tổng đúng $4$ lần nên bằng cách cộng tất cả $10$ tổng và chia hết quả cho $4$, Bod sẽ thu được

$a+b+c+d+e.$

Trừ đi tổng lớn nhất và nhỏ nhất, Bob sẽ thu được số lớn thứ ba là $c.$ Tiếp tục trừ $c$ vào tổng lớn thứ nhì, chính là $c+e$ thì Bob thu được $e.$ Trừ $e$ vào tổng lớn nhất, Bob thu được $d$. Bằng cách tương tự, Bob sẽ tìm ra được các giá trị $a,b.$ \medskip

2) Câu trả lời là khẳng định. Giả sử các số Alice đã chọn là $a\le b\le c\le d\le e\le f.$ Tương tự trên, ta cũng tính được tổng $S$ các số của bộ. Trừ $S$ cho tổng lớn nhất và nhỏ nhất, ta thu được tổng $c+d.$ \medskip

Trừ $S$ cho tổng lớn nhì và tổng nhỏ nhất, ta được $c+e.$ Trừ $S$ cho tổng lớn nhất và tổng nhỏ nhì, ta được $b+d.$

Từ đây suy ra $a+c=S-(b+d)-(e+f)$, trong đó ta biết $e+f$ vì đó là tổng lớn nhất.

Lúc bấy giờ, Bob đã tìm được ba tổng $a+b,a+c,b+c$ nên sẽ tính được $T=a+b+c$ và dễ dàng tìm được $a,b,c.$ Tương tự, Bob có thể tìm được $d,e,f.$ \medskip

3) Câu trả lời là phủ định.

Ta thấy rằng có hai bộ tám số là $1,5,7,9,12,14,16,20$ và $2,4,6,10,11,15,17,19$ đều cho cùng $28$ tổng theo đôi một giống nhau nên chắc chắn rằng Bob không thể biết được bộ mà Alice đã chọn.

Bài 8: (JBMO 2014)

Với mỗi số nguyên dương $n$, hai người $A,B$ chơi một trò chơi như sau: Cho một đống có $s$ viên sỏi và hai người chơi thay phiên nhau chơi, $A$ đi trước. Ở mỗi lượt, người chơi được bốc hoặc $1$ viên sỏi, hoặc một số $p$ nguyên tố các viên sỏi, hoặc một bội của $n$ các viên sỏi. Người bốc được viên cuối cùng là chiến thắng. Giả sử hai người đều chơi với chiến thuật tối ưu, hỏi có bao nhiêu giá trị $s$ để người $B$ có chiến thuật thắng?

Lời giải

Ta gọi các giá trị $s$ để cho người $A$ có chiến thuật thắng là vị trí thắng và các vị trí còn lại là vị trí thua. Ta cần tìm số lượng vị trí thua.

Giả sử có $k$ vị trí thua thuộc tập hợp $$X=\{{{s}_{1}},{{s}_{2}},{{s}_{3}},\ldots ,{{s}_{k}}\}.$$

Trước hết, ta thấy rằng mỗi bội của $n$ là vị trí thắng (vì người $A$ có thể lấy tất cả các viên sỏi ở ngay lần đi đầu tiên). Khi đó, nếu có ${{s}_{i}}\equiv {{s}_{j}}(\bmod n)$ và ${{s}_{i}}>{{s}_{j}}$ thì ở lượt đi đầu tiên, $A$ bốc ${{s}_{i}}-{{s}_{j}}$ viên sỏi (vì số này chia hết cho $n$). Nhưng lúc đó, còn lại ${{s}_{j}}$ viên sỏi và đây là vị trí thua của $B$ nên sẽ là vị trí thắng của $A$, mâu thuẫn.

Do đó, tất cả các số trong $X$ đều không đồng dư với nhau theo modulo $n$ hay $k=\left| X \right|\le n-1.$ \medskip

Ta sẽ chứng minh rằng $k=n-1.$ Thật vậy,

Để có được điều đó, ta sẽ chỉ ra rằng ở mỗi lớp thặng dư khác $0$ của $n$, luôn có một vị trí thua bằng phản chứng. Giả sử rằng tồn tại $r\in \{1,2,3,\ldots ,n-1\}$ sao cho $mn+r$ là vị trí thắng với mỗi số nguyên dương $m.$ Gọi $u$ là vị trị thua lớn nhất (nếu $k>0$) hoặc $0$ (nếu $k=0$).

Đặt $s$ là bội chung nhỏ nhất của tất cả các số nguyên dương từ $2$ đến $u+n+1.$ Khi đó, tất cả các số $s+2,s+3,\ldots ,s+u+n+1$ đều là hợp số. \medskip

Xét số nguyên dương ${m}’$ thỏa mãn

$s+u+2\le {m}’n+r\le s+u+n+1$.

Để ${m}’n+r$ là vị trí thắng thì phải có số tự nhiên $p$ là $1$, là số nguyên tố hoặc là bội của $n$ sao cho hiệu ${m}’n+r-p$ sẽ là vị trí thua, là $0$ hoặc là một số nhỏ hơn hoặc bằng $u.$ Chú ý rằng

$$s+2\le {m}’n+r-u\le p\le {m}’n+r\le s+u+n+1$$

nên $p$ phải là hợp số, chứng tỏ $p$ chỉ có thể là bội của $n$ (theo giả thiết của đề bài). \medskip

Đặt $p=qn$ thì ${m}’n+r-q=({m}’-q)n+r$ cũng sẽ là một vị trí thắng khác; tuy nhiên, theo nguyên lý trò chơi thì không thể đi từ vị trí thằng này đến vị trí thắng khác được. Điều mâu thuẫn này cho thấy không thể xảy ra trường hợp toàn bộ các số dạng $mn+r$ là vị trí thắng. \medskip

Từ đây ta suy ra rằng có ít nhất $n-1$ vị trí thua nên từ các điều trên, ta thấy có đúng $n-1$ vị trí thua hay có $n-1$ vị trí mà người $B$ có chiến lược để thắng.

Bài 9: (JBMO 2015)

Một khối chữ $L$ bao gồm ba khối vuông ghép như một trong các hình bên dưới:

Cho trước một bảng $5\times 5$ bao gồm $25$ ô vuông đơn vị, một số nguyên dương $k\le 25$ và một số lượng tùy ý các khối chữ $L$ nêu trên. Hai người chơi $A,B$ cùng tham gia một trò chơi như sau: bắt đầu bởi $A$, hai người sẽ lần lượt đánh dấu các ô vuông của bảng cho đến khi nào tổng số ô được đánh dấu bởi họ là $k.$ \medskip

Ta gọi một cách đặt các khối chữ $L$ trên các ô vuông đơn vị còn lại chưa được đánh dấu là tốt nếu như nó không bị chồng lên nhau, đồng thời mỗi khối đặt lên đúng ba ô vuông như một trong các hình ở trên. $B$ sẽ thắng nếu như với mọi cách đặt tốt ở trên, luôn luôn tồn tại ít nhất ba ô vuông đơn vị chưa được đánh dấu trên bảng. \medskip

Xác định giá trị $k$ nhỏ nhất (nếu có tồn tại) để $B$ có chiến lược thắng.

Lời giải

Ta sẽ chứng minh rằng $A$ sẽ thắng nếu $k=1,2,3$ và $B$ thắng nếu $k=4.$ Suy ra giá trị nhỏ nhất của $k$ là $4.$ \medskip

1) Nếu $k=1$ thì người chơi $A$ sẽ đánh dấu ô ở góc trên bên trái và đặt các khối như bên dưới

Khi đó, rõ ràng $A$ thắng. \medskip

2) Nếu $k=2$ thì vẫn tương tự trên, $A$ đánh dấu vào ô ở góc trên bên trái. Khi đó, cho dù $B$ đánh dấu ô nào đi nữa thì $A$ cũng sẽ có cách đặt tương tự như trên, thiếu đi nhiều nhất là $2$ ô thuộc cùng khối vuông chữ $L$ với ô mà $B$ chọn. Điều này chứng tỏ $A$ vẫn thắng. \medskip

3) Nếu $k=3$ thì cũng tương tự, ở lượt sau, $A$ đánh dấu vào ô cùng khối chữ $L$ với ô mà $B$ đã đánh dấu. Khi đó, $A$ vẫn thắng. \medskip

4) Với $k=4$, ta sẽ chứng minh rằng $B$ sẽ luôn có chiến lược thắng cho dù $A$ đi thế nào đi nữa. Rõ ràng còn lại $21$ ô nên $A$ phải chọn cách đánh dấu sao cho có thể đặt được toàn bộ $7$ khối vuông chữ $L$ (vì nếu không thì sẽ còn lại ít nhất $3$ ô chưa được đặt). \medskip

Giả sử trong lượt đầu tiên, $A$ không chọn ô nào trong hàng cuối (vì nếu có thì ta xoay ngược bảng lại và lập luận tiếp một cách tương tự). Khi đó, $B$ sẽ chọn ô số $1$ như bên dưới.

Nếu trong lượt tiếp theo, $A$ không chọn ô nào trong các ô $2,3,4$ thì $B$ chọn ô số $3.$ Khi đó, rõ ràng ô số $2$ sẽ không thể đặt lên bởi bất cứ khối chữ $L$ nào và $B$ chiến thắng.
Nếu trong lượt tiếp theo, $A$ chọn ô số $2$ thì $B$ chọn ô số $5$, dẫn đến ô số $3$ không thể đặt lên bởi khối $L$ nào.
Nếu trong lượt tiếp theo, $A$ chọn một trong hai ô $3$ hoặc $4$ thì $B$ chọn ô còn lại, kết quả tương tự trên, ô số $2$ cũng sẽ không thể tiếp cận.

Vậy nói tóm lại, $k=4$ là giá trị nhỏ nhất cần phải tìm.

Bài 10: (JBMO 2016)

Một bảng kích thước $5\times 5$ được gọi là “tốt” nếu như mỗi ô của nó có chứa một đúng bốn giá trị phân biệt, và mỗi giá trị xuất hiện đúng một lần trong tất cả các bảng con $2\times 2$ của bảng đã cho. Tổng tất cả các số có trên bảng được gọi là “giá” của bảng. Với mỗi bộ bốn số thực, ta có thể xây dựng tất cả các bảng tốt và tính giá của nó. Tính số giá phân biệt lớn nhất có thể có.

Lời giải

Ta sẽ chứng minh rằng số giá phân biệt lớn nhất là $60.$ Ta có nhận xét sau: \medskip

Nhận xét: Trong mỗi bảng tốt, mỗi hàng chứa đúng hai số trong các số hoặc mỗi cột chứa đúng hai số trong các số. \medskip

Thật vậy, ta thấy mỗi hàng của bảng đều chứa ít nhất hai số (vì nếu chứa toàn bộ là một số thì mâu thuẫn với giả thiết). Khi đó, nếu toàn bộ các hàng đều chứa hai số thì nhận xét đúng. \medskip

Giả sử ngược lại là có hàng $R$ chứa ít nhất ba số trong bốn số của bảng là $x,y,z,t$. Khi đó, các số đó phải có nằm ở vị trí liên tiếp nào đó trên hàng, giả sử là $x,y,z$ liên tiếp. Theo giả thiết thì trong mỗi bảng $2\times 2$, ta đều có đủ bốn giá trị nên trong hàng phía trên và phía dưới của $R$ phải chứa $z,t,x$ theo đúng thứ tự đó, và tương tự là $x,y,z$. Ta có bảng như bên dưới

* & x & y & z & * \\

* & z & t & x & * \\

* & x & y & z & * \\

* & z & t & x & * \\

* & x & y & z & * \\

Điền thêm các ô còn lại, dễ thấy rằng các cột đều chứa đúng hai số. Nhận xét được chứng minh. \medskip

Không mất tính tổng quát, ta có thể giả sử mỗi hàng của bảng đều có đúng hai số (nếu không thì có thể xoay bảng lại). Nếu không xét hàng đầu tiên và cột đầu tiên, ta sẽ có bảng $4\times 4$ mà trong đó, mỗi số trong $x,y,z,t$ đều xuất hiện $4$ lần nên tổng các số trong bảng này là $4(x+y+z+t).$

Do đó, ta chỉ cần tính xem có bao nhiêu cách khác nhau để đặt các số lên hàng đầu tiên ${{R}_{1}}$ và cột đầu tiên ${{C}_{1}}.$ Gọi $a,b,c,d$ là số lần xuất hiện của các số $x,y,z,t$ thì khi đó, tổng tất cả các số của bảng sẽ là

$$4(x+y+z+t)+xa+yb+zc+td.$$

Nếu hàng $1-3-5$ chứa các số $x,y$ với $x$ ở vị trí đầu tiên của hàng $1$ thì các hàng $2-4$ sẽ chứa các số $z,t$ (theo giả sử ở trên). Khi đó, ta có

$a+b=7$ và $a\ge 3,b\ge 2$,

$c+d=2$ và $c\ge d.$ \medskip

Khi đó $(a,b)=(5,2),(4,3)$ tương ứng với $(c,d)=(2,0),(1,1).$ Suy ra $(a,b,c,d)$ sẽ nhận các bộ là $$(5,2,2,0),(5,2,1,1),(4,3,2,0),(4,3,1,1).$$

Tổng số hoán vị của các bộ là $$\frac{4!}{2!}+\frac{4!}{2!}+4!+\frac{4!}{2!}=60.$$

Bằng cách chọn $x={{10}^{3}},y={{10}^{2}},z=10,t=1$ thì dễ thấy rằng các tổng tương ứng với mỗi hoán vị của bộ số trên đều phân biệt, nghĩa là giá của các bảng đều phân biệt. Vậy số lượng giá tối đa là $60.$

Dưới đây là một số bài toán để bạn đọc tự rèn luyện thêm:

Bài 11. (JBMO 2019) Cho bảng ô vuông $5\times 100$ được chia thành $500$ ô vuông con đơn vị, trong đó có $n$ được tô đen và còn lại tô trắng. Hai ô vuông kề nhau nếu chúng có cạnh chung. Biết rằng mỗi ô vuông đơn vị sẽ có tối đa hai ô vuông đen kề với nó. Tìm giá trị lớn nhất của $n.$

Bài 12. (JBMO 2020) Alice và Bob chơi một trò chơi như sau: Alice chọn một tập hợp $A={1,2,\ldots ,n}$ với $n\ge 2.$ Sau đó, bắt đầu bằng Bob, họ sẽ thay phiên chọn một số trong tập $A$ sao cho: đầu tiên Bob chọn bất kỳ số nào, sau đó, các số được chọn phải khác các số đã chọn và hơn kém đúng $1$ đơn vị so với số nào đó đã chọn. Trò chơi kết thúc khi tất cả các số trong $A$ đã được chọn. Alice thắng nếu tổng các số bạn ấy chọn được là hợp số. Ngược lại thì Bob thắng. Hỏi ai là người có chiến lược thắng?

Chỉnh hợp – Hoán vị – Tổ hợp

Chỉnh hợp

Mỗi cách sắp xếp $k$ phần tử (phân biệt) vào $n$ vị trí phân biệt ($n\geq k$) được gọi là một chỉnh hợp chập $k$ của $n$.

Tính chất. Số chỉnh hợp chập $k$ của $n$ là $$A_n^k = \dfrac{(n!)}{(n-k)!}$$

Hoán vị.

Mỗi chỉnh hợp chập $n$ của $n$ được gọi là một hoán vị, hay mỗi cách sắp xếp $n$ phần tử vào $n$ vị trí được gọi là một hoán vị của $n$ phần tử. Số hoán vị của $n$ phần tử là $P_n = n!$.

Định nghĩa khác. Cho tập $A = {1, 2, \cdots, n}$. Mỗi song ánh từ $A$ vào $A$ được gọi là một hoán vị.

Ví dụ 1. Có 8 bạn nam và 2 bạn nữ được xếp thành một hàng dài. Hỏi có bao nhiêu cách xếp thỏa:

a) Xếp bất kì.
b) 8 bạn nam kề nhau,2 bạn nữ kề nhau.
c) Các bạn nam giữa hai bạn nữ.

Ví dụ 2. Có 8 bạn nam và 4 bạn nữ. Có bao nhiêu cách sắp xếp các bạn này thành một hàng sao cho không có hai bạn nữ nào đứng kề nhau.

Ví dụ 3. Cho tập $A = {0, 1, 2, 3, 4, 5}$. Từ $A$ có thể lập được bao nhiêu số

a) Là số chẵn có 4 chữ số khác nhau.
b) Là số lẻ có 5 chữ số khác nhau và chia hết cho 3.

Tổ hợp. Cho tập hợp $A$ có $n$ phần tử. Một tập hợp con có $k$ phần tử của $A$ được gọi là một tổ hợp chập $k$ của $n$ phần tử.

Tính chất. Số tổ hợp có chập $k$ của $n$ là: [C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{(n-k)! k!}]

Ví dụ 4. Đội văn nghệ của trường gồm 4 bạn học sinh lớp 10, 5 học sinh lớp 11, 4 học sinh lớp 12.

a) Có bao nhiêu cách chọn ra hai bạn hát song ca?
b) Có bao nhiêu cách chọn ra 3 bạn hát tam ca mà mỗi khối có một học sinh?
c) Có bao nhiêu cách chọn ra một đội múa gồm 5 bạn trong đó có ít nhất 2 học sinh lớp 11.

Ví dụ 5. Cho tập $A = {1, 2, 3, 4, 5}, B = {a, b, c, d, e, }$, $C = {x, y, z}$.

a) Có bao nhiêu song ánh từ $A$ vào $B$.
b) Có bao nhiêu ánh xạ từ $A$ vào $C$? Có bao nhiêu đơn ánh từ $C$ vào $A$.
c) Có bao nhiêu đơn ánh từ $C$ và $A$ sao cho $f(x) + f(y) + f(z)$ là số chẵn.

Bài tập rèn luyện

Bài 1. Cho tập $A = {0, 1, 2, 3, 4,5,6, a, b, c, d}$

a) Có bao nhiêu hoán vị của $A$.
b) Có bao nhiêu hoán vị của $A$ mà các chữ số đứng kề nhau.
c) Có bao nhiêu hoán vị của $A$ mà không có chữ cái nào đứng kề nhau?

Bài 2. Cho tập $A = {0, 1, 2, 3, 4, 5, 6 }$

a)Từ A có thể lập được bao nhiêu số có 5 chữ số khác nhau.
b) Có bao nhiêu hoán vị của A mà hai chữ số lẻ không đứng kề nhau.
c) Từ A có thể lập được bao nhiêu số có 4 chữ số mà chữ số đứng sau lớn hơn chữ số đứng liền trước.
d) Từ A có thể lập được bao nhiêu số có 3 chữ số chia hết cho 3.

Bài 3. Xếp $ m $ bạn nam và $ n $ bạn nữ thành 1 hàng, với $m,n\in \mathbb{N}$. Hỏi có bao nhiêu cách xếp nếu:

a) Xếp tùy ý;
b) Không có bạn nam nào đứng cạnh nhau $\left( m\le n+1 \right);$
c) $ n $ bạn nữ đứng liền kề nhau;
d) Một bạn nam A và một bạn nữ B đứng cạnh nhau.

Bài 4. Tính: $1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdot \cdot \cdot +n\cdot n!,n\in \mathbb{N}.$

Bài 5. Tính: $\dfrac{1}{\left( 1+1 \right)!}+\dfrac{2}{\left( 2+1 \right)!}+\cdot \cdot \cdot +\dfrac{n}{\left( n+1 \right)!}$ với $n\in \mathbb{N}.$

Bài 6. Cho $n,r\in \mathbb{N}$ với $r\le n.$ Chứng minh rằng:

a) $A_{n}^{r}=nA_{n-1}^{r-1};$
b) $A_{n}^{r}=\left( n-r+1 \right)A_{n}^{r-1};$
c) $A_{n}^{r}=\dfrac{n}{n-r}A_{n}^{r-1},$ với $r<n;$
d) $A_{n+1}^{r}=A_{n}^{r}+rA_{n}^{r-1};$
e) $A_{n+1}^{r}=r!+r\left( A_{n}^{r-1}+A_{n-1}^{r-1}+…+A_{r}^{r-1} \right).$

Bài 7. Một nhóm có 15 hóc sinh, trong đó có 5 bạn nữ. Hỏi có bao nhiêu cách chọn 9 học sinh sao cho có đúng 3 học sinh nữ:

a) để thành lập một hội đồng.
b) để thành lập một hội đồng với 9 vị trí khác nhau.

Bài 8. Có 10 cái ghế được xếp thành một hàng. 7 học sinh được xếp vào 7 cái ghế sao cho không có 2 học sinh nào ngồi chung một cái ghế. Hỏi có bao nhiêu cách xếp sao cho không có 2 cái ghế trống nào liền nhau.

Bài 9. Có 8 cái hộp được xếp thành hàng. Hỏi có bao nhiêu cách đặt 5 viên bi khác nhau vào các hộp nếu mỗi hộp chứa nhiều nhất 1 viên bi và không có hai hộp không chứa bi nào đứng cạnh nhau?

Bài 10. Xếp một nhóm có 20 học sinh, trong đó có 3 bạn nữ là: A, B, C và 4 bạn nam: X,Y,Z,T thành 2 hàng, mỗi hàng 10 học sinh. Hỏi có bao nhiêu cách xếp sao cho 3 bạn nữ luôn ở hàng trước, còn 4 bạn nam ở hàng phía sau.

Bài 11. Hỏi có bao nhiêu cách xếp 7 bạn nam và 2 bạn nữa thành một hàng sao cho các bạn gái cách nhau bởi đúng 3 bạn nam?

Bài 12. Tìm số $(m+n)$-nhị phân là một dãy chữ số với $ m $ số 0 và $ n $ số 1 sao cho không có 2 số 1 nào đứng kề nhau, khi $n\le m+1.$

Bài 13. Lớp A có 10 bạn nữ và 15 bạn nam và lớp B có 4 nữ và 10 nam. Một hội đồng gồm 7 thành viên được chọn từ 2 lớp đó. Hỏi có bao nhiêu cách chọn các thành viên sao cho có đúng 4 bạn của lớp B và có đúng 5 bạn nam.

Bài 14. Trong mỗi trường hợp sau, tìm số tuyến đường ngắn nhất từ $ O $ đến $ P $ trong sơ đồ được cho dưới đây:
a) Tuyến đường phải đi qua $ A $.
b) Tuyến đường phải qua đoạn $AB$.
c) Tuyến đường phải đi qua $A$ và $C$.
d) Đoạn đường $AB$ bị đóng.

Bài 15. Tìm số cách chọn một nhóm gồm $ 2k $ người từ $n$ cặp đôi, với $k,n\in \mathbb{N}$ và $2k\le n,$ trong mỗi trường hợp sau đây:

a) Có $k$ cặp đôi trong nhóm đó.
b) Không có cặp đôi nào trong nhóm đó.
c) Có ít nhất một cặp đôi được chọn trong nhóm.

d) Có đúng 2 cặp đôi được chọn trong nhóm đó.

Bài 16. Cho một đa giác có 10 đỉnh.

a) Có bao nhiêu đường chéo.
b) Có bao nhiêu tam giác có 3 đỉnh là 3 đỉnh thuộc đa giác.
c) Có bao nhiêu tam giác có đúng 1 cạnh trùng với cạnh của đa giác.
d) Có bao nhiêu tam giác không có cạnh nào trùng với cạnh của đa giác.
e) Biết rằng không có 3 đường chéo nào đồng quy. Tìm số giao điểm của các đường chéo.

Bài 17. Cho đa giác đều có 100 cạnh. Hỏi có bao nhiêu hình chữ nhật tạo ra từ các đỉnh của đa giác trên.

Bài 18. Cho A là tập hợp các số nguyên dương từ 1 đến 100. Hỏi có bao nhiêu tập con có 3 phần tử của A thỏa:

a) Tổng các số chia hết cho 3
b) Tổng các số chia hết cho 4.

Bài 19. Chung kết cuộc thi tiếng hát học đường có 3 bạn vào chung kết, mỗi bạn hát 2 bài khác nhau. Hỏi có bao nhiêu cách sắp xếp chương trình sao cho không có ai hát liên tiếp.

Bài 20. Có bao nhiêu cách chọn ra 3 số từ tập $A = {1, 2, \cdots, 100}$ sao cho một số là trung bình cộng của hai số còn lại.

Toán Việt

Chia sẻ và học hỏi

Tag Archives: ToHop

Suy luận phản chứng (phần 2)

Giải toán như … viết văn

Bất biến và đơn biến – Phần 1

Bất biến và nửa bất biến – Phần 2

Giải bài toán bằng đại lượng cực biên – Phần 2

Trắc nghiệm phép đếm

Phương pháp chứng minh phản chứng (P2)

Phương pháp ánh xạ trong các bài toán tổ hợp

Các bài toán tổ hợp trong kì thi Junior Bankan – P1

Chỉnh hợp – Hoán vị – Tổ hợp