Trovare il proprio numero in una casella di

https://stackoverflow.com/questions/34345

09-06-2019
|

Domanda

100 (o un numero pari 2N :-) ) prigionieri sono in una sala A.Essi sono numerati da 1 a 100.

Uno per uno (da prigioniero #1 di prigioniero #100, nell'ordine, saranno lasciate in una stanza B 100 caselle numerate da 1 a 100) li attendono.All'interno dell' (chiuso) scatole sono i numeri da 1 a 100 (i numeri all'interno delle scatole sono permutate in modo casuale!).

Una volta all'interno della camera B, ogni prigioniero ottiene per l'apertura di 50 caselle (egli sceglie quale egli apre).Se si trova il numero che è stato assegnato a lui in uno di questi il 50 caselle, il prigioniero arriva a piedi in una stanza C e tutte le finestre sono chiuse di nuovo prima del prossimo si entra in sala B sala A.In caso contrario, tutti i prigionieri (in camere A, B e C) viene ucciso.

Prima di entrare in sala B, i prigionieri possono concordare una strategia (algoritmo).Non c'è modo di comunicare tra le camere (e nessun messaggio può essere lasciato nella sala B!).

C'è un algoritmo che massimizza la probabilità che tutti i prigionieri sopravvivere?Che probabilità significa che l'algoritmo di raggiungere?

Note:

Fare le cose a caso (quello che voi chiamate "non strategia"), al contrario, dà una probabilità di 1/2 per ogni prigioniero, ma allora la probabilità di tutti loro sopravvivenza è 1/2^100 (che è abbastanza basso).Si può fare molto meglio!
I prigionieri non sono autorizzati a riordinare le scatole!
Tutti i prigionieri vengono uccisi la prima volta che un detenuto non riesce a trovare il suo numero. E nessuna comunicazione è possibile.
Suggerimento:uno può salvare più di 30 prigionieri in media, che è molto di più che (50/100) * (50/99) * [...] * 1

Soluzione

Questo puzzle è spiegato alla http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml e la persona che fa un lavoro molto migliore di spiegare il problema.

"Tutti i prigionieri vengono uccisi" affermazione è sbagliata.Il "si può risparmiare il 30+ media" è sbagliato, il articolo dice che il 30% del tempo è possibile risparmiare 100% dei prigionieri.

Altri suggerimenti

Ho trovato un low tech soluzione a questo tipo di problema è sempre il modo migliore per andare.

prima facciamo alcune ipotesi circa la situazione

I prigionieri non sono tutti programmatori o matematici
Non voglio morire
Le guardie sono armate

Così, con un 0,005% di probabilità di vedere il domani, c'è una molto semplice e low tech soluzione a questo problema. RIOT

tutti i suoi circa le perdite v potenziale di guadagno, le probabilità sono che i prigionieri lontano numero di guardie, e l'utilizzo di ogni altro come scudi umani, in quanto sono tutti morti comunque se non, essi possono aumentare la probabilità di una loro forza, una guardia, una volta che la sua arma non c'possibilità va, aiutandoli potere più guardie per ottenere più potenza di fuoco per aumentare ulteriormente c'tasso di sopravvivenza.una volta che le guardie di rendersi conto di cosa succede, probabilmente correre per le colline e bloccare il carcere, questo darà il supporto di un testa a testa, e quindi la sua una questione di diritti umani.

Implementare un algoritmo di ordinamento per ordinare le caselle secondo i numeri al loro interno.

Primo prigioniero ordinamenti 50 scatole, e il secondo prigioniero ordina l'altro 50 e si fonde con il primo.(Si noti che il secondo prigioniero in grado di indovinare i valori all'interno del primo 50 scatole)

Dopo il 2 ° prigioniero, tutte le caselle saranno ordinati !!!

Tutti gli altri possono aprire le scatole contenenti i loro numeri di facilmente, allora.

Non so se questo è consentito, ma la migliore approssimazione che posso trovare è:

EDIT:Ok, penso che questo rende.Naturalmente sto trattando questo come un problema del calcolo, non credo che tutti I prisioner sarà in grado di eseguire questo, anche se è abbastanza dritto in avanti, se non.

