Mình thấy bài toán này vẫn chưa được giải quyết trọn vẹn. Không hiểu sau mod lại đưa ra thêm bài mới. Như vậy liệu có mâu thuẫn với tiêu chí của ban tổ chức không?
Lời giải của bạn chanhquocnghiem là khá hay và thú vị. Tuy nhiên nếu hiểu đề bài theo nghĩa "mới" (theo như người ra đề đã giải thích) thì sẽ tồn tại một con mọt thông minh (vì nó là mọt Toán mà). Vì nó thông minh nên mỗi lần đổi màu khoang trắng nó sẽ làm cho bác sỹ phải thất vọng. Lúc này nếu bác sỹ làm theo kế sách của bạn chanhquocnghiem thì bác sỹ sẽ kiên nhẫn ngồi chờ sơ hở của con mọt.
Có cách nào để làm trắng mọi con mọt không, kể cả những con mọt thông minh và không muốn bị tẩy trăng?
Sau đây, mình xin trình bày một cách tẩy trắng universal (có tác dụng trên tất cả mọt). Cách làm của mình dựa theo ý tưởng của bác sỹ chanhquocnghiem.
Giả sử ta cần tẩy trắng một con mọt Toán. Ta đánh dấu các khoang trắng bởi các số $0$ và khoang đen bởi số $1$ và chọn một vị trí gốc để sao cho số nhị phân thu được là lớn nhất (viết theo chiều từ đầu đến đuôi rồi quay lại nếu vẫn còn khoang phía sau). Ta gọi số này là độ trắng của mọt. Để dễ hình dung ta xét ví dụ sau:
Mọt có các khoang là : DTDTDT
Khi đó (chọn gốc ở chỗ nào thì cũng tính đươc cùng một độ trắng) độ trắng của mọt là $101010 = 2^5 +2^3+2^1=42$.
Áp dụng ý tưởng của bác sỹ chanhquocnghiem chúng ta cần một thuật toán để làm tăng độ trắng của mọt.
Xét một con mọt bất kỳ và ta đánh dấu vị trí gốc của nó (có thể có nhiều, khi đó chỉ cần chọn một gốc là được). Ta cũng đánh dấu vị trị ngọn (khoang màu đen cuối cùng tính từ gốc theo hướng từ đầu đến đuôi). Nếu ngọn không nằm ở đuôi thì ta cứ chờ. Vì nếu như mọt tự biến một khoang trắng thành đen thì độ trắng sẽ tăng lên mà ta chưa cần phải làm gì cả. Nếu ngọn nằm ở đuôi thì ta làm trắng khoan đấy. Tiếp theo nếu mọt làm đen bất cứ khoan nào trước khoang gốc thì độ trắng cũng sẽ tăng lên (Đây là một tính chất khá thú vị của số nhị phân, Exercise?). Nếu mọt không chịu chuyển màu thì ta cứ việc chuyển đen thành trắng và mọt sẽ trắng toàn thân.
Như vậy sau mỗi bước, mọt sẽ hoặc là trắng toàn thân hoặc là tăng độ trặng Khi mà độ trắng maximum rồi thì mọt đen toàn thân và bác sỹ chanhquocnghiem đã chỉ cho chúng ta cách tẩy trắng một con mọt đen toàn thân như thế nào.
Bài viết đã được chỉnh sửa nội dung bởi ChinhLu: 06-07-2014 - 23:19