Câu hỏi 76
Trên gác mái, ông nội có một số hữu hạn thùng rác rỗng. Mỗi thùng rác là một hình hộp chữ nhật có độ dài các cạnh là số nguyên. Một thùng rác có thể được bỏ vào trong một thùng khác khi và chỉ khi có thể ghép tương ứng một-một các độ dài cạnh của hai thùng sao cho mỗi độ dài cạnh của thùng thứ nhất nhỏ hơn độ dài cạnh tương ứng của thùng kia. Không thùng rác nào có thể chứa hai thùng rác khác, trừ khi hai thùng đó đã được đặt thùng này vào trong thùng kia. Ông nội muốn bỏ đi càng nhiều thùng rác càng tốt để tiết kiệm chỗ. Ông nghĩ ra thuật toán sau: tìm chuỗi dài nhất các thùng rác có thể lần lượt bỏ vào trong nhau, sau đó lặp lại với các thùng còn lại, v.v., cho đến khi không thể bỏ thêm thùng nào nữa. Khi thực hiện thuật toán này, ở mỗi bước chuỗi dài nhất cần chọn hóa ra là duy nhất. Có nhất thiết đúng là khi kết thúc quá trình, số thùng rác bị bỏ đi là lớn nhất có thể hay không?