Một trăm ổ khóa và một trăm chìa khóa

33

“Lượng tử”

VÌ

TRẺ HƠN

Một trăm ổ khóa và một trăm chìa khóa

S.DORICHENKO

Gửi Ngài Mycroft Holmes, tôi xin lỗi vì bức thư đáng lo ngại này, nhưng Sherlock Holmes hiện đang ở trong tình trạng tồi tệ. Việc thiếu những thứ để chiếm giữ tâm trí đã ảnh hưởng cực kỳ bất lợi đến sức khỏe của anh ấy. Bạn tôi thực sự cần một bài toán phức tạp. Nếu thế giới tội phạm không còn khả năng ứng phó với những thách thức như vậy, thì có lẽ một câu đố logic nào đó xứng đáng với bộ óc vĩ đại này sẽ được giải đáp? Với hy vọng, bác sĩ Watson

Gửi Tiến sĩ John Watson, tôi mãi mãi biết ơn sự quan tâm của ông dành cho anh trai tôi. Hiện tại tôi đang bận giải một bài toán và vẫn chưa giải được. Nó không hoàn toàn mang tính pháp lý, nhưng chính Moriarty đã đặt ra một thách thức ở đây. Có lẽ điều này sẽ khiến Sherlock quan tâm? Tôi đang đính kèm các điều kiện. Trân trọng, Mycroft Holmes

---

• Vậy, Watson, có 100 chiếc ổ khóa và 100 chiếc chìa khóa trông giống hệt nhau, chất thành một đống phải không? – Có, và đúng một chiếc chìa khóa phù hợp với mỗi ổ khóa. Và bạn cần tìm ra ổ khóa nào được mở bằng chìa khóa nào. “Chà, đó không phải là một công việc dễ chịu, nhưng nếu bạn có chút thời gian và kiên nhẫn thì nó không khó thực hiện.” Hãy xếp các ổ khóa thành một hàng và bắt đầu kiểm tra chìa khóa… - Nhưng trong trường hợp xấu nhất, đây là 10.000 lần kiểm tra! Ngay cả khi bạn dành bốn giây cho một lần kiểm tra, thì đó là 40 nghìn giây – hơn 11 giờ! – Bạn của tôi, rõ ràng là bạn đã không được dạy toán tốt. Bạn định nhét từng chiếc chìa khóa vào từng ổ khóa phải không? - Tất nhiên, không phải lúc nào bạn cũng gặp may mắn.

TRẺ EM HỌC SINH

– Nhưng bạn chỉ cần cắm chìa khóa đầu tiên 99 lần: nếu vẫn không vừa thì là từ ổ khóa cuối cùng. - Có lẽ. Vậy chỉ có 9900 tờ séc? - Lại qua rồi. Chúng tôi sẽ loại bỏ cặp khóa phím được tìm thấy và 98 lần kiểm tra là đủ cho khóa thứ hai. - Đó là sự thật. Và khóa thứ ba sẽ phải được kiểm tra không quá 97 lần, v.v. Hóa ra một số tiền khủng khiếp: 99 98 … 2 1 0. Kỳ lạ thay, chiếc chìa khóa thứ một trăm của tôi lại yêu cầu 0 séc? – Tất nhiên, khóa của anh ta sẽ được phát hiện tự động. – Số tiền này bằng bao nhiêu? – Theo truyền thuyết, cậu bé Gauss đã tìm ra điều đó gần như ngay lập tức nhờ một thủ thuật nhỏ. Anh ta lấy hai tổng như vậy và chia các số hạng thành 100 cặp 99 0, 98 1, 97 2, …, 0 99, mỗi cặp cho 99. Điều này có nghĩa là tổng ban đầu là $50 ˜^{99}$, tức là 4950 séc. Bốn giây cho mỗi lần kiểm tra - chính xác là năm giờ rưỡi. Bây giờ hãy để tôi đi - thực sự, những chuyện vặt vãnh này chỉ làm tình trạng của tôi trở nên tồi tệ hơn. - Nhưng Holmes, trong nhật ký của mình, Moriarty tuyên bố đã tìm ra cách phân phối chìa khóa nhanh hơn 4950 tờ séc và có sự đảm bảo! Đúng là anh ấy đã không giải thích điều đó - họ nói, phương pháp này phức tạp đến mức không có đủ chỗ trong nhật ký… - Ồ, niềm đam mê của anh ấy với những hiệu ứng rẻ tiền. Nhanh hơn 4950 lần kiểm tra? Holmes rơi vào im lặng hồi lâu. Thật đáng kinh ngạc, sau một thời gian, khuôn mặt anh bắt đầu trở nên sống động và một tia sáng quen thuộc hiện lên trong mắt anh. – Thú vị lắm, Watson. Moriarty là giáo sư toán học, nhưng có vẻ như ông đã sai ở đây. Và tôi sẽ chứng minh điều đó! - Anh sẽ chứng minh điều đó chứ? Làm thế nào điều này có thể được chứng minh? Điều gì sẽ xảy ra nếu anh ta có một phương pháp xảo quyệt, chưa được biết đến… - Watson, anh có quen với việc chứng minh toán học không? Hãy để tôi kiểm tra bạn. Bạn có đồng ý rằng trước tiên bạn cần tìm ít nhất một cặp chìa khóa phù hợp không? - Ừm… có lẽ, đúng vậy, vì hoàn toàn không rõ có thể làm được điều gì khác ở đây -

