Bài tập nâng cao · Bài 41
Bài tập nâng cao Hoán vị, chỉnh hợp và tổ hợp · Bài 41
Cho 63 viên bi khác nhau và 6 cái hộp khác nhau, hỏi có bao nhiêu cách bỏ 63 viên bi đó vào 6 hộp trên sao cho khi cần lấy $n$ bi ($1\leq n\leq63$) trong 6 hộp trên? Chẳng hạn, cần lấy 9 viên bi, thì ta có sẵn hai hộp đựng 8 viên và 1 viên bi, lúc này ta chỉ cần lấy hai hộp này ra.
Xem lời giải
Lời giải
Với số $n$ bất kỳ ($1\leq n\leq63$), ta luôn có biểu diễn duy nhất $n=a_1+a_2\cdot2+a_3\cdot2^2+a_4\cdot2^3+a_5\cdot2^4+a_6\cdot2^5$ với $a_i=0$ hoặc $a_i=1$.
Do đó để có thể lấy $n$ bi bất kỳ bởi $m$ hộp thì số bi của $6$ hộp là $1,2,2^2,2^3,2^4,2^5$ hay $1,2,4,8,16,32$.
Số cách chia số lượng bi cho $6$ hộp là $6!$.
Giả sử hộp $H_1$ có 1 bi, có 63 cách chọn.
Hộp $H_2$ có 2 bi, có $C_{62}^2$ cách chọn.
Hộp $H_3$ có 4 bi, có $C_{60}^4$ cách chọn.
Hộp $H_4$ có 8 bi, có $C_{56}^8$ cách chọn.
Hộp $H_5$ có 16 bi, có $C_{48}^{16}$ cách chọn.
Xếp 32 bi còn lại vào hộp $H_6$ có 1 cách chọn.
Vậy số cách chia cần tìm là: $6!\cdot63\cdot C_{62}^2\cdot C_{60}^4\cdot C_{56}^8\cdot C_{48}^{16}\cdot1$ cách.
Do đó để có thể lấy $n$ bi bất kỳ bởi $m$ hộp thì số bi của $6$ hộp là $1,2,2^2,2^3,2^4,2^5$ hay $1,2,4,8,16,32$.
Số cách chia số lượng bi cho $6$ hộp là $6!$.
Giả sử hộp $H_1$ có 1 bi, có 63 cách chọn.
Hộp $H_2$ có 2 bi, có $C_{62}^2$ cách chọn.
Hộp $H_3$ có 4 bi, có $C_{60}^4$ cách chọn.
Hộp $H_4$ có 8 bi, có $C_{56}^8$ cách chọn.
Hộp $H_5$ có 16 bi, có $C_{48}^{16}$ cách chọn.
Xếp 32 bi còn lại vào hộp $H_6$ có 1 cách chọn.
Vậy số cách chia cần tìm là: $6!\cdot63\cdot C_{62}^2\cdot C_{60}^4\cdot C_{56}^8\cdot C_{48}^{16}\cdot1$ cách.