Ứng dụng tính chẵn lẻ trong giải các bài toán Tổ hợp

Thuvientoan.net xin gửi đến bạn đọc tài liệu Ứng dụng tính chẵn lẻ trong giải các bài toán Tổ hợp.

Bên cạnh các bài toán đếm hoặc chứng minh trên các đại lượng không có sự biến đổi, các bài toán Tổ hợp cũng thường mô tả quá trình mà ở đó, có một hoặc nhiều đối tượng được tác động, thay đổi liên tục. Cách tiếp cận phổ biến để xử lí là tìm kiếm tính bất biến, tìm đặc điểm đặc trưng nào đó của sự thay đổi nhằm giảm bớt độ phức tạp.
Trong chương này, chúng ta sẽ đề cập đến hai yếu tố rất cơ bản nhưng có vai trò đáng kể trong hướng tiếp cận như thế, đó là tính chẵn lẻ và ước chung lớn nhất sinh ra từ tổ hợp tuyến tính của nhiều số. Đặc điểm chung của hai yếu tố này là tính bất biến, không phụ thuộc hoặc ít phụ thuộc vào thứ tự thực hiện các tác động, giúp cho công việc lập luận trở nên đơn giản hơn rất nhiều.

Tính chẵn lẻ
Đây là một trong các yếu tố cơ bản nhất của Số học. Khi cần dùng nó trong Tổ hợp, ta thường xem xét một số tình huống mà một đối tượng, đại lượng nào đó chỉ có hai trạng thái. Tác động vào đó, từ trạng thái này, đối tượng sẽ đổi thành trạng thái kia và ngược lại, chẳng hạn như việc tung đồng xu với mặt sấp ngửa, tắt mở bóng đèn, lượt thích trên facebook (click lẻ lần thì được hiển thị đã thích còn click chẵn lần thì được hiển thị chưa thích),... Như thế, nếu tác động vào đối tượng đó một số lẻ lần, trạng thái sẽ thay đổi.

Ước chung lớn nhất và thuật toán Euclid
Khi nói đến nhiều đối tượng, đặc trưng của chúng thường được sử dụng chính là ước chung lớn nhất. Đó là yếu tố không bao giờ thay đổi khi xét các tổ hợp tuyến tính của nhóm đối tượng. Tại đây, ta gọi đại lượng ax + by là một tổ hợp tuyến tính của x, y với a, b ∈ Z.

Tải tại đây.

THEO THUVIENTOAN.NET

Liên hệ
Tin liên quan
    2020 Copyright © THUVIENTOAN.NET Web Design by Nina.vn
    Online: 9   |   Total: 132935
    Hotline tư vấn miễn phí: 0907233487
    icon zalo

    Ứng dụng tính chẵn lẻ trong giải các bài toán Tổ hợp