Câu hỏi 53
Cho một xâu gồm các chữ số 0 và 1, Giacomo muốn chia nó thành các khối gồm 2 hoặc 3 chữ số liên tiếp sao cho thỏa mãn một trong hai điều kiện sau:
(1) trong mỗi khối, mọi chữ số 0 (nếu có) đều đứng bên trái mọi chữ số 1 (nếu có). Tức là các khối được phép là $00,01,11,000,001,011,111$;
(2) trong mỗi khối, mọi chữ số 0 (nếu có) đều đứng bên phải mọi chữ số 1 (nếu có). Tức là các khối được phép là $00,10,11,000,100,110,111$.
Ví dụ, với xâu 011011, cách chia $01|10|11$ không hợp lệ vì các khối không đồng thời cùng thuộc loại (1), cũng không đồng thời cùng thuộc loại (2). Còn cách chia 011|011 thì hợp lệ vì mọi khối đều thuộc loại (1).
a. Cho $m, n$ là các số nguyên lớn hơn hoặc bằng 0, với $m+n \geq 2$. Chứng minh rằng xâu gồm $m$ chữ số 0 theo sau là $n$ chữ số 1 có thể chia thành các khối như Giacomo mong muốn.
b. Cho $l \geq 4$ là số nguyên. Chứng minh rằng số xâu gồm các chữ số 0 và 1 có độ dài $l$ mà Giacomo không thể chia như trên là $2^{l-3}$.
(1) trong mỗi khối, mọi chữ số 0 (nếu có) đều đứng bên trái mọi chữ số 1 (nếu có). Tức là các khối được phép là $00,01,11,000,001,011,111$;
(2) trong mỗi khối, mọi chữ số 0 (nếu có) đều đứng bên phải mọi chữ số 1 (nếu có). Tức là các khối được phép là $00,10,11,000,100,110,111$.
Ví dụ, với xâu 011011, cách chia $01|10|11$ không hợp lệ vì các khối không đồng thời cùng thuộc loại (1), cũng không đồng thời cùng thuộc loại (2). Còn cách chia 011|011 thì hợp lệ vì mọi khối đều thuộc loại (1).
a. Cho $m, n$ là các số nguyên lớn hơn hoặc bằng 0, với $m+n \geq 2$. Chứng minh rằng xâu gồm $m$ chữ số 0 theo sau là $n$ chữ số 1 có thể chia thành các khối như Giacomo mong muốn.
b. Cho $l \geq 4$ là số nguyên. Chứng minh rằng số xâu gồm các chữ số 0 và 1 có độ dài $l$ mà Giacomo không thể chia như trên là $2^{l-3}$.