Tag Archives: Phuongphapchungminh

Suy luận phản chứng

Leave a reply

Bài viết này dành cho các em lớp 5, 6, 7

Các nhà toán học trong quá khứ đã làm việc chăm chỉ để khám phá bản chất của các chứng minh, và một loạt các kỹ thuật chứng minh đã được phát triển qua nhiều thế kỷ. Hôm nay, chúng tôi sẽ giới thiệu một phương pháp chứng minh quan trọng được gọi là bằng chứng do mâu thuẫn.

Ta thường gặp bài toán kiểu: Có A là đúng và cần suy ra X cũng đúng, trong một số trường hợp ta suy luận trực tiếp như sau: có A đúng thì có C đúng, có C đúng thì có D đúng, …, rồi suy ra X đúng, ở đây ta dùng A làm giả thiết để cho các suy luận sau. Tuy vậy một số tình huống ta không sử dụng được giả thiết A đúng, ta có thể dùng kĩ thuật suy luận phản chứng như sau: Giả sử X sai, tức là ta chấp nhận một giả thiết mới là X sai, từ giả thiết này ta dẫn đến một điều gì đó vô lí, hoặc dẫn đến A sai; khi đó điều giả sử đó là không đúng, tức là ta có điều cần chứng minh. Thế mạnh của suy luận phản chứng là mình có thêm một giả thiết để giúp trong việc suy luận dễ dàng hơn.

Ví dụ 1. Có tồn tại hay không số nguyên lẻ lớn nhất?

Lời giải Giả sử tồn tại số nguyên lẻ lớn nhất là $m$.

khi đó $m+2$ cũng là số lẻ và $m+2 > m$ nên mâu thuẫn vì theo giả sử thì $m$ là lớn nhất.

Vậy không có số nguyên lẻ lớn nhất.

Ví dụ 2. 5 cầu thủ bóng đá đã cùng nhau ghi được 14 bàn thắng, với mỗi cầu thủ ghi ít nhất 1 bàn. Chứng minh rằng ít nhất 2 trong số họ ghi được số bàn thắng như nhau. số bàn thắng.

Lời giải. Giả sử không có ai ghi số bàn thắng bằng nhau.

Khi đó người ghi ít nhất là 1 bàn, người kế tiếp ghi ít nhất là 2 bàn, người thứ 3 ghi ít nhất 3 bàn, cứ như thế người ghi nhiều nhất có số bàn thắng ít nhất là 5 bàn, khi đó tổng số bàn thắng của 5 người ít nhất là $1+2+3+4+5 = 15$ (mâu thuẫn).

Vậy có hai người ghi số bàn thắng bằng nhau.

Ví dụ 3. Quốc hội của một quốc gia được thành lập bởi các nghị sĩ đại diện từ 8 tỉnh. Năm mươi trong số các nghị sĩ này quyết định thành lập một ủy ban. Chứng minh rằng ủy ban này sẽ bao gồm 8 người từ cùng một tỉnh hoặc người từ tất cả 8 tỉnh.

Lời giải. Giả sử ủy bản mỗi tỉnh không có quá 7 người và chỉ đến từ 7 tỉnh trở lại, khi đó số thành viên ủy ban là không qua 49 người, mâu thuẫn.

Vậy trong ủy ban sẽ có một tỉnh có 8 người hoặc thành viên đến từ cả 8 tỉnh.

Ví dụ 4. Viết 10 số từ 0 đến 9 trên một vòng tròn, mỗi số viết đúng một lần.

a) Có tồn tại hay không cách viết sao cho tổng hai số liên tiếp không nhỏ hơn 9?
b) Có tồn tại hay không cách viết sau cho tổng 3 số liên tiếp lớn hơn 12?
Lời giải.

a) Giả sử tồn tại cách viết sao cho tổng hai số liên tiếp không nhỏ hơn 9, xét số 0 và hai số kề với 0 là $a, b$ ta có $0+a \geq 9, 0 + b \geq 9$, suy ra $a=b=9$ mâu thuẫn, vì mỗi số viết đúng 1 lần.

b) Giả sử tồn tại cách viết thỏa đề bài. Tổn các số là 45, bỏ số 9, và xếp 9 số còn lại làm ba nhóm, mỗi nhóm 3 số liên tiếp, khi đó tổng của chúng lớn hơn 36, tuy vậy ta thấy 9 số đó là $0, 1,2, \cdots 8$ tổng là 36, đây là điều mâu thuẫn.

Vậy không cách ghi thỏa đề bài.

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

Bài 1. Chứng minh rằng khi cho $n+1$ con thỏ vào $n$ cái chuồng thì có chuồng chứa ít nhất 2 con thỏ.

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

Bài 3. Tích của 22 số nguyên bằng 1. Chứng minh rằng tổng của chúng không thể bằng 0.

Bài 4. Có thể chia tập $X = \{1, 2, …, 2022\}$ thành các tập rời nhau sao cho mỗi tập có ít nhất 3 phần tử và phần tử lớn nhất bằng tổng các phần tử còn lại?

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. 

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

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

