Câu 6HSGChuyên đề: Đếm có điều kiện kề nhau hoặc loại trừ • Lớp 10Tổ hợp không thứ tựVận dụng cao#Thiếu hình vẽ#flag:missing_figure
a) Cho hình chữ nhật gồm ô vuông cạnh bằng 1. Xét đường đi có độ dài 18 từ đến dọc theo cạnh các hình vuông đó và đổi hướng đúng 4 lần. Tính số đường đi khác nhau có thể có. Dưới đây là một ví dụ đường đi thỏa yêu cầu của bài toán.
b) Cho là tập con của tập gồm nhiều hơn 1010 phần tử. Chứng minh rằng chứa phần tử là lũy thừa của 2 hoặc chứa hai phần tử phân biệt có tổng là lũy thừa của 2.
a) Cho hình chữ nhật gồm ô vuông cạnh bằng 1. Xét đường đi có độ dài 18 từ đến dọc theo cạnh các hình vuông đó và đổi hướng đúng 4 lần. Tính số đường đi khác nhau có thể có. Dưới đây là một ví dụ đường đi thỏa yêu cầu của bài toán.
b) Cho là tập con của tập gồm nhiều hơn 1010 phần tử. Chứng minh rằng chứa phần tử là lũy thừa của 2 hoặc chứa hai phần tử phân biệt có tổng là lũy thừa của 2.
b) Cho là tập con của tập gồm nhiều hơn 1010 phần tử. Chứng minh rằng chứa phần tử là lũy thừa của 2 hoặc chứa hai phần tử phân biệt có tổng là lũy thừa của 2.
Đáp án chính thức: Tự luận
Hướng dẫn giải chi tiết
(AI giải đề cho tôi)
Câu 6a: Vì độ dài đường đi từ A đến C đúng bằng 18 = 10 + 8 (khoảng cách Manhattan), mọi bước đều phải đi sang phải hoặc đi lên, tức đường đi đơn điệu. Đường đi có đúng 4 lần đổi hướng nên gồm 5 đoạn liên tiếp, các đoạn đổi kiểu luân phiên (ngang–dọc–ngang–dọc–ngang hoặc dọc–ngang–dọc–ngang–dọc), mỗi đoạn có độ dài dương. TH1: bắt đầu bằng đoạn ngang: cần h1+h3+h5=10 với hi≥1 nên có C(9,2)=36 cách; và v2+v4=8 với vi≥1 nên có C(7,1)=7 cách; được 36·7=252 đường. TH2: bắt đầu bằng đoạn dọc: v1+v3+v5=8 cho C(7,2)=21 cách; h2+h4=10 cho C(9,1)=9 cách; được 21·9=189 đường. Tổng số đường đi: 252+189=441. (Kết quả 441 trùng với lời giải chính thức của đề ở trang 17–18: khả năng 1 cho C(7,2)·C(9,1)=189, khả năng 2 cho C(9,2)·C(7,1)=252, tổng 441.)
Câu 6b: Phân loại các số theo trị số 2-adic: số x có dạng 2^a·u với u lẻ thì mọi cặp x+y là lũy thừa của 2 phải có cùng trị số a (vì 2^a·u+2^b·v với u,v lẻ chỉ là lũy thừa của 2 khi a=b). Xét các lớp L_a={2^a·u : u lẻ, 2^a·u≤2026}. Trong mỗi lớp, ghép cặp 2^a·u với 2^a·w sao cho u+w là lũy thừa của 2, khi đó tổng cặp bằng 2^a·2^m là lũy thừa của 2. Cụ thể: L0 (1013 số lẻ): lấy singleton {1}; ghép {3,5}(=8), {7,9}(=16), {11,21}, {13,19}, {15,17}(=32), và các cặp {x, 2048−x} với x lẻ từ 23 đến 1023 (501 cặp, bạn từ 1025 đến 2025): được 506 cặp phủ hết 1012 số còn lại. L1 (507 số): singleton {2}; ghép {3,5}, {7,9}, và {x,1024−x} với x lẻ từ 11 đến 511 (251 cặp): 253 cặp. L2 (253 số): singleton {4}; ghép {3,5}(=8) và {x,512−x} với x lẻ từ 7 đến 255 (125 cặp): 126 cặp. L3 (127 số): singleton {8}; ghép {x,256−x} với x lẻ từ 3 đến 125 (62 cặp) và cặp {127,129}(=256): 63 cặp. L4 (63 số): singleton {16}; ghép {x,128−x} với x lẻ từ 3 đến 63 (31 cặp). L5 (32 số, gồm 32,96,...,2016): ghép {32u, 32(64−u)} với u lẻ từ 1 đến 31: 16 cặp, tổng bằng 2048. L6: 8 cặp {64u, 64(32−u)} tổng 2048; L7: 4 cặp {128u, 128(16−u)} tổng 2048; L8 (4 số 256, 768, 1280, 1792): 2 cặp {256,1792}, {768,1280} tổng 2048; L9: cặp {512,1536} tổng 2048; L10: singleton {1024}. Kiểm tra: 6 singleton {1,2,4,8,16,1024} và 1010 cặp, phủ đúng 6+2020=2026 số. Giả sử A không chứa lũy thừa của 2 và không có hai phần tử phân biệt có tổng là lũy thừa của 2. Khi đó A không chứa phần tử nào của 6 singleton, và A chứa nhiều nhất một phần tử trong mỗi cặp (nếu chứa cả hai thì tổng của chúng là lũy thừa của 2). Suy ra |A| ≤ 1010, mâu thuẫn với |A| ≥ 1011. Vậy A phải chứa một lũy thừa của 2 hoặc hai phần tử phân biệt có tổng là lũy thừa của 2. Đáp số câu a: 441.
Câu 6a: Vì độ dài đường đi từ A đến C đúng bằng 18 = 10 + 8 (khoảng cách Manhattan), mọi bước đều phải đi sang phải hoặc đi lên, tức đường đi đơn điệu. Đường đi có đúng 4 lần đổi hướng nên gồm 5 đoạn liên tiếp, các đoạn đổi kiểu luân phiên (ngang–dọc–ngang–dọc–ngang hoặc dọc–ngang–dọc–ngang–dọc), mỗi đoạn có độ dài dương. TH1: bắt đầu bằng đoạn ngang: cần h1+h3+h5=10 với hi≥1 nên có C(9,2)=36 cách; và v2+v4=8 với vi≥1 nên có C(7,1)=7 cách; được 36·7=252 đường. TH2: bắt đầu bằng đoạn dọc: v1+v3+v5=8 cho C(7,2)=21 cách; h2+h4=10 cho C(9,1)=9 cách; được 21·9=189 đường. Tổng số đường đi: 252+189=441. (Kết quả 441 trùng với lời giải chính thức của đề ở trang 17–18: khả năng 1 cho C(7,2)·C(9,1)=189, khả năng 2 cho C(9,2)·C(7,1)=252, tổng 441.)
Câu 6b: Phân loại các số theo trị số 2-adic: số x có dạng 2^a·u với u lẻ thì mọi cặp x+y là lũy thừa của 2 phải có cùng trị số a (vì 2^a·u+2^b·v với u,v lẻ chỉ là lũy thừa của 2 khi a=b). Xét các lớp L_a={2^a·u : u lẻ, 2^a·u≤2026}. Trong mỗi lớp, ghép cặp 2^a·u với 2^a·w sao cho u+w là lũy thừa của 2, khi đó tổng cặp bằng 2^a·2^m là lũy thừa của 2. Cụ thể: L0 (1013 số lẻ): lấy singleton {1}; ghép {3,5}(=8), {7,9}(=16), {11,21}, {13,19}, {15,17}(=32), và các cặp {x, 2048−x} với x lẻ từ 23 đến 1023 (501 cặp, bạn từ 1025 đến 2025): được 506 cặp phủ hết 1012 số còn lại. L1 (507 số): singleton {2}; ghép {3,5}, {7,9}, và {x,1024−x} với x lẻ từ 11 đến 511 (251 cặp): 253 cặp. L2 (253 số): singleton {4}; ghép {3,5}(=8) và {x,512−x} với x lẻ từ 7 đến 255 (125 cặp): 126 cặp. L3 (127 số): singleton {8}; ghép {x,256−x} với x lẻ từ 3 đến 125 (62 cặp) và cặp {127,129}(=256): 63 cặp. L4 (63 số): singleton {16}; ghép {x,128−x} với x lẻ từ 3 đến 63 (31 cặp). L5 (32 số, gồm 32,96,...,2016): ghép {32u, 32(64−u)} với u lẻ từ 1 đến 31: 16 cặp, tổng bằng 2048. L6: 8 cặp {64u, 64(32−u)} tổng 2048; L7: 4 cặp {128u, 128(16−u)} tổng 2048; L8 (4 số 256, 768, 1280, 1792): 2 cặp {256,1792}, {768,1280} tổng 2048; L9: cặp {512,1536} tổng 2048; L10: singleton {1024}. Kiểm tra: 6 singleton {1,2,4,8,16,1024} và 1010 cặp, phủ đúng 6+2020=2026 số. Giả sử A không chứa lũy thừa của 2 và không có hai phần tử phân biệt có tổng là lũy thừa của 2. Khi đó A không chứa phần tử nào của 6 singleton, và A chứa nhiều nhất một phần tử trong mỗi cặp (nếu chứa cả hai thì tổng của chúng là lũy thừa của 2). Suy ra |A| ≤ 1010, mâu thuẫn với |A| ≥ 1011. Vậy A phải chứa một lũy thừa của 2 hoặc hai phần tử phân biệt có tổng là lũy thừa của 2. Đáp số câu a: 441.
