Pages: [1]   Go Down
Print
Author Topic: Trovare la STAR  (Read 988 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Lordmarius
Matricola
*
Offline Offline

Posts: 10



« on: 15-04-2016, 14:43:21 »

Salve a tutti. Credo di aver trovato la soluzione all'enigma proposto dal prof. Catalano a lezione l'ultima volta.
Per chi non si ricorda:
ci sono N persone a una festa: una di loro è una star, che non conosce nessuno ma che è conosciuta da tutti. L'obiettivo è di individuare la star potendo chiedere agli invitati solo "Tu conosci lui/lei?".
Ecco la mia soluzione, che risolve il quesito in N-1 passi  univ :

- Divido l'insieme delle persone in coppie ordinate (nel caso in cui gli invitati siano dispari ne tengo uno da parte e lo reinserisco alla fine)
-Pongo agli elementi di sinistra la domanda rispetto ai rispettivi elementi di destra (in tutto fanno N/2 domande)
-Elimino tutti gli elementi di sinistra che hanno risposto SI', in quanto certamente nessuno di loro è la star
-Elimino tutti gli elementi di destra il cui compagno di coppia abbia risposto NO, per lo stesso motivo
-Ripeto il procedimento ricorsivamente con i restanti invitati non scartati, dividendoli nuovamente in coppie
-All'occorrenza (invitati in numero dispari) aggiungo l'ultimo elemento, che avevo tenuto da parte, come elemento dell'ultima coppia quando il procedimento avrà restituito una sola persona

Esempio: Alla festa sono invitate 10 persone, che chiameremo "1,2,3,4,5,6,7,8,9,10". Supponiamo che la star sia il numero 10. Per creare una situazione "mista", in cui qualcuno conosce almeno una persona ed è conosciuto almeno da una persona, suppongo anche che ogni persona conosca le due persone "successive numericamente" (quindi 1 conosce 2 e 3 ecc...). Creo delle coppie casuali.
Le coppie create sono: (uso il simbolo "->" per "conosce" e "-x" per "non conosce")
1->3 , 8->9 , 7-x5 , 4-x2 , 6->10.
Elimino 1,8,5,2,6. Riformo delle coppie casuali con i rimanenti:
3-x9 , 7->10 , rimane fuori il numero 4, che tengo da parte
Elimino 9,7. Resta la coppia 3->10
Elimino 3. Reinserisco il 4 con 4->10 o con 10-x4 ( è uguale ). Al che ho individuato la star, in sole 9 domande!

Fatemi sapere cosa ne pensate!
Logged
emmeesse
Matricola
*
Offline Offline

Posts: 25


« Reply #1 on: 15-04-2016, 20:36:54 »

Sostanzialmente vuol dire che disponendoli in coppie mantieni soltanto gli elementi per cui è stato detto "SI" (che sono conosciuti) e che dicono "NO" (ovvero che non conoscono), e ripeti il procedimento fino alla fine, quando sarà restituita una sola persona. Giusto?
Logged
Lordmarius
Matricola
*
Offline Offline

Posts: 10



« Reply #2 on: 16-04-2016, 16:14:47 »

sì, come detto nei punti 3 e 4 Smiley
Logged
Pages: [1]   Go Up
Print
Jump to: