il quarto della serie di info tratti da http://www.geocities.com/CollegePark/Lo ... /comb.html
vorrei controllare la mia soluzione, quindi ne approfitto per postarlo perché mi è piaciuto. Se avete problemi con la traduzione, chiedete pure
A journalist is looking for a person named Z at a meeting of N persons. He has been told that Z knows all the other people at the meeting but none of them knows Z. The journalist may ask any person X : 'Do you know that man?' about any Y.
1) Can he be certain to find Z by asking less than N questions?
2) What minimal number of questions are needed to find Z?
2b)(Prove that a lesser number won't work.)
Il giornalista alle prime armi
Il giornalista alle prime armi
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget
Paul Borget
sei andato a prendere uno di quelli che NON avevo fatto... avevi il 50%.. 
... sono tutti molto belli, vero? Soprattutto sono variegati...
1) yep...
2)(n-1)
3) bisogna verificare almeno (n-1) rapporti--->ed (n-1) sono sufficienti
mi scuso per eventuali errori... mi pareva facile e quindi sicuramente ne ho fatti... fammi sapere!
rigt or wrong, sono contento che qualcuno li abbia aperti...
... sono tutti molto belli, vero? Soprattutto sono variegati...1) yep...
2)(n-1)
3) bisogna verificare almeno (n-1) rapporti--->ed (n-1) sono sufficienti
mi scuso per eventuali errori... mi pareva facile e quindi sicuramente ne ho fatti... fammi sapere!
rigt or wrong, sono contento che qualcuno li abbia aperti...
beh, è la mia stessa conclusione, ma l'interessante è come può trovare l'individuo misterioso...! Quindi, che procedimento usa?info ha scritto:sei andato a prendere uno di quelli che NON avevo fatto... avevi il 50%..
1) yep...
2)(n-1)
3) bisogna verificare almeno (n-1) rapporti--->ed (n-1) sono sufficienti
mi scuso per eventuali errori... mi pareva facile e quindi sicuramente ne ho fatti... fammi sapere!
rigt or wrong, sono contento che qualcuno li abbia aperti...
sono bellini, peccato che il mio inglese non sia proprio perfetto, per cui un paio li ho saltati di netto dopo aver letto il testo...
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget
Paul Borget
ok---
se chiedo:
A, conosci B?
* no --- se fossi Z conosceresti tutti, non mi interessi: tu, A, non sei Z!
* si --- se conosci B, vuol dire che B non è Z... se fosse Z, nessuno dovrebbe conoscerlo...
in ogni caso abbiamo scartato una persona. Con ogni domanda scartiamo 1 persona, con (n-1) domande capiamo per esclusione chi è Z...
------
formalizzo un pò più decentemente la prova ora...doma la riguardo:
facendo una domanda, possiamo scartare al max una persona.
Infatti se la persona A risponde no, di B posso solo sapere che non è conosciuta da A... Potrei dire che B è Z solo se sapessi che B non è conosciuta da altre (n-2) persone (infatti Z è l'unica che non è conosciuta da nessuno), ma in questo caso avrei dovuto fare precedentemente (n-2) domande... Se la persona A risponde si, di A posso solo sapere che conosce una persona, per dire che è Z dovrei sapere che conosce altre (n-2) persone (infatti è l'unica che conosce tutti) ma per questo avrei già dovuto fare (n-2) domande... in conclusione o elimino una persona a domanda oppure devo avere già fatto (n-2) domande...
-----------------------------------
cmq se hai bisogni per l'inglese chiedi pure, anche se in generale mi paiono abb chiari...
se chiedo:
A, conosci B?
* no --- se fossi Z conosceresti tutti, non mi interessi: tu, A, non sei Z!
* si --- se conosci B, vuol dire che B non è Z... se fosse Z, nessuno dovrebbe conoscerlo...
in ogni caso abbiamo scartato una persona. Con ogni domanda scartiamo 1 persona, con (n-1) domande capiamo per esclusione chi è Z...
------
formalizzo un pò più decentemente la prova ora...doma la riguardo:
facendo una domanda, possiamo scartare al max una persona.
Infatti se la persona A risponde no, di B posso solo sapere che non è conosciuta da A... Potrei dire che B è Z solo se sapessi che B non è conosciuta da altre (n-2) persone (infatti Z è l'unica che non è conosciuta da nessuno), ma in questo caso avrei dovuto fare precedentemente (n-2) domande... Se la persona A risponde si, di A posso solo sapere che conosce una persona, per dire che è Z dovrei sapere che conosce altre (n-2) persone (infatti è l'unica che conosce tutti) ma per questo avrei già dovuto fare (n-2) domande... in conclusione o elimino una persona a domanda oppure devo avere già fatto (n-2) domande...
-----------------------------------
cmq se hai bisogni per l'inglese chiedi pure, anche se in generale mi paiono abb chiari...
Ultima modifica di info il 26 apr 2005, 22:09, modificato 2 volte in totale.
a posto!
...oltretutto conferma tutti i simpatici luoghi comuni (e tragiche verità) sui giornalisti...
magari quando ho tempo torno sul sito, adesso sono abb occupato. se ho bisogno ti mando un mp. Grazie mille!!
...oltretutto conferma tutti i simpatici luoghi comuni (e tragiche verità) sui giornalisti...
magari quando ho tempo torno sul sito, adesso sono abb occupato. se ho bisogno ti mando un mp. Grazie mille!!
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget
Paul Borget