TÍNH CHẴN LẺ TRONG BÀI TOÁN TỔ HỢP

Tính chẵn lẻ là một trong các bất biến quan trọng nhất trong một số tình huống tổ hợp. Đó là một ý tưởng đơn giản nhưng vô cùng hiệu quả. Tính chẵn lẻ là việc xét đồng dư theo modulo 2, một cách phức tạp hơn ta có thể nghĩ đến một lớp đồng dư theo modulo là một số tự nhiên tùy ý như một bất biến trong một số bài toán.
 VD1: Có 2015 bánh răng được xếp trên một mặt phẳng kề nhau tạo thành một vòng kín. Hỏi các bánh răng có thể quay cùng lúc hay không?
Lời giải: Câu trả lời là không. Mấu chốt ở bài này là việc phát hiện ra hai bánh răng kề nhau luôn quay ngược nhau. Giả sử bánh răng thứ nhất quay theo chiều dương kéo theo bánh thứ hai quay chiều âm, bánh thứ ba quay chiều dương... Như vậy bánh có số thứ tự lẻ quay chiều dương còn bánh có thứ tự chẵn quay chiều âm. Do đó bánh số 1 và số thứ 2015 cùng quay chiều dương. Vô lý. Ý tưởng chính của bài toán trên là sự xen kẽ chiều quay của các bánh răng. Tìm đối tượng xen kẽ cũng là hướng đi đầu tiên của các bài toán sau.
VD2:Trong một bàn cờ vua , một quân mã bắt đầu đi từ vị trí a1 và trở lại đó sau một số bước đi. Chứng minh số bước đi vừa thực hiện là một số chẵn.
Lời giải: Vị trí ban đầu của con mã là màu đen. Sau bước đi thứ nhất nó đến ô màu trắng, sau bước thứ hai nó đến ô màu đen.... Như vậy sau lẻ bước nó đến ô trắng và sau chẵn bước nó đến ô đen. Suy ra đpcm.
 VD3: Một đường gấp khúc khép kín được tạo bởi 11 đoạn thẳng nằm trên một mặt phẳng. Tồn tại hay không một đường thẳng d không đi qua bất kỳ đầu mút nào của các đoạn thẳng trên và cắt tất cả 11 đoạn thẳng đó.
Lời giải:
Gọi $(P_1), (P_2)$ là hai nửa mặt phẳng có bờ là đt d. Kí hiệu đường gấp khúc trên là $A_1A_2A_3...A_{11}A_1$ . Giả sử $A_1$ thuộc $(P_1)$ thì $A_2$ thuộc $(P_2)$, $A_3$ thuộc $(P_1)$,...,$A_{11}$ thuộc $(P_1)$. Nhưng khi đó $A_1$ và $A_{11}$ cùng thuộc $(P_1)$ nên d không thể cắt đoạn $A_1A_{11 }$điều này trái với giả thiết nên không thể tồn tại đường thẳng d thỏa mãn.
VD4 Ba quả bóng hockey A, B, C nằm trên một sân chơi. Một người đánh một trong ba quả đó sao cho nó đi qua giữa hai quả còn lại. Anh ta làm thể 25 lần. Liệu anh ta có thể đưa ba quả bóng trở về vị trí ban đầu hay không?
Lời giải:

