Tìm kiếm một mục

55

A. Orlov

chủ đề Ponsk

Số căn hộ

Hãy nghe câu chuyện mà người hàng xóm Lyusya kể cho tôi *).

— Ngôi nhà tám tầng mới của chúng tôi có hai lối vào. Cửa của bốn căn hộ mở vào từng phòng giam. Hôm qua mọi người gặp tôi ngoài sân và hỏi tôi sống ở căn hộ nào. Tôi trả lời:

• Bạn có thể đoán được. Anh ấy có thể hỏi tôi những câu hỏi, chỉ cần lưu ý rằng tôi sẽ chỉ trả lời “có” hoặc “không”.
  Một cậu bé lập tức nói:
• Không có gì sai cả. Tôi sẽ hỏi bạn có đúng là bạn sống ở căn hộ số 1, số 2, số 3, số 4, …
  …, số 63, cho đến khi bạn nói có.
  Và nếu bạn luôn nói “không” thì bạn đang sống ở căn hộ số 64.
  Tôi sẽ cần hơn sáu mươi ba câu hỏi.

Nhưng rồi cô gái ngắt lời anh:

• Nghĩ mà xem, sáu mươi ba!
  Ba mươi hai câu hỏi là đủ đối với tôi! Đầu tiên tôi tìm xem bạn sống ở lối vào nào. Tôi sẽ hỏi: “Bạn sống ở lối vào đầu tiên phải không?” Nếu bạn trả lời “có”, điều đó có nghĩa là lần đầu tiên; Nếu bạn trả lời “không” - trong phần thứ hai. Và sau đó tôi sẽ đi qua tất cả các căn hộ ở lối vào theo thứ tự.
  “Và với tôi thì mười bốn là đủ rồi!” đứa nhỏ nhất hét lên vui vẻ

từ toàn bộ công ty. “Tôi đã tìm ra tầng này trong bảy câu hỏi và căn hộ ở tầng đó trong bảy câu hỏi khác!”

“Bạn nghĩ sao,” Lucy hỏi tôi, “sẽ cần bao nhiêu câu hỏi để tìm ra số căn hộ?”

Tôi trả lời ngay cho Lyusya: “Năm câu hỏi chưa đủ, nhưng sáu câu hỏi là đủ”. Đầu tiên tôi hỏi:
— Có đúng là bạn sống ở lối vào đầu tiên không?

Lucy trả lời: “Không,” và tôi nhận ra rằng căn hộ của cô ấy nằm ở lối vào thứ hai. Câu hỏi thứ hai phức tạp hơn:

• Có đúng là bạn sống dưới sàn nhà không?
• Đúng.
• Có đúng là cái thứ ba thấp hơn không?
• KHÔNG.
• Đến một phần ba?
• KHÔNG.

Điều này có nghĩa là Lucy sống ở lối vào thứ hai trên tầng bốn. Tôi còn hai câu hỏi dành cho bốn căn hộ “đáng ngờ” - số 45, số 46, số 47 và số 48 (dễ dàng tính toán rằng cửa của bốn căn hộ này mở ra tầng 4 ở lối vào thứ hai).

— Có đúng là số căn hộ của bạn lớn hơn 46 không?

• KHÔNG.
  – Bạn sống ở căn hộ số 45 phải không?
• KHÔNG.
  “Vậy là cậu sống ở căn hộ số 46,” tôi đắc thắng nói.

