🔥 [TSA · TƯ DUY TỔ HỢP] Chọn Không Kề Nhau, Xác Suất Chia Hết, Mã Đi Tuần & Cánh Tay Robot
Chuyên đề TSA Tư duy Toán học: chọn vị trí không kề nhau trên hàng ngang và quanh bàn tròn, xác suất lập số chia hết cho 5, 15, 25, bài toán quân mã đổi chỗ…
C(n−k+1, k)
THPT AI LUKATO · TSA Tư duy Toán học · Tổ hợp & mô hình hóa
Tư duy tổ hợp: đếm có cấu trúc , không đếm mò
Năm dạng bài “nhìn lạ” của TSA và đề thi THPT: chọn các vị trí không kề nhau trên hàng ngang và quanh bàn tròn, xác suất lập số chia hết, quân mã đổi chỗ, cánh tay robot quay quanh một khớp. Mỗi dạng có một ý tưởng chìa khóa biến bài toán rối rắm thành một phép tính ngắn. Toàn bộ đề bài do LUKATO biên soạn mới; mọi đáp số đều được kiểm chứng bằng máy tính (vét cạn hoặc tính toán chính xác).
🎯 TSA · Tư duy Toán học
5 ý tưởng chìa khóa
4 mô phỏng tương tác · 2 bàn cờ chơi thử
12 câu luyện tập tự chấm
00 Bản đồ chuyên đề
Năm dạng bài, năm ý tưởng chìa khóa
Phần Tư duy Toán học của TSA có 60 phút cho nhiều dạng câu hỏi (nhiều lựa chọn, đúng/sai, kéo thả, điền đáp án). Với những bài dưới đây, đếm từng trường hợp có thể mất 10 phút; nhìn ra cấu trúc thì chỉ cần 1–2 phút.
Dạng · Tình huống · Ý tưởng chìa khóa · Kết quả
1 · Chọn k trong n vị trí xếp hàng ngang, không có hai vị trí kề nhau · “Dồn hàng”: b_i=a_i-(i-1) là một song ánh · \dbinom{n-k+1}{k}
2 · Như trên nhưng các vị trí xếp quanh vòng tròn · Xét riêng vị trí số 1 được chọn hay không · \dfrac{n}{n-k}\dbinom{n-k}{k}
3 · Lập ngẫu nhiên số có các chữ số khác nhau, hỏi xác suất chia hết · Chữ số tận cùng + tổng chữ số theo lớp dư mod 3 · Đếm bộ chữ số rồi mới xếp
4 · Các quân mã trên bàn cờ nhỏ phải đổi chỗ cho nhau · Vẽ đồ thị nước đi rồi “duỗi thẳng”; quân không vượt được nhau · Đánh giá số nước tối thiểu
5 · Cánh tay gồm nhiều thanh, khóa góc, quay quanh gốc · Khoảng cách từ đầu mút tới gốc không đổi khi quay · Cộng vectơ, lấy độ dài
Nguyên tắc chung Trước khi đếm, hỏi: “Có cách mã hóa nào biến điều kiện khó thành điều kiện quen thuộc không?” Dạng 1 biến “không kề” thành “chọn tự do”. Dạng 4 biến bàn cờ thành một đường thẳng. Dạng 5 biến chuyển động quay thành một đường tròn.
01 Dạng 1 · Không kề nhau trên hàng ngang
Dồn hàng: biến “không kề” thành “chọn tự do”
Định lí Chứng minh bằng song ánh
Số cách chọn k vị trí trong n vị trí xếp thành hàng ngang (đánh số 1,2,\dots,n) sao cho không có hai vị trí nào kề nhau là \dbinom{n-k+1}{k}\qquad(0\le k\le n).
Mã hóa. Gọi các vị trí được chọn là a_1<a_2<\dots<a_k. Điều kiện không kề: a_{i+1}-a_i\ge2.
Dồn hàng. Đặt b_i=a_i-(i-1), tức là dịch vị trí thứ i sang trái i-1 ô. Khi đó b_{i+1}-b_i=(a_{i+1}-a_i)-1\ge1, nên 1\le b_1<b_2<\dots<b_k\le n-(k-1)=n-k+1.
Ngược lại , mọi bộ b_1<\dots<b_k chọn tự do trong \{1,\dots,n-k+1\} cho lại bộ a_i=b_i+(i-1) thỏa mãn điều kiện. Đây là song ánh, nên số cách bằng \dbinom{n-k+1}{k}.
Cách nhìn thứ hai: nhét vào khe Xếp trước n-k vị trí không được chọn thành hàng; chúng tạo ra n-k+1 khe (kể cả hai đầu). Mỗi vị trí được chọn nằm ở một khe khác nhau, nên có \dbinom{n-k+1}{k} cách.
Mở rộng: khoảng cách ít nhất d Nếu yêu cầu a_{i+1}-a_i\ge d, đặt b_i=a_i-(d-1)(i-1), ta được \dbinom{n-(d-1)(k-1)}{k} cách. Công thức không kề là trường hợp d=2.
🪑 Mô phỏng · Bấm vào ghế để chọn, xem phép “dồn hàng”
n = 10
k = 3
Trạng thái –
Bộ a_i (vị trí chọn) –
Bộ b_i=a_i-(i-1) –
Công thức | Vét cạn –
Ví dụ 1.1 · Phòng thi Trả lời ngắn Vận dụng
Một dãy bàn thi có 12 ghế xếp thành hàng ngang. Cần xếp 4 thí sinh (khác nhau) vào dãy sao cho không có hai thí sinh nào ngồi cạnh nhau. a) Có bao nhiêu cách chọn ra 4 ghế? b) Có bao nhiêu cách xếp chỗ cho 4 thí sinh?
Lời giải
a) Chọn 4 ghế không kề trong 12 ghế: \dbinom{12-4+1}{4}=\dbinom94=126 cách.
b) Với mỗi bộ 4 ghế, xếp 4 thí sinh vào có 4!=24 cách: 126\cdot24=3\,024 cách.
Đáp án: a) 126 · b) 3 024
Bẫy Đề hỏi “xếp chỗ cho thí sinh” (người khác nhau) thì phải nhân thêm 4!. Đề hỏi “chọn ghế” thì không nhân.
Ví dụ 1.2 · Chọn số cách nhau Trả lời ngắn Vận dụng cao
a) Có bao nhiêu cách chọn 3 số từ tập \{1,2,\dots,20\} sao cho không có hai số nào là hai số tự nhiên liên tiếp?
b) Có bao nhiêu cách chọn 3 số từ tập đó sao cho hai số bất kì hơn kém nhau ít nhất 3 đơn vị?
Lời giải
a) Đây đúng là bài “không kề” với n=20, k=3: \dbinom{18}{3}=816.
b) Khoảng cách ít nhất d=3: đặt b_i=a_i-2(i-1), được 1\le b_1<b_2<b_3\le 20-4=16. Số cách: \dbinom{16}{3}=560.
Đáp án: a) 816 · b) 560 (đã kiểm chứng bằng vét cạn)
02 Dạng 2 · Không kề nhau trên vòng tròn
Vòng tròn khác hàng ngang ở đúng một cặp: vị trí 1 và vị trí n
Định lí Chia hai trường hợp
Có n vị trí quanh một vòng tròn (vị trí n kề vị trí 1). Số cách chọn k vị trí không có hai vị trí nào kề nhau (1\le k<n) là \dbinom{n-k-1}{k-1}+\dbinom{n-k}{k}=\dfrac{n}{n-k}\dbinom{n-k}{k}.
Vị trí 1 được chọn. Khi đó vị trí 2 và vị trí n bị loại. Còn chọn k-1 vị trí trong hàng ngang 3,4,\dots,n-1 (gồm n-3 vị trí): \dbinom{(n-3)-(k-1)+1}{k-1}=\dbinom{n-k-1}{k-1} cách.
Vị trí 1 không được chọn. Vòng tròn bị “cắt” thành hàng ngang 2,3,\dots,n (gồm n-1 vị trí): \dbinom{(n-1)-k+1}{k}=\dbinom{n-k}{k} cách.
Rút gọn. Vì \dbinom{n-k-1}{k-1}=\dfrac{k}{n-k}\dbinom{n-k}{k} nên tổng bằng \left(\dfrac{k}{n-k}+1\right)\dbinom{n-k}{k}=\dfrac{n}{n-k}\dbinom{n-k}{k}.
⭕ Mô phỏng · Bàn tròn: bấm ghế để chọn
n = 10
k = 3
Trạng thái –
Trường hợp ghế 1 được chọn –
Trường hợp ghế 1 không được chọn –
Tổng theo công thức | Vét cạn –
Ví dụ 2.1 · Bàn tròn Trả lời ngắn Vận dụng
Mười bạn ngồi quanh một bàn tròn. Giáo viên chọn ngẫu nhiên 3 bạn lên bảng. Tính số cách chọn sao cho không có hai bạn nào được chọn ngồi cạnh nhau, và xác suất tương ứng.
Lời giải
Số cách: \dbinom{6}{2}+\dbinom{7}{3}=15+35=50 (hoặc \dfrac{10}{7}\dbinom73=50). Không gian mẫu: \dbinom{10}{3}=120.
Đáp án: 50 cách · xác suất \dfrac{50}{120}=\dfrac{5}{12}\approx0{,}42
Ví dụ 2.2 · Đa giác đều Trả lời ngắn Vận dụng cao
Cho đa giác đều 12 đỉnh. Có bao nhiêu tam giác có ba đỉnh là đỉnh của đa giác và không có cạnh nào là cạnh của đa giác?
Tam giác màu cam (đỉnh 1, 5, 8) thỏa mãn. Tam giác viền đỏ (đỉnh 3, 4, 10) có cạnh 3–4 là cạnh của đa giác nên bị loại.
Cách 1 · Nhận ra dạng vòng tròn
Tam giác không có cạnh chung với đa giác \iff ba đỉnh đôi một không kề nhau trên vòng 12 đỉnh. Áp dụng công thức với n=12, k=3: \dfrac{12}{9}\dbinom93=\dfrac{12}{9}\cdot84=112.
Cách 2 · Phần bù (để kiểm tra)
Tổng số tam giác: \dbinom{12}{3}=220. Có đúng 2 cạnh chung: ba đỉnh liên tiếp, có 12 tam giác. Có đúng 1 cạnh chung: chọn cạnh (12 cách), đỉnh thứ ba không kề hai đầu mút (12-4=8 cách), được 96. Vậy 220-12-96=112.
Đáp án: 112 tam giác
03 Dạng 3 · Xác suất lập số chia hết
Chọn bộ chữ số trước, xếp thứ tự sau
Không gian mẫu chuẩn: lập ngẫu nhiên một số tự nhiên có L chữ số đôi một khác nhau (chữ số đầu khác 0), mọi số như vậy đồng khả năng. Số phần tử: 9\cdot A_9^{L-1}.
Ví dụ 3.1 · Một kết quả bất ngờ Tư duy Vận dụng
Chứng minh rằng với mọi L từ 2 đến 10, xác suất để số lập được chia hết cho 5 luôn bằng \dfrac{17}{81}.
Lời giải
Tận cùng 0: các vị trí còn lại lấy từ 9 chữ số, có A_9^{L-1} số. Tận cùng 5: chữ số đầu có 8 cách (khác 0 và 5), các vị trí giữa có A_8^{L-2} cách, được 8A_8^{L-2} số. Dùng A_9^{L-1}=9A_8^{L-2}:
P=\dfrac{9A_8^{L-2}+8A_8^{L-2}}{9\cdot 9A_8^{L-2}}=\dfrac{17}{81}.
Xác suất không phụ thuộc số chữ số: luôn \tfrac{17}{81}\approx0{,}21
Ví dụ 3.2 · Chia hết cho 15 Trả lời ngắn Vận dụng cao
Lập ngẫu nhiên một số tự nhiên có 5 chữ số đôi một khác nhau. Tính xác suất để số đó chia hết cho 15 (làm tròn đến hàng phần nghìn).
Lời giải từng bước
Không gian mẫu: 9\cdot A_9^4=9\cdot3\,024=27\,216.
Tách điều kiện. Chia hết cho 15 \iff tận cùng là 0 hoặc 5, và tổng các chữ số chia hết cho 3. Chia các chữ số theo số dư khi chia cho 3: R_0=\{0,3,6,9\}, R_1=\{1,4,7\}, R_2=\{2,5,8\}.
Tận cùng 0. Chọn 4 chữ số còn lại từ \{1,\dots,9\} (mỗi lớp dư có 3 chữ số) với tổng chia hết cho 3. Gọi (x_0,x_1,x_2) là số chữ số lấy từ mỗi lớp, cần x_1+2x_2\equiv0\pmod3:
(x_0,x_1,x_2) · Số bộ
(0,2,2) · \binom32\binom32=9
(1,3,0) · \binom31\binom33=3
(1,0,3) · 3
(2,1,1) · \binom32\cdot3\cdot3=27
Tổng · 42 bộ
Mỗi bộ xếp tùy ý vào 4 vị trí đầu: 42\cdot4!=1\,008 số.
Tận cùng 5. Chọn 4 chữ số từ \{0,1,2,3,4,6,7,8,9\}: R_0=\{0,3,6,9\}, R_1=\{1,4,7\}, R_2=\{2,8\}. Cần tổng bốn chữ số \equiv1\pmod3 (vì 5\equiv2):
(x_0,x_1,x_2) · Số bộ · Có chữ số 0
(3,1,0) · \binom43\cdot3=12 · \binom32\cdot3=9
(2,0,2) · \binom42\cdot1=6 · 3
(1,2,1) · 4\cdot3\cdot2=24 · 6
Tổng · 42 · 18
Bộ có chữ số 0: chữ số đầu có 3 cách, còn lại 3!: 18\cdot18=324 số. Bộ không có 0: 24\cdot4!=576 số. Cộng: 900 số.
Kết luận. P=\dfrac{1\,008+900}{27\,216}=\dfrac{1\,908}{27\,216}=\dfrac{53}{756}\approx0{,}070.
Đáp án: ≈ 0,070 (máy vét cạn cho đúng 1 908 số)
Bẫy chữ số 0 Khi tận cùng là 5 và bộ chữ số có chứa 0, chữ số 0 không được đứng đầu. Nhân 4! cho mọi bộ sẽ đếm thừa 18\cdot6=108 số.
🔢 Máy vét cạn · kiểm tra mọi con số
Số chữ số L =
Chia hết cho
Không gian mẫu –
Số thỏa mãn –
Xác suất (phân số) –
Xác suất (thập phân) –
04 Dạng 4 · Quân mã đổi chỗ
Vẽ đồ thị nước đi, rồi “duỗi thẳng” bàn cờ
Quân mã đi theo hình chữ L (2 ô theo một hướng, 1 ô theo hướng vuông góc). Trên bàn cờ nhỏ, hãy nối hai ô bằng một đoạn thẳng nếu mã nhảy được giữa chúng. Đồ thị thu được thường là một vòng hoặc một đường có nhánh . Vì hai quân không được đứng cùng một ô, các quân không thể vượt qua nhau trên một đường không có nhánh. Đó là chìa khóa để đánh giá số nước tối thiểu.
Ví dụ 4.1 · Bài toán cổ điển Guarini (năm 1512) Tư duy Vận dụng cao
Trên bàn cờ 3\times3 (đánh số ô 1 đến 9 theo hàng, từ trái sang phải, từ trên xuống dưới), hai mã trắng ở ô 1, 3 và hai mã đen ở ô 7, 9. Mỗi nước di chuyển một quân tới ô trống. Cần ít nhất bao nhiêu nước để hai mã trắng và hai mã đen đổi chỗ cho nhau?
♞ Chơi thử · bấm một quân rồi bấm ô sáng để đi
Số nước: 0
Lời giải và đánh giá
Đồ thị. Ô giữa (ô 5) không nhảy được đi đâu. Tám ô còn lại tạo thành một vòng khép kín: 1-6-7-2-9-4-3-8-1.
Thứ tự trên vòng. Đi theo vòng: Trắng (1), trống (6), Đen (7), trống (2), Đen (9), trống (4), Trắng (3), trống (8). Thứ tự xoay vòng của 4 quân là T – Đ – Đ – T và không bao giờ đổi, vì các quân không vượt được nhau.
Đánh giá. Để trắng tới ô 7, 9 và đen tới ô 1, 3 mà vẫn giữ thứ tự, cách duy nhất là cả bốn quân cùng quay nửa vòng: mỗi quân đi đúng 4 bước trên vòng. Vậy cần ít nhất 4\cdot4=16 nước.
Thực hiện. Mỗi lượt cho bốn quân tiến một bước theo cùng chiều (quân đứng trước đi trước), lặp lại 4 lượt: đủ 16 nước.
Đáp án: 16 nước
Ví dụ 4.2 · Bàn cờ khuyết gồm 9 ô (đề LUKATO) Nhiều lựa chọn Vận dụng cao
Bàn cờ gồm 9 ô như hình, đánh số từ 1 đến 9. Hai mã trắng T_1 ở ô 1, T_2 ở ô 3 và một mã đen Đ ở ô 7. Mỗi nước di chuyển một quân tới ô trống. Cần ít nhất bao nhiêu nước để T_1 và T_2 đổi chỗ cho nhau (mã đen có thể dừng ở bất kì ô nào)?
A. 12 B. 14 C. 16 D. 18
♞ Chơi thử · bấm một quân rồi bấm ô sáng để đi
💡 Gợi ý: đồ thị nước đi
Số nước: 0
Lời giải và đánh giá
Đồ thị. Các nước đi nối thành đường chính 1-6-7-2-8-4-3 (dài 6 bước) với một nhánh cụt 7-9-5 mọc ra từ ô 7.
Đánh giá (lập luận trực quan). T_1 phải đi hết đường chính: ít nhất 6 nước; T_2 cũng vậy: ít nhất 6 nước. Hai quân trắng không thể vượt nhau trên đường chính, nên một quân phải tạt vào nhánh cụt rồi quay ra: thêm ít nhất 2 nước. Mã đen đang chắn ngay ngã ba 7 nên phải lùi sâu vào nhánh (7 → 9 → 5) để nhường ô 9: thêm ít nhất 2 nước. Tổng ít nhất 6+6+2+2=16.
Một lời giải 16 nước. T_1: 1→6. T_2: 3→4→8→2. Đ : 7→9. T_1: 6→7. Đ : 9→5. T_1: 7→9. T_2: 2→7→6. T_1: 9→7→2→8→4→3. T_2: 6→1.
Máy tính duyệt toàn bộ trạng thái (tìm kiếm theo chiều rộng) xác nhận 16 là số nước nhỏ nhất. Nếu bắt mã đen phải về lại ô 7 thì cần 18 nước.
Đáp án: C. 16 nước
Ba phương án nhiễu đến từ đâu 12: chỉ cộng quãng đường, quên rằng các quân không vượt được nhau. 14: nhớ nước tạt vào nhánh nhưng quên phải dời mã đen. 18: tự thêm điều kiện mã đen phải về chỗ cũ.
05 Dạng 5 · Cánh tay robot quay quanh gốc
Quay không làm thay đổi khoảng cách tới tâm quay
Ví dụ 5.1 · Cánh tay gắp linh kiện Trả lời ngắn Vận dụng cao
Một cánh tay robot có khớp cố định tại gốc O của hệ trục Oxy (đơn vị: cm), gồm ba thanh OA=20, AB=30, BC=12. Các khớp A, B được khóa sao cho: thanh AB lệch 60^\circ theo chiều ngược kim đồng hồ so với thanh OA; thanh BC lệch 90^\circ theo chiều ngược kim đồng hồ so với thanh AB. Ban đầu thanh OA nằm dọc theo tia Ox. Sau đó toàn bộ cánh tay quay tự do quanh O. Trong quá trình quay, khoảng cách lớn nhất từ đầu kẹp C đến trục hoành là bao nhiêu cm (làm tròn đến hàng phần mười)?