Giả sử ban đầu ba quả bóng được sắp thứ tự theo chiều dương. Sau mỗi lượt chơi thì thứ tự của chúng thay đổi từ dương sang âm và ngược lại. Do vậy sau lượt đánh thứ nhất thứ tự của chúng theo chiều âm, sau lượt thứ hai lại đổi thành chiều dương,...Sau 25 lượt thì thứ tự của 3 quả bóng đó là chiều âm, do đó anh ta không thể đưa chúng về vị trí ban đầu.
VD5: Có hay không một đường gấp khúc khép kín gồm 9 đoạn thẳng sao cho mỗi đoạn cắt duy nhất một trong các đoạn còn lại?
Lời giải:
Nếu tồn tại đường gấp khúc đó thì tập hợp các đoạn thẳng trên có thể chia thành từng cặp các đoạn thẳng giao nhau. Như vậy tổng số đoạn thẳng phải là số chẵn.
Nhận xét: Điểm mấu chốt của ví dụ trên là nếu một nhóm các đối tượng có thể chia thành từng cặp thì số các đối tượng là một số chẵn. Sau đây là một số ví dụ tương tự.
VD6: Có thể chia một đa giác lồi 13 cạnh thành các hình bình hành được không?
Lời giải:
Giả sử thực hiện được công việc trên. Khi đó cạnh A1A2 phải thuộc một hình bình hành A1PNM trong đó A1P thuộc A1A2. Tiếp đó tồn tại hình bình hành RSPQ trong đó P,Q thuộc MN... Quá trình này cứ tiếp tục đến khi tồn tại một hình bình hành có cạnh song song với A1 A2 và thuộc một cạnh AmAm+1 nào đó và cạnh Am Am+1 tương ứng với A1A2 là duy nhất. Như vậy các cạnh của đa giác được chia thành các cặp nên số cạnh phải là số chẵn . Vô lý. Tương tự ta giải quyết các bài toán sau nhờ kỹ thuật “ghép cặp”
VD7: 25 quân cờ được đặt trên bàn cờ 25x25 sao cho mỗi quân cờ đối xứng với một quân cờ khác qua một đường chéo. Chứng minh có ít nhất một quân cờ được đặt trên một đường chéo.
VD8: Cho một bảng 15x15 ta viết các số từ 1 đến 15 sao cho hai ô đối xứng với nhau qua một trong hai đường chéo chính thì chứa hai số bằng nhau và không có số nào trong cùng một hàng hoặc một cột bằng nhau. Chứng tỏ rằng không có hai số nào trên đường chéo chính bằng nhau.
VD9: Hình vuông “kỳ diệu” là một bảng vuông 6x6 với mỗi một con số ở mỗi ô sao cho tổng các số ở mỗi cột, mỗi hàng và hai đường chéo bằng nhau . Có thể lập ra một hình vuông “kỳ diệu” từ 36 số nguyên tố đầu tiên không?
Lời giải:
Không . Vì khi đó tổng các số thuộc hình vuông là một số chẵn trong khi đó tổng của 36 số nguyên tố đầu tiên lại là số lẻ.
VD10: Các số từ 1 đến 10 được viết trên bảng theo một hàng ngang theo một thứ tự bất kỳ. Liệu có thể chèn vào giữa tất cả hai số kề nhau một cách tùy ý dấu “+” hoặc dấu “-” sao cho kết quả cuối cùng nhận được là số 0 hay không?
Lời giải: Giả sử ban đầu các dấu gồm toàn dấu “+” sau đó ta thay một số dấu cộng bằng dấu trừ. Bất biến ở đây là tính chẵn lẻ của tổng 10 số đó không đổi. Nhưng tổng các số từ 1 đến 10 là số lẻ nên sau hữu hạn bước không thể đưa về tình huống đề bài yêu cầu.
VD11: Một con châu chấu nhảy trên một đường thẳng. Bước đầu tiên của nó dài 1 cm, bước thứ hai dài 2cm và cứ thế, mỗi bước nó có thể nhảy về bên trái hoặc bên phải. Hỏi sau 2015 bước nó có thể trở về vị trí ban đầu hay không ?
Câu trả lời là không.
VD 12: Trên bảng có các số 1;2;3;...;2013. Một học sinh xóa hai số bất kỳ và thay bằng giá trị tuyệt đối của hiệu hai số đó. Sau hữu hạn bước chỉ còn một số trên bảng. Số này có thể abừng 0 được không?
Lời giải: Ta có (a + b) - |a - b| là số chẵn với hai số tự nhiên a, b bất kỳ. Như vậy tổng cac số sau mỗi bước luôn cùng tính chẵn lẻ. Do đó số cuối cùng phải là số lẻ vì tổng các số ban đầu là lẻ.
VD 13:
Có 45 điểm cùng nằm trên một đường thẳng AB, tất cả đều nằm ngoài đoạn AB. Chứng minh tổng khoảng cách tổng các khoảng cách từ các điểm này tới A khác tổng các khoảng cách từ các điểm đó tới B.
Lời giải:
Nhận thấy hiệu hai tổng khoảng cách đó luôn bằng số lẻ lần độ dài đoạn thẳng AB nên ta có đpcm.

Bản chất của bất biến xét theo tính chẵn lẻ là xét theo modul 2. Ta có thể tổng quát khi thay 2 bởi một số tự nhiên khác.  
VD14: Cho 1000 số từ 1 đến một 1000 được viết theo một hàng ngang trên bảng. Mỗi lần ta thay một hoặc vài số trên bảng bởi tổng các chữ số của nó. Hỏi dãy số cuối cùng thu được có nhiều số 1 hơn hay nhiều số 2 hơn?