34

KVAN T 2023/№1

thùng. Đợi đã… Nhưng rồi mọi thứ đều rõ ràng! Nếu bạn hoàn toàn không may mắn, bạn sẽ không tìm thấy cặp đầu tiên nhanh hơn trong 99 séc, cặp thứ hai - trong 98… Và đây rồi, tổng của chúng ta, đây là mức tối thiểu! - Chúng tôi bị bắt ngay. Tại sao bạn không thể nhét các chìa khóa khác nhau vào các ổ khóa khác nhau, thực hiện nhiều lần kiểm tra như vậy và sau đó đột nhiên hiểu ngay về một số chìa khóa và ổ khóa cái gì đi với cái gì? - Điều này có vẻ không hợp lý… - Bạn có đảm bảo là chắc chắn sẽ không thành công không? - Thực sự thì tôi không biết. “Vậy thì bạn vẫn chưa có bằng chứng.” - Sao có thể thế được? - Hãy cố gắng lý luận theo thứ tự. Trực giác mách bảo tôi rằng không có thuật toán nào đảm bảo thành công với ít hơn 4950 lần thử. Và con quỷ Moriarty này tuyên bố rằng có một thuật toán. Vâng, hãy coi như giáo sư đã đúng. Và chúng ta sẽ đẩy anh ta vào bẫy - tất nhiên là về mặt tinh thần. “Nhưng để làm được điều này, bạn phải đưa cho anh ta, thậm chí về mặt tinh thần, một bộ chìa khóa và ổ khóa để anh ta không xử lý được?” “Đó chính xác là những gì chúng tôi sẽ làm.” Hãy tưởng tượng, chúng tôi đã đưa cho anh ấy ổ khóa và chìa khóa. Giáo sư lấy một loại chìa khóa nào đó và chèn vào

đi vào ổ khóa nào đó… Nếu anh ta đoán đúng, chúng ta lập tức đổi bên trong ổ khóa này bằng ổ khóa khác sao cho chìa khóa không vừa. - Chúng tôi là quý ông, không phải kẻ lừa đảo, và chúng tôi sẽ không… - Watson, chúng tôi chỉ kiểm tra xem thuật toán có hoạt động trong mọi trường hợp hay không. Do đó, việc thay thế như vậy là khá hợp pháp - các ổ khóa không thể phân biệt được và giáo sư có thể đã bắt gặp một chiếc ổ khóa có nội thất khác. - Tiếp theo là gì? – Anh ta kiểm tra một số cặp khóa tiếp theo. Và một lần nữa, nếu cần, chúng tôi thay đổi phần bên trong của các ổ khóa để chiếc chìa khóa này cũng không vừa - miễn là tất cả các lần kiểm tra trước đó không làm thay đổi kết quả… - Nhưng bạn không thể làm điều này đến vô cùng, đến một lúc nào đó, chiếc chìa khóa tiếp theo chắc chắn sẽ vừa. - Cậu nói đúng. Nhưng chờ đã! Tại sao sau đó kiểm tra phím này? - Xin lỗi, Holmes, tôi không hiểu. – Moriarty không phải là kẻ ngốc. Anh ta có hồ sơ về tất cả các lần kiểm tra mà anh ta đã thực hiện. Cho đến nay, chưa có một chiếc chìa khóa nào hoạt động. Và thế là anh ta nhét chìa khóa X vào ổ khóa Y, và - thật kinh khủng - chúng ta không thể thay đổi được gì cả

35

“Lượng tử”

VÌ

TRẺ HƠN

các vị trí mà không làm hỏng kết quả trước đó, do đó khóa không khớp. Nhưng rồi chính Moriarty sẽ hiểu điều này! - Nhưng bằng cách nào, Holmes? – Anh ta có thể suy nghĩ kỹ tất cả các ổ khóa và chìa khóa có thể trùng khớp. Và vì không có sự trùng khớp nào bảo toàn kết quả của những lần kiểm tra trước đó, trong đó khóa X và khóa Y không khớp với nhau nên nó sẽ phát hiện ra điều này. – Tại sao không có thư từ như vậy? “Nếu không chúng tôi đã tìm thấy anh ấy và cho kết quả xét nghiệm tiếp theo là âm tính.” – Hơi rắc rối một chút… – Anh không nên nghi ngờ điều đó đâu, Watson. Nhưng nếu bạn muốn, thì chúng ta sẽ nói với giáo sư, giống như một quý ông, rằng ông ấy đã đoán đúng và không cần phải thực hiện việc kiểm tra này. - Nhưng tại sao vậy, Holmes? – Tôi cảm thấy điều này rất quan trọng để chứng minh! Rốt cuộc, bây giờ chúng ta có quyền cho rằng thuật toán của giáo sư như sau: ông ấy kiểm tra rất nhiều, kết quả luôn âm tính, và đến một lúc nào đó ông ấy chợt hiểu ra về tất cả các chìa khóa, cái nào thuộc về ổ khóa nào! – Về tất cả các chìa khóa? - Vâng, vâng. Đầu tiên có thể là về một hoặc nhiều phím cùng một lúc. Khi mọi thứ trở nên rõ ràng với anh ta về một số khóa, anh ta không kiểm tra chúng mà hành động sâu hơn theo thuật toán của riêng mình, chỉ thực hiện những kiểm tra có thể cho kết quả âm tính. Và chúng tôi sẽ đảm bảo kết quả tiêu cực này. Cho đến khi anh ấy hiểu mọi thứ về tất cả các chìa khóa. - Và sau đó? – Đề nghị của bạn là gì, bạn của tôi? - Không có chút ý tưởng nào cả. – Có vẻ như chúng ta đang đi cùng một hướng… Vậy thì tôi có một yêu cầu - bây giờ, hãy phát triển cho giáo sư một cách thuận tiện và nhỏ gọn để ghi lại kết quả kiểm tra của ông ấy, và tôi sẽ suy nghĩ thêm một chút. Holmes tựa lưng vào ghế và rít một hơi từ tẩu thuốc. Khoảng nửa tiếng trôi qua thì đột nhiên… - Eureka! Watson, mọi thứ đều rõ ràng với tôi. Bạn dạo này thế nào? – Như bác sĩ ghi chép thường xuyên

TRẺ EM HỌC SINH

về tình trạng bệnh nhân của mình, tôi nghĩ rằng tôi có thể ghi lại tất cả các lần kiểm tra liên tiếp vào một cuốn sổ. Nhưng nếu bạn tiết kiệm không gian, có lẽ tốt hơn là bạn nên đánh số các phím và ổ khóa rồi vẽ các ô $таблицу,^{100} u^{100}$ lớn. Và khi kiểm tra, chẳng hạn như cặp “chìa khóa thứ 6, khóa thứ 75”, hãy đặt dấu cộng ở dòng thứ 6 ở ​​vị trí thứ 75 nếu chìa khóa vừa và dấu trừ nếu nó không vừa. - Hoan hô, Watson. Phương pháp này cực kỳ thuận tiện. Hãy để tôi nhắc bạn rằng Moriarty luôn đặt ra những điểm trừ. Anh ấy sẽ cung cấp ít hơn 4950 chiếc và đột nhiên anh ấy sẽ hiểu, phải không? – Đúng vậy, khi kết thúc công việc của thuật toán, nó sẽ chỉ nêu bật tất cả những ưu điểm. Sherlock Holmes nhăn mặt. – Những ưu điểm này, chúng có thể tạo thành một bức tranh khá hỗn loạn… Không sao, bây giờ chúng ta sẽ sắp xếp theo thứ tự. Rốt cuộc, 100 điểm cộng này nằm ở mỗi cột và mỗi hàng. Nhưng hãy chú ý, Watson - trong bảng của chúng tôi, bạn có thể sắp xếp lại các hàng và cột mà không có gì bị hỏng - nếu bạn sắp xếp lại các phím và ổ khóa cho phù hợp, phải không? - Có lẽ, đúng vậy. “Sau đó, chúng ta sẽ tìm dấu cộng ở cột đầu tiên và di chuyển hàng có dấu cộng này lên trên cùng, sau đó chúng ta sẽ tìm dấu cộng ở cột thứ hai và đặt hàng có dấu cộng này ngay bên dưới hàng đầu tiên, v.v.” – Bạn muốn các điểm cộng xếp ngay ngắn theo đường chéo? - Đúng. Điều này là không cần thiết nhưng nó sẽ làm cho lời giải trở nên đặc biệt rõ ràng. Vì vậy, ít hơn 4950 điểm trừ được đưa vào bảng, sau đó các điểm cộng được xếp theo đường chéo rõ ràng, không còn lựa chọn nào khác. Nhưng 4950 là gì? Có bao nhiêu ô trong bảng? – Ta có bảng 100 và 100, tổng cộng là 10.000 ô. – Có bao nhiêu ô trên đường chéo? - Tất nhiên là 100. - Điều này có nghĩa là còn lại 9900 ô để trừ, trong đó có ít hơn 4950 - chưa đến một nửa số ô còn lại! - Anh đang có ý gì vậy, Holmes? – Chúng ta cần chia các ô thành từng cặp đối xứng nhau theo đường chéo! tôi đây