Câu hỏi 14
Cho số nguyên dương $k$ và hai số nguyên $b\gt w\gt 1$. Có hai chuỗi ngọc: một chuỗi gồm $b$ viên đen, một chuỗi gồm $w$ viên trắng. Độ dài chuỗi là số viên ngọc trên chuỗi.
Cắt các chuỗi qua nhiều bước theo quy tắc sau. Ở mỗi bước:
(i) Xếp các chuỗi theo độ dài không tăng. Nếu bằng nhau, chuỗi trắng đứng trước chuỗi đen. Chọn $k$ chuỗi đầu có nhiều hơn một viên; nếu có ít hơn $k$ chuỗi dài hơn 1, chọn tất cả chúng.
(ii) Cắt mỗi chuỗi đã chọn thành hai phần có độ dài chênh nhau không quá một.
Chẳng hạn, nếu có các chuỗi ngọc đen dài $5,4,4,2$, các chuỗi ngọc trắng dài $8,4,3$, và $k=4$, thì các chuỗi 8 viên trắng, 5 viên đen, 4 viên trắng và 4 viên đen lần lượt được cắt thành $(4,4),(3,2),(2,2)$ và $(2,2)$.
Quá trình dừng ngay sau bước mà lần đầu xuất hiện một viên ngọc trắng đứng riêng. Chứng minh lúc đó vẫn còn một chuỗi có ít nhất hai viên ngọc đen.
Cắt các chuỗi qua nhiều bước theo quy tắc sau. Ở mỗi bước:
(i) Xếp các chuỗi theo độ dài không tăng. Nếu bằng nhau, chuỗi trắng đứng trước chuỗi đen. Chọn $k$ chuỗi đầu có nhiều hơn một viên; nếu có ít hơn $k$ chuỗi dài hơn 1, chọn tất cả chúng.
(ii) Cắt mỗi chuỗi đã chọn thành hai phần có độ dài chênh nhau không quá một.
Chẳng hạn, nếu có các chuỗi ngọc đen dài $5,4,4,2$, các chuỗi ngọc trắng dài $8,4,3$, và $k=4$, thì các chuỗi 8 viên trắng, 5 viên đen, 4 viên trắng và 4 viên đen lần lượt được cắt thành $(4,4),(3,2),(2,2)$ và $(2,2)$.
Quá trình dừng ngay sau bước mà lần đầu xuất hiện một viên ngọc trắng đứng riêng. Chứng minh lúc đó vẫn còn một chuỗi có ít nhất hai viên ngọc đen.