Lời giải:
Trong dãy số trên có 112 số chia 9 dư 1 và 111 số chia 9 dư 2. Vậy dãy số cuối cùng có số 1 nhiều hơn số 2.
Nhận xét:  Đại lượng bất biến ở đây là một số tự nhiên và tổng các chữ số của nó có cùng số dư trong phép chia cho 9
VD15: Mối bước cho phép chọn một số tự nhiên a và phân tích a thành tích hai số tự nhiên m, n sau đó viết lên bảng hai trong số bốn số m ± 2, n ± 2. Ban đầu ta có số a = 20152015...2015 (100 số 2015). Hỏi sau một số bước như vậy có thu được một dãy gồm toàn số 1 hay không?
Lời giải:
Vì a chia 4 dư 3 nên trong hai số m, n phải có một số chia 4 dư 1 và một số chia 4 dư 3.Mà số chia 4 dư 1 thì cộng 2 hay trừ đi 2 đều chia 4 dư 3. Do đó ở mỗi bước luôn có mặt số chia 4 dư 3, như vậy sau hữu hạn bước không thể ra kết quả như đề yêu cầu.
Nhận xét: Bài này ta để ý đến a là một số chia 4 dư 3 cũng như việc tồn tại các số như vậy trong dãy.
VD16:Trên bảng có hai số 1 và 2. Thực hiện việc ghi số theo nguyên tắc sau: Nếu trên bảng có hai số a, b thì được phép ghi thêm số c = a + b + ab. Hỏi bằng cách đó có thể xuất hiện các số 2013, 2014 và 2015 được không?
Lời giải:
Dãy các số được viết là: 1; 2; 5; 11; 17;... Dễ thấy các số viết thêm trong dãy trên đều chia 3 dư 2. Như vậy bất biến trên cho phép ta khẳng định số 2013 và 2014 không thể có mặt. Với số 2015 ta phải dùng bất biến khác.
Đem tăng thêm 1 cho mỗi số hạng ở dãy trên thì ta nhận được dãy: 2; 3; 6; 12; 18;... Ta chứng minh cho các số hạng của dãy đều có dạng 2m.3n nhưng số 2015 + 1 không có tính chất đó.
VD17: Có ba đống sỏi với số lượng tương ứng là 8; 9; 19 viên. Ta được phép chọn hai đống sỏi và chuyển một viên của mỗi đống đã chọn sang đống còn lại. Hỏi sau một số lần làm như vậy ta có thể thu được ba đống sỏi mỗi đống có đúng 12 viên không?
Lời giải:
Bất biến trong bài này là trong tất cả các trạng thái thì số dư của số sỏi trong mối đống trong phép chia cho 3 là một hoán vị của bộ {0;1;2}. Do đó không thể thưch hiện được.

Tương tự ta có bài sau:

VD18: Ngoài biển đông, trên một hòn đảo sinh sống ba giống thằn lằn có ba loại màu: màuxám có 133 con, màu nâu có 155 con và màu đỏ có 177 con. Nếu hai con thằn lằn khác màu gặp nhau thì chúng đồng thời đổi sang màu thứ ba (ví dụ nếu thằn lằn màu xám gặp thằn lằn màu nâu thì cả hai con đều đổi sang màu đỏ). Trong những trường hợp hai con thằn lằn cùng màu gặp nhau thì chúng giữ nguyên không đổi màu. Có xảy ra tình trạng là trên đảo tất cả thằn lằn cùng một màu được không?
VD19: A và B tiến hành trò chơi với 2014 hạt gạo. Một nước đi là lấy khỏi đống gạo đó 1;2 hoặc 3 hạt. A đi trước và thay phiên nhau. Người nào lấy được hạt gạo sau cùng sẽ là người chiến thắng. Ai là người có thể luôn chiến thắng và chiến thuật ra sao?
Lời giải:
A sẽ là người luôn chiến thắng nếu chới theo chiến thuật sau: Bước 1: A lấy 2 hạt gạo. Bước 2: B lấy x hạt (x = 1;2;3) 7 Bước 3: A lấy 4 – x hạt Cứ tiếp tục như vậy....Ta thấy sau mối lần A lấy thì số gạo còn lại luôn là bội của 4. Ở bước áp chót số gạo còn lại là 4 hạt thì dù B có chọn cách chơi nào thì A cũng là người thắng cuộc.  
VD20: Có một tờ giấy được cắt thành 6 mảnh hoặc 11 mảnh. Sau đó mỗi mảnh bất kỳ trong số đó lại được cắt thành 6 hoặc 11 mảnh nhỏ hơn. Hỏi có thể tạo thành 2015 mảnh không?
Lời giải:
Sau mỗi lần cắt một mảnh giấy thành 6 mảnh hoặc 11 mảnh thì số mảnh giấy tăng lên là 5 hoặc 10. Như vậy tính bất biến của bài toán là “số mảnh giấy luôn tăng lên một bội số của 5”. Vậy số mảnh giấy sau các lần cắt có dạng 1 + 5k, mặt khác 2005 có dạng 5k nên với cách cắt như trên, từ một tờ giấy ban đầu, ta không thể cắt được thành 2005 mảnh. Nhận xét. Bất biến của bài toán là số mảnh giấy tăng lên luôn là một bội số của 5.
VD21: Trên bảng, người ta viết các số tự nhiên liên tiếp từ 1 đến 100 sau đó thực hiện trò chơi như sau: mỗi lần xóa hai số bất kỳ và viết một số mới bằng tổng lập phương của hai số đã cho. Việc làm này thực hiện liên tục cho đến khi còn một số trên bảng. Hỏi số cuối cùng còn lại trên bảng có thể là $987654321^n$ (n là số tự nhiên lớn hơn 1) hay không? Tại sao?
Lời giải:
Để ý rằng : $(a^3 + b^3 ) – (a + b) = (a^3 - a) + (b^3 - b )$ luôn chia hết cho 3 với mọi cặp số tự nhiên a, b. Do đó sau mỗi lần chơi tổng các số ban đầu thay đổi một lượng là bội của 3. Vì tổng các số từ 1 đến 100 chia cho 3 dư 1 nên ở trạng thái kết thúc ta cũng phải thu được số chia 3 dư 1, nhưng số đề cho lại là số chia hết cho 3.
Ta cùng luyện tập thêm một số bài cùng chủ đề sau:
Bài 1: Một con ốc sên bò trên một mặt phẳng với vận tốc không đổi. Sau mỗi 15 phút thì nó lại rẽ theo một góc vuông. Chứng minh ốc sên có thể quay lại điểm xuất phát sau một số nguyên lần.
Lời giải:
hi con ốc sên quay trở lại vị trí xuất phát thì nó đã đi được một đường gấp khúc khép kín. Kí hiệu: $\overrightarrow{a},\overrightarrow{-a},\overrightarrow{b},\overrightarrow{-b}$
chỉ các hướng đi lên, đi xuống, sang trái, sang phải của ốc sên. Gọi m, n, p,q là số lần đi lên , xuống, sang trái, sang phải. Ta cần chứng minh (m + n + p + q) là bội của 4.
Từ  $m\overrightarrow{a}+n \overrightarrow{-a}+p \overrightarrow{b}+q\overrightarrow{-b}=0$ mà hai véc to a,b khác phương  nên suy ra m = n và p = q. Do cứ sau 15 phút ốc sên lại rẽ sang góc $90^o$ nên m + n = p + q. Từ đó ta được đpcm
Bài 2: Ba con châu chấu chơi trò nhảy cóc trên một đường thẳng. Cứ mỗi nước đi một con châu chấu nhảy qua một con khác nhưng không nhảy qua hai con. Chúng có thể trở về vị trí ban đầu sau 2n + 1 bước không?
Lời giải:
Sau mỗi lần nhảy thì luôn có một con giữ nguyên vị trí. Sau số chẵn lần nhảy thì có 0 hoặc 3 con cùng đúng vị trí ban đầu. Nhưng 2n + 1 là số lẻ lần không thể thực hiện được.
Bài 3: Một số tự nhiên gồm 17 chữ số. Một học sinh đảo ngược thứ tự các chữ số của số đó rồi đem cộng với số ban đầu. Chứng minh tổng tạo thành có ít nhất một chữ số chẵn.
 Giải:
Gọi số đó là:
$A=\overline{a_1a_2..a_{17}}, B=\overline{a_{17}..a_1a_2}, C=A+B$
Đặt: $x_i=a_i+a_{18-i}$. Xét dãy:
$x_1x_2..x_8x_9x_8x_7..x_1$
Giả sử các chữ số của C gồm toàn số lẻ.Cộng theo hàng dọc ta thấy: x9 chẵn nên x8 phải nhớ 1 sang suy ra: x7 chẵn, x6 nhớ 1 sang, x5 chẵn,..., x1 chẵn. Do đó chữ số đơn vị của C là chẵn. Mâu thuẫn.
Bài 4: Có 100 người lính trong một doanh trại. Mỗi tối 3 người trong số họ có ca trực. Hỏi có thể xảy ra tình huống sau một khoảng thời gian nào đó mỗi người đều trực với tất cả những người còn lại đúng một lần hay không?
Lời giải: Giả sử có thể xảy ra tình huống trên. Xét một người lính A nào đó, từ gt suy ra số người còn lại sẽ được phân hoạch thành các cặp trực cùng A. Nhưng khi đó suy ra tổng số lính của doanh trại phải là số lẻ. Vô lý.
Bài 5: Có 9 số được đặt trên một vòng tròn gồm 4 số 1 và 5 số 0. Mỗi hành động sau được coi là một bước: Ta thêm số 0 vào giữa hai số cạnh nhau nếu hai số đó khác nhau, trường hợp ngược lại ta thêm số 1. Hai số cũ sau đó bị xóa. Hỏi sau một số bước đi các số còn lại có thể bằng nhau được hay không?
Bài 6: Có 25 bạn nam và 25 bạn nữ ngồi quanh một bàn tròn. Chứng minh tồn tại một bạn có cả hai “hàng xóm” là nam. (Tương tự có một bạn có hai hàng xóm đều là nữ).
Lời giải
Kí hiệu 25 bạn nam là N1, N2, ..., N25. Gọi x1, x2,..., x25 là số bạn nữ ngồi giữa hai bạn nam (Ni, Ni+1) với N1 = N26. Ta có: x1+ x2+...+ x25 = 25. (1) Nếu tồn tại xi = 1 thì bài toán được chứng minh. Trường hợp ngược lại: Từ (1) có ít nhất 13 số xi bằng 0. Nếu x1 = x25 = 0 thì N25 chính là người cần tìm. Nếu x1, x25 không đồng thời bằng 0 thì theo nguyên lý Diricle sẽ có một cặp xj = xj+1 = 0 khi đó Nj+1 là người cần tìm.
Bài 7: Hai người chơi cờ. Sau mỗi ván người thắng được 2 điểm, người thua được 0 điểm, nếu hòa thì mỗi người được 1 điểm. Hỏi sau một số ván cờ liệu có 10 xảy ra tình huống một người được 10 điểm, một người được 13 điểm hay không?
Lời giải:
Câu trả lời ở đây là không. Bất biến là tính chẵn lẻ của tổng số điểm của hai người chơi là không đổi.
Bài 8: Trên mặt bàn có 2017 viên bi gồm 667 viên xanh, 669 viên đỏ và 671 viên vàng. Thực hiện thuật toán như sau: Mỗi lần lấy đi hai viên bi khác màu và đặt thêm hai viên bi có màu còn lại. Hỏi có nhận được trạng thái tất cả các viên bi trên bàn có cùng một màu được không?
Lời giải:
Kí hiệu X(n), Đ(n), V(n) tương ứng với số bi màu xanh, đỏ, vàng sau bước đi thứ n. Như vậy X(0) = 667, Đ(0) = 669 , V(0) = 671. Từ thuật toán đề ra ta thấy bất biến ở đây là số dư của các hiệu X(n) – Đ(n), Đ(n) – V(n), V(n) – X(n) không đổi trong phép chia cho 3. Xuất phát từ trạng thái ban đầu ta có các số dư này là 1;2;1. Nhưng ở trạng thái kết thức số bi của ba loại trên là một hoán vị của {0;0;2007} nên không thể thực hiện được.
Bài 9 Trong dãy 1, 9, 9, 9, 8, . . . , mỗi chữ số bắt đầu từ chữ số thứ năm bằng chữ số hàng đơn vị của tổng bốn chữ số liền trước nó. Hỏi trong dãy này có gặp các bộ 1234 và 5678 không?
Lời giải:
Ta thay mỗi chữ số của dãy đã cho bằng số 0 nếu nó là số chẵn và bằng số 1 nếu nó là số lẻ. Ta nhận được dãy số 111101111011110..., trong đó cứ sau bốn chữ số 1 có một chữ số 0 và cứ sau mỗi số 0 có bốn chữ số 1. Các bộ số 1234 và 5678 ứng với các bộ 4 chữ số 1010 và 1001 nên không thể có mặt trong dãy số đã cho.