Trovare i primi 50 numeri primi, facciamo asume le teniamo in un array chiamato i numeri primi.

Il primo prissioner entra in camera B e apre la prima casella e trova il numero di m.
Attendere primes[1]^m (che sarebbe la 3^m)
Aprire la casella 2 e leggere il numero --> n
Attendere (primes[2]^n - 1) * primes[1]^m, che sarebbe (5^n - 1) * 3^m e il tempo totale è stato di attesa sarebbero 3^n * 5^n

Ripetere.Dopo il primo prisioner il tempo totale per lui sarebbe:3^m * 5^n * 7^p ...= X

Prima della seconda prisioner entra nella stanza ridurre X.Sapete in anticipo i numeri primi che sono stati utilizzati in modo fattorizzazione è banale.Così facendo si ottiene m, n, p, ecc in modo che la seconda prisioner conosce ogni casella/combinazione di numero precedente prisioner utilizzato.

La probabilità che il primo a ottenere tutti uccisi è di 1/2, il secondo 50 / (100 - n) (essendo n il numero di tentativi di primo), la terza avrà 50 / (100 - n - m) se n + m = 100, allora tutte le posizioni sono note), e così via.

Ovviamente la prossima prissioner deve saltare il già noto caselle (fatta eccezione per l'ultima scelta, se la scatola che contiene il suo numero è già noto)

Non so qual è l'esatta possibilità come dependes come molte scelte che hanno a che fare, ma direi che è abbastanza alta.

EDIT:Rileggendo, se il prissioner, non deve fermarsi quando egli ottiene il suo numero, quindi, la probabilità per l'intero gruppo è notevolmente migliorata, esattamente il 50%.

EDIT2:@OysterD vedere in questo modo.Se il primo prisioner in grado di aprire 50 scatole poi la seconda a sapere se il suo numero è in qualsiasi di caselle.Se lo è, allora si può aprire altri 49 (e così facendo l'apprendimento di box/numero di una combinazione di tasti di 100 caselle) e, infine, aprire il suo uno.Quindi, se il primo prissioner riesce quindi a tutti riesce.Ricordate che ogni prisioner fornisce un modo per gli altri di conoscere esattamente le scatole, la combinazione di numero per ogni scatola che si apre.

Forse non sto leggendo a destra, ma la questione sembra essere mal costruiti o informazioni mancanti.

Se si trova il numero di assegnato a lui in uno di questi il 50 caselle, il prigioniero arriva a piedi in una stanza C e tutte le finestre sono chiuse di nuovo prima che il prossimo passeggiate in sala B sala A.In caso contrario, tutti prigionieri nelle camere A, B e C) si ucciso.

L'ultima frase non significa che tutti i prigionieri vengono uccisi la prima volta che un detenuto non riesce a trovare il loro numero?Se no, cosa succede ai prigionieri che non trovano il loro numero?

Se la comunicazione non è possibile, e ogni volta che un prigioniero entra in camera B è sempre nello stesso stato, non vi è alcuna possibilità per una strategia.

I prigionieri potessero dire prima di lasciare la sala che Un numero di box che stanno per aprire.Ma senza successiva prigionieri sapere se hanno avuto successo o meno (supponendo che il fallimento non è mancata per tutti) quando il prossimo prigioniero entra in camera B hanno ancora le stesse probabilità di prendere il loro numero è come la precedente prigioniero (sempre 1:100).

Se il fallimento è il fallimento per tutti, quindi, sapendo che la casella di precedenti prigionieri aperto, e in forza del fatto che essi non sono stati tutti uccisi, ogni successiva prigioniero potrebbe ridurre le probabilità di prendere la cassa sbagliata, da una scatola.cioè1:100 per il primo prigioniero, 1:99 per il secondo, fino a 1:1 per l'ultimo.

I prigionieri potrebbero essere d'accordo che il prigioniero 1 aprire le scatole 1-50.

Se sono ancora vivi, sono d'accordo che la prossima prigioniero apre finestre di 2-51.(il 2 è arbitrario, ma è semplice per ricordare questa regola) le Sue probabilità di sopravvivere dato che P1 è sopravvissuto ora sono 50/99.Si desidera eliminare l'apertura di un dialogo quando si sa che la precedente ragazzo ha trovato il suo.

Non so se è ottimale, ma è molto meglio di quanto casuale.

La probabilità di sopravvivenza che sembra

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

Penso che dal momento che non è possibile la comunicazione, la strategia migliore sarebbe coinvolgere

la distribuzione di probabilità di ogni prigionieri nel modo più uniforme possibile

Sono sulla strada giusta o no?

Informazioni disponibili per ogni prigioniero:

Il numero di survivied prigionieri, quindi, se si dispone di un efficiente box sistema di raccolta che utilizza l'ordine di qualsiasi prigioniero, entra in sala B, quindi una strategia è sicuramente possibile

Che scatole precedenti prigionieri prelevati.Naturalmente, nessuna comunicazione è possibile durante la corsa e non sarebbe possibile ricordare 100s casella di raccolta di permutazione. Ma è possibile utilizzare queste informazioni per calcolare in un sistema prima inizia la pista.

Il mio prendere:

Disegnare una tabella di numeri con 2 colonne, la prima colonna contiene il numero di casella (casella da #1 a box#100).Ogni prigioniero e poi viene a prendere 50 scatole e qualunque sia la scatola che il plettro, si dovrebbe inserire 1 segno nella corrispondente riga della seconda colonna.

Tutti i prigionieri sono tuttavia tenuti a non prendere qualsiasi box doppio.E non potrebbe essere segnato più di 50.Alcuni detenuti possono avere meno opzioni rispetto ad altri, in quanto alcuni di dialogo può ottenere riempito al 50 marchi di prima.

Quando un detenuto è trasferito a camera B lui/lei apre qualsiasi caselle di ha segnato su.

Se tutti i prigionieri vengono uccisi quando qualcuno non riesce a trovare il loro numero si sia risparmiare 100 o 0.Non c'è modo di salvare 30 persone.

Stesso concetto.

Aonther prendere:

Scrivere un elenco dei primi 100 numeri binari che ha cinquanta 1s e cinquanta 0s.

Ordina dal più basso al più alto.

Prigioniero #1 ottiene il primo numero, prigioniero #2 ottiene il secondo, prigioniero #3 ottiene il terzo e così via...

Ogni prigioniero ricorda la sua/il suo numero binario.

Quando ogni prigioniero è trasferito a camera B, poi corrispondere le cifre binarie del numero ricordava con ogni casella, il bit più alto è abbinato con la prima casella a sinistra, la prossima bit più alto è abbinato con il secondo prima casella a sinistra ...il bit più basso è abbinato con la casella all'estrema destra.

Lui/lei apre qualsiasi caselle abbinato con 1 e lasciare scatole chiuse, abbinato con 0.

Questo sarebbe minimizza la probabilità perché i primi prigionieri saranno mostrati anche le cifre che sono diversi da prigionieri e detenuti, che ha chiuso insieme sarebbe arrivare a cifre vicine.Questo non garantisce la sopravvivenza, ma se i primi prigionieri riescono a sopravvivere, le probabilità sono il più tardi i detenuti hanno una maggiore probabilità di sopravvivere così.

Non ho pensato le cifre esatte e le motivazioni, però, ma questa è una soluzione rapida che posso pensare in questo momento.

Non ci sono limiti di tempo in questione, in modo suggerisco che i detenuti dovrebbero decidere di prendere 1 ora al di dialogo e aprire nell'ordine presentato.Se il secondo prigioniero è ammesso nella stanza dopo 2 ore poi si sa che il primo prigioniero trovato il suo numero nella casella 2.Perciò sa saltare la casella di 2 nella sua sequenza e apre le caselle da 1, 3, 4...51 Primi prigionieri di probabilità di perdere sono 50/100 Dare che il primo prigioniero sopravvissuto poi il secondo prigionieri possibilità di vincita sono 50/99 Quindi, la risposta sembra essere ((50 ^51)*49!)/100!che, secondo google rende 2.89*10^-9 che è praticamente nullo Quindi, anche se i prigionieri sapevano le scatole in precedenza fortunati trovato il loro numero non ci sarebbe alcuna speranza

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow