Có một câu đố thú vị ở phần cuối của Harry Potter và Hòn đá Phù thủy. Harry và Hermione bước vào phòng, sau đó lối vào bị chặn bởi ngọn lửa ma thuật và họ chỉ có thể rời khỏi phòng bằng cách giải câu đố sau:
Có nguy hiểm ở phía trước và sự cứu rỗi ở phía sau bạn,
Hai người bạn tìm thấy trong số chúng tôi sẽ giúp bạn;
Với một trong bảy bạn sẽ tiếp tục tiến về phía trước
Người kia sẽ đưa bạn về ngay.
Trong hai chúng tôi bạn sẽ chỉ tìm thấy rượu tầm ma,
Và ba mang đến sự hủy diệt, bí mật đứng thành một hàng.
Vì vậy, hãy chọn loại nào bạn muốn nếm thử,
Để làm điều này, chúng tôi đưa ra bốn lời khuyên.
Chất độc đã cố gắng che giấu sức nóng chết người của nó một cách vô ích,
Bạn sẽ luôn tìm thấy anh ấy ở bên trái chai rượu,
Và biết rằng những người ở rìa nắm giữ một món quà khác,
Nhưng nếu bạn muốn tiếp tục thì sẽ không có ai giúp đỡ.
Tất cả chúng ta đều có kích thước khác nhau, từ cạnh này sang cạnh khác,
Cái chết của bạn không nằm trong cái nhỏ hơn, nhưng cũng không nằm trong cái lớn hơn;
Cái thứ hai từ bên phải và cái thứ hai từ bên trái
Họ có mùi vị giống như anh em sinh đôi, mặc dù trông họ không giống nhau.
[từ “bản dịch dân gian” của cuốn sách “Harry Potter và hòn đá phù thủy”]
Nói một cách đơn giản, họ cần hiểu chai nào chứa loại thuốc nào.
Trong bài viết này, chúng ta sẽ giải tất cả 42 biến thể có thể có của câu đố này bằng cách sử dụng lập trình và vẽ sơ đồ kết quả (như hình trên, chỉ lớn hơn nhiều).
Đợi chút, 42 lựa chọn đến từ đâu?
Điều này là do vị trí của các lọ thuốc “nhỏ hơn” và “lớn hơn” không được chỉ định. Cái lớn hơn có thể ở một trong bảy vị trí, điều này mang lại 6 lựa chọn còn lại cho cái nhỏ hơn, tổng cộng là 7 * 6 = 42. Sẽ không thể tìm ra chính xác sự sắp xếp mà JK Rowling đã nghĩ đến khi cô ấy nghĩ ra với câu đố này, trừ khi cô ấy nói về nó trên Twitter của bạn. Chà, cho đến khi ngày tất yếu đó đến, chúng ta có thể chọn một phiên bản ngẫu nhiên và làm việc với nó. Tuy nhiên, sẽ không có gì đảm bảo về khả năng giải được của nó, đó là lý do tại sao chúng tôi làm việc vì lợi ích chung, giải quyết tất cả 42 biến thể của câu đố (hoặc chứng minh tính không thể giải được của chúng).
QUYẾT ĐỊNH ĐÃ
Đầu tiên, đây là tất cả những hạn chế của câu đố, được trình bày lại bằng những thuật ngữ đơn giản:
- Có hai loại thuốc vô hại, 3 loại thuốc độc, một loại cho phép bạn tiến lên và một loại cho phép bạn lùi lại.
- Ở phía bên trái của mỗi loại thuốc vô hại là một loại thuốc độc.
- Thuốc của cả hai bên đều khác nhau và không có loại thuốc nào cho phép bạn tiến về phía trước.
- Chai lớn nhất và nhỏ nhất không chứa chất độc.
- Chai thứ hai bên trái và chai thứ hai bên phải chứa cùng một lọ thuốc.
Làm thế nào để đối phó với điều này? Hãy xem xét lựa chọn sau. Lưu ý rằng, như câu đố đã nói, trong hàng có 1 chai nhỏ hơn tất cả những chai còn lại và 1 chai lớn hơn tất cả những chai còn lại.
Chúng ta hãy cố gắng xem qua tất cả các lựa chọn một cách ngu ngốc - lấy từng chai một và chọn tất cả các tùy chọn có thể có cho nội dung.
Ví dụ, chai đầu tiên không thể chứa lọ thuốc đưa chúng ta tiến về phía trước do hạn chế số 3. Nó cũng không chứa thuốc an toàn do hạn chế số 2 - không thể có chất độc ở bên trái của nó. Điều này khiến chúng ta có các lựa chọn về thuốc độc và thuốc phản tác dụng. Hãy thử cả hai lựa chọn.
Trong các hình ảnh sau, lọ thuốc màu xanh lá cây tượng trưng cho chất độc, màu cam là đồ uống an toàn, màu xanh lam là lọ thuốc di chuyển lùi và màu tím là lọ thuốc di chuyển về phía trước.
Hãy lặp lại quy trình này cho cả hai tùy chọn hoạt động - lấy chai thứ hai và lần lượt thử tất cả các tùy chọn nội dung có thể chấp nhận được. Điều này sẽ cung cấp cho chúng tôi những điều sau đây:
Tiếp tục hành động theo hướng này và loại bỏ tất cả các phương án làm việc trong đó một số chai không thể đổ đầy thuốc mà không vi phạm các hạn chế được liệt kê, chúng tôi sẽ đi đến lựa chọn duy nhất có thể chấp nhận được:
Đương nhiên, chúng tôi không có gì đảm bảo sẽ tìm ra giải pháp. Có thể không có lời giải hoặc có thể có một vài lời giải (và nếu bạn có nhiều lời giải, điều này cũng giống như câu đố không thể giải được vì bạn không biết lọ thuốc nào đúng).
Áp dụng thuật toán cho tất cả các phương án cho ta lời giải sau. 8 phiên bản của câu đố có thể giải được, 8 phiên bản không có lời giải và 26 phiên bản có nhiều lời giải.
Tìm hiểu thêm về các giải pháp
Có phải tất cả các phiên bản đã giải được của câu đố đều có điểm chung không? Đúng! Xin lưu ý rằng trong đó chai nhỏ nhất hoặc lớn nhất nằm ở vị trí thứ 2 hoặc thứ 6. Điều này cho phép chúng tôi kết luận rằng chai thứ 2 và thứ 6 chứa thuốc an toàn do hạn chế số 4 và số 5. Nếu không có bước này, chúng tôi không thể loại trừ khả năng những chai này chứa chất độc và chúng tôi sẽ đưa ra một số giải pháp khả thi. Các phương án đã giải cũng yêu cầu chai "đặc biệt" thứ hai (nhỏ nhất hoặc lớn nhất) phải được đặt ở vị trí thứ 3 hoặc thứ 4. Nếu không, không thể tìm thấy vị trí chính xác của lọ thuốc đưa chúng ta tiến về phía trước.
Kết quả
Tôi sẽ kết thúc bằng một trích dẫn từ cuốn sách.
Hermione thở ra một hơi lớn, và Harry ngạc nhiên khi nhận ra cô đang mỉm cười - đó là điều cuối cùng anh có thể nghĩ đến. "Tuyệt vời," Hermione nói. - Đây không phải là phép thuật - đây là logic, một câu đố. Rất nhiều pháp sư vĩ đại nhất không có một chút logic nào và họ sẽ bị mắc kẹt ở đây mãi mãi."
Nhưng đợi một chút - có lẽ chúng ta có thể tìm ra phiên bản kinh điển của câu đố dựa trên đoạn hội thoại trong cuốn sách:
“Hiểu rồi,” cô nói. “Cái chai nhỏ nhất sẽ dẫn chúng ta qua ngọn lửa đen và tới Hòn đá.”
...
“Và cái nào sẽ cho phép bạn quay trở lại qua ngọn lửa tím?”
Hermione chỉ vào một cái chai tròn ở phía bên phải hàng ghế.
Chết tiệt. Tùy chọn này vẫn cung cấp cho chúng tôi một số giải pháp. Tweet, DR.
mã
Nếu bạn quan tâm đến đoạn mã để giải câu đố này và vẽ sơ đồ, bạn có thể .
Nguồn: www.habr.com