Tài liệu tham khảo
 1) Mathematical – Circles – Russian Experience
 2) Giải toán bằng đại lượng bất biến – Nguyễn Hữu Điển
 3) Một số chuyên đề trên mạng

Bài toán trò chơi

Bài toán:
Trên bảng viết n ( $n\geq 4$) số nguyên dương liên tiếp. Hai người A và B lần lượt chọn một số từ n số đã cho và xóa số đó đi và thực hiện đến khi trên bảng còn lại 2 số a,b. Biết rằng A thắng cuộc nếu gcd(a,b)=1, B thắng cuộc nếu gcd(a,b)>1. Ai là người thắng cuộc nếu A đi trước :

a) n=2017

b) n là một số nguyên dương không nhỏ hơn 2016

Lời giải:

Trường hợp tổng quát cho $n>8$: Nếu $n$ lẻ, đặt $n=2k+1$. Chiến thuật giúp $A$ thắng: đầu tiên $A$ sẽ loại $n$ ra khỏi bảng và chia $n-1$ số còn lại thành $k$ cặp $(1,2),(3,4),...,(2k-1,2k)$.Mỗi lượt $B$ sẽ chọn $1$ số trong $1$ cặp bất kì, $A$ chỉ việc loại số còn lại trong cặp đó và trên bảng luôn còn những cặp số liên tiếp nên cuối cùng trên bảng sẽ còn $2$ số liên tiếp và $A$ sẽ thắng. Còn nếu $n$ chẵn thì $B$ sẽ thắng: Đặt $n=2k$ gọi $S_i$ là hiệu giữa số số chẵn với số số lẻ trên bảng sau bước thứ $i$ của $B$. Có $S_0=0$, chiến thuật thắng của $B$ như sau: Rõ ràng trò chơi sẽ kết thúc sau $k-1$ bước, trong $k-2$ bước đầu của $B$, anh ta sẽ chọn ra $2$ số lẻ $m,n$ với $(m,n)>1$ (luôn chọn được vì $n>8$) và sẽ chỉ loại những số lẻ trên bảng khác $m,n$ nếu có thể. Nếu trong $k-2$ bước đầu của $A$, $A$ chọn loại $1$ số lẻ tại bước thứ $i$ và $B$ chọn loại $1$ số lẻ khác thì $S_i\geq 2$. Lúc đó $B$ sẽ chọn loại tất cả các số lẻ khác trên bảng và $S_i$ sẽ không giảm. Cuối cùng trên bảng còn ít nhất $2$ số chẵn, $A$ và $B$ cứ loại dần đến khi chỉ còn $2$ số chẵn và $B$ thắng. Còn nếu $A$ luôn chọn loại số chẵn trong $k-2$ bước đầu thì sau $k-2$ bước của cả $2$, trên bảng còn $2$ số chẵn $a,b$ và $2$ số lẻ $m,n$. Nếu sau đó $A$ chọn loại $1$ số trong cặp $(a,b)$ thì $B$ sẽ loại số còn lại trong nhóm đó và trên bảng còn $2$ số $m,n$ với $(m,n)>1$. Còn nếu $A$ chọn loại $1$ số trong $(m,n)$ thì $B$ loại số còn lại, trên bảng còn $2$ số $a,b$ chẵn có $(a,b)>1$. Tóm lại $A$ thắng nếu $n$ lẻ, $B$ thắng nếu $n$ chẵn

