Bài 1: Một hội nghị Toán học quốc tế có 2011 nhà toán học tham dự. Biết rằng một nhà toán học bất kì trong số đó quen biết ít nhất với 1509 nhà toán học khác. Hỏi có thể lập ra một tiểu ban gồm 5 nhà toán học mà người bất kì trong 5 người đó đều quen biết những người con lại của tiểu ban đó hay không ?
Lời giải
Gọi S là tập các nhà Toán học trong hội nghị thì |S|=2011. Giả sử $x,y \in S$, ta quy ước nếu x,y quen biết nhau thì viết (x;y)=1. Xét $a,b \in S$ mà $(a;b)=1$. Đặt:
$A=\left \{ c\in S|c \ne b, (c,a)=1 \right \},B= \left \{c \in S| c \ne a, (c,b)=1 \right \}$
Thì $|A|, |B| \ge 1508, |A \cup B| \le 2009$
Suy ra: $|A \cap B|=|A|+|B|-|A \cup B| \ge 1007$ Do đó tồn tại $c \in A \cap B$, tức là tồn tại 3 nhà toán học a,b,c đôi một quen biết nhau.
Xét:$C=\left \{ d \in S|d \ne a, d\ne b,(d,c)=1 \right \}$ thì $|C| \ge 1507$ và $|(A \cap B) \cup C| \le 2009$ Suy ra:
$|A \cap B \cap C |=|A \cap B|+|C|-|(A \cap B) \cup C| \ge 505$ Do đó tồn tại $d \in A \cap B \cap C$ chứng tỏ có 4 nhà toán học a,b,c,d đôi một quen nhau. Tương tự xét $D$
Ta thu được $|A \cap B \cap C \ cap D| \ge 505+1506-2009=2$
Do đó tồn tại $e \in A \cap B \cap C \cap D$, chứng tỏ có 5 nhà toán học a,b,c,d,e đôi một quen biết nhau. Vậy có thể lập ra một tiểu ban gồm 5 nhà toán học mà bất kì trong 5 người đó đều quen biết những người còn lại của tiểu ban đó.
Bài 2: Trên đường tròn (C) có 2011 điểm. Hỏi có bao nhiêu cách xóa đi 11 điểm sao cho không có hai điểm bị xóa nào cạnh nhau.
Lời giải
Ta gọi một trong số 2011 điểm là A. Có hai trường hợp sau:
Trường hợp 1: Điểm A không bị xóa. Sau khi xóa 11 điểm còn lại 2000 điểm. Xen kẽ giữa 2000 điểm này có 2000 khoảng trông. Mười một điểm bị xóa tương ứng với 11 trong số 2000 khoảng trống nói trên. Do đó số cách thực hiện trong trường hợp này là:
$C^{11}_{2000}$
Trường hợp 2. Điểm A bị xóa. Sau khi xóa tiếp 10 điểm, còn lại 2000 điểm. Xen kẽ những 2000 điểm này có 1999 khoảng trống không kề với vị trí của điểm A. 10 điểm bị xóa (không kể điểm A) tương ứng với 10 trong số 1999 khoảng trống nói trên. Do đó số cách thực hiện trong trường hợp này bằng:
$C^{10}_{1999}$
Theo quy tắc cộng, cách xóa cần tìm thỏa mãn đề bài là:
$C^{11}_{2000}+C^{10}_{1999}$
Hiển thị các bài đăng có nhãn tổ hợp. Hiển thị tất cả bài đăng
Hiển thị các bài đăng có nhãn tổ hợp. Hiển thị tất cả bài đăng
Chủ Nhật, 1 tháng 1, 2017
Chủ Nhật, 20 tháng 11, 2016
Về phép đếm quay quanh tâm
Ví dụ 1(VMO 2010): Cho bảng 3x3 và n là một số nguyên dương cho trước. Tìm số các cách tô màu không như nhau khi tô mỗi ô bởi 1 trong n màu.
Hai cách tô màu được gọi là như nhau nếu 1 cách nhận được từ cách kia bởi 1 phép quay quanh tâm.
Lời giải:
Cách của thầy Trần Nam Dũng:
Ví dụ 2: (AIME 1996) Hai ô của hình vuông 7 × 7 được tô bằng màu vàng. Các ô còn lại được tô bằng màu đỏ. Hai cách tô đượcc coi là tương đương nhau nếu chúng có thể thu được từ nhau bằng một phép quay trên mặt phẳng của hình vuông. Đếm sô các cách tô màu không tương đương.
Lời giải:
(Xây dựng hệ trục trên hình vuông ô đầu tiên đánh số 1 từ trái sang đánh đến số 7, từ trên xuống đánh từ 1 đến 7)
Ta chia hai ô màu vàng của hình vuông thành 3 loại:
Loại 1: có 1 ô (4;4), thì ô còn lại có 48 cách chọn ( có thể bị lặp). Do các phép quay 90 độ, 180 độ, 270 độ tạo thành những cách khác ta phải loại bớt nên có 48/4=12 cách chọn
Loại 2: các ô có tọa độ là (4,x), (4, 8-x) và (x,4), (8-x, 4) và các ô chéo của hình vuông con ở trong thì khi đó sẽ có 4.3=12 cách chọn như vậy.(Do có 3 hình vuông con mà tâm là (4;4))
Loại 3: Không tính loại 2. Rõ ràng là $\frac{\mathbb{C}_2^{49}-24}{4}$
Tổng cộng có: $\frac{\mathbb{C}_2^{49}-24}{4}+12=300$ cách chọn.
Có thể thấy rõ qua hình sau:
Chú ý: -Có thể không xài loại 1 làm gì nhưng viết vào để cho dễ hình dung.
-Đây là trường hợp của bổ đề Burnside
Ví dụ 3 (tạp chí Kvant số 5 năm 2000): Một đường tròn chia làm p cung bằng nhau. Hỏi có bao nhiêu cách tô các cung bằng a màu. Hai cách tô được gọi là giống nhau nếu có thể thu được từ nhau bởi 1 phép quay.
Với bài toán trên, có $ a^p $ cách tô màu p cung. Trong những số cách ấy, có những cách ta đếm lặp, cần loại đi. Ta thấy rằng nếu p cung được tô bởi 1 màu thì khi quay các góc 2pi/p, 4pi/p,..., 2(p-1)pi/p không thu được những cách tô khác. (ta có thể chứng minh rằng nếu $n \vdots k$ khi đó tồn tại phép quay góc 2kpi/p biến đường tròn này thành đường tròn kia) . Trong khi đó, những cách tô sử dụng 2 màu trở lên khi quay sẽ cho ra các cách tô khác (chú ý tính nguyên tố của p). Vì vậy, mỗi một cách tô sử dụng 1 màu (có a cách tô như vậy) chỉ được đếm 1 lần trong tổng $a^p $cách tô, trong khi đó mỗi cách tô sử dụng 2 màu trở lên (có $a^p - a$ cách tô như vậy) được đếm p lần trong tổng nói trên.
Từ đó suy ra số cách tô cần tìm bằng $ a + \dfrac{a^p-a}{p} $.
Hai cách tô màu được gọi là như nhau nếu 1 cách nhận được từ cách kia bởi 1 phép quay quanh tâm.
Lời giải:
Cách của thầy Trần Nam Dũng:
Ví dụ 2: (AIME 1996) Hai ô của hình vuông 7 × 7 được tô bằng màu vàng. Các ô còn lại được tô bằng màu đỏ. Hai cách tô đượcc coi là tương đương nhau nếu chúng có thể thu được từ nhau bằng một phép quay trên mặt phẳng của hình vuông. Đếm sô các cách tô màu không tương đương.
Lời giải:
(Xây dựng hệ trục trên hình vuông ô đầu tiên đánh số 1 từ trái sang đánh đến số 7, từ trên xuống đánh từ 1 đến 7)
Ta chia hai ô màu vàng của hình vuông thành 3 loại:
Loại 1: có 1 ô (4;4), thì ô còn lại có 48 cách chọn ( có thể bị lặp). Do các phép quay 90 độ, 180 độ, 270 độ tạo thành những cách khác ta phải loại bớt nên có 48/4=12 cách chọn
Loại 2: các ô có tọa độ là (4,x), (4, 8-x) và (x,4), (8-x, 4) và các ô chéo của hình vuông con ở trong thì khi đó sẽ có 4.3=12 cách chọn như vậy.(Do có 3 hình vuông con mà tâm là (4;4))
Loại 3: Không tính loại 2. Rõ ràng là $\frac{\mathbb{C}_2^{49}-24}{4}$
Tổng cộng có: $\frac{\mathbb{C}_2^{49}-24}{4}+12=300$ cách chọn.
Có thể thấy rõ qua hình sau:
Chú ý: -Có thể không xài loại 1 làm gì nhưng viết vào để cho dễ hình dung.
-Đây là trường hợp của bổ đề Burnside
Ví dụ 3 (tạp chí Kvant số 5 năm 2000): Một đường tròn chia làm p cung bằng nhau. Hỏi có bao nhiêu cách tô các cung bằng a màu. Hai cách tô được gọi là giống nhau nếu có thể thu được từ nhau bởi 1 phép quay.
Với bài toán trên, có $ a^p $ cách tô màu p cung. Trong những số cách ấy, có những cách ta đếm lặp, cần loại đi. Ta thấy rằng nếu p cung được tô bởi 1 màu thì khi quay các góc 2pi/p, 4pi/p,..., 2(p-1)pi/p không thu được những cách tô khác. (ta có thể chứng minh rằng nếu $n \vdots k$ khi đó tồn tại phép quay góc 2kpi/p biến đường tròn này thành đường tròn kia) . Trong khi đó, những cách tô sử dụng 2 màu trở lên khi quay sẽ cho ra các cách tô khác (chú ý tính nguyên tố của p). Vì vậy, mỗi một cách tô sử dụng 1 màu (có a cách tô như vậy) chỉ được đếm 1 lần trong tổng $a^p $cách tô, trong khi đó mỗi cách tô sử dụng 2 màu trở lên (có $a^p - a$ cách tô như vậy) được đếm p lần trong tổng nói trên.
Từ đó suy ra số cách tô cần tìm bằng $ a + \dfrac{a^p-a}{p} $.
Chú ý: Từ kết quả này có thể suy ra định lí Fermat nhỏ.
Thứ Tư, 16 tháng 11, 2016
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
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:
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
Thứ Ba, 15 tháng 11, 2016
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:
Thứ Ba, 11 tháng 10, 2016
Mở rộng của định lý Dirac
Định lý Ore: Nếu đồ thị vô hướng G=(V,E) có số đỉnh là $n \ge 3$ và $deg(u)+deg(v) \ge n$ thỏa mãn cho mọi cặp đỉnh không kề nhau u và v của G, thì G là đồ thị Hamilton.
Chứng minh.
Giả sử định lý không đúng và G=(V, E) có cỡ cực đại cấp n thỏa mãn các điều kiện của Định lý nhưng không là đồ thị Hamilton. Dễ thấy rằng thêm một cạnh bất kỳ vào một đồ thị có những tính chất chỉ ra trong định lý sẽ tạo ra một đồ thị cũng có những tính chất ấy. Vì G là đồ thị không là Hamilton cấp n có cỡ cực đại thỏa mãn các điều kiện , nên đồ thị nhận được khi thêm vào G một cạnh bất kì nối hai đỉnh không kề nhau trong G là đồ thị có chu trình Hamilton cạnh thêm đó. Suy ra hai đỉnh bất kỳ không kề nhau trong G được nối với nhau bằng một đường Hamilton
Vì G không là đồ thị Hamilton nên G khác đồ thị đầy đủ $K_n$. Do đó tồn tại hai đỉnh không kề nhau trong G, chẳng hạn $v_1$ và $v_n$. Theo khẳng định vừa chứng minh ở đoạn trên tồn tại trong G đường Hamilton nối $v_1$ với $v_n$ chẳng hạn $v_1v_2..v_n$.
Kí hiệu các đỉnh kề với $v_1$ bằng $v_{i_1},v_{i_2},..v_{i_k}$ trong đó k là bậc của đỉnh $v_1$ và $2=i_1<i_2<..<i_k$. Hiền nhiên là $v_n$ không thể kề với một đỉnh nào của G dạng $v_{i_j-1}$ bởi vì khi đó G sẽ có chu trình Hamilton là $v_1v_2..v_{i_j-1}v_nv_{n-1}..v_{i_j}v_1$.
Do đó ký hiệu $N(v_1)=\begin{Bmatrix}
v_{i_j} \in V|j=1,2,..k
\end{Bmatrix}$ và $N*(v_n)=\begin{Bmatrix}
v_{i+1} \in V | v_i \ne v_n, \begin{Bmatrix}
v_i,v_n
\end{Bmatrix} \in E
\end{Bmatrix}$
Thì $N(v_1) \cap N^*(v_n)$ là rỗng.
Vì thế: $n \le deg(v_1)+deg(v_n) = k+(n-1-k)=n-1$ (mâu thuẫn)
Như vậy ta có điều phải chứng minh.
Có thể thấy rằng định lý Dirac này là hệ quả của định lý Ore do:
nếu có hai đỉnh trong đồ thị không kề nhau bất kì u và v trong G ta có $deg(u)+deg(v) \ge n/2+n/2=n$ áp dụng định lý Ore ta có điều phải chứng minh.
Chứng minh.
Giả sử định lý không đúng và G=(V, E) có cỡ cực đại cấp n thỏa mãn các điều kiện của Định lý nhưng không là đồ thị Hamilton. Dễ thấy rằng thêm một cạnh bất kỳ vào một đồ thị có những tính chất chỉ ra trong định lý sẽ tạo ra một đồ thị cũng có những tính chất ấy. Vì G là đồ thị không là Hamilton cấp n có cỡ cực đại thỏa mãn các điều kiện , nên đồ thị nhận được khi thêm vào G một cạnh bất kì nối hai đỉnh không kề nhau trong G là đồ thị có chu trình Hamilton cạnh thêm đó. Suy ra hai đỉnh bất kỳ không kề nhau trong G được nối với nhau bằng một đường Hamilton
Vì G không là đồ thị Hamilton nên G khác đồ thị đầy đủ $K_n$. Do đó tồn tại hai đỉnh không kề nhau trong G, chẳng hạn $v_1$ và $v_n$. Theo khẳng định vừa chứng minh ở đoạn trên tồn tại trong G đường Hamilton nối $v_1$ với $v_n$ chẳng hạn $v_1v_2..v_n$.
Kí hiệu các đỉnh kề với $v_1$ bằng $v_{i_1},v_{i_2},..v_{i_k}$ trong đó k là bậc của đỉnh $v_1$ và $2=i_1<i_2<..<i_k$. Hiền nhiên là $v_n$ không thể kề với một đỉnh nào của G dạng $v_{i_j-1}$ bởi vì khi đó G sẽ có chu trình Hamilton là $v_1v_2..v_{i_j-1}v_nv_{n-1}..v_{i_j}v_1$.
Do đó ký hiệu $N(v_1)=\begin{Bmatrix}
v_{i_j} \in V|j=1,2,..k
\end{Bmatrix}$ và $N*(v_n)=\begin{Bmatrix}
v_{i+1} \in V | v_i \ne v_n, \begin{Bmatrix}
v_i,v_n
\end{Bmatrix} \in E
\end{Bmatrix}$
Thì $N(v_1) \cap N^*(v_n)$ là rỗng.
Vì thế: $n \le deg(v_1)+deg(v_n) = k+(n-1-k)=n-1$ (mâu thuẫn)
Như vậy ta có điều phải chứng minh.
Có thể thấy rằng định lý Dirac này là hệ quả của định lý Ore do:
nếu có hai đỉnh trong đồ thị không kề nhau bất kì u và v trong G ta có $deg(u)+deg(v) \ge n/2+n/2=n$ áp dụng định lý Ore ta có điều phải chứng minh.
Thứ Hai, 10 tháng 10, 2016
Định lý Dirac và ứng dụng
Định lý (Dirac 1952)
Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.
Chứng minh:
Ký hiệu n đỉnh của G là .
.
Không mất tính tổng quát giả sử đường đi H dài nhất của G là . H có độ dài là l. Như vậy mọi đường đi đơn của G có độ dài nhỏ hơn l+1.
. H có độ dài là l. Như vậy mọi đường đi đơn của G có độ dài nhỏ hơn l+1.
Nếu thì suy ra luôn điều phải chứng minh.
thì suy ra luôn điều phải chứng minh.
Xét trường hợp .
.
Gọi tất cả các đỉnh liền kề với là (với và ≥). Dễ thấy với mọi j chạy từ 1 tới t, vì nếu tồn tại , thì suy ra tồn tại đường đi có độ dài l+1:
là 
(với 
và 
≥
). Dễ thấy 
với mọi j chạy từ 1 tới t, vì nếu tồn tại 
, thì suy ra tồn tại đường đi có độ dài l+1:- .
.
Nếu đỉnh mà liền kề với đỉnh thì ta sẽ tạo được đường đi có độ dài l+1:
mà liền kề với đỉnh 
thì ta sẽ tạo được đường đi có độ dài l+1:
(vô lý).
Vậy không liền kề với các đỉnh , với j chạy từ 1 đến t. Mà ≥, nên suy ra bậc của nhỏ hơn (vô lý).
Vậy trường hợp l<n là không tồn tại.
Suy ra điều phải chứng minh.
Ứng dụng của nó là bài toán nổi tiếng sau:
Bài toán: Tại một hội nghị có 2n quan khách.trong đó mỗi quan khách có nhiều nhất n-1 kẻ thù.chứng minh rằng có thể xếp 2n nguời đó trên 1 vòng tròn sao cho không ai ngồi cạnh kẻ thù của mình
Lời giải:
Ta xây dựng đồ thị G như sau:
-Đỉnh: là các điểm trong mặt phẳng hay trong không gian tương ứng với các quan khách, dùng mã số của các quan khách để ghi trên các đỉnh tương ứng.
-Cạnh: hai đỉnh được nối với nhau bằng cạnh khi và chỉnh khi hai quan khác tương ứng thuộc hai đỉnh đó không là kẻ thù của nhau.
Khi đó ta được một đồ thị G mô tả toàn bộ quan hệ giữa các quan khách. Vì đồ thị G có đúng 2n đỉnh, và mỗi đỉnh có bậc không nhỏ hơn n nên theo định lý Dirac ta có G có chu trình Halminton. Dựa vào chu trình này ta có thể xếp tất cả các quan khách thỏa mãn yêu cầu đề bài
Thứ Hai, 15 tháng 8, 2016
Định lý Dirichle
(Định lí Dirichle) Cho $\alpha$ là một số vô tỉ. Chứng minh rằng, tồn tại vô hạn các số nguyên p,q với q>0 sao cho:
$|\alpha -\frac{p}{q}| <\frac{1}{q^2}$
Lời giải:
Trước hết ta chứng minh với mọi $ N \ge q$ luôn tồn tại p,q thỏa mãn:
$|\alpha -\frac{p}{q}| <\frac{1}{qN}$
Thật vậy ta chia các [0;1) thành các khoảng $[\frac{k-1}{N};\frac{k}{N})(k =\overline{1,N})$
Thì theo nguyên lý Dirichle sẽ tồn tại hai số { $\alpha q_i$ } và { $\alpha q_j$ } thuộc vào một đoạn ( q= 0,1,..N)
$\Rightarrow \left | \begin{Bmatrix}
\alpha q_i
\end{Bmatrix}- \begin{Bmatrix}
\alpha q_j
\end{Bmatrix} \right |<\frac{1}{N(q_i-q_j)}\\\Rightarrow \left | \alpha -\frac{\begin{bmatrix}
\alpha q_i
\end{bmatrix}-\begin{bmatrix}
\alpha q_j
\end{bmatrix}}{q_i-q_j} \right | <\frac{1}{N(q_i-q_j)}$ Điều phải chứng minh.
Ta giả sử chỉ có hữu hạn các số p,q thỏa mãn đề bài Kí hiệu tập này là X.
Khi đó sẽ tồn tại M sao cho $|\alpha -\frac{p}{q}| >M$
Chọn N sao cho $\frac{1}{M}<N$ Khi đó tồn tại các số nguyên dương $p_i, q_i$ sao cho
$|\alpha -\frac{p_i}{q_i}| <\frac{1}{q_iN} <\frac{1}{q_iN}<\frac{1}{q_i^2}$
Suy ra $p_i,q_i$ thuộc X, nhưng $M >\frac{1}{q_iN} $ (mâu thuẫn)
Vậy ta có điều phải chứng minh.
$|\alpha -\frac{p}{q}| <\frac{1}{q^2}$
Lời giải:
Trước hết ta chứng minh với mọi $ N \ge q$ luôn tồn tại p,q thỏa mãn:
$|\alpha -\frac{p}{q}| <\frac{1}{qN}$
Thật vậy ta chia các [0;1) thành các khoảng $[\frac{k-1}{N};\frac{k}{N})(k =\overline{1,N})$
Thì theo nguyên lý Dirichle sẽ tồn tại hai số { $\alpha q_i$ } và { $\alpha q_j$ } thuộc vào một đoạn ( q= 0,1,..N)
$\Rightarrow \left | \begin{Bmatrix}
\alpha q_i
\end{Bmatrix}- \begin{Bmatrix}
\alpha q_j
\end{Bmatrix} \right |<\frac{1}{N(q_i-q_j)}\\\Rightarrow \left | \alpha -\frac{\begin{bmatrix}
\alpha q_i
\end{bmatrix}-\begin{bmatrix}
\alpha q_j
\end{bmatrix}}{q_i-q_j} \right | <\frac{1}{N(q_i-q_j)}$ Điều phải chứng minh.
Ta giả sử chỉ có hữu hạn các số p,q thỏa mãn đề bài Kí hiệu tập này là X.
Khi đó sẽ tồn tại M sao cho $|\alpha -\frac{p}{q}| >M$
Chọn N sao cho $\frac{1}{M}<N$ Khi đó tồn tại các số nguyên dương $p_i, q_i$ sao cho
$|\alpha -\frac{p_i}{q_i}| <\frac{1}{q_iN} <\frac{1}{q_iN}<\frac{1}{q_i^2}$
Suy ra $p_i,q_i$ thuộc X, nhưng $M >\frac{1}{q_iN} $ (mâu thuẫn)
Vậy ta có điều phải chứng minh.
Thứ Ba, 9 tháng 8, 2016
Bài tổ hợp nhỏ
Bài toán: Có một số học sinh xếp thành một vòng tròn. Cô giáo yêu cầu các bạn học sinh đứng cạnh nhau bắt tay nhau. Gọi b là số học sinh nam, g là số học sinh nữ, B là số cặp học sinh nam bắt tay nhau và G là số cặp học sinh nữ bắt tay nhau. Chứng minh rằng: b-g=B-G.
Lời giải của bài toán rất đơn giản như sau:
i) Với số học sinh là hai, ta xét là TRAI - TRAI, GÁI - GÁI, GÁI - TRAI thì thấy khẳng định bài toán đúng.
ii) Bây giờ giả sử bài toán đúng với số học sinh $n$. Bây giờ ta thêm một em học sinh vô. Vai trò mấy em này như nhau, nên giả sử ta thêm bạn nữ vào
Khi đó $B' = B$ và $G' = G + 1$.
a) TH1. Ta nhét em ấy vào giữa GÁI - GÁI thì $b' = b$ và $g' = g + 1$. Khi đó $B' - G' = B - G - 1 = b - g - 1 = b' - g'$.
b) TH2. Ta nhét em ấy vào giữa TRAI - GÁI thì $b' = b$ và $g' = g + 1$. Tương tự trên ta cũng có đpcm.
c) TH3. Ta nhét em ấy vào giữa TRAI - TRAI thì $b' = b - 1$ và $g' = g$. Lúc đó $B' - G' = B - G - 1 = b - 1 - g = b' - g'$. Xong.
Dùng hàm sinh trong bài toán đếm
Bài 1: $x+2y+3z=n (n \in N) $ có bao nhiêu nghiệm nguyên không âm ?
Giải:
Bổ đề : $\text{Với }|a|<1\text{ thì }\sum_{i=0}^{\infty}a^i=\lim_{n\to\infty}\sum_{i=0}^{n}a^i=\lim_{n\to\infty}(1+a+a^2+...+a^n)=\lim_{n\to\infty}\frac{1-a^{n+1}}{1-a}=\frac{1}{1-a}$
Dùng PP hàm sinh :
Xét $|a|<1$ và $f(a)=\left(\sum_{x=0}^{\infty}a^x\right)\left(\sum_{y=0}^{\infty}a^{2y}\right)\left(\sum_{z=0}^{\infty}a^{3z}\right)$$=\sum_{x=0,y=0,z=0}^{\infty}A_{x,y,z}.a^{x+2y+3z}=\sum_{n=0}^{\infty}A_n.a^n$ (1)Ta thấy số nghiệm của pt(*) tương ứng chính là hệ số $A_n$ của $a^n$ trong khai triển $f(a)$
$f(a)=\frac{1}{1-a}.\frac{1}{1-a^2}.\frac{1}{1-a^3}=\frac{1}{(1-a)^3(1+a)(1+a+a^2)}$$=\frac{\frac{1}{8}}{1+a}+\frac{\frac{17}{72}}{1-a}+\frac{\frac{1}{4}}{(1-a)^2}+\frac{\frac{1}{6}}{(1-a)^3}+\frac{\frac{1}{9}(2+a)}{1+a+a^2}$
Mà ta có các khai triển sau (Maclaurin):
$\frac{1}{(1-a)^m}=(1-a)^{-m}=\sum_{k=0}^{\infty}\binom{-m}{k}(-1)^ka^k=\sum_{k=0}^{\infty}C_{k+m-1}^{m-1}a^k$
$\frac{1}{1+a+a^2}=(1-a).\frac{1}{1-a^3}=(1-a).\sum_{k=0}^{\infty}a^{3k}=\sum_{k=0}^{\infty}(a^{3k}-a^{3k+1})$
$\frac{2+a}{1+a+a^2}=(2+a)\sum_{k=0}^{\infty}(a^{3k}-a^{3k+1})=\sum_{n=0}^{\infty}(2a^{3k}-a^{3k+1}-a^{3k+2})$
Suy ra
$f(a)=\frac{1}{8}\sum_{n=0}^{\infty}(-1)^na^n+\frac{17}{72}\sum_{n=0}^{\infty}a^n+\frac{1}{4}\sum_{n=0}^{\infty}(n+1)a^n+\frac{1}{6}\sum_{n=0}^{\infty}\frac{(n+1)(n+2)}{2}a^n$$+\frac{1}{9}\sum_{k=0}^{\infty}(2a^{3k}-a^{3k+1}-a^{3k+2})$ (2)
Đồng nhất các hệ số của $a^n$ trong (1) và (2), ta có :
$\boxed{}$ Nếu $n=3k$ thì $A_n=\frac{(-1)^{3k}}{8}+\frac{17}{72}+\frac{3k+1}{4}+\frac{(3k+1)(3k+2)}{12}+\frac{2}{9}=\frac{3(-1)^k+21+36k+18k^2}{24}$
$\boxed{}$ Nếu $n=3k+1$ thì $A_n=\frac{(-1)^{3k+1}}{8}+\frac{17}{72}+\frac{3k+2}{4}+\frac{(3k+2)(3k+3)}{12}-\frac{1}{9}=\frac{3(-1)^{k+1}+27+48k+18k^2}{24}$
$\boxed{}$ Nếu $n=3k+2$ thì $A_n=\frac{(-1)^{3k+2}}{8}+\frac{17}{72}+\frac{3k+3}{4}+\frac{(3k+3)(3k+4)}{12}-\frac{1}{9}=\frac{3(-1)^{k}+45+60k+18k^2}{24}$
Vậy :
$\boxed{}$ Nếu $n=3k,k=2t$ tức $n=6t$ thì $A_n=\frac{24+72t+72t^2}{24}=1+3t+3t^2=\frac{(n+3)^2+3}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k,k=2t+1$ tức $n=6t+3$ thì $A_n=\frac{72+144t+72t^2}{24}=3+6t+3t^2=\frac{(n+3)^2}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+1,k=2t$ tức $n=6t+1$ thì $A_n=\frac{24+96t+72t^2}{24}=1+4t+3t^2=\frac{(n+3)^2-4}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+1,k=2t+1$ tức $n=6t+4$ thì $A_n=\frac{96+168t+72t^2}{24}=4+7t+3t^2=\frac{(n+3)^2-1}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+2,k=2t$ tức $n=6t+2$ thì $A_n=\frac{48+120t+72t^2}{24}=2+5t+3t^2=\frac{(n+3)^2-1}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+2,k=2t+1$ tức $n=6t+5$ thì $A_n=\frac{120+192t+72t^2}{24}=5+8t+3t^2=\frac{(n+3)^2-4}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
Tóm lại Số nghiệm tự nhiện của pt $x+2y+3z=n$ là $A_n=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
Bài 2: Đếm xem có bao nhiêu cách chia
cái kẹo giống nhau thành phần có số lượng khác nhau. (Mỗi phần ít nhất 1 cái kẹo)
Gọi $x_1,x_2,x_3,x_4$ lần lượt là số kẹo ở mỗi phần
Không mất tính tổng quát, giả sử $x_1<x_2<x_3<x_4$
Đặt $x_i=x_{i-1}-s_i$, với $i=2,3,4$. Ta có:
$32=x_1+x_2+x_3+x_4=x_1+x_2+2x_3+s_4=x_1+3x_2+2s_3+s_4=4x_1+3s_2+2s_3+s_4$
Ta đưa bài toán từ tìm số bộ nguyên dương $\left ( x_1,x_2,x_3,x_4 \right )$ thành đếm số bộ nguyên dương $\left ( x_1,s_2,s_3,s_4 \right )$
Đặt $y_1=x_1-1$, $y_i=s_i-1$, $i=2,3,4$, ta có:
$y_1+2y_2+...+4y_4=22$
Ta có:
$y_1+2y_2+...+4y_4=22$
$y_1 \leq 22$, $y_2 \leq 11$, $y_3 \leq 7$, $y_4 \leq 5$
Số bộ nguyên không âm $\left ( y_1,y_2,y_3,y_4 \right )$ chính là hệ số của $x^22$ trong đa thức sau:
$P\left ( x \right )=(1+x^4+...+x^{20})(1+x^3+...+x^{21})(1+x^2+...+x^{22})(1+x+...+x^{22})$
$=\frac{\left ( x^{24}-1 \right )^3(x^{23}-1)}{\left ( x-1 \right )...(x^4-1)}$
$=\frac{(x^{23}-1)(x^{24}-1)(x^{12}+1)^2(x^6+1)(x^2-x+1)(x^8+x^4+1)}{(x-1)^2}$
$=(...+x^{22}-2 x^{21}+4 x^{20}-2 x^{19}+4 x^{18}-2 x^{17}+3 x^{16}-x^{15}+3 x^{14}-2 x^{13}+3 x^{12}-x^{11}+2 x^{10}-x^9+2 x^8-x^7+2 x^6-x^5+x^4+x^2-x+1)(1+2x+3x^2+...)$
$=(...+x^{22}-2 x^{21}+5 x^{20}-2 x^{19}+4 x^{18}-2 x^{17}+3 x^{16}-x^{15}+3 x^{14}-2 x^{13}+3 x^{12}-x^{11}+2 x^{10}-x^9+2 x^8-x^7+2 x^6-x^5+x^4+x^2-x+1)(1+2x+3x^2+...)$
Hệ số $x^{22}$ trong đa thức trên là $1\times 1-2\times 2+5\times 3-2 \times 4+4 \times 5-2 \times 6+3 \times 7-8+3 \times 9-2 \times 10+3 \times 11-12+2\times 13-14+2 \times 15-16+2 \times 17-18+19+21-22+23=136$
Vậy số cách chia kẹo thoả mãn yêu cầu đề bài là $136$
Giải:
Bổ đề : $\text{Với }|a|<1\text{ thì }\sum_{i=0}^{\infty}a^i=\lim_{n\to\infty}\sum_{i=0}^{n}a^i=\lim_{n\to\infty}(1+a+a^2+...+a^n)=\lim_{n\to\infty}\frac{1-a^{n+1}}{1-a}=\frac{1}{1-a}$
Dùng PP hàm sinh :
Xét $|a|<1$ và $f(a)=\left(\sum_{x=0}^{\infty}a^x\right)\left(\sum_{y=0}^{\infty}a^{2y}\right)\left(\sum_{z=0}^{\infty}a^{3z}\right)$$=\sum_{x=0,y=0,z=0}^{\infty}A_{x,y,z}.a^{x+2y+3z}=\sum_{n=0}^{\infty}A_n.a^n$ (1)Ta thấy số nghiệm của pt(*) tương ứng chính là hệ số $A_n$ của $a^n$ trong khai triển $f(a)$
Mặt khác :
$f(a)=\frac{1}{1-a}.\frac{1}{1-a^2}.\frac{1}{1-a^3}=\frac{1}{(1-a)^3(1+a)(1+a+a^2)}$$=\frac{\frac{1}{8}}{1+a}+\frac{\frac{17}{72}}{1-a}+\frac{\frac{1}{4}}{(1-a)^2}+\frac{\frac{1}{6}}{(1-a)^3}+\frac{\frac{1}{9}(2+a)}{1+a+a^2}$
Mà ta có các khai triển sau (Maclaurin):
$\frac{1}{(1-a)^m}=(1-a)^{-m}=\sum_{k=0}^{\infty}\binom{-m}{k}(-1)^ka^k=\sum_{k=0}^{\infty}C_{k+m-1}^{m-1}a^k$
$\frac{1}{1+a+a^2}=(1-a).\frac{1}{1-a^3}=(1-a).\sum_{k=0}^{\infty}a^{3k}=\sum_{k=0}^{\infty}(a^{3k}-a^{3k+1})$
$\frac{2+a}{1+a+a^2}=(2+a)\sum_{k=0}^{\infty}(a^{3k}-a^{3k+1})=\sum_{n=0}^{\infty}(2a^{3k}-a^{3k+1}-a^{3k+2})$
Suy ra
$f(a)=\frac{1}{8}\sum_{n=0}^{\infty}(-1)^na^n+\frac{17}{72}\sum_{n=0}^{\infty}a^n+\frac{1}{4}\sum_{n=0}^{\infty}(n+1)a^n+\frac{1}{6}\sum_{n=0}^{\infty}\frac{(n+1)(n+2)}{2}a^n$$+\frac{1}{9}\sum_{k=0}^{\infty}(2a^{3k}-a^{3k+1}-a^{3k+2})$ (2)
Đồng nhất các hệ số của $a^n$ trong (1) và (2), ta có :
$\boxed{}$ Nếu $n=3k$ thì $A_n=\frac{(-1)^{3k}}{8}+\frac{17}{72}+\frac{3k+1}{4}+\frac{(3k+1)(3k+2)}{12}+\frac{2}{9}=\frac{3(-1)^k+21+36k+18k^2}{24}$
$\boxed{}$ Nếu $n=3k+1$ thì $A_n=\frac{(-1)^{3k+1}}{8}+\frac{17}{72}+\frac{3k+2}{4}+\frac{(3k+2)(3k+3)}{12}-\frac{1}{9}=\frac{3(-1)^{k+1}+27+48k+18k^2}{24}$
$\boxed{}$ Nếu $n=3k+2$ thì $A_n=\frac{(-1)^{3k+2}}{8}+\frac{17}{72}+\frac{3k+3}{4}+\frac{(3k+3)(3k+4)}{12}-\frac{1}{9}=\frac{3(-1)^{k}+45+60k+18k^2}{24}$
Vậy :
$\boxed{}$ Nếu $n=3k,k=2t$ tức $n=6t$ thì $A_n=\frac{24+72t+72t^2}{24}=1+3t+3t^2=\frac{(n+3)^2+3}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k,k=2t+1$ tức $n=6t+3$ thì $A_n=\frac{72+144t+72t^2}{24}=3+6t+3t^2=\frac{(n+3)^2}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+1,k=2t$ tức $n=6t+1$ thì $A_n=\frac{24+96t+72t^2}{24}=1+4t+3t^2=\frac{(n+3)^2-4}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+1,k=2t+1$ tức $n=6t+4$ thì $A_n=\frac{96+168t+72t^2}{24}=4+7t+3t^2=\frac{(n+3)^2-1}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+2,k=2t$ tức $n=6t+2$ thì $A_n=\frac{48+120t+72t^2}{24}=2+5t+3t^2=\frac{(n+3)^2-1}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
$\boxed{}$ Nếu $n=3k+2,k=2t+1$ tức $n=6t+5$ thì $A_n=\frac{120+192t+72t^2}{24}=5+8t+3t^2=\frac{(n+3)^2-4}{12}=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
Tóm lại Số nghiệm tự nhiện của pt $x+2y+3z=n$ là $A_n=\left\lfloor\frac{(n+3)^2+3}{12}\right\rfloor$
Bài 2: Đếm xem có bao nhiêu cách chia
cái kẹo giống nhau thành phần có số lượng khác nhau. (Mỗi phần ít nhất 1 cái kẹo)
Giải:
Gọi $x_1,x_2,x_3,x_4$ lần lượt là số kẹo ở mỗi phần
Không mất tính tổng quát, giả sử $x_1<x_2<x_3<x_4$
Đặt $x_i=x_{i-1}-s_i$, với $i=2,3,4$. Ta có:
$32=x_1+x_2+x_3+x_4=x_1+x_2+2x_3+s_4=x_1+3x_2+2s_3+s_4=4x_1+3s_2+2s_3+s_4$
Ta đưa bài toán từ tìm số bộ nguyên dương $\left ( x_1,x_2,x_3,x_4 \right )$ thành đếm số bộ nguyên dương $\left ( x_1,s_2,s_3,s_4 \right )$
Đặt $y_1=x_1-1$, $y_i=s_i-1$, $i=2,3,4$, ta có:
$y_1+2y_2+...+4y_4=22$
Ta có:
$y_1+2y_2+...+4y_4=22$
$y_1 \leq 22$, $y_2 \leq 11$, $y_3 \leq 7$, $y_4 \leq 5$
Số bộ nguyên không âm $\left ( y_1,y_2,y_3,y_4 \right )$ chính là hệ số của $x^22$ trong đa thức sau:
$P\left ( x \right )=(1+x^4+...+x^{20})(1+x^3+...+x^{21})(1+x^2+...+x^{22})(1+x+...+x^{22})$
$=\frac{\left ( x^{24}-1 \right )^3(x^{23}-1)}{\left ( x-1 \right )...(x^4-1)}$
$=\frac{(x^{23}-1)(x^{24}-1)(x^{12}+1)^2(x^6+1)(x^2-x+1)(x^8+x^4+1)}{(x-1)^2}$
$=(...+x^{22}-2 x^{21}+4 x^{20}-2 x^{19}+4 x^{18}-2 x^{17}+3 x^{16}-x^{15}+3 x^{14}-2 x^{13}+3 x^{12}-x^{11}+2 x^{10}-x^9+2 x^8-x^7+2 x^6-x^5+x^4+x^2-x+1)(1+2x+3x^2+...)$
$=(...+x^{22}-2 x^{21}+5 x^{20}-2 x^{19}+4 x^{18}-2 x^{17}+3 x^{16}-x^{15}+3 x^{14}-2 x^{13}+3 x^{12}-x^{11}+2 x^{10}-x^9+2 x^8-x^7+2 x^6-x^5+x^4+x^2-x+1)(1+2x+3x^2+...)$
Hệ số $x^{22}$ trong đa thức trên là $1\times 1-2\times 2+5\times 3-2 \times 4+4 \times 5-2 \times 6+3 \times 7-8+3 \times 9-2 \times 10+3 \times 11-12+2\times 13-14+2 \times 15-16+2 \times 17-18+19+21-22+23=136$
Vậy số cách chia kẹo thoả mãn yêu cầu đề bài là $136$
Thứ Tư, 22 tháng 6, 2016
Định lý EGZ
Định lý Erdős Pál, Abraham Ginzburg és Abraham Ziv:
Từ 2n-1 số nguyên cho trước, luôn chọn được n số sao cho tổng của chúng chia hết cho n.
Lời giải:
$\blacksquare$ ta chứng minh $\mathcal{E}(p)$ đúng với $p\in \mathbb{P}$
Với $p=2$ thì dễ thấy đúng ta xét với $p$ lẻ
gọi các số trong tập là $a_1,a_2,...,a_{2p-1}$
giả sử không tồn tại $p$ số nào chia hết cho $p$
$\Rightarrow \left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}\equiv 1(mod\ p)$
$\Rightarrow \sum_{1\le i_1<...<i_p\le 2p-1}\left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}\equiv \begin{pmatrix} 2p-1\\p \end{pmatrix}(mod\ p)$ $(*)$
ta có
$\begin{pmatrix} 2p-1\\p \end{pmatrix}\equiv \begin{pmatrix} 1\\1 \end{pmatrix}\begin{pmatrix} p-1\\ 0 \end{pmatrix}\not \equiv 0(mod\ p)$
ta sẽ chứng minh vế trái $(*)$ chia hết cho $p$,thật vậy ta có
$\sum_{1\le i_1<...<i_p\le 2p-1}\left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}=\sum_{s_1+s_2+...+s_p=p-1}\frac{(p-1)!}{s_1!s_2!...s_p!}\sum _{1\le i_1<...<i_p\le 2p-1}a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$ (thức ra từ chỉ cần $\sum _{1\le i_1<...<i_p\le 2p-1}a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$)
trong các số $s_1,s_2,...,s_p$ sẽ có $m \in \left [ 1,p-1 \right ]$ số bằng $0$ nên sẽ có $\begin{pmatrix} 2p-1-(p-m)\\m \end{pmatrix}=\begin{pmatrix} p+m-1\\ m \end{pmatrix}$ cách chọn các số $a_{i_j}$
mà $s_j=0$ do đó số $a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$ sẽ được lặp $\begin{pmatrix} p+m-1\\m \end{pmatrix}$ lần ( Có ý nghĩa: sau khi loại bỏ $p-m$ số có số mũ khác 0 thì cần m số (trong $2p-1-(p-m)$ số) có mũ bằng $0$ (vì $a_i^0..a_n^0=1$))
mặt khác
$\begin{pmatrix} p+m-1\\ m \end{pmatrix}\equiv \begin{pmatrix} 1\\0 \end{pmatrix}\begin{pmatrix} m-1\\m \end{pmatrix}\equiv 0(mod\ p)$ (hoặc có thể dùng định nghĩa nhị thức newton để chứng minh.)
$\Rightarrow p\mid VT_{(*)}$
điều này dẫn đến mâu thuẫn
$\blacksquare$ ta chứng minh nếu $\mathcal{E}(u)$ và $\mathcal{E}(v)$ đúng thì $\mathcal{E}(uv)$ đúng
gọi $2uv-1$ số nguyên dương là $a_1,a_2,...,a_{2uv-1}$
vì $2uv-1>2u-1$ nên tồn tại $u$ số có tổng chia hết cho $u$ và gọi tổng đó là $b_1$
lặp lại $2v-2$ lần ta có các tổng $b_1,b_2,...,b_{2v-2}$ chia hết cho $u$
do đó còn lại $2uv-1-u(2v-2)=2u-1$ số thì chọn được tổng $b_{2v-1}$ số chia hết cho $u$
mặt khác trong các số $b_1,b_2,...,b_{2v-1}$ ta sẽ chọn được $v$ số chia hết cho $v$
mặt khác $v$ số này cũng chia hết cho $u$ nên $uv$ số này $($ do mỗi tổng có $u$ số $)$ chia hết cho $uv$
vậy bài toán được chứng minh hoàn toán
Thứ Hai, 30 tháng 5, 2016
Dùng nguyên lí Dirichlet để giải bài toán tổ hợp - Phần 2
Bài toán: Tìm số tự nhiên n lớn nhát sao cho tồn tại n số nguyên không âm $x_1,x_2,..x_n$ không đồng thời bằng 0, sao cho với mọi $\varepsilon _1, \varepsilon _2,..\varepsilon _n$ $\in$ {-1;0;1} không đồng thời bằng 0 sao cho $n^3$ không chia hết cho $\varepsilon _1x_1+\varepsilon _2x_2+..\varepsilon _nx_n$
Lời giải.
Với n=9 ta chọn $1,2,2^2,..2^8$
Khi đó: $| \varepsilon _1+..+2^9\varepsilon _9|\le 1+2+..2^8<9^3$
Nếu $n\ge10$ không mất tính tổng quát, giả sử $n=10$ khi đó số tập con của S={$x_1,x_2,..z_10$} là $2^{10}$ và vì $2^{10}>10^3$ nên theo nguyên lí Dirichlet tồn tại hai tập A và B là tập con của S sao cho tổng các phần tử của A có cùng số dư với tổng các phần tử của B.
Khi đó đặt $\varepsilon _i=1$ nếu $x_i$ thuộc A nhưng không thuộc B, $\varepsilon _i=-1$ nếu $x_i$ thuôc B nhưng không thuộc A, bằng 0 trong trường hợp còn lại khi đó:
$\sum \varepsilon _ix_i \vdots n^3$
Lời giải.
Với n=9 ta chọn $1,2,2^2,..2^8$
Khi đó: $| \varepsilon _1+..+2^9\varepsilon _9|\le 1+2+..2^8<9^3$
Nếu $n\ge10$ không mất tính tổng quát, giả sử $n=10$ khi đó số tập con của S={$x_1,x_2,..z_10$} là $2^{10}$ và vì $2^{10}>10^3$ nên theo nguyên lí Dirichlet tồn tại hai tập A và B là tập con của S sao cho tổng các phần tử của A có cùng số dư với tổng các phần tử của B.
Khi đó đặt $\varepsilon _i=1$ nếu $x_i$ thuộc A nhưng không thuộc B, $\varepsilon _i=-1$ nếu $x_i$ thuôc B nhưng không thuộc A, bằng 0 trong trường hợp còn lại khi đó:
$\sum \varepsilon _ix_i \vdots n^3$
Chủ Nhật, 29 tháng 5, 2016
Dùng nguyên lí Dirichlet để giải bài toán tổ hợp-Phần 1
Bài toán: Gọi $n_1<n_2<..<n_{2000}<10^{100}$ là một số nguyên dương. Chứng minh rằng có thể tìm được hai tập A và B khác nhau không rỗng là tập con của {$n_1,n_2,..n_{2000}$} thỏa cấc điều kiện:
i) $|A|=|B|$
ii) $\sum_{x\in A}x=\sum_{x\in B}x$
iii) $\sum_{x\in A}x^2=\sum_{x\in B}x^2$
Lời giải
Lưu ý: $\binom{2000}{1000}$ là số hạng lớn nhất trong các số hạng $\binom{2000}{k}$.
Gọi S là tất cả tập con của tập {$n_1,n_2,..n_{2000}$} sao cho S có 1000 phần tử, ta có:
$0< \sum_{x\in S}x<1000.10^{100}$
$0< \sum_{x\in S}x^2<1000.10^{200}$
Vậy số các cặp $( \sum_{x\in S}x, \sum_{x\in S}x^2)$ ít hơn $10^{306}$
Mặt khác:
Số tập hợp chứa 1000 phần tử là: $\binom{2000}{1000}>\frac{\sum_{k=0}^{2000}\binom{2000}{k}}{2001}> \frac{2^{2000}}{2001}> \frac{10^{600}}{2001}>10^{306}$
Nên theo nguyên lí Dirichlet tồn tại hai tập hợp C và D chứa 1000 phần tử sao cho $( \sum_{x\in C}x, \sum_{x\in C}x^2)=( \sum_{x\in D}x, \sum_{x\in D}x^2)$
Loại bỏ các phần tử chung của C và D ta thu được hai tập A và B thỏa mãn điều kiện đề bài.
Chủ Nhật, 15 tháng 5, 2016
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:
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
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
Thứ Sáu, 13 tháng 5, 2016
Dùng đơn biến và số dư để giải bài toán tổ hợp
Bài toán: Bắt đầu với dãy: S=(a,b,c,d) của các số nguyên không âm. Đặt $S_1=T(S)=(|a-b|,|b-c|,|c-d|,|d-a|)$. Tương tự $S_2=T(S_1)$. Hỏi có tồn tại $S_i$ sao cho $S_i=(0;0;0;0)$
Giải
Chúng ta thử vài trường hợp:
(0, 3, 10, 13) → (3, 7, 3, 13) → (4, 4, 10, 10) → (0, 6, 0, 6) → (6, 6, 6, 6) → (0, 0, 0, 0)
(8, 17, 3, 107) → (9, 14, 104, 99) → (5, 90, 5, 90) → (85, 85, 85, 85) → (0, 0, 0, 0),
(91, 108, 95, 294) → (17, 13, 99, 203) → (4, 86, 104, 186) → (82, 18, 82, 182) → (64, 64, 100, 100) → (0, 36, 0, 36) → (36, 36, 36, 36) → (0, 0, 0, 0).
1) Đặt max S là phần tử lớn nhất của S. Khi đó $max S_{i+1} \le max S_i$ và $max S_{i+4}< max S_i$ ( Vì khi $max S_{i+1} = max S_i$ Khi $(S_i=(0, S_{i+1},a,b)$ tới $S_{i+3}$ nó sẽ giảm)
2) Sau nhiều nhất 4 bước, tất cả 4 số sẽ trở thành số chẵn. Thật vậy ta sẽ xét đồng dư 2. Do tính đối xứng nên ta chỉ xét trường hợp này ( các trường hợp khác tương tự) :
0001 → 0011 → 0101 → 1111 → 0000 và 1110 → 0011. Vì thế sau nhiều nhất 4 bước tất cả các số sẽ chia hết cho 2, sau nhiều nhất 8 bước chia hết $2^2$,..sau nhiều nhất 4k bước thì các số sẽ chia hết $2^k$ cho k thật lỡn ta sẽ có tất cả cá số đều bằng 0
Giải
Chúng ta thử vài trường hợp:
(0, 3, 10, 13) → (3, 7, 3, 13) → (4, 4, 10, 10) → (0, 6, 0, 6) → (6, 6, 6, 6) → (0, 0, 0, 0)
(8, 17, 3, 107) → (9, 14, 104, 99) → (5, 90, 5, 90) → (85, 85, 85, 85) → (0, 0, 0, 0),
(91, 108, 95, 294) → (17, 13, 99, 203) → (4, 86, 104, 186) → (82, 18, 82, 182) → (64, 64, 100, 100) → (0, 36, 0, 36) → (36, 36, 36, 36) → (0, 0, 0, 0).
1) Đặt max S là phần tử lớn nhất của S. Khi đó $max S_{i+1} \le max S_i$ và $max S_{i+4}< max S_i$ ( Vì khi $max S_{i+1} = max S_i$ Khi $(S_i=(0, S_{i+1},a,b)$ tới $S_{i+3}$ nó sẽ giảm)
2) Sau nhiều nhất 4 bước, tất cả 4 số sẽ trở thành số chẵn. Thật vậy ta sẽ xét đồng dư 2. Do tính đối xứng nên ta chỉ xét trường hợp này ( các trường hợp khác tương tự) :
0001 → 0011 → 0101 → 1111 → 0000 và 1110 → 0011. Vì thế sau nhiều nhất 4 bước tất cả các số sẽ chia hết cho 2, sau nhiều nhất 8 bước chia hết $2^2$,..sau nhiều nhất 4k bước thì các số sẽ chia hết $2^k$ cho k thật lỡn ta sẽ có tất cả cá số đều bằng 0
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.
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.
Thứ Hai, 2 tháng 5, 2016
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 ô.
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 ô.
Chủ Nhật, 1 tháng 5, 2016
Dùng phép song ánh để chứng minh bài toán tổ hợp- Phần 2
Hôm nay ta tiếp tục dùng phép song ánh để giải bài toán đếm trong tổ hợp.
Ví dụ 2: Cho tập A={1,2,..,2n}. Một tập con B của A gọi là một tập cân nếu trong tập đó số các số chẵn và các số lẻ bằng nhau. ( Tập rỗng là một tập cân). Tính số tập cân của A.
Giải.
Gọi N là họ các tập con của A có đúng n phần tử, B là một tập cân. $B_1, B_2$ tương ứng các tập số chẵn và lẻ của B thì $B_1=B_2$.
Ta xây dựng một ánh xạ như sau;
$f: B \rightarrow N$
Trong đó $f(B)=B_1 \cup (Y\setminus B_2)$
$\Rightarrow |f(B)|=|B_1|+|Y|-|B_2|$ vậy muốn cho $f(B)$ thuộc $N$ thì trước hết $Y$ phải có n phần tử và Y không có phần tử chung với $B_1$. Như vậy $Y$ phải tập tất cả số lẻ của tập $A$ ($|Y|=n)$
Nên f đơn ánh
Nếu có tập $M$ thuộc $N$. Kí hiệu $M_1$, $M_2$ là tập số chẵn số lẻ của M thì $|M_1|+|M_2|=n$. Ta phải tìm xây dựng $B_1,B_2$ theo $M_1, M_2$ sao cho $|B_1|=|B_2|$ thì $B_2=Y \setminus M_2$ và $B_1=M_1$. $\Rightarrow f(B)=M$.
Như vậy ta xây dựng song ánh giữa B và N.
Vậy A có tấp cả $C^n_{2n}$
Nhận xét: Tại sao lại xây dựng f đi từ B đến N ? Thực ra qua một vài phép liệt kê ta sẽ thấy !
Một số bài tập cho bạn đọc:
1/(Bài toán chia kẹo của Euler) Có m chiếc kẹo giống nhau chia cho n em bé. Hỏi có bao nhiêu cách chia?
Ví dụ 2: Cho tập A={1,2,..,2n}. Một tập con B của A gọi là một tập cân nếu trong tập đó số các số chẵn và các số lẻ bằng nhau. ( Tập rỗng là một tập cân). Tính số tập cân của A.
Giải.
Gọi N là họ các tập con của A có đúng n phần tử, B là một tập cân. $B_1, B_2$ tương ứng các tập số chẵn và lẻ của B thì $B_1=B_2$.
Ta xây dựng một ánh xạ như sau;
$f: B \rightarrow N$
Trong đó $f(B)=B_1 \cup (Y\setminus B_2)$
$\Rightarrow |f(B)|=|B_1|+|Y|-|B_2|$ vậy muốn cho $f(B)$ thuộc $N$ thì trước hết $Y$ phải có n phần tử và Y không có phần tử chung với $B_1$. Như vậy $Y$ phải tập tất cả số lẻ của tập $A$ ($|Y|=n)$
Nên f đơn ánh
Nếu có tập $M$ thuộc $N$. Kí hiệu $M_1$, $M_2$ là tập số chẵn số lẻ của M thì $|M_1|+|M_2|=n$. Ta phải tìm xây dựng $B_1,B_2$ theo $M_1, M_2$ sao cho $|B_1|=|B_2|$ thì $B_2=Y \setminus M_2$ và $B_1=M_1$. $\Rightarrow f(B)=M$.
Như vậy ta xây dựng song ánh giữa B và N.
Vậy A có tấp cả $C^n_{2n}$
Nhận xét: Tại sao lại xây dựng f đi từ B đến N ? Thực ra qua một vài phép liệt kê ta sẽ thấy !
Một số bài tập cho bạn đọc:
1/(Bài toán chia kẹo của Euler) Có m chiếc kẹo giống nhau chia cho n em bé. Hỏi có bao nhiêu cách chia?
Đây cũng chính là bài toán: “Tìm số nghiệm không âm của phương trình : 
($n, m \in N^*$).
Các bạn có thể nghiên cứu chuyên đề tại đây.
2( Lấy trong TLCT)/ Cho trước số nguyên dương n và số nguyên dương r thoả $r<n-r+1$. Giả sử X={1,2..n}. Hoi r có bao nhiêu tập con A của X đồng thời có tính chất:
+ Chứa r phần tử
+ Không chứa hai số nguyên liên tiếp.
(Gợi ý: Các bạn thử liệt kê như Vd 2 các bạn sẽ có hướng làm).
Thứ Năm, 28 tháng 4, 2016
Dùng phép song ánh để giải bài toán tổ hợp-Phần 1
Đối với một số bài tổ hợp đếm, thì thay vì đếm theo đề bài rất khó khăn ta có thể đếm bằng cách xây dựng một song ánh và áp dụng tính chất:
"Nếu có một phép song ánh đi từ tập X đến tập Y thì |X|=|Y| (trong đó X, Y là hai tập hữu hạn)". Và chuyển về một bài toán đơn giản hơn để tính toán.
Giải
Ta bắt đầu xây dựng một phép song ánh:
Gọi M là các số nguyên dương viết trong hệ thập phân có 2n chữ số, trong đó có n chữ số 1 và n chữ số 2. Ta sẽ chứng minh |M|=|N|
Với mỗi số có n chữ số gồm các chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2, ta nhân đôi thành số có 2n chữ số theo quy tắc sau: đầu tiên, hai phiên bản của số này được viết kề nhau thành số có có 2 chữ số, sau đó các chữ số 3 ở n chữ số đầu và các chữ số 4 ở n chữ số sau được đổi thành chữ số 1, các chữ số 3 ở n chữ số sau và các chữ số 4 ở n chữ số đầu được đổi thành chữ số 2.
Như thế ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh. Ta thấy với mỗi phần tử thuộc M đều được xác định bởi 1 phần tử N bằng cách ta cắt n chữ số đầu và n chữ số còn lại rồi cộng theo quy tắc 1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được các số gồm các chữ số 1,2,3,4 với số chữ số 1 bằng số chữ số 2.
Vậy ta có |M|=|N|
Số phần tử của |M|=$2^n.C^n_{2n}$ nên $|N|=2^n.C^n_{2n}$.
Như vậy qua phép song ánh ta đã đếm số phần tử của N bằng cách đơn giản hơn do chỉ cần đếm số phần tử của tập M.
Sở dĩ có phép cộng trên là do ta đã sử dụng đơn ánh để xây dựng tính chất từ $M$ sang $N$.
Như thế ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh. Ta thấy với mỗi phần tử thuộc M đều được xác định bởi 1 phần tử N bằng cách ta cắt n chữ số đầu và n chữ số còn lại rồi cộng theo quy tắc 1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được các số gồm các chữ số 1,2,3,4 với số chữ số 1 bằng số chữ số 2.
Vậy ta có |M|=|N|
Số phần tử của |M|=$2^n.C^n_{2n}$ nên $|N|=2^n.C^n_{2n}$.
Như vậy qua phép song ánh ta đã đếm số phần tử của N bằng cách đơn giản hơn do chỉ cần đếm số phần tử của tập M.
Sở dĩ có phép cộng trên là do ta đã sử dụng đơn ánh để xây dựng tính chất từ $M$ sang $N$.
Thứ Ba, 22 tháng 3, 2016
Nguyên lí Dirichlet và cách giải bằng tổng quát bài toán
Giải. Ta giải bài toán tổng quát sau
Cho hai dãy hữu hạn các số nguyên dương như sau:
$x_1 \le x_2 \le ..\le x_m\le n$; $y_1 \le y_2\ le...\le y_n \le m$ Khi đó tồn tại các chỉ số
$1 \le i_1 \le i_2 \le m; 1\le j_1 \le j_2 \le n$ sao cho:
$\sum_{i=i_1}^{i_2}x_i=\sum_{i=j_1}^{j_2}y_j$
Đặt: $a_p=\sum_{i=1}^{p}x_i (p \in Z, 1\le p \le m), b_q=\sum_{j=1}^{q}y_j(q \in Z, 1 \le q\le n)$
Vai trò của các số trên là như nhau nên ta có thể giả sử: $a_m \le b_n$
Lúc đó với mỗi p nhận giá trị từ 1 đến m tồn tại f(p) là chỉ số bé nhất mà $a_p \le b_{f(p)}$. Xét m hiệu:
$ b_{f(1)}-a_1; b_{f(2)}-a_2;.... b_{f(m)}-a_m. $
Ta chứng minh mọi hiệu đều bé hơn m. Thật vậy nếu có chỉ số p nào đó sao cho $m \le b_{f(p)}-a_p$ thì $m<b_{f(p)}$ suy ra f(p)>1 và
$m \le b_{f(p)-1}+y_{f(p)}-a_p$ nên $0 \le m-y_{f(p)} \le b_{f(p)-1}-a_p$ nên $a_p\le b_{f(p)-1}$ (mâu thuẫn)
Bây giờ nếu có 1 trong các $b_{f(i)}-a_i=0$ thì ta có cách chọn $i_1=j_1=1; i_2=i, j_2=f(i)$ thoả mãn đề bài
Nếu không có hiệu nào bằng không thì theo nguyên lí dirichlet tồn tại 2 hiệu bằng nhau tức là có r,s thoả mãn:
$b_{f(s)}-a_s=b_{f(r)}-a_r$ hay $b_{f(s)}-b_{f(r)}=a_s-a_r$
Chọn $i_1=r+1; i_2=s j_1=f(r)+1, j_2=f(s)$ ta cũng có đẳng thức đề bài.
Vậy ta có điều phải chứng minh.
Nhận xét: -Đôi khi tổng quát hoá bài toán lại là cách hữu hiệu để giải một bài toán rườm rà nào đó.
-Ta có thể thấy rằng mấu chốt của bài toán là giả sử $a_m \le b_n$ nếu như $b_n \le a_m$ thì sao ? do ta đã nói không mất tính tổng quát có nghĩa là nếu $b_n \le a_m$ thì chỉ việc thay x,z,m,i,p bởi y,b,n,j,q ta vẫn thu được lời giải chính xác.
- Chỉ số bé nhất f(p) chính là điều kiện chặt để giải bài toán ở đây ta đã dùng nguyên lí cực hạn
- Còn chứng minh mọi hiệu bé hơn m là để dùng dirichle
Đăng ký:
Bài đăng (Atom)