Bài tập to hợp tuyến tính có lời giải
Skip to content
Show Tổ hợp tuyến tính (Linear combination) là một trong những chủ đề cốt lõi trong lĩnh vực toán rời rạc (Discrete mathematics) được phát triển từ những bài toán sơ đẳng nhất, nền tảng nhất: bài toán đếm. Trong chương trình học THPT, lý thuyết tổ hợp tuyến tính được giới thiệu và thực hành thông qua các khái niệm về hoán vị (permutation), chỉnh hợp chập k (k-permutation), tổ hợp (combination),…. Tuy nhiên, vì khá nhiều lý do, việc “đếm” chỉ được các quý thầy cô dừng lại ở phần công thức, áp dụng công thức, mà chưa hình thành được tư duy và phương pháp đếm có tính nền tảng cho học sinh. Trong bài viết này, chúng ta không đi sâu vào lý thuyết mà đào sâu vào 1 bài tập, được chia sẻ khá nhiều và đương nhiên, vì không có nền tảng của việc “đếm” mà các lời giải chúng ta có thể thấy được đa phần đều sai. Thông qua phân tích bài tập này, ZeFro mong muốn góp một phần nhỏ trong việc xây dựng nền tảng tư duy toán học, tư duy phản biện cho bạn đọc Lưu ý: Bài viết này mang khá nhiều ý kiến chủ quan của người viết, nếu các bạn có những sự đóng góp cho bài viết hãy để lại trong phần bình luận. Với một số chú thích riêng của tác giả sẽ được ký hiệu NV. Một lưu ý sau cùng, các lời giải sai được dẫn trong bài viết về bản chất đã sai, chúng tôi không đả kích tổ chức, cá nhân nào đã đưa ra lời giải. Vì thế chúng tôi sẽ không chịu trách nhiệm nếu các tổ chức, cá nhân cảm thấy bị “xúc phạm” hay “tổn thương”. Vì sự thật là sự thật. Trước khi đi vào các bài tập sau đây chúng ta sẽ cùng nhau thống nhất một điều sau đây: Việc liệt kê và đếm trong bài toán tổ hợp tuyến tính là hoàn toàn bình thường (nguyên tắc vét cạn – brute force), không sai, các lý thuyết về tổ hợp tuyến tính: hoán vị, chỉnh hợp, tổ hợp,… là việc tổng quát hóa, quy luật hóa việc đếm. Vì thế nếu gặp các bài toán về tổ hợp tuyến tính, chúng ta có nhiều cách tiếp cận khác nhau. Hãy bắt đầu bằng một bài tập sau đây: Bài toán 1: Từ các chữ số {1, 2, 3} lập được bao nhiêu số tự nhiên mà mỗi số có 6 chữ số đồng thời thỏa mãn hai điều kiện sau: Mỗi chữ số có mặt 2 lần và hai chữ số giống nhau không đứng cạnh nhau: Lưu ý: Vì phải lặp lại yêu cầu đề bài thường xuyên nên trong bài viết này, khi người viết ghi dạng cú pháp “số có 6 chữ số” tức là đang nhắc đến nội dung của bài toán 1: “số có 6 chữ số lập từ các chữ số 1, 2, 3” Để bắt đầu chúng ta sẽ khảo sát một bài toán nhỏ hơn gần tương tự của bài toán trên tuy nhiên chỉ có một ràng buộc, với mục tiêu hình thành cách giải tổng quát hơn cho bài toán phía trên Bài toán 1.1: Từ các chữ số {2, 3}, chúng ta lập được bao nhiêu số tự nhiên mội số có 6 chữ số đồng thời thỏa mãn điều kiện sau: Mỗi chữ số có mặt 3 lần. Vậy với cách tiếp cận đầu tiên, chúng ta có thể liệt kê ra tất cả các số 6 chữ số lập từ 2 và 3 mà mỗi chữ số lặp lại 3 lần. Chúng ta hãy thử liệt kê kết quả của bài toán trên bằng các dòng lệnh python như sau: import itertools
listA = list(itertools.permutations("222333", 6))
listB = [''.join(element) for element in listA]
permutation_list = list(set(listB))
permutation_list.sort()
print(permutation_list)
Tổng cộng chúng ta có 20 hoán vị phù hợp với yêu cầu đề bài trên, tuy nhiên chúng ta có thể chưa có được hướng đi cụ thể. Vậy hãy cùng nhau phân tích:
Từ đó đáp án của của bài toán 1.1 có thể viết dưới dạng công thức như sau: Trước khi qua phân tích kế tiếp, chúng ta thử nhìn thêm một bài toán khác tương tự, tuy nhiên có thể khiến chúng ta bất ngờ: Bài toán 1.1.1: Từ các chữ số {2, 3}, chúng ta lập được bao nhiêu số tự nhiên mội số có 6 chữ số đồng thời thỏa mãn điều kiện sau: chữ số 2 có mặt 4 lần và chữ số 3 có mặt 2 lần. Lập luận tương tự như trên, thì ta được số lượng số có thể tìm được trông giống như sau: Và điều đặc biệt gì qua bài toán trên, điều đó tùy thuộc vào bạn đọc. Tổng quát hóa bài tập 1.1, chúng ta có bài toán sau:Bài toán 1.2: Với tập n phần tử , thiết lập số có chữ số sao cho mỗi chữ số trong đều xuất hiện k lần. Có bao nhiêu số Sử dụng lập luận tương tự như trên, hoặc phương pháp quy nạp chúng ta có thể tìm ra được đáp án cho bài toán trên: Như vậy, quay lại bài toán 1, từ các chữ số {1, 2, 3} chúng ta có thể lập được 90 số tự nhiên mà mỗi số có 6 chữ số thỏa mãn điều kiện: mỗi chữ số có mặt 2 lần. Chúng ta có thể kiểm tra tại phần đáp án
Nếu bạn muốn củng cố và hệ thống kiến thức cho các kỳ thi Tốt nghiệp, Đánh giá Năng lực Đại học, hãy sử dụng dịch vụ PEN của Học mãi. Trong các bài viết của ZeFro chỉ tập trung vào việc hiểu rõ các khải niệm cơ bản nhất. Và mặc định các bạn đã hiểu rõ các kiến thức căn bản trong sách giáo khoa 2. Khi phần bù trở thành gánh nặnga. Phân tích vế còn lại của bài toán 1Trong phần còn lại của bài toán 1, chúng ta còn lại một điều kiện nữa đó là: trong số có 6 chữ số thiết lập như trên, “hai chữ số giống nhau không đứng cạnh nhau”. Tới đây sự phân cực của các lời giải đúng và sai bắt đầu hình thành. Sự phân cực đó trông như thế nào, chúng ta hãy cùng nhau phân tích Lối mòn của tư duyTrong tác phẩm khá nổi tiếng về tâm lý học hành vi, Daniel Kahneman (1934, Nobel kinh tế 2002) đã chỉ ra [1]: đôi khi thông qua kinh nghiệm và suy diễn cảm tính chúng ta có thể bỏ qua những lập luận lý tính (logic) để đi đến ngay một kết luận. Điều này thể hiện rõ trong các đáp án sai (xem phần đáp án) nhằm giải quyết bài toán 1 bên trên, đều có một điểm chung:
Quay trở lại tiêu đề của phần này, chúng ta nói rằng khi phần bù trở thành gánh nặng, vì sao lại thế? Như những gì đã phân tích, khi tính toán có liên quan đến phần bù, chúng ta đều “mong muốn” rằng phần bù được tính toán có ít trường hợp và dễ dàng tính toán. Chính cái tâm lý trên đã che mờ các nhận định của chúng ta. Vì thế gánh nặng ở đây không phải nằm ở vấn đề, mà chính xác hơn, nằm ở chúng ta – những người đang cố giải quyết vấn đề. Vậy trong bài toán này có bao nhiêu hướng tiếp cận?Chúng ta có thể thấy được thông qua các phân tích như trên và thông qua bảng liệt kê mà chúng ta có thể tạo ra thông qua lập trình như sau:
Trong cách tiếp cận trực tiếp, từ yêu cầu của bài toán 1, chúng ta có thể thấy được yêu cầu chặt chẽ của đề bài “hai chữ số giống nhau không đứng cạnh nhau” tạo một điều kiện cho chúng ta xây dựng lập luận như sau:
Từ các suy luận nêu trên, chúng ta có thể mô hình hóa việc lựa chọn các hoán vị của theo đặc tính phụ thuộc của chúng theo sơ đồ cây như hình bên dưới (xem phiên bản chất lượng cao tại đây – NV). Tuy nhiên đến đây vẫn chưa phải đáp án cuối cùng, nếu chúng ta xem xét hoán vị cụ thể thì ta thấy chữ số 1 được lặp lại 3 lần, không thỏa mãn yêu cầu “mỗi chữ số chỉ lặp lại 2 lần”, vì thế chúng ta phải “cắt tỉa” sơ đồ cây bên dưới theo điều kiện: nếu chữ số nào bắt đầu lặp lại lần thứ 3, chúng ta phải tỉa đi cành gắn liền với chữ số đó (Tham khảo đáp án – NV) Mô hình cây biểu diễn cho các trường hợp hoán vị có thể có thỏa mãn yêu cầu 2 chữ số giống nhau không đứng cạnh nhau. Tham khảo đáp án, xem hình ảnh chất lượng cao tại đâyViệc tìm đáp án người viết xin nhường lại cho bạn đọc, các bạn có thể tham khảo các lời giải đúng, lời giải sai tại phần đáp án và cùng thảo luận với các tác giả tại phần bình luận. Trong phần kế tiếp chúng ta chỉ thảo luận về việc hình thành lập luận cho phương pháp đếm trực tiếp mà không đi sâu hơn vào lời giải và đáp số chính xác.
Nếu bạn cảm thấy bài viết này hoặc các bài viết khác hữu ích cho các bạn, hãy chia sẻ bài viết này giúp ZeFro. Nếu bạn cảm thấy công việc của team giúp ích cho bạn, rất mong được bạn mời team một ly café
Trong phần kế tiếp…Thảo luận về lý thuyết cốt lõi của hoán vị (permutation), chỉnh hợp chập k (k-permutation) và tổ hợp (combination) và các ứng dụng trên thực tế của tổ hợp tuyến tính. 4. Bài học ở đây là gì?
Tài liệu tham khảo
Ý tưởng và thực hiện: Thomas Ho |