Dùng bất biến, đơn biến để giải bài toán tổ hợp - Phần 2

1) Cho tập hợp {3,4,12}. Mỗi bước chọn 2 số a,b rồi thay bởi 0,6a-0,8b và 0,8a+0,6b. Hỏi có thể đạt được:

a) {4,6,12}

b) {x,y,z} với |x-4|, |y-6|, |z-12| đều nhỏ hơn hơn $1/\sqrt{3}$

Giải:

Ta có $(0,6a-0,8b)^2+(0,8a+0,6b)^2=a^2+b^2.$
$3^2+4^2+12^2=13^2$
Suy ra các điểm có dang (a,b,c) nằm trên hình cầu quanh O với bán kính 13

$4^2+6^2+12^2=14^2$ nên không thể đạt được a) Do $4^2+6^2+12^2$ khác đại lượng bất biến đó.

b) Do $(x-4)^2+(y-6)^2+(z-12)^2<1$ nên

Nhận xét: Điều quan trọng bất biến ở đây là khoảng cách từ điểm (a,b,c) đến O.

2) Cho bàn cờ 8x8 được tô trắng đen. Hỏi có thể tô sao cho còn một ô đen không, nếu:

a) Đổi màu lại tất cả ô trong 1 hàng hoặc cột.

b) Đổi màu lại (trắng thành đen, đen thành trắng) tất cả các ô của ô vuông 2x2 bất kì.

Giải:

a) Chọn một hàng và một cột giả sử ô đó có b đen và 8-b trắng thì sau khi đổi sẽ có b trnawgs và 8-b đen. số lượng ô đen thay đổi bằng |(8-b)-b| là một số chẵn. Nên tính chẵn lẻ của số ô đen không đổi. 1 ô đen là số chẵn. Ban đầu có số chẵn ô đen nên không được.

b) Giả sử ô 2x2 có 1 ô đen, 2 ô đen, 3 ô đen, 4 ô đen thì chứng minh rằng sau khi đổi màu số ô đen cũng là số chẵn nên ta có đáp án cũng là không được.

Lưu ý: bàn cờ ta xét được tô trắng đen như bàn cờ vua.

3) Trên vòng tròn có 5 số 1 và 4 số 0 được sắp xếp tùy ý. Sau đó ta thực hiện phép biến đổi sau. Giữa hai số giống nhau điền số 0, giữa hai số khác nhau điền số 1. Cuối cùng xóa 9 số ban đầu đi ta được 9 số mới. Chứng minh sau hữu hạn bước không thể có 9 số 0.

Giải

Ta sẽ đi ngược:

(0,0,..0) <- (1,1,1....1) <-(1,0,1,0,..1,0) phải có tổng số số 0 và 1 là số chẵn mà 4+5=9 nên không tồn tại.

4) Cho bảng hình chữ nhật, mỗi ô ta ghi một số nguyên dương. Với mỗi bước, bạn có thể nhân đôi tất cả các số trên hàng hoặc giảm 1 từng số của cột nào đó. Chứng minh rằng sau hữu hạn bước ta sẽ thu được bảng toàn chữ số 0.

Giải

Xét cột đầu tiên. Nếu số nhỏ nhất côt đó không phải 1 ta giảm cho bằng 1. Nếu có một số số 1 ở cột đó thì ta nhân hai tất cả các số tương ứng ở hàng chứa số 1. Rồi sao đó giảm 1 đơn vị ở cột đầu tiên. Cứ như vậy ta sẽ thu được cột đầu tiên tất cả chữ số 1. Rồi giảm 1 đơn vị ta sẽ có tất cả số 0 cho cột. Tương tự cột tiếp theo

5) Một hàng ta viết 1000 số nguyên. Dưới mỗi số a ở hàng đầu, là một số nguyên f(a) sao cho f(a) là số lần xuất hiện của a ở hàng đầu. Tương tự ta có hàng thứ 3 từ hàng thứ 2,vv, Chứng minh rằng, cuối cùng sẽ có một hàng giống y như hàng trước nó.

Giải:

Như hình vẽ ví dụ, ta thấy rằng dưới chữ số a của hàng 2 thì sẽ có số b ở hàng 3 sao cho $b \ge a$

Ta có dãy trên là dãy tăng như lại bị chặn trên nên sẽ có một hàng y hệt hàng trước.