Bài viết dựa vào bài giảng của NCS. Vương Trung Dũng (trường PTNK-ĐHQG) trong lớp chuyên đề 10 toán tại Star Education.

 

Ánh xạ là một khái niệm khó và quan trọng trong toán học, có vai trò trong hầu hết các lĩnh vực toán học. Trong bài giảng này ta xét ứng dụng của ánh xạ trong các bài toán tổ hợp.

Ánh xạ và một số tính chất

Định nghĩa. Cho hai tập hợp $X$ và $Y$ khác rỗng. Một ánh xạ $f$ từ tập $X$ đến tập $Y$ là một quy tắc đặt tương ứng mỗi phần tử $x$ của $X$ với một và chỉ một phần tử $y$ của $Y$, kí hiệu là $y = f(x)$.

Kí hiệu $f: X \longrightarrow Y$.

$f(x) = y$.

Các khái niệm: Cho ánh xạ $f: X \longrightarrow Y$.

  • $y = f(x)$ được gọi là ảnh của $x$.
  • $f(X) = \{f(x)|x \in X\}$ tập ảnh của $f$.
  • $y \in Y$ thì $f^-1(y) = \{x\in X|f(x) = y\}$ được gọi là tạo ảnh của $y$.

Đơn ánh, toàn ánh, song ánh

  1. Ánh xạ $f: X \longrightarrow Y$ được gọi là đơn ánh nếu với $a,b \in X$ mà $a \ne b$ thì $f(a) \ne f(b)$. Nói một cách khác ánh xạ $f$ là một đơn ánh nếu và chỉ nếu với $a, b \in X$ mà $f(a)=f(b)$ thì suy ra $a=b.$
  2. Ánh xạ $f:X \longrightarrow Y$ được gọi là toàn ánh nếu với mỗi phần tử $y \in Y$ đều tồn tại một phần tử $x \in X$ sao cho $f(x)=y$. Như vậy $f$ là toàn ánh nếu và chỉ nếu $f(X)=Y$.
  3. Ánh xạ $f: X \longrightarrow Y$ được gọi là song ánh giữa $X$ và $Y$ nếu và chỉ nếu nó vừa là đơn ánh và vừa là toàn ánh. Như vậy $f$ là song ánh nếu với mỗi $y \in Y$ tồn tại duy nhất một phần tử $x \in X$ sao cho $y=f(x).$

Ánh xạ và tập hợp

Cho $A = { 1, 2,\cdots, n }$. $X$ là tập khác rỗng. Nếu có một song ánh từ tập $X$ đến $A$ thì ta nói $X$ có $n$ phần tử và kí hiệu $|X| = n$.

Nếu không tồn tại song ánh thì ta nói $X$ có vô hạn phần tử.

  • Nếu tồn tại một song ánh từ $X$ vào tập các số tự nhiên, ta nói $X$ có lực lượng đếm được, ngược lại thì ta nó $X$ có lực lượng không đếm được.
  • Các tập số tự nhiên, số nguyên và hữu tỷ là các tập có lực lượng đếm được.

Định lý 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|.$

Ánh xạ và các bài toán đếm, đẳng thức tổ hợp.

Ví dụ 1. Cho tập $X_n = {1, 2, \cdots, n}$, gọi $P(X_n)$ là tập các tập con của $X_n$, và $S_n$ là tập các dãy nhị phân có độ dài $n$. Tìm một song ánh từ $P(X_n)$ vào $S_n$, suy ra số tập con của $X_n$.

Gợi ý

Định nghĩa một ánh xạ $f: P(X_n) \longrightarrow S_n$ như sau:
Với mỗi $S \in P(X_n)$ (tức là $S \subset X_n$) ta đặt $$ f(S)=y_1y_2 \dots y_n$$
trong đó
$$y_i=\begin{cases}
1, y_i \in S&\\
0, y_i \notin S.&
\end{cases}
$$
Ví dụ , nếu $X=\{1; 2; 3; 4; 5\}, S_1=\{4\}, S_2=\{2; 3; 5\}$ thì $f(S_1)=00010, f(S_2)=01101, f(\emptyset)=00000, f(X)=11111$ .
Dễ dàng kiểm tra đây là một song ánh từ $P(X)$ vào $Y$.
Do đó theo nguyên lý song ánh ta có $|P(X)|=|Y|=2^n$.

Ví dụ 2. Hãy tính trung bình cộng của tất cả các số N gồm 2014 chữ số thỏa mãn N chia hết cho 9 và các chữ số của N được lập từ $X={1,2,…,8}$

Gợi ý

Gọi M là tập các số thỏa yêu cầu đề bài.

