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

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!
Nội dung trích xuất từ tài liệu:
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ên1 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 đổiliê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ủanó. 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 (haytí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ếtthú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 → . . . → α nBà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 haykhô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ậttoá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 đốitượ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ộtmà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êntiếp. 226 Hội thảo khoa học, Hưng Yên 25-26/02/20172 Sử dụng đại lượng bất biến để giải bài toán tổ hợp2.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àutấ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ắngBan đầu, có 1 ô đen, 63 ô trắngKế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ành8 − 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ắngthà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ôngthể đạ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ộtchú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 × 8nà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 ...