6) Một bàn cờ vua 8x8. Mỗi bước, có thể chọn 4x4 hoặc 3x3 và cộng thêm 1 vào mỗi số nguyên trong hình vuông đó ( Bàn cờ vua có điền số nguyên). Hỏi có thể luôn luôn nhận được một bàn cờ với:

a) tất cả các số đều chia hết cho 2 ?

b) tất cả các số đều chia hết cho 3 ?

Giải:

 a) Ta đặt S là tổng các số trong ô vuông trừ hàng 3 và hàng 6 thì số dư của S mỗi lần thay đổi là bất biến. Nên nếu tổng lúc đầu lẻ thì ta không thu được (Số dư S cho 2)

b) Tương tự ta đặt S là tổng các số trong ô vuông trừ hàng 4 và 8 thì số dư của S cho 3 mỗi lần thay đổi là bất biến nên nếu tỏng S không chia hết cho 3 ta cũng có đpcm

7) Cho (m,n)=1. Bắt đầu với m số nguyên, chọn n số nguyên trong chúng và cộng một vào mỗi số (n<m). Hỏi sau một số lần lặp lại thì có thể nhận được m số nguyên toàn bằng nhau không ?

Giải:
Có. Theo định lí bezout ta có: nx=my+1. Giờ ta viết $x_1,..x_m$ trên vòng tròn theo chiều kim đồng hồ và $x_1 \le x_2 \le..\le x_m$. Ta bắt đầu từ$x_1$ tới $x_n$ tăng 1 đơn vị như vậy một số lần ta sẽ có tất cả các số đều tăng 1 đơn vị như còn dư một số$x_m$. Như vậy $x_{max}-x_{min}$=1 như vậy sau một số lần nó sẽ giảm đến 0 và ta có đpcm.

8) Các số 1,2..2n được xếp theo thứ tự tùy ý vào các nơi được đánh dấu sẵn: 1,2 ..2n. Giờ ta cộng số ô đánh dấu và số trong ô đánh dấu. Chứng minh rằng bao giờ cũng có hai tổng có cùng số dư khi chia cho 2n.

Giả sử không có, thì các tổng có số dư là 0,1,2,3..2n-1.

Tổng tất cả các tổng đó bằng: 2(1+2+..2n-1)=2n(2n+1) chia hết 2n

Tổng các số dư khi cho cho 2n lại bằng n(2n-1) không chia hết cho 2n

Vô lí, vậy ta có đpcm

Dùng bất biến, đơn biến để giải bài toán tổ hợp - Phần 1

1) Cho n là số tự nhiên lẻ. Đầu tiên bạn A viết các số 1,2,..2n lên bảng. Sau đó bạn ấy chọn hai số a, b bất kì, xoá nó và viết lại số |a-b|, Chứng minh rằng chữ số cuối cùng còn lại là một số lẻ.

Lời giải:

Đặt $S=1+2+..2n=n(2n+1)$ lẻ. Mỗi bước thực hiện ta có $S'=S+|a-b|-a-b=S-2min(a,b)$. Vì vậy tính chẵn lẻ của S là bất biến. Số cuối cùng phải đồng dư 1 mod 2.

2) Một vòng tròn được chia thành sáu phần. Sau đó, các con số 1, 0, 1, 0, 0, 0 được viết
vào các phần (ngược chiều kim đồng hồ). Bạn có thể làm tăng hai số kề nhau một số bằng 1.Có thể cân bằng các số sau hữu hạn bước hay không ?

Lời giải:

Giả sử $a_1, a_2,..a_6$ là các số trên các phần đó. Ta có: $I=a_1 −a_2 +a_3 −a_4 +a_5 −a_6$ là một đại lượng bất biến. Ban đầu $I=2$ nên không thể cho $I=0$ được

3) Trong Quốc hội Sikinia, mỗi thành viên có ít nhất ba kẻ thù. Chứng minh
rằng ngôi nhà có thể được chia thành hai ngôi nhà, để mỗi thành viên có ít nhất
một kẻ thù trong chính ngôi nhà của mình.

Lời giải:

Ban đầu cho bất kì các thành viên vào hai ngôi nhà.

Đặt H là tổng số của tất cả các kẻ thù của mỗi thành viên đều có trong chính ngôi nhà của mình.

Bây giờ giả sử A có ít nhất hai ( có thể 3)  kẻ thù trong nhà của mình. Khi đó, A sẽ có ít nhất 1 kẻ thù trong nhà khác. Nếu A chuyển nhà, số H sẽ giảm (Tăng 1 giảm 2). Điều này giảm không thể mãi mãi. Tại một số thời gian, H đạt tối thiểu tuyệt đối của nó.
Sau đó, chúng ta đã đạt đến phân phối yêu cầu.

4) Giả sử các số a,b,c,d không đồng thời bằng nhau.Bắt đầu với (a, b, c, d) và
nhiều lần thay thế (a, b, c, d) bằng cách (a - b, b - c, c - d, d - a). Sau đó ít nhất một trong 4
số sẽ lớn vô cùng

