Câu hỏi 8
Một từ là một dãy gồm không hoặc nhiều chữ cái thuộc tập $\{A,B,C,D,E,F,G,H,I\}$. Hai từ được gọi là liên hệ nếu có thể biến từ này thành từ kia bằng một dãy các thao tác:
(a) đổi chỗ hai chữ cái kề nhau;
(b) xóa hai chữ cái kề nhau giống nhau;
(c) chèn hai chữ cái kề nhau giống nhau.
Ví dụ BACA và BCAA liên hệ bằng cách đổi chỗ A và C kề nhau; BCAA và BC liên hệ bằng cách xóa hoặc chèn hai chữ A kề nhau. Nguồn còn ghi rằng từ rỗng không có chữ cái liên hệ với bất kỳ từ nào chỉ gồm hai chữ cái kề nhau.
Một tập không chứa hai từ nào liên hệ nhau có nhiều nhất bao nhiêu từ?
Chỉ ghi đáp số: một số nguyên không âm nhỏ hơn 1000.
(a) đổi chỗ hai chữ cái kề nhau;
(b) xóa hai chữ cái kề nhau giống nhau;
(c) chèn hai chữ cái kề nhau giống nhau.
Ví dụ BACA và BCAA liên hệ bằng cách đổi chỗ A và C kề nhau; BCAA và BC liên hệ bằng cách xóa hoặc chèn hai chữ A kề nhau. Nguồn còn ghi rằng từ rỗng không có chữ cái liên hệ với bất kỳ từ nào chỉ gồm hai chữ cái kề nhau.
Một tập không chứa hai từ nào liên hệ nhau có nhiều nhất bao nhiêu từ?
Chỉ ghi đáp số: một số nguyên không âm nhỏ hơn 1000.