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 sao cho khi cần lấy $n$ bi, với $1\le n\le63$, ta chỉ cần lấy một số hộp nguyên vẹn? Chẳng hạn, cần lấy $9$ viên thì lấy hai hộp đựng $8$ viên và $1$ viên.
Xem lời giải
Lời giải
Với số $n$ bất kỳ $\left( 1\leq n\leq 63 \right)$, ta luôn có biểu diễn duy nhất $n=a_{1}+a_{2}.2+a_{3}.2^{2} +a_{4}.2^{3} +a_{5}.2^{4} +a_{6}.2^{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!.63.C_{62}^{2}.C_{60}^{4}.C_{56}^{8}.C_{48}^{16}.1$ 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!.63.C_{62}^{2}.C_{60}^{4}.C_{56}^{8}.C_{48}^{16}.1$ cách.