Ta xây dựng một ánh xạ đi từ M đến M như sau: Với mỗi $N=\overline{a_1a_2…a_{2014}} \in M$ dặt $f(N)=\overline{b_1,b_2,…,b_{2014}}$ với $b_i=9-a_i$ với mọi $i=1,2,…,2014$. Vì $N+f(N)=99…9$ (2014 số 9) chia hết cho 9 và N chia hết cho 9 nên suy ra $f(N)$ cũng chia hết cho 9. Do đó $f$ là một ánh xạ đi từ M vào M. Hơn nữa dễ thấy $f$ là một song ánh. Từ đó suy ra $$ 2\sum_{N \in M}N=\sum_{N \in M}(N+f(N))=|M|.99…9 .$$ Vậy trung bình cộng của các số trong M là $99…9:2.$

Ví dụ 3. Cho tập S gồm tất cả các số nguyên dương trong đoạn $[1,2,…,2002]$. Gọi T là tập hợp tất cả các tập con khác rỗng của S. Với mỗi X thuộc T ký hiệu m(X) là trung bình cộng các phần tử thuộc X. Tính $$ m=\frac{\sum_{X \in T}m(X)}{|T|}. $$

Gợi ý

Xây dựng song ánh $f: T \longrightarrow T$ như sau: với mọi $X \in T $ đặt tương ứng $f(X)=\{2003-x: x \in X\}$.\\
Khi đó $m(X)+m(f(X))=2003$. Do đó $$2 \sum m(X)=\sum (m(X)+m( f(X)))=|T|.2003 \Rightarrow m=\dfrac{\sum m(X)}{|T|}=\dfrac{2003}{2}$$

Ví dụ 4.  Cho $X={1,2,…,n}$. Có bao nhiêu tập con $k$ phần tử của X sao cho trong mỗi tập con không chứa 2 số nguyên liên tiếp.

Gợi ý

Gọi A là tập tất cả các tập con $k $ phần tử của X mà trong mỗi tập không chứa 2 số nguyên liên tiếp và B là tập tất cả các tập con của tập $Y=\{1,2,…, n-(k-1) \}$. Ta xây dựng song ánh từ A đến B như sau: Lấy $S=\{s_1,s_2,…,s_k \} \in A$ (không mất tổng quát có thể giả sử $s_1<s_2<…<s_k$) đặt tương ứng với $f(S)=\{s_1, s_2-1, s_3-2,…, s_k-(k-1) \}$. Dễ chứng minh đây là một song ánh. Từ đó có $C^k_{n-k+1}$ tập thoả yêu cầu đề bài.

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

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)$.

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 \textit{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)$.

Bài 3. 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$.

Bài 4. 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$.

Bài 5. Cho các số tự nhiên $k, n, m$ thỏa điều kiện $1<k \le n, m>1$. Hỏi có bao nhiêu chỉnh hợp chập $k: (a_1,a_2,…,a_k)$ của $n$ số tự nhiên đầu tiên mà mỗi chỉnh hợp đều thỏa mãn ít nhất một trong hai điều kiện sau:

i) Tồn tại $i, j \in {1,2,…,k}$ sao cho $i < j$ và $a_i>a_j$.

ii) Tồn tại $i \in {1,2,…,k}$ sao cho $a_i-i$ không chia hết cho $m$.

Bài 6. Cho các số nguyên dương $n, k, p$ với $k \ge 2$ và $k(p+1) \le n.$ Cho $n$ điểm phân biệt cùng nằm trên một đường tròn. Tô tất cả $n$ điểm đó bởi hai màu xanh, đỏ (mỗi điểm được tô bởi một màu) sao cho có đúng $k$ điểm được tô bởi màu xanh và trên mỗi cung tròn mà hai đầu mút là hai điểm màu xanh liên tiếp (tính theo chiều quay kim đồng hồ) đều có ít nhất $p$ điểm được tô màu đỏ. Hỏi có tất cả bao nhiêu cách tô khác nhau?

Bài 7. 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$.

Bài 8. Trong một hội nghị có $n$ nhà toán học. Biết rằng nếu hai nhà toán học nào đó quen nhau thì họ không quen chung thêm một người nào nữa, còn nếu hai nhà toán học này không quen nhau thì họ quen chung với đúng hai nhà toán học khác nữa. Chứng minh rằng $8n-7$ là số chính phương.

Bài 9. Trong một trại hè toán học có 40 học sinh. Biết rằng cứ 19 học sinh bất kỳ thì đều viết thư hỏi bài một học sinh khác (Nếu học sinh A viết thư hỏi bài học sinh B thì không nhất thiết học sinh B phải viết thư hỏi bài học sinh A và dĩ nhiên A cũng không viết thư hỏi chính mình). Chứng minh rằng trong trại hè này tồn tại một tập $T_0$ gồm 20 học sinh sao cho với mỗi $P \in T_0$ thì 19 người còn lại không đồng thời viết thư hỏi bài P.

Bài 10. Gọi M là số số nguyên dương trong hệ thập phân có $2n$ chữ số trong đó có $n$ chữ số 1 và $n$ chữ số 2. Gọi N là số số nguyên dương có $n$ chữ số trong hệ thập phân trong đó chỉ có các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh $|M|=|N|.$

(Hết phần 1)