Bạn có hiểu tại sao lại cần rất ít 问卷 không? Mỗi câu hỏi của tôi chia số lượng căn hộ “đáng ngờ” (trong đó có những số đáp số “có” và những số đáp số “không”. Trong mọi trường hợp, số lượng căn hộ “đáng ngờ” đã giảm đúng một nửa.

Có thể chứng minh rằng không thể đạt được sự chắc chắn trong năm câu hỏi.

56

Bảng sau đây sẽ giúp chúng ta ở đây:

0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
0 0 1 0 0
1 1 1 1 0
1 1 1 1 1

Chúng tôi sẽ viết đáp số của Lucina bằng các số 1, 0. Nếu cô ấy trả lời “có”, chúng tôi sẽ viết “1”, và nếu không thì viết “0”. Chúng ta viết đáp số đầu tiên trong phần đơn vị, số thứ hai trong phần chục, v.v. Sau đó, chúng ta có thể viết bất kỳ tổ hợp nào của năm đáp số dưới dạng số một và số không, số đó sẽ là một số có năm chữ số, mỗi chữ số là số 0 hoặc một. Hãy viết tất cả các số như vậy theo thứ tự tăng dần - chúng ta sẽ có được bảng của mình. Tổng cộng có 32 số.

Bây giờ, giả sử rằng chúng ta luôn đoán được căn hộ qua năm câu hỏi. Điều này có nghĩa là, khi biết số có năm chữ số được tạo thành từ số 0 và số 1, chúng ta có thể gọi tên chính xác số căn hộ. Nhưng vì chúng ta có 32 số có năm chữ số nên chúng ta chỉ có thể đặt tên cho 32 căn hộ chứ không phải 64 như trong điều kiện.

Số điện thoại

Bạn muốn tìm ra số điện thoại có bảy chữ số của tôi bằng cách hỏi tôi những câu hỏi mà tôi sẽ chỉ trả lời “có” hoặc “không”. Hãy nghĩ ra cách đảm bảo thành công với số lượng câu hỏi ít nhất.

Một đồng tiền giả

Có 26 đồng xu giống hệt nhau. Trong số đó, một chiếc là giả, nó nhẹ hơn những chiếc còn lại. Có cân cốc (không có con trỏ hoặc quả cân). Số cân nhỏ nhất có thể dùng để tìm một đồng xu giả là bao nhiêu?

bài toán này có thể được giải theo cách tương tự như cách trước. Chỉ có bạn nên cố gắng giảm hơn một nửa số lượng xu “đáng ngờ”,

57

a trong ba: xét cho cùng, mỗi lần cân có ba kết quả có thể xảy ra - cốc bên trái nặng hơn, cốc bên phải nặng hơn, cốc cân bằng. Vì vậy, đầu tiên chúng ta đặt 9 đồng xu vào mỗi cốc. Nếu cốc bên trái nặng thì đồng tiền giả nằm ở cốc bên phải; nếu cốc bên phải nặng hơn thì đồng tiền giả nằm ở cốc bên trái; nếu các cốc cân bằng thì đồng tiền giả là trung bình cộng của các đồng xu không đặt lên cân. Điều này có nghĩa là sau lần cân đầu tiên, vẫn còn 9 hoặc thậm chí 8 đồng xu “đáng ngờ”. Sau đó, chúng ta sẽ đặt ba đồng xu “đáng ngờ” vào mỗi cốc. Sau lần cân thứ hai, vẫn còn lại ba hoặc hai đồng xu “đáng ngờ”. Bằng cách đặt một trong số chúng lên cốc, chúng ta sẽ tìm ra đồng xu nào là giả.

Không có cách nào để phát hiện chắc chắn một đồng tiền giả trong hai lần cân, bởi vì bất kỳ đồng nào trong số 26 đồng xu đều có thể là tiền giả và chỉ có 9 kết quả có trọng số của hai lần cân (mỗi kết quả trong số ba kết quả của lần cân đầu tiên có thể được kết hợp với mỗi kết quả trong số ba kết quả của lần cân thứ hai) và 9 nhỏ hơn 26.

Cuộc thảo luận

Bạn có hiểu nhiệm vụ chung của chúng ta là gì không? Có căn hộ, có tiền xu; có những câu hỏi, ở đây có những sự cân nhắc. Và họ có rất nhiều điểm chung. Cả ở đây và ở đó, chúng tôi đều đặt câu hỏi: trong một trường hợp với Lucy, trường hợp khác với Libra, và chúng tôi nhận được đáp số: trong một trường hợp từ Lucy, trường hợp khác từ Libra.

Các nhà khoa học cũng làm điều tương tự khi họ tiến hành một thí nghiệm - họ đặt câu hỏi. Có một câu nói nổi tiếng: “Một thí nghiệm vật lý là một câu hỏi mà chúng ta đặt ra cho thiên nhiên”. Tất nhiên, không chỉ các nhà vật lý, mà cả các nhà hóa học và nhà sinh học—tất cả những người nghiên cứu về tự nhiên—đều có thể nói điều này về các thí nghiệm của họ. Và nếu bạn muốn trở thành nhà toán học thực thụ, thì bạn cần có khả năng đặt câu hỏi.

Mối liên hệ bài toán của chúng tôi với một trong những nhánh toán học hiện đại - lý thuyết thông tin. Ví dụ, cách nhanh nhất để truyền tải thông điệp về một số điện thoại là gì nếu chúng ta chỉ có hai loại tín hiệu? Đây là lý thuyết thông tin bài toán điển hình. Bạn có thể đọc thêm về lý thuyết này trong cuốn sách “Xác suất và thông tin” của A. M. Yaglom và I. M. Yaglom (M., “Nauka”, 1973).

Thêm hai đồng tiền giả nữa

a) Trước mặt bạn đặt sáu đồng xu giống hệt nhau, trong đó có hai đồng tiền giả (mỗi đồng nặng hơn đồng thật 1 e). Bạn cũng có một thang đo không có con trỏ hoặc thang đo. Tuy nhiên, những chiếc cân này không nhạy lắm và phản ứng với sự chênh lệch trọng lượng ít nhất là 2 e. Tìm cách nhận biết cả hai đồng tiền giả trong bốn lần cân.

6. Có sáu đồng xu giống hệt nhau. Bốn trong số đó là thật, mỗi quả 4 e và hai quả là giả, với tổng khối lượng là 8 e: một quả nặng hơn một chút, quả kia nhẹ hơn. Số lần cân nhỏ nhất trên một chiếc cân cốc không có kim chỉ hoặc cân cần thiết để cân cả hai đồng tiền giả và xác định đồng tiền nào nhẹ hơn, đồng tiền nào nặng hơn?

Griri phổ quát

Chọn khối lượng của bốn griri sao cho chúng có thể được sử dụng để đo bất kỳ số gam nào từ 1 đến 40 trên thang cốc. (Có thể đặt Griri lên cả hai cốc.)

Câu đố đoán với chướng ngại vật

Bạn sẽ đoán lại số điện thoại có bảy chữ số, nhưng bây giờ tôi có thể trả lời sai một trong những câu hỏi của bạn đáp số. Khi đó bạn sẽ hỏi những câu hỏi nào và bạn sẽ cần ít nhất bao nhiêu câu hỏi?