zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Sử dụng đại lượng bất biến và đơn biến trong toán tổ hợp

Chia sẻ: AndromedaShun _AndromedaShun | Ngày: | Loại File: PDF | Số trang:15

Báo xấu

39
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hai đại lượng thường được sử dụng là bất biến và đơn biến. Bất biến là một đại lượng không thay đổi trong quá trình chúng ta thực hiện các phép biến đổi. Đơn biến là một đại lượng thay đổi, nhưng chỉ theo một chiều. Dựa vào đại lượng bất biến hoặc đơn biến, ta có thể giải quyết được các bài toán về thuật toán được đưa ra trong bài viết sau đây. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sử dụng đại lượng bất biến và đơn biến trong toán tổ hợp

Hội thảo khoa học, Hưng Yên 25-26/02/2017 SỬ DỤNG ĐẠI LƯỢNG BẤT BIẾN VÀ ĐƠN BIẾN TRONG TOÁN TỔ HỢP Vũ Thị Thuần THPT Chuyên Hưng Yên 1 Kiến thức cơ bản Trong một loạt bài toán ta thường gặp tình huống sau, một hệ thống nào đó thay đổi liên tục trạng thái của mình và cần phải chỉ ra một điều gì đó về trạng thái cuối cùng của nó. Khảo sát cục bộ sau đó tất cả các lần thay đổi như vậy là một việc làm rất phức tạp và khó khăn. Nhưng ta lại có thể trả lời câu hỏi mà bài toán yêu cầu nhờ tính một đại lượng đặc biệt nào đó đặc trưng cho tất cả các trạng thái của hệ thống đó. Hai đại lượng thường được sử dụng là bất biến và đơn biến. Bất biến là một đại lượng (hay tính chất) không thay đổi trong quá trình chúng ta thực hiện các phép biến đổi. Đơn biến là một đại lượng (hay tính chất) thay đổi, nhưng chỉ theo một chiều (tức là tăng lên hoặc giảm xuống). Dựa vào đại lượng bất biến hoặc đơn biến, ta có thể giải quyết được các bài toán về thuật toán. Bài toán mở rộng 1. (Bài toán tìm kiếm thuật toán). Cho trạng thái ban đầu α0 và trạng thái kết thúc αn . Hỏi có hay không thuật toán T trên A sao cho khi thực hiện T hữu hạn lần ta thu được αn ? T T T T α o → α1 → α2 → . . . → α n Bài toán mở rộng 2. Cho thuật toán T trên A và trạng thái ban đầu α. a) Xét trạng thái β ∈ A. Hỏi có thể nhận được β từ α sau hữu hạn lần thực hiện thuật toán T hay không? b) Tìm tập hợp α gồm tất cả các trạng thái có thể nhận được từ α sau hữu hạn bước thực hiện thuật toán T α = { β ∈ A : β = T n (α)} Các bất biến thường được sử dụng là tính chẵn lẻ, số dư trong một phép chia, một tổng, một tích, một biểu thức đại số. Đôi khi người ta còn sử dụng sự tô màu, tức là chia các đối tượng đang xét ra làm các nhóm (mỗi nhóm gồm các đối tượng được đánh dấu cùng một màu). Trên thực tế phương pháp sử dụng đại lượng đơn biến hoặc bất biến được tiến hành như sau: Tính một đại lượng nào đó bằng 2 cách, đầu tiên nó được tính ở trạng thái ban đầu và trạng thái cuối cùng, sau đó khảo sát sự thay đổi của nó qua một số lần thay đổi nhỏ liên tiếp. 226
Hội thảo khoa học, Hưng Yên 25-26/02/2017 2 Sử dụng đại lượng bất biến để giải bài toán tổ hợp 2.1 Bất biến liên quan đến tính chia hết (hoặc số dư trong một phép chia) a) Bất biến là tính chẵn, lẻ. Ví dụ 1. Cho một bàn cờ kích thước 8 × 8, tô đen một ô bất kì. Mỗi bước cho phép đổi màu tất cả các ô trên cùng một hàng hoặc một cột (ô đen thay bằng ô trắng và ngược lại). Hỏi có khi nào tất cả các ô trên bàn cờ cùng màu không? Nhận xét 1. + Việc khảo sát tất cả các phương án đổi màu trong bài toán là không thực hiện được, ta thử xem có quy luật nào chi phối tất cả các phương án này không? Ta xem xét sự thay đổi số lượng ô đen và ô trắng Ban đầu, có 1 ô đen, 63 ô trắng Kết thúc có 64 ô đen, 0 ô trắng (hoặc 64 ô trắng, 0 ô đen) Mỗi bước thực hiện sẽ đổi màu 8 ô (1 hàng hoặc 1 cột), giả sử trước bước đổi màu thứ k, có xk ô đen và 64 − xk ô trắng. Bước đổi màu k biến a ô đen thành a ô trắng, 8 − a ô trắng thành 8 − a ô đen. Như vậy, sau bước đổi màu thứ k, số ô đen là xk − a + 8 = xk + (8 − 2a), số ô trắng 64 − xk + (2a − 8). Từ đó, ta có được nhận xét về sự thay đổi số lượng ô trắng, đen sau mỗi phép đổi màu. Lời giải. Mỗi bước thực hiện sẽ đổi màu 8 ô (1 hàng hoặc 1 cột), giả sử trước bước đổi màu thứ k, có xk ô đen, và 64 − xk ô trắng. Bước đổi màu k biến a ô đen thành a ô trắng, 8 − a ô trắng thành 8 − a ô đen. Như vậy, sau bước đổi màu thứ k, số ô đen là xk − a + 8 = xk + (8 − 2a), số ô trắng 64 − xk + (2a − 8). Như vậy, sau mỗi lần thực hiện, thì số ô đen tăng hoặc giảm một số chẵn. Ban đầu có 1 ô đen, như vậy, sau mỗi bước đổi màu, thì số lượng ô đen vẫn là một số lẻ. Như vậy, không thể đạt được trạng thái có 64 ô đen, 0 ô trắng hoặc 0 ô đen, 64 ô trắng. Ví dụ 2. Cho một bàn cờ kích thước 9 × 9, gồm 1 ô đen và 80 ô trắng. Thực hiện thuật toán, mỗi lần thay đổi màu tất cả các ô trên cùng 1 hàng hoặc 1 cột (ô đen thay bằng ô trắng và ngược lại). Hỏi có khi nào tất cả các ô trên bàn cờ cùng màu đen không? Nhận xét 2. Thuật toán tương tự như bài trước, tuy nhiên, mỗi lần thực hiện thuật toán sẽ đổi màu 9 ô, như vậy tính chẵn lẻ của số lượng ô đen không bất biến. Tuy nhiên, để ý kĩ một chút, ta hoàn toàn có thể đưa bài toán về bài toán 1: Xét hình vuông 8 × 8 ở 1 góc mà chứa ô đen. Khi đó, việc thực hiện thuật toán của đề bài sẽ hoặc không thay đổi hình vuông 8 × 8 này, hoặc thay màu tất cả các ô trên cùng một hàng hoặc một cột. Lời giải. Giả sử ô màu đen nằm ở phần hình vuông 8 × 8 được tô đậm trên hình vẽ. Khi đó, mỗi lần thực hiện thuật toán thì hoặc không làm thay đổi hình vuông 8 × 8 này, hoặc sẽ đổi màu 1 hàng hoặc 1 cột của hình vuông 8 × 8 này. Như vậy, theo bài toán 1 thì số ô đen 227
Hội thảo khoa học, Hưng Yên 25-26/02/2017 trong hình vuông 8 × 8 này luôn là số lẻ. Tức là không xảy ra trường hợp cả 64 ô đều màu đen. Vậy không xảy ra trường hợp cả bàn cờ màu đen. Ví dụ 3. 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 liệu có thể xảy ra trường hợp một người được 7 điểm và người kia được 10 điểm được không? Lời giải. Gọi S(n) là tổng số điểm của cả hai người sau ván thứ n. Ta có S(n + 1) = S(n) + 2, Do đó, S(n) bất biến theo modun 2. Suy ra S(n) ≡ S(0) ≡ 0( mod 2), ∀n ≥ 0 Vậy không thể xảy ra trường hợp một người được 7 điểm, một người được 10 điểm. Nhận xét 3. Tính bất biến ở đây là tính chẵn lẻ của tổng số điểm của hai ngươi chơi. Ví dụ 4. Viết các số 1, 2, 3, . . . , 2014 lên bảng. Thực hiện thuật toán, mỗi lần xóa đi hai số a, b bất kì và viết thêm số c = | a − b| . Chứng minh rằng số còn lại cuối cùng trên bảng là một số lẻ. Lời giải. Vì a + b + ( a − b) = 2a nên a + b và a − b cùng tính chẵn, lẻ. Gọi S(n) là tổng các số trên bảng sau bước thứ n. Vì sau mỗi bước, tổng a + b được thay bởi c = | a − b| nên S(n) giữ nguyên tính chẵn, lẻ, hay bất biến theo modun 2. Mặt khác S(0) = 1 + 2 + .. + 2014 = 1007.2015 là số lẻ nên S(n) là lẻ với mọi n. Vậy số cuối cùng còn lại trên bảng là một số lẻ. 228
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Nhận xét 4. Tính bất biến ở đây là tính chẵn lẻ của tổng các số trên bảng. 2.2 Bài tập tương tự Bài 1 (Trích đề thi Vô địch Liên Xô - 1975). Trên bảng ta viết một số chữ số 0, một số chữ số 1 và một số chữ số 2. Sau đó ta cứ xóa đi một cặp hai chữ số khác nhau và thay thế vào đó một chữ số khác với hai chữ số đã xóa. Chứng minh rằng: Nếu trong kết quả cuối cùng trên bảng chỉ còn một chữ số thì kết quả đó không phụ thuộc vào thứ tự các cặp chữ số được xóa Bài 2. Cho dãy số 1, 2, 3, 4, . . . , 2013. Mỗi lần thay hai số a, b bởi số a − b. Hỏi có khi nào thu được toàn số 0 hay không? Thay 2013 bằng số tự nhiên N, tìm điều kiện của N để kết quả cuối cùng thu được toàn số 0? Bài 3. Cho một bàn cờ 7 × 7, tô đen 4 ô ở 4 góc. Thực hiện thuật toán, mỗi lần thay đổi màu 1 hàng hoặc một cột (ô đen thay bằng ô trắng và ngược lại). Hỏi có khi nào tất các ô trên bàn cờ cùng màu không? b) Bất biến liên quan đến tính chia hết cho một số lớn hơn 2 hoặc số dư trong một phép chia cho một số lớn hơn 2. Ví dụ 5. (Đề thi chọn đội tuyển dự thi HSGQG tỉnh Bắc Ninh, năm 2007) Trên bàn có 2007 viên bi gồm 667 bi xanh, 669 bi đỏ, 671 bi vàng. Thực hiện thuật toán như sau, mỗi lần lấy đi 2 viên bi khác màu và đặt thêm 2 viên bi có màu còn lại. Hỏi có thể nhận được trạng thái mà trên bàn chỉ còn lại các viên bi cùng màu được không? Lời giải. Gọi X (n), D (n) và V (n) tương ứng là số bi màu xanh, số bi màu đỏ và số bi màu vàng sau bước thứ n. Xét các đại lượng X (n) − D (n), D (n) − V (n), V (n) − X (n). Vì mỗi lần lấy đi 2 viên bi khác màu và đặt thêm 2 viên bi có màu còn lại nên các đại lượng X (n) − D (n), D (n) − V (n), V (n) − X (n) bất biến theo modun 3. Ta có X (0) − D (0) = −2, D (0) − V (0) = 2, V (0) − X (0) = 4. Nên số dư của các đại lượng này khi chia cho 3 sau mỗi lần thực hiện thuật toán là 1; 2; 1. Ta lại thấy, số bi ở trên bàn luôn không thay đổi (mỗi lần thực hiện, lấy đi 2 viên và đặt thêm 2 viên khác), vậy nếu trên bàn chỉ còn các viên bi cùng màu tức là số viên bi đỏ, xanh, vàng còn lại là một hoán vị của tập 2007, 0, 0, vậy các đại lượng X (n) − D (n), D (n) − V (n), V (n) − X (n) đều chia hết cho 3 (mâu thuẫn). Từ đó, suy ra không thể nhận được trạng thái mà trên bàn chỉ còn lại các viên bi cùng màu. Nhận xét 5. Việc lấy thêm đi 2 viên bi khác nhau và đặt thêm 2 viên bi có màu còn lại tạo ra bất biến về hiệu số các viên bi khi chia cho 3 ở bài toán. 229
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Ví dụ 6. Mỗi bước cho phép chọn 1 số a, phân tích a thành tích hai số m, n và viết lên bảng m ± 2, n ± 2 tùy ý (ví dụ a = 99 = 9 × 11, 9 − 2 = 7, 11 + 2 = 13, như vậy có thể viết lên bảng số 7 và số 13 thay cho số 99). Hỏi sau một số bước như vậy,từ số 99. . . ..99 (2012 chữ số 9) có thu được trên bảng một dãy gồm toàn các số 9 không? Lời giải. Nếu a là một số chia cho 4 dư 3 thì trong 2 số m, n có một số chia 4 dư 1, một số chia 4 dư 3. Một số chia 4 dư 1 thì cộng hay trừ 2 đều chia 4 dư 3. Vậy, sau khi thực hiện phép thay đổi thì từ 1 số chia 4 dư 3 luôn tồn tại 1 số chia 4 dư 3 còn lại. Số 99. . . ..99 (2012 chữ số 9) chia 4 dư 3, như vậy, sau một số bước biến đổi được chỉ ra ở đề bài thì cuối cùng, luôn tồn tại một số chia 4 dư 3. Một dãy gồm toàn số 9, tức là dãy gồm toàn số chia 4 dư 1. Vậy không thể thu được dãy số như trên. Nhận xét 6. Bất biến trong bài toán là sự tồn tại một số chia 4 dư 3 trong dãy. Ví dụ 7. Trên bảng có hai số 1 và 2. Thực hiện việc ghi số theo quy 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ể ghi được các số 2010 và 11111 hay không? Lời giải. Dãy các số được viết là 1, 2, 5, 11, 17, . . . Dễ dàng chứng minh được các số được viết thêm trên bảng đều chia cho 3 dư 2. Bất biến trên cho phép ta loại trừ được số 2010 trong dãy các số được viết trên bảng. Tuy nhiên, bất biến đó không cho phép ta loại trừ số 11111. Ta đi tìm một bất biến khác. Quan sát các số được viết và quy tắc viết thêm số, ta có c = a + b + ab ⇒ c + 1 = ( a + 1)(b + 1). Và nếu cộng thêm 1 vào các số thuộc dãy trên, ta có dãy mới 2, 3, 6, 12, 18, . . . Như vậy, nếu cộng thêm 1 vào các số viết thêm thì các số này đều có dạng 2n .3m với m ∈ N. Do 11111 + 1 = 11112 = 3.8.463 nên không thuộc dãy các số viết được. Do đó không thể viết được các số 2010 và 11111. Nhận xét 7. Bài toán trên sử dụng 2 bất biến. 2.3 Bài tập tương tự Bài 4. Các số tự nhiên 0, 1, 2, 3, . . . được viết trong các ô của một bảng ô vuông kích thước 2003 × 2003 theo vòng xoáy trôn ốc (xoáy ngược chiều kim đồng hồ) sao cho số 0 nằm ở ô trung tâm (tâm của bảng). Các dòng và cột của bảng được đánh số tăng dần từ dưới lên trên và từ trái sang phải (bắt đầu từ số 1). a) Số 2004 nằm ở dòng nào, cột nào? Tại sao? b) Thực hiện thuật toán sau, lần đầu tiên, thay số 0 ở ô trung tâm bởi 1998; mỗi lần tiếp theo, cho phép lấy ra 12 số trong 12 ô liên tiếp trong cùng một hàng hoặc trong cùng một cột hoặc trong cùng một hình chữ nhật 3 × 4 rồi tăng mỗi số đó lên một đơn vị. Hỏi sau một số lần như vậy ta có thể làm cho tất cả các số trong bảng đều là bội của 2004 hay không? Tại sao? 230
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Bài 5. Ở xứ sở nọ, nàng công chúa bị một con rồng hung hãn 100 đầu bắt đi. Chàng hoàng tử lên đường đi cứu công chúa, chàng có 2 thanh kiếm, thanh 1 chặt được 21 đầu rồng, thanh 2 chặt được 3 đầu rồng nhưng rồng lại mọc thêm 2012 đầu. Nếu hoàng tử chặt được hết đầu của rồng thì cứu được công chúa. Hỏi hoàng tử có cứu được công chúa không? Nếu số lượng đầu rồng ban đầu là N, N thỏa mãn điều kiện gì thì hoàng tử cứu được công chúa? 2.4 Bất biến là một tổng, một tích, một biểu thức đại số. Ví dụ 8. Một dãy gồm có 19 phòng. Ban đầu mỗi phòng có một người. Sau đó, cứ mỗi ngày có hai người nào đó chuyển sang hai phòng bên cạnh nhưng theo hai chiều ngược nhau, Hỏi sau một số ngày, có hay không trường hợp mà (a) Không có ai ở phòng có thứ tự chẵn. (b) Có 10 người ở phòng cuối. Lời giải. Đánh số các phòng theo thứ tự từ 1 đến 19 Ta cho mỗi vị khách một thẻ ghi số phòng mình đang ở. Gọi S(n) là tổng các số ghi trên thẻ của tất cả các vị khách trong ngày thứ n. Vì mỗi ngày có hai người nào đó chuyển sang hai phòng bên cạnh nhưng theo hai chiều ngược nhau nên S(n) không hề thay đổi. Vậy S(n) = S(1) = 1 + 2 + 3 + · · · + 19 = 190. a) Vì có lẻ người nên nếu không ai ở phòng có thứ tự chẵn thì S(n) là tổng của 19 số lẻ, tức là S(n) là số lẻ, mâu thuẫn. Vậy trường hợp này không xảy ra. b) Nếu có 10 người ở phòng cuối (phòng 19) thì S(n) > 19.10 = 190, mâu thuẫn.Vậy trường 231
Hội thảo khoa học, Hưng Yên 25-26/02/2017 hợp này cũng không xảy ra. Nhận xét 8. Bất biến của bài toán là tổng các số ghi trên thẻ của tất cả các vị khách. Ví dụ 9. Xét một bảng vuông 4 x 4 ô. Tại mỗi ô của bảng vuông có chứa dấu “+” hoặc dấu “- ”. Mỗi lần thực hiện, cho phép đổi dấu của tất cả các ô trên cùng một hàng hoặc cùng một cột. Giả sử bảng hình vuông ban đầu có 1 dấu “+” và 15 dấu “-”. Hỏi có thể đưa bảng ban đầu về bảng có toàn dấu “+” được không? Lời giải. Thay tất cả các dấu “+” bằng 1 và dấu “ - ” bằng −1. Mỗi lần thực hiện đổi dấu tất cả các ô trên cùng 1 hàng hoặc 1 cột, tức là đổi dấu của 4 số nên tích của 16 số trên bảng là không thay đổi. Tích của 16 số ban đầu là −1, sau mỗi lần biến đổi vẫn là −1. Nếu bảng toàn dấu “+” tức là tích của 16 số trên bảng là 1. Như vậy, dù có dù có thực hiện bao nhiêu lần thì từ bảng vuông ban đầu không thể đưa về bảng vuông toàn dấu “+”. Nhận xét 9. Bất biến trong bài toán là tích tất cả các số trên các ô của bảng. 1 2 3 80 Ví dụ 10. Trên bảng có các số ; ; ;... . 80 80 80 80 Mỗi lần thực hiện, cho phép xóa đi hai số a, b bất kì và thay bởi a + b − 2ab. Hỏi sau 1987 lần thực hiện phép xóa, số còn lại trên bảng là số nào? Lời giải. Giả sử các số trên là a1 , a2 , a3 , . . . , ak . Xét tích P = (2a1 − 1)(2a2 − 1) . . . (2ak − 1). Khi đó, sau mỗi lần biến đổi, tích trên bị mất đi hai thừa số (2a − 1)(2b − 1) và được thêm vào thừa số 2( a + b − 2ab) − 1 = −(2a − 1)(2b − 1) Tức là sau mỗi lần biến đổi giá trị tuyệt đối của tích P là không thay đổi. 40 1 Vì tích ban đầu bằng 0 (do bảng ban đầu có chứa số = ) nên sau mỗi lần biến đổi thì 80 2 tích này luôn bằng 0. 1 Vậy số còn lại cuối cùng trên bảng là s thỏa mãn 2s − 1 = 0, hay s = . 2 Nhận xét 10. Bất biến trong bài toán là tích tất cả các giá trị của hàm số y = 2x − 1tại các số trên bảng. Ví dụ 11. Cho đa thức P( x ) = ax2 + bx + c, có thể thực hiện một trong hai phép biến đổi a) Đổi chỗ a và c b) Đổi biến x bởi x + t với t ∈ R. Hỏi từ x2 − 31x − 3 có thể thu được x2 − 20x − 12 không? Tìm mối liên hệ của hai đa thức P( x ) và Q( x ) sao cho từ đa thức này có thể thu được đa thức kia bởi hai phép biến đổi nói 232
Hội thảo khoa học, Hưng Yên 25-26/02/2017 trên. Lời giải. Xét biểu thức P( x + t) = a( x + t)2 + b( x + t) + c = ax2 + (2at + b) x + at2 + c có ∆ = (2at + b)2 − 4a( at2 + c) = 4a2 t2 + 4abt + b2 − 4a2 t2 − 4ac = b2 − 4ac. Xét biểu thức P1 ( x ) = cx2 + bx + a có ∆ = b2 − 4ac. Như vậy, cả 2 phép biến đổi trên không làm thay đổi đại lượng ∆ ( ∆ bất biến với hai phép biến đổi). Xét P( x ) = x2 − 31x − 3 có ∆ = 312 + 4.3 = 973 Q( x ) = x2 − 20x − 12 có ∆ = 202 + 4.12 = 448 Vậy từ P( x ) ta không thể thu được Q( x ) thông qua hai phép biến đổi trên. Hai đa thức P( x ) và Q( x ) mà từ đa thức này có thể thu được đa thức kia bởi hai phép biến đổi nói trên khi chúng có giá trị của biệt thức ∆ bằng nhau. Nhận xét 11. Đại lượng bất biến là biệt thức ∆. 2.5 Bài tập tương tự Bài 6. Tại mỗi đỉnh của đa giác lồi A1 A2 . . . A1993 ta ghi một dấu “+” hoặc một dấu “-” sao cho trong 1993 dấu đó có cả dấu “+” và dấu “-”. Thực hiện việc thay dấu như sau, mỗi lần thay dấu đồng thời tại tất cả các đỉnh của đa giác theo quy tắc - Nếu dấu tại Ai và Ai+1 là như nhau thì dấu tại Ai được thay là dấu “+” - Nếu dấu tại Ai và Ai+1 là khác nhau thì dấu tại Ai được thay là dấu “+” (Quy ước A1994 là A1 ). Chứng minh rằng, tồn tại số nguyên k sao cho khi thực hiện liên tiếp k lần phép thay dấu nói trên, ta được đa giác A1 A2 . . . A1993 mà dấu tại mỗi đỉnh Ai (i = 1, 1993) trùng với dấu của đỉnh đó ngay sau lần thay dấu thứ nhất. Bài 7. Trên bảng cho đa thức f ( x ) = 3x2 + 4x + 3. Thực hiện trò chơi sau, nếu trên bảng đã có đa thức P( x ) thì được phép viết thêm lên bảng một trong hai đa thức sau 1 1 Q ( x ) = x 2 f ( + 1), R ( x ) = ( x − 1)2 f ( ). x x−1 Hỏi sau một số bước ta có thể viết được đa thức g( x ) = x2 + 10x + 9. 2.6 Bài toán tô màu. Ví dụ 12. Bàn cờ vua 8 × 8 bị mất hai ô ở hai góc đối diện. Hỏi có thể lát phần còn lại của bàn cờ bởi các quân Domino 2 × 1 được không? Lời giải. Mỗi quân Domino lát vào bàn cờ luôn chiếm một ô trắng và một ô đen. Do đó, nếu lát được phần còn lại của bàn cờ thì số ô trắng và số ô đen bằng nhau. Nhưng do hai ô ở đối diện của bàn cờ là hai ô cùng màu nên số ô màu trắng và số ô màu đen trong phần còn lại của 233
Hội thảo khoa học, Hưng Yên 25-26/02/2017 bàn cờ không bằng nhau. Vậy không lát được phần còn lại của bàn cờ bằng các quân Domino. Nhận xét 12. Tô các ô của bàn cờ đan xen bằng 2 màu, xét số lượng các ô của từng màu. Ví dụ 13. Cho một bảng ô vuông kích thước kích thước 8 × 8 được điền số như sau Cho phép thực hiện việc thay đổi các số trong bảng theo quy tắc, mỗi lần lấy tất cả các số nằm trong hình vuông kích thước 3 × 3 hoặc 4 × 4 rồi tăng mỗi số lên 1 đơn vị. Hỏi khẳng 234
Hội thảo khoa học, Hưng Yên 25-26/02/2017 định sau đúng hay sai ? Với mỗi cách điền số ban đầu, nhờ việc thực hiện liên tiếp phép thay số nói trên đối với bảng số ban đầu ta sẽ nhận được bảng 8 × 8 mà ở mỗi ô vuông con của bảng đó là một số chia hết cho 3. Lời giải. Tô màu bảng như hình vẽ. Nhận xét 1. Bất kể hình vuông con 3 × 3 nào cũng đều chứa đúng 6 ô vuông đen hoặc 9 ô vuông đen. Bất kể hình vuông con 4 × 4 nào cũng đều chứa đúng 12 ô đen. Do đó, sau mỗi lần thay số, ta không làm thay đổi số dư trong phép chia cho 3 của tổng các số trong các ô của phần gạch chéo. Tổng các số trong các ô ở phần bôi đen ở trên chia 3 dư 2, nên tổng các số sau các bước biến đổi cũng chia 3 dư 2, tức là không thể đạt được trạng thái mà số trong mọi ô vuông con đều chia hết cho 3. Ví dụ 14. Hình tròn được chia thành 2011 hình dẻ quạt. Xếp 2012 viên kẹo vào các phần dẻ quạt. Mỗi bước, cho phép chuyển hai viên ở cùng một phần sang hai phần kề khác hướng. Chứng minh rằng đến lúc nào đó có ít nhất 1006 phần có chứa kẹo. Lời giải. Nhận xét 2. Quá trình trên là không dừng lại, vì việc thực hiện mỗi bước không làm thay đổi số viên kẹo ban đầu. Có 2011 hình dẻ quạt, 2012 viên kẹo, nên sau mỗi bước luôn tồn tại một hình dẻ quạt có lớn hơn hoặc bằng 2 viên kẹo (nguyên lí Đirichle), nói cách khác, sau mỗi bước thì luôn có thể thực hiện được bước tiếp theo. Nhận xét 3. đến một lúc nào đó, 2 phần cạnh nhau bất kì có kẹo (ít nhất là một ô có kẹo). Giả sử điều này không đúng, tức là tồn tại hai hình dẻ quạt kề nhau không bao giờ có kẹo. Bỏ 2 hình dẻ quạt này đi, có thể coi 2009 hình dẻ quạt còn lại là một chuỗi 2009 ô hình chữ nhật thẳng hàng. Như vậy quá trình này dừng lại được. Vậy điều giả sử là sai. Tức là đến một lúc nào đó 2 phần cạnh nhau bất kì thì có kẹo. Lúc này, chia 2011 ô thành 1006 phần như sau: 1 ô có kẹo, 1005 cặp ô kề nhau. Khi đó, mỗi cặp ô sẽ có ít nhất 1 ô có kẹo, như vậy sẽ có ít nhất 1006 ô có kẹo. Nhận xét 4. 2 ô kề nhau có kẹo sau bước nhảy vẫn luôn có kẹo. Xét 2 ô kề nhau có kẹo, nếu lấy kẹo từ 2009 ô còn lại để thực hiện phép nhảy thì 2 ô này vẫn luôn có kẹo, nếu lấy kẹo từ 1 trong 2 ô này để thực hiện phép nhảy, vì lấy 2 viên kẹo và chuyển sang 2 phần bên nó, nên sẽ chắc chắn sẽ chuyển kẹo vào ô còn lại. Vậy trong mọi tình huống, 2 ô này luôn có kẹo. 235
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Ví dụ 15. Điền 29 số nguyên dương đầu tiên vào các ô vuông con của bảng 6 × 5 như sau (bảng 1 ). Hình 1: Bảng 1 Cho phép đổi vị trí các số trong bảng theo quy tắc,mỗi lần, lấy 1 số nằm ở ô kề với ô trống rồi chuyển số đó sang ô trống. Hỏi nhờ việc thực hiện liên tiếp một số hữu hạn lần phép chuyển số nói trên đối với bảng ban đầu, ta có thể nhận được bảng số sau (bảng 2) không? Hình 2: Bảng 2 Lời giải. Giả sử nhờ phép chuyển số theo quy tắc của đề bài, từ bảng 1 ta có thể nhận được bảng 2. (1) Ta coi ô trống của mỗi bảng là ô được điền số 0. Với mỗi bảng số nhận được trong quá trình chuyển số, ta liệt kê tất cả các số trong bảng theo thứ tự từ trái qua phải, từ trên xuống dưới. Khi đó, ứng với mỗi bảng số ta sẽ có một hoán vị của 30 số tự nhiên đầu tiên. Và do đó, từ giả thiết (1) cho thấy, từ hoán vị (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 ) (gọi là 236
Hội thảo khoa học, Hưng Yên 25-26/02/2017 hoán vị I) ta có thể nhận được hoán vị (29, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 1 ) (gọi là hoán vị 2) nhờ việc thực hiện liên tiếp 1 số hữu hạn lần phép đổi chỗ các số hạng trong hoán vị theo quy tắc, mỗi lần, lấy một số khác 0 của hoán vị rồi đổi vị trí của số hạng đó và 0 cho nhau. (2) Giả sử ( a1 , a2 , . . . , a30 ) là một hoán vị của 30 số tự nhiên đầu tiên. Ta gọi cặp số ( ai , a j ) là cặp số ngược của hoán vị vừa nêu nếu ai > a j và i < j. Dễ thấy, sau mỗi lần thực hiện phép đổi chỗ các số hạng theo quy tắc (2) đối với hoán vị ( a1 , a2 , . . . , a30 ) thì số cặp số ngược của hoán vị sẽ tăng hoặc giảm một số lẻ đơn vị. (3) Ta có số cặp số ngược của hoán vị I là 12, số cặp số ngược của hoán vị II là 67. Từ đó kết hợp với (3) suy ra từ hoán vị I ta chỉ có thể nhận được hoán vị II sau 1 số lẻ lần thực hiện phép đổi chỗ các số hạng. Điều này cho thấy, nếu từ bảng 1 ta nhận được bảng 2 thì số lần chuyển số phải là số lẻ. (4) Tô màu tất cả các ô vuông con của bảng 6 × 5 bởi 2 màu xanh, đỏ sao cho 2 ô kề nhau có 2 màu khác nhau. Thế thì, sau mỗi lần chuyển số, số 0 sẽ được chuyển từ ô có màu này sang ô có màu kia. Và vì thế, do số 0 ở bảng 1 và số 0 ở bảng 2 nằm ở hai ô có màu giống nhau nên từ bảng 1 chỉ có thể nhận được bảng 2 sau một số chẵn lần chuyển số. Điều này mâu thuẫn với (4). Vậy từ bảng 1 ta không thể nhận được bảng 2 nhờ phép chuyển số theo quy tắc của đề bài. Nhận xét 13. Nhờ việc tô màu các ô vuông con trong bảng, ta tìm được số lần chuyển số là một số chẵn. Từ các suy luận về cặp số ngược, ta tìm được số lần chuyển số là một số lẻ. Từ đó có được kết quả của bài toán. Trong bài toán này, phát hiện và sử dụng cặp số ngược có vai trò quan trọng. Cặp số ngược cũng được sử dụng trong bài toán sau Ví dụ 16. Ở các vị trí khác nhau của một đường đua ô tô vòng tròn cùng một thời gian có 25 ô tô xuất phát theo cùng một hướng. Theo thể lệ cuộc đua, các ô tô có thể vượt lẫn nhau, nhưng cấm không được vượt đồng thời hai xe cùng lúc. Các ô tô đến đích là các điểm mà chúng xuất phát ban đầu cùng một lúc. Chứng minh rằng trong suốt cuộc đua có một số chẵn lần vượt nhau của các ô tô. Lời giải. Ta sơn 1 trong số 25 ô tô màu vàng, còn các ô tô khác đánh số thứ tự là 1, 2, . . . , 24 theo thứ tự mà chúng ở thời điểm ban đầu sau ô tô màu vàng (theo chiều chuyển động của các ô tô). Ở tâm dủa đường đua ta sẽ đặt một cái bảng để ghi số thứ tự của các ô tô sắp xếp sau ô tô vàng sau mỗi lần các ô tô vượt nhau, tức là ta được một hoán vị của 1, 2, . . . , 24. Trường hợp 1: Mỗi lần 2 ô tô trong các ô tô từ 1 đến 24 vượt nhau thì trên bảng vẽ có 2 số liền nhau đổi chỗ cho nhau. trường hợp 2: Nếu trước khi có lần vượt của một ô tô nào với ô tô vàng, các số trên bảng lập thành một hoán vị a1 , a2 , . . . , a24 thì sau lần vượt đó sẽ có hoán vị a2 , a3 , . . . , a24 , a1 . Từ đó hoán vị trên có thể chuyển xuống hoán vị dưới bằng 23 phép chuyển vị, tức là phép đổi chỗ 2 số đứng liền nhau. 237
Hội thảo khoa học, Hưng Yên 25-26/02/2017 2.7 Bài tập tương tự Bài 8 (IMO - 2004). Ta định nghĩa viên gạch hình móc câu là hình gồm 6 ô vuông đơn vị như hình vẽ dưới đây, hoặc hình nhận được do lật hình đó (sang trái, sang phải, lên trên, xuống dưới) hoặc hình nhận được do xoay hình đó đi một góc. Hãy xác định tất cả các hình chữ nhật m × n, trong đó m, n là các số nguyên dương sao cho có thể lát hình chữ nhật đó bằng các viên gạch hình móc câu. Bài 9 (VMO - 1991). Cho bảng 1991 × 1992. Kí hiệu (m, n) là ô vuông nằm ở giao của hàng thứ m và cột thứ n. Tô màu các ô vuông của bảng theo quy tắc sau, lần thứ nhất tô 3 ô (r, s), (r + 1, s + 1), (r + 2, s + 2); 1 ≤ r ≤ 1989, 1 ≤ s ≤ 1990, từ lần thứ hai, mỗi lần tô đúng ba ô chưa có màu nằm cạnh nhau trong cùng một hàng hoặc cùng một cột. Hỏi bằng cách nào đó có thể tô màu được tất cả các ô của bảng được không? Bài 10 (VMO - 2006). Xét bảng ô vuông 4m × n (m, n là các số nguyên dương lớn hơn 3). Thực hiện trò chơi sau, mỗi lần đặt 4 viên bi vào 4 ô của bảng (mỗi ô một viên bi) mà 4 ô đó tạo thành một trong những hình dưới đây. Hỏi sau một số lần ta có thể nhận được bảng mà số bi trong các ô bằng nhau được không nếu a) m = 2004 và n = 2006? b) m = 2005 và n = 2006 ? 238
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Bài 11. Cho n(n ≥ 2) học sinh đứng thành hàng dọc. Sau mỗi lần cô giáo thổi còi, có 2 em đổi chỗ cho nhau. Hỏi sau một số lẻ lần thổi còi, ta có thể thấy tất cả các em học sinh đều đứng ở vị trí ban đầu của mình hay không? 3 Sử dụng đại lượng đơn biến để giải bài toán tổ hợp Ví dụ 17. Xét bảng ô vuông m × n(m, n ≥ 2). Trong mỗi ô của bảng ta điền một số thực. Thực hiện thuật toán như sau, mỗi lần lấy ra một hàng hoặc một cột có tổng các số nhỏ hơn 0 và đổi dấu tất cả các số trong hàng (hoặc cột) đó. Chứng minh rằng sau hữu hạn bước ta nhận được bảng mà tổng các số mỗi hàng và tổng các số trong mỗi cột là số không âm. Lời giải. Gọi S(n) là tổng tất cả các số trong bảng sau bước thứ n. Ta có, S(n + 1) > S(n), ∀n > 0. Do đó, S(n) là một hàm đơn biến. Mặt khác, số trạng thái có thể nhận được là hữu hạn nên chỉ có thể thực hiện thuật toán hữu hạn lần và ta nhận được bảng thỏa mãn yêu cầu bài toán. Ví dụ 22. Cho một dãy phòng dài vô hạn, được đánh số 1, 2, 3, . . . Có một số hữu hạn người sống trong dãy phòng. Mỗi ngày có hai người sống ở hai phòng cạnh nhau chuyển sang hai phòng khác nhau theo hai hướng ngược nhau nhưng không được tráo đổi vị trí cho nhau. Chứng minh rằng việc chuyển phòng đó dừng lại sau hữu hạn ngày. Lời giải. Ta đưa cho mỗi người một chìa khóa, trên đó có ghi số phòng của mình đang ở. Gọi S(n) là tích các số viết trên các chìa khóa ở ngày thứ n. Ta có S ( n + 1) k ( k + 1) = < 1, ∀n ≥ 1 S(n) (k − 1)(k + 2) Trong đó k và k + 1 là các phòng có người chuyển. Do đó, S(n) là một đơn biến. Do S(n) giảm và S(n) ∈ N∗ nên việc chuyển phòng phải dừng lại sau hữu hạn ngày. Ví dụ 18. Tô đen 09 ô của bàn cờ 10 × 10. Mỗi lần tô màu đen một ô chưa tô nếu nó kề với ít nhất hai ô đen (kề được hiểu là chung cạnh). Có thể tô màu hết bàn cờ hay không? Nếu là 10 ô thì sao? Nếu là hình vuông n × n thì lúc đầu cần tô đen ít nhất bao nhiêu ô để có thể tô đen cả bàn cờ. Lời giải. Chu vi những hình đen hoặc không giảm, hoặc giảm 2, hoặc giảm 4. Tổng chu vi những hình đen ban đầu nhỏ hơn hoặc bằng 36. Chu vi bàn cờ 10 × 10 là 40. Như vậy, không thể tô đen cả bàn cờ. Ví dụ 19 (VMO 2012). Cho số nguyên dương n. Có n học sinh nam và nnhọc sinh nữ xếp thành một hàng ngang, theo thứ tự tùy ý. Mỗi học sinh (trong số 2n học sinh vừa nêu) được cho một số kẹo bằng đúng số cách chọn ra hai học sinh khác giới với X và đứng ở hai phía của X. Chứng minh rằng tổng số kẹo mà tất cả 2n học sinh nhận được không vượt quá 1 2 3 n ( n − 1). 239
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Lời giải. Gọi các bạn nam lần lượt là x1 , x2 , . . . , xn và các bạn nữ lần lượt là y1 , y2 , . . . , yn . Bằng tính toán trực tiếp ta thấy rằng nếu các bạn nam nữ xếp xen kẽ x1 , y1 , x2 , y2 , . . . , xn , yn 1 thì tổng số kẹo của 2n bạn đúng bằng n(n2 − 1). 3 Để chứng minh kết luận của bài toán ta sẽ chứng tỏ rằng một cách xếp hàng bất kì đều có thể chuyển dần về cách xếp xen kẽ như trên mà trong quá trình chuyển tổng số kẹo mà các bạn nhận được không giảm đi. Giả sử một cách xếp hàng bất kì đã có đúng r bạn nam và đúng r bạn nữ ở cuối được xếp xen kẽ (0 ≤ r < n). Không mất tổng quát, ta có thể giả sử hàng có một trong hai dạng sau i) . . . , yr+1 , xr+k , . . . , xr+1 , xr , yr , xr−1 , yr−1 , . . . , x1 , y1 | {z } | {z } k bạn nữ liên tiếp k bạn nam liên tiếp ii) . . . , xr+1 , yr+k , . . . , yr+1 , xr , yr , xr−1 , yr−1 , . . . , x1 , y1 , khi k > 1. | {z } | {z } k bạn nữ liên tiếp k bạn nam liên tiếp Trong trường hợp i), ta chuyển bạn yr+1 đến vị trí ngay trước bạn xr . Khi đó chỉ có số kẹo của các bạn yr+1 , xr+k , . . . , xr+1 thay đổi. Bằng tính toán trực tiếp ta thấy tổng số kẹo tăng một lượng là (k2 − k). Trong trường hợp ii), ta chuyển bạn xr+1 đến vị trí ngay trước bạn yr+1 . Khi đó chỉ có số kẹo của các bạn xr+1 , yr+k , . . . , yr+2 thay đổi. Ta tính được tổng số kẹo cũng tăng một lượng là ( k 2 − k ). Như vậy, sau không quá n lần chuyển thì hàng được xếp xen kẽ nam, nữ. Do đó tổng số kẹo 1 trong một cách xếp bất kì luôn nhỏ hơn hoặc bằng n(n2 − 1). 3 240

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.