Lời giải:
Đặt $P_n=(a_n, b_n, c_n, d_n)$ là 4 số sau khi đổi n lần. Khi đó ta có: $a_n+b_n+c_n+d_n=0$ (với $n \ge 1$)
Chúng ta không nhìn thấy cách nào để sử dụng bất biến... Nhưng nếu nhìn theo hướng hình học thì thật hữu ích. Chức năng rất quan trọng cho các điểm $P_n$ trong không gian 4 chiều là khoảng cách tử điểm đó đến điểm gốc là $(0;0;0;0)$ là: $a_n^2+b_n^2+c_n^2+d_n^2$. Nếu ta chứng minh nó không có giới hạn trên ta có điều phải chứng minh.

Ta sẽ cố gắng tìm mối liên hệ giữa $P_n$ và $P_{n+1}$:

$\sum a_{n+1}^2=\sum (a_n-b_n)^2=2\sum a_n^2-2\sum a_nbn$

Mặt khác:

$0=(\sum a_n)^2=(a_n+c_n)^2+(b_n+c_n)^2+2\sum a_nb_n$

Cộng hai vế lại suy ra: $ \sum a_{n+1}^2\ge\sum a_n^2$

Như vậy ta kết luận rằng với $n \ge 2$

$\sum a_n^2\ge2^{n-1}\sum a_1^2$

Như vậy khoảng cách từ điểm $P_n$ đến điểm gốc tăng không có giới hạn trên. Tức là phải có một số đạt đến vô cùng.

5) Có 2n  đại sứ được mời đến một bữa tiệc. Mỗi đại sứ có nhiều nhất n-1
kẻ thù. Chứng minh rằng các đại sứ có thể được ngồi quanh một chiếc bàn tròn, để
không ai ngồi cạnh một kẻ thù.

Giải

Đầu tiên chúng ta xếp chỗ ngồi các đại sứ bất kì. Gọi H là số cặp đôi thù địch ở gần nhau. Chúng ta phải tìm ra một thuật toán làm giảm số này bất cứ khi nào H> 0. Đặt (A, B) là một cặp thù địch với B ngồi bên trái của A (Như trong hình Fig 1.3). Chúng ta phải tách chúng ra để gây ra ít xáo trộn càng tốt. Điều này sẽ đạt được nếu chúng ta đảo ngược cung BA' nhận được hình Fig 1.4, H sẽ được giảm nếu (A,A') và (B, B') trên hình Fig 1.4 là cặp đôi thân thiện. Mà với A ta lại có ít nhất n bạn. Mà họ không thể là kẻ thù của B được nên có bạn A' của A lại là bạn của B, bên phải B'- bạn của B.

Bài toán tổ hợp tô màu

Bài: Vùng nọ có khu đất vàng 100 × 100 m, chia ra làm 100 lô, mỗi lô 10 × 10 m. Vua bãi rác muốn lấn chiếm khu đất này nên sai tay chân đổ rác vào một số ô. Nếu một ô nào chưa có rác mà có ít nhất hai ô cạnh nó (có chung cạnh) đã bị đổ rác thì (đáng tiếc) hôm sau nhân dân cũng sẽ đổ rác vào ô đó. Nếu đến một ngày nào đó tất cả các ô đều bị đổ rác thì vua bãi rác sẽ chiểm khu đất. Nếu vua bãi rác muốn chiếm khu đất này thì lúc đầu cần đổ rác vào ít nhất mấy ô?

Giải

Ta đưa bài toán về mô hình bảng ô vuông kích thước 10 × 10 và mỗi ô bị đổ rác thì sẽ được tô đen. Mỗi bước biến đổi tương ứng với việc ta tô đen một ô chưa được tô và chung cạnh với ít nhất hai ô được tô đen. Do đó, ta chỉ cần tìm số ô đen được tô ban đầu sao cho sau một số hữu hạn bước biến đổi, ta có thể tô đen cả bảng. Gọi p là chu vi của tất cả các phần được tô đen. Ta chứng minh rằng sau mỗi bước biến đổi thì p không tăng. Thật vậy, do ở mỗi bước biến đổi ta tô đen một ô khi nó phải chung cạnh với ít nhất hai ô đen. Ta có các trường hợp sau: Chu vi không đổi, chu vi giảm 2 đơn vị, chu vi giảm 4 đơn vị.

Khi cả bảng được tô đen thì p' = 10 × 4 = 40. Do đó, để tô đen cả bảng ban đầu p ≥ p' = 40. Mà mỗi ô có chu vi là 4. Suy ra ban đầu cần tô ít nhất p/4 = 10 ô. Ta tô mười ô trên cùng một đường chéo chính thì sau hữu hạn bước biến đổi thì cả bảng sẽ được tô đen. Ban đầu vua cho đổ rác vào mười ô trên một đường chéo chính số 1. Ngày hôm sau các ô trên hai đường chéo chính số 2 sẽ bị đổ rác (do mỗi ô đều kề hai ô ở đường chéo số 1). Tiếp tục như vậy thì đến ngày thứ 10 cả khu đất sẽ bị đổ rác. Đáp số: 10 ô.