Bài tập to hợp tuyến tính có lời giải

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.

Các bài viết trong chuỗi bài viết về Tổ hợp tuyến tính

1. Tất cả đều xuất phát từ việc đếm

a. Bài toán mà ai cũng có thể giải sai

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. Phân tích bài toán

Để 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:

• Với số có 6 chữ số lập ra từ tập hợp {a, b, c, d, e, f} thì có tất cả 6! = 720 hoán vị
• Tuy nhiên, nếu trường hợp các hoán vị được tạo thành từ 6 chữ số khác nhau, tuy nhiên trong trường hợp này, các chữ số có sự lặp lại. Vậy có thể giả sử và , như vậy thì 2 hoán vị và cùng biểu diễn giá trị: 223233. Không chỉ có 2 hoán vị trên biểu diễn giá trị 223233, vậy câu hỏi được đặt ra là có bao nhiêu con số bị lặp lại như trên trong 6! hoán vị ta tìm được?

• Lấy trường hợp của số 223233 đã đề cập ở trên nếu chỉ xét các số có dạng giống như , chúng ta có 3! hoán vị như thế. Tương tự, nếu chỉ xét các số có dạng giống như , chúng ta có 3! hoán vị. Từ đây chúng ta có tổ hợp của các số tạo ra từ {a, b, c, d, e, f} cùng biểu diễn cho số 223233 là: 3!.3! = 36 tổ hợp, hay chính xác hơn là 36 lần lặp lại[Hãy tìm hiểu thêm về tích Descartes của 2 tập hợp].
• Tương tự lập luận trên, chúng ta đều có thể tìm được dữ kiện chung: mỗi số trong 6! hoán vị ban đầu đều đã được lặp lại 3!.3! = 36 lần

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ặng

a. Phân tích vế còn lại của bài toán 1

Trong 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ư duy

Trong 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:

• Với yêu cầu “hai chữ số giống nhau không đứng cạnh nhau”, điều này đưa chúng ta đến 2 ấn tượng như sau: thứ nhất, việc sắp xếp số có 6 chữ số mà 2 chữ số giống nhau không đứng cạnh nhau sẽ khó hơn việc tìm số có 6 chữ số mà tồn tại ít nhất một cặp chữ số giống nhau nằm kề nhau; thứ hai, theo “kinh nghiệm” của chúng ta, trong bài này phương pháp được sử dụng đó là phương pháp phần bù, ta sẽ tính số hoán vị 6 chữ số mà tồn tại ít nhất một cặp chữ số giống nhau nằm kề nhau sau đó lấy phần bù ta sẽ tìm được đáp số chính xác.
• Về mặt lập luận, lập luận như trên là đúng, tuy nhiên, khi mọi người bắt tay vào làm, cái sai trong tiềm thức chúng ta sẽ dần lộ rõ ra: các đáp án sai đều tính toán các số 2 chữ số giống nhau đứng cạnh nhau đều dựa vào việc tìm các cặp có dạng như sau [Xem phần đáp án], tách các cặp số dựa trên các cặp vị trí [1, 2], [3, 4], [5, 6], ví dụ như các số sau: 112323, 212133, 312213,… Tuy nhiên hãy nhìn vào hình bên dưới, hãy chú ý vào ô màu xanh dương, và chúng ta sẽ thảo luận tiếp.

• Trong việc chia tách như chúng ta đã thảo luận ở trên chúng ta đã quên một trường hợp: nếu như các chữ số giống nhau đứng cạnh nhau theo các cặp vị trí [2, 3], [4, 5], ví dụ như: 122313, 232113,… thì lập luận như trên đã bỏ qua trường hợp này, dẫn đến đáp án sẽ xem những số này thuộc về tập hợp các số có 2 chữ số giống nhau không nằm kề nhau, đây chính là sai lầm trong việc lập luận theo lối kinh nghiệm như trên.

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:

1. Chúng ta có thể tiếp cận bằng phương pháp phần bù, tuy nhiên, phải tìm được tất cả các trường hợp mà các số có 6 chữ số mà các chữ số giống nhau cạnh nhau [có thể tham khảo 1 bài giải theo hướng này trong phần đáp án – NV]
2. Hoặc chúng ta sẽ tiếp cận trực tiếp hơn, tìm số có 6 chữ số lập nên từ các chữ số 1, 2, 3, mỗi chữ số xuất hiện 2 lần mà không có 2 chữ nào nằm cạnh nhau. Cách tiếp cận trực tiếp này có vẻ sẽ dễ dàng hơn, vì sao?

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:

• Xét số có dạng
• Vì vai trò của 3 chữ số 1, 2, 3 đều như nhau trong bài toán 1 vì thế, khi chúng ta cố định chữ số a = 1 và tính toán số hoán vị của theo chữ số a thì kết quả của phương pháp đếm [hoán vị khi a = 1] sẽ bằng với trường hợp cố định a = 2 hoặc a = 3. Như vậy, số lượng hoán vị thỏa mãn yêu cầu bài toán 1 sẽ là: .
• Xét trường hợp cố định chữ số a = 1, ta sẽ thấy được rằng các hoán vị của sẽ có các điều kiện như sau: chữ số b phải khác 1 và từ chữ số b ta có chuỗi suy luận [tham khảo hình bên dưới]

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]

Việ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ì?

• Thưa các thầy cô, hãy kiểm tra kĩ lưỡng các bài toán trước khi đưa ra, đôi khi cách lý luận của người ra đề có nhiều lỗ hỏng nếu không được kiểm chứng với các phương pháp khác.
• Hãy cẩn thận với các loại kiến thức mì ăn liền, luôn sẵn sàng thực hành tư duy phản biện, đặt câu hỏi. Vì một lúc nào đó, lớp sương mù giả dối bị đánh bay đi, để lại chân lý mà chúng ta luôn luôn chờ đợi.
• Đôi khi phương pháp đơn giản nhất lại là phương pháp hữu hiệu nhất đưa ta đến giải pháp cho một vấn đề. Và đôi khi lý luận suông [lý luận không dựa trên logic, ngụy biện] là thứ xa rời giải pháp đúng đắn nhất.

“Các lời dạy […] như ngón tay chỉ mặt trăng. Nếu đã thấy mặt trăng thì có thể biết rằng cái dùng để chỉ mặt trăng đó [ngón tay] không phải là mặt trăng”

Trích Kinh Viên Giác theo Phật học Tinh hoa, học giả Thu Giang Nguyễn Duy Cần

Tài liệu tham khảo

1. Daniel Kahneman, “Tư duy Nhanh và Chậm”,

Ý tưởng và thực hiện: Thomas Ho