Tìm số của riêng bạn trong một hộp

Question

100 (hoặc một số thậm chí số 2N :-)) tù nhân đang ở trong một phòng A. Họ được đánh số từ 1 đến 100.

Từng người một (từ tù nhân số 1 đến tù nhân # 100, theo thứ tự), họ sẽ được đưa vào phòng B trong đó 100 hộp (đánh số từ 1 đến 100) đang đợi họ. Bên trong hộp (đóng) là các số từ 1 đến 100 (các số bên trong các hộp được uốn ngẫu nhiên!).

Khi ở trong phòng B, mỗi tù nhân được mở 50 hộp (anh ta chọn người mà anh ta mở). Nếu anh ta tìm thấy số đã được giao cho anh ta trong một trong 50 hộp, tù nhân được đi vào một phòng C và tất cả các hộp được đóng lại trước khi người tiếp theo bước vào phòng B từ phòng A. Nếu không, tất cả các tù nhân (trong phòng A, B và C) bị giết.

Trước khi vào phòng B, các tù nhân có thể đồng ý về chiến lược (thuật toán). Không có cách nào để giao tiếp giữa các phòng (và không có thông điệp nào có thể được để lại trong phòng B!).

Có thuật toán nào tối đa hóa khả năng tất cả các tù nhân sống sót không? Thuật toán đó có thể đạt được xác suất nào?

Ghi chú:

• Làm điều ngẫu nhiên (những gì bạn gọi là 'không có chiến lược') thật sự mang một xác suất 1/2 cho mỗi tù nhân, nhưng sau đó xác suất của tất cả trong số họ sống sót là 1/2^100 (khá thấp). Người ta có thể làm tốt hơn nhiều!

• Các tù nhân không được phép sắp xếp lại các ô!

• Tất cả các tù nhân bị giết lần đầu tiên một tù nhân không tìm thấy số của mình. Và không thể giao tiếp được.

• Gợi ý: người ta có thể tiết kiệm được hơn 30 tù nhân trung bình, mà là nhiều hơn nữa mà (50/100) * (50/99) * [...] * 1

Answer 1

Câu đố này được giải thích tại http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml và người đó thực hiện tốt hơn công việc giải thích vấn đề.

Tuyên bố "tất cả các tù nhân bị giết" là sai. "Bạn có thể tiết kiệm 30+ trung bình" cũng sai, article nói rằng 30% thời gian bạn có thể tiết kiệm 100% số tù nhân.

Answer 2

Thực hiện thuật toán phân loại và sắp xếp các hộp theo các số bên trong chúng.

Tù nhân thứ nhất sắp xếp 50 hộp và tù nhân thứ hai sắp xếp 50 ô còn lại và hợp nhất với người thứ nhất. (Lưu ý rằng tù nhân thứ hai có thể đoán các giá trị trong 50 hộp đầu tiên)

Sau khi tù nhân thứ 2, tất cả các hộp sẽ được sắp xếp theo thứ tự sắp xếp !!!

Mọi người khác có thể mở các hộp chứa số của chúng một cách dễ dàng sau đó.

Answer 3

Tôi tìm ra giải pháp công nghệ thấp cho loại vấn đề này luôn là cách tốt nhất để đi.

đầu tiên chúng tôi thực hiện một số giả định về tình hình

• Các tù nhân là không phải tất cả các lập trình viên hoặc các nhà toán học
• Họ không muốn chết
• Các lính canh cũng được trang bị

Vì vậy, với một cơ hội 0,005% mà họ sẽ thấy ngày mai, có một giải pháp công nghệ rất đơn giản và thấp cho vấn đề này. RIOT

tất cả về lỗ và lợi ích tiềm năng, cơ hội là các tù nhân vượt xa số bảo vệ và sử dụng nhau làm lá chắn, vì tất cả họ đều là người chết nếu không, họ có thể tăng cơ hội họ sẽ vượt qua quyền lực bảo vệ, một khi họ có vũ khí của mình có cơ hội đi lên, giúp họ hơn quyền lực bảo vệ nhiều hơn để có được nhiều năng lượng lửa hơn nữa để tăng tỷ lệ sống sót. một khi các lính canh nhận ra những gì đang xảy ra, họ có thể sẽ chạy trên những ngọn đồi và khóa nhà tù, điều này sẽ đưa cho giới truyền thông một cái đầu và sau đó là vấn đề nhân quyền.

Answer 4

Có lẽ tôi không đọc đúng, nhưng câu hỏi có vẻ là thông tin được xây dựng hoặc thiếu thông tin sai.

Nếu ông tìm thấy con số đó đã được giao cho ông trong một trong những 50 hộp, các tù nhân được cho đi vào phòng C và tất cả các hộp được đóng một lần nữa trước khi người tiếp theo bước vào phòng B từ phòng A. Nếu không, tất cả tù nhân (trong phòng A, B và C) sẽ bị bị giết.

Câu cuối cùng có nghĩa là tất cả các tù nhân đều bị giết lần đầu tiên tù nhân không tìm thấy số của họ? Nếu không, điều gì sẽ xảy ra với các tù nhân không tìm thấy số của họ?

Nếu không thể giao tiếp, và bất cứ khi nào một tù nhân vào phòng B, nó luôn ở trạng thái giống nhau thì không có khả năng cho chiến lược.

Các tù nhân có thể nói trước khi rời phòng A hộp số nào họ sẽ mở. Nhưng nếu không có tù nhân tiếp theo biết liệu họ có thành công hay không (giả định thất bại vì không phải là thất bại cho tất cả) khi tù nhân tiếp theo vào phòng B họ vẫn có cùng tỷ lệ chọn số của họ là tù nhân trước (luôn luôn 1: 100) .

Nếu thất bại cho một thất bại, thì khi biết hộp mà các tù nhân trước đó mở ra, và do thực tế là họ chưa bị giết, mỗi tù nhân liên tiếp có thể giảm tỷ lệ chọn sai hộp bởi một hộp. tức là 1: 100 cho tù nhân đầu tiên, 1:99 cho người thứ hai, xuống đến 1: 1 cho người cuối cùng.

Answer 5

Các tù nhân có thể đồng ý rằng tù nhân 1 hộp mở 1-50.

Nếu tất cả họ vẫn còn sống, họ đồng ý rằng tù nhân tiếp theo sẽ mở hộp 2-51. (2 là tùy ý, nhưng đơn giản để nhớ quy tắc này) tỷ lệ cược của ông sống sót cho rằng P1 sống sót bây giờ là 50/99. Bạn muốn loại bỏ mở một hộp khi bạn biết rằng anh chàng trước đó tìm thấy của mình.

Tôi không biết nếu đó là tối ưu, nhưng nó tốt hơn rất nhiều so với ngẫu nhiên.

Xác suất sống sót trông giống như

50/100 * 50/99 * 50/98 *. . .50/51 * 1

Answer 6

Tôi không biết nếu điều này được cho phép nhưng xấp xỉ tốt nhất mà tôi có thể tìm thấy là:

EDIT: Ok, tôi nghĩ rằng điều này làm cho nó. Tất nhiên tôi đang xử lý vấn đề này như một vấn đề về máy tính, tôi không nghĩ rằng bất kỳ người giám sát nào sẽ có thể thực hiện điều này, mặc dù là khá thẳng về phía trước nếu bạn không.

Tìm 50 số nguyên tố đầu tiên, giả sử chúng ta giữ chúng trong một mảng được gọi là số nguyên tố.

• Prissioner đầu tiên vào phòng B và mở hộp đầu tiên và tìm số m.
• số nguyên tố Chờ [1]^m (đó sẽ là 3^m)
• mở hộp 2 và đọc số -> n
• Chờ (số nguyên tố [2]^n - 1) * số nguyên tố [1 ]^m, đó sẽ là (5^n - 1) * 3^m và tổng thời gian anh ta chờ đợi sẽ là 3^n * 5^n

Lặp lại. Sau khi người đầu tiên prisioner tổng thời gian cho anh ta sẽ là: 3^m * 5^n * 7^p ... = X

Trước khi người thứ hai đi vào phòng factorize X. Bạn biết trước các số nguyên tố đã được sử dụng để yếu tố là tầm thường. Làm như vậy bạn có được m, n, p, v.v ... do đó người thứ hai biết tất cả các hộp/số kết hợp các prisioner trước đó được sử dụng.

Xác suất người đầu tiên nhận mọi người bị giết là 1/2, người thứ hai sẽ có 50/(100 - n) (là số lượng của trang đầu tiên) cái thứ ba sẽ có 50/(100 - n - m) (nếu n + m = 100 thì tất cả các vị trí đã biết) và cứ thế.

Rõ ràng là prissioner tiếp theo phải bỏ qua các hộp đã được biết đến (ngoại trừ cho sự lựa chọn cuối cùng nếu hộp đó chứa số của mình đã được biết)

Tôi không biết khả năng chính xác là những gì vì nó dependes trên có bao nhiêu lựa chọn họ phải làm nhưng tôi muốn nói nó khá cao.

EDIT: Rereading, nếu prissioner không phải dừng lại khi nhận được số của mình thì xác suất cho cả nhóm được cải thiện rất nhiều, chính xác là 50%.

EDIT2: @OysterD xem theo cách này. Nếu người đầu tiên prisioner có thể mở 50 hộp sau đó người thứ hai biết nếu số của nó là trong bất kỳ hộp nào. Nếu có, thì anh ta có thể mở 49 người khác (và bằng cách làm như vậy, học tập hộp/số comination của 100 hộp) và cuối cùng mở một của mình. Vì vậy, nếu prissioner đầu tiên succeds sau đó tất cả mọi người succeds. Hãy nhớ rằng mỗi prisioner cung cấp một cách để người khác biết chính xác các hộp/số kết hợp cho mỗi hộp ông mở ra.

Answer 7

Tôi nghĩ rằng vì không có thông tin liên lạc là có thể, chiến lược tốt nhất sẽ bao gồm

phân phối xác suất của mỗi tù nhân như đồng đều càng tốt

Tôi có đi đúng đường hay không?

Thông tin có sẵn cho mỗi tù nhân:

• Số lượng tù nhân survivied, vì vậy nếu bạn có một hệ thống hộp chọn hiệu quả mà sử dụng theo thứ tự bất kỳ tù nhân bước vào phòng B, sau đó một chiến lược là chắc chắn có thể
• Những hộp mà các tù nhân trước đó đã chọn. Tất nhiên, không có thông tin liên lạc nào có thể là trong thời gian chạy và sẽ không thể nhớ bất kỳ hoán vị chọn hộp 100 nào. Nhưng bạn có thể sử dụng thông tin này để tính toán trong hệ thống trước khi bắt đầu chạy.

mất của tôi:

1. Vẽ một bảng các số với 2 cột, cột đầu tiên chứa số hộp (từ hộp # 1 tới hộp # 100). Mỗi tù nhân sau đó được chọn 50 hộp và bất kỳ hộp nào họ chọn, họ nên đặt 1 nhãn lên hàng tương ứng trong cột thứ hai.
2. Tuy nhiên, tất cả các tù nhân được yêu cầu không bao giờ chọn bất kỳ ô nào hai lần. Và không có hộp nào có thể được đánh dấu hơn 50. Một số tù nhân có thể nhận được ít lựa chọn hơn những người khác vì một số hộp có thể được lấp đầy tới 50 điểm trước.
3. Khi một tù nhân được chuyển đến phòng B, anh ta/cô ấy mở bất kỳ hộp nào anh ấy đã đánh dấu.

Answer 8

Khái niệm tương tự.

mất Aonther:

1. Viết ra một danh sách 100 số nhị phân đầu tiên trong đó có năm mươi 1s và 0s năm mươi.
2. Sắp xếp chúng từ thấp nhất đến cao nhất.
3. Tù nhân số 1 nhận số đầu tiên, tù nhân số 2 nhận số thứ hai, tù nhân số 3 đạt số thứ ba và cứ như vậy ...
4. Từng tù nhân nhớ số nhị phân của mình.
5. Khi bất kỳ tù nhân nào được chuyển đến phòng B, anh/cô ấy khớp các chữ số nhị phân của số anh nhớ với từng ô, bit cao nhất được kết hợp với hộp ngoài cùng bên trái, bit cao nhất tiếp theo hộp ngoài cùng bên trái ... bit thấp nhất được kết hợp với hộp ngoài cùng bên phải.
6. Ông/bà sẽ mở ra bất cứ điều gì hộp phù hợp với 1 và rời khỏi hộp kín phù hợp với 0.

Điều này sẽ giảm thiểu xác suất vì tù nhân sớm sẽ có được chữ số đó là khác nhau từ các tù nhân sau đó và tù nhân trong đó có số gần nhau sẽ nhận được các chữ số gần nhau. Điều này không đảm bảo khả năng sống sót nhưng nếu các tù nhân đầu tiên sống sót, rất có thể các tù nhân sau này sẽ có xác suất sống sót cao hơn.

Tôi chưa nghĩ ra các con số chính xác và lý do chính xác, nhưng đây là một giải pháp nhanh chóng mà tôi có thể nghĩ đến vào lúc này.

Answer 9

Nếu tất cả tù nhân bị giết khi ai đó không tìm thấy số của họ thì bạn có thể tiết kiệm được 100 hoặc 0. Không có cách nào để tiết kiệm 30 người.

Answer 10

Không có bất kỳ giới hạn thời gian nào trong câu hỏi nên tôi khuyên các tù nhân nên quyết định lấy 1 giờ mỗi hộp và mở chúng theo thứ tự được trình bày. Nếu tù nhân thứ hai được phép vào phòng sau 2 giờ thì anh ta biết rằng tù nhân đầu tiên tìm thấy số điện thoại của anh ta trong hộp 2. Vì vậy anh ta biết bỏ qua hộp 2 theo thứ tự của mình và mở hộp 1, 3, 4 ... 51 Tỷ lệ cược đầu tiên của các tù nhân khi thua là 50/100 Cho rằng tù nhân đầu tiên sống sót sau đó cơ hội của tù nhân thứ hai là 50/99 Vì vậy, câu trả lời có vẻ là ((50^51) * 49!)/100! mà theo google làm cho 2.89 * 10^-9 đó là khá nhiều nil Vì vậy, ngay cả khi các tù nhân biết các hộp trước đây may mắn tìm thấy số của họ trong đó sẽ không có hy vọng