Misurando la distanza delle stelle...

[Ponnamperuma]

Pino ha davanti 99 stelle e vuole sapere quale sia più vicina a lui... Dispone di uno strumento che, misurando contemporaneamente la distanza di tre stelle qualunque, indica quale sia la più vicina...
Determinare il numero minimo di misurazioni che Pino deve effettuare per capire quale sia la stella più vicina.

Ora, io credo che sia 49, perchè con due diversi metodi viene fuori questo numero... tuttavia non so dimostrare che questo sia effettivamente il minimo. Inoltre c'è un'altra opzione, minore di 49, 33... solo che non riesco neanche a dimostrare formalmente che con 33 misurazioni sia impossibile.
Credo che il mio sia un problema di ignoranza della tecnica dimostrativa, visto che l'esercizio dovrebbe essere banale (viene da un primo turno delle OliInf)...

Grazie in anticipo!
Ciao!

P.S.: Spero di aver azzeccato la sezione del forum... ma dovrei esserci riuscito!

[MindFlyer]

Con 33 è evidentemente impossibile!
Ogni misurazione coinvolge esattamente 3 stelle. Per determinare la stella di distanza minima, bisogna necessariamente aver coinvolto tutte le stelle almeno una volta in una misurazione. Per far questo con 33 misurazioni, l'unico modo è dividere le 99 stelle in 33 terne e fare una misurazione su ogni terna. Ma fatto questo, si vede facilmente che non si può estrarre la stella di distanza minima, perché non si sono mai confrontare tra loro stelle di terne diverse.

[Ponnamperuma]

Dunque effettivamente basta osservare questo... ma se non avessi avuto l'opzione 33 e mi fosse stato chiesto di determinare il minimo? Come fare a dimostrare che 49 (configurazione che so ottenere) è il risultato cercato? Ciao!

[MindFlyer]

Allora, usiamo un piccolo lemma di facile dimostrazione: un albero binario con n nodi non foglia ha esattamente 2n+1 nodi (foglie comprese).
Ora, una sequenza di misurazioni che trova la stella più vicina, la puoi vedere come un albero binario, dove ogni nodo non foglia rappresenta una misurazione. Per ogni misurazione, il nodo che la rappresenta è la stella più vicina secondo quella misurazione, e i nodi figli sono le altre 2 stelle coinvolte nella misurazione.
A questo punto, se esistesse una sequenza di 48 misurazioni che crea un albero binario, quest'albero avrebbe esattamente 2*48+1=97 nodi. Quindi le 48 misurazioni potrebbero coinvolgere al più 97 stelle, e non le 99 che abbiamo.

[Katerina89]

cia' mind eh!!!!!!!!!!!!

mi spiace eh.... ma quello che dici e' propio falso eh.....

insomma voglio dire che non per forza l'albero che fai e' binario eh!!!! e poi chi ti dice che deve essere un'albero?? insomma senza cicli?!? eh....

io pensavo che si poteva fare anche cosi'....

facciamo finta che disegniamo delle costellazioni nel cielo. per ogni misura tu aggiungi una stellina fantasma e la colleghi alle tre che hai misurato. e facciamo che si fa questa cosa per 48 misure. cosa capita? eh....

capita che alla fine ai fatto stelline 99+48=147 e collegamenti 48*3=144. pero' osserva che un grafo con 144 collegamenti non puo' essere connesso. ok? si vede per induzione eh!!!! e allora nel cielo ci sono almeno due costellazioni. pero' se io allontano tutte le stelle di una costellazione insieme, i risultati delle misure che ho fatto non cambiano eh!!!!!

allora tu prendi la costellazione che conteneva la stellina piu' vicina e ZAP! la mandi lontano lontano lontano: le misure che hai fatto rimangono ancora buone, pero' adesso la stellina piu' vicina e' un'atra.

cosa ne pensi????

cia' eh raga!!!!![/img]

[SkZ]

Non sarebbe piu' semplice usando quello che penso sia uno dei metodi risolutivi di Pannamperuna:?:
Per trovare la piu' vicina devo per forza analizzare tutte le stelle.
Inoltre devo almeno confrontare una stella con tutte le altre (direttamente o indirettamente: essendo il confronto un <, vale la proprieta' transitiva), dato che il risultato e' un estremo (per la distanza) dell'insieme.
Se prendo un gruppo di 3 stelle e cerco la stella piu' vicina, dopo di che confronto la stella ottenuta con altre 2 delle stelle rimaste e ciclo.
Alla fine ho effettuato 49 misurazioni e ho soddisfatto alle due clausole iniziali e ho trovato il risultato. Quindi con 49 operazioni trovo il risultato e opero almeno le operazioni minime per trovarlo, quindi deve essere il minimo numero di operazioni.
Ergo 48 operzioni non puo' essere il minimo perche con tale numero posso confrontare la stella piu' vicina con al piu' altre 96 stelle, mentre a me serve confronterla con 98.

Penso di aver scritto anche qualche concetto di troppo. Comunque tale soluzione ricorda l'albero di MindFlyer, quindi non penso che abbia sbagliato. Anche se il suo albero attualmente (6.35am e appena svegliato) non riesco avisulizzarlo con facilita'

[MindFlyer]

Forse non è chiara la mia costruzione. Mea culpa che l'ho spiegata di fretta credendo che si capisse (ora non ho molto tempo, però.. dico solo che i nodi del mio albero non sono in realtà stelle ma sono "etichette" di stelle, quindi più nodi possono avere la stessa etichetta, ed inoltre si ottiene un albero solo quando le misurazioni forniscono la stella più vicina, non sempre). Comunque, Katerina, nota che i nostri due metodi generalizzati ad un numero qualsiasi di stelle e di misurazioni forniscono gli stessi risultati (quindi in base a cosa asserisci che ciò che dico è falso? piuttosto dì che non si capisce una cippa di quello che ho scritto), e credo anche che si possano ricondurre l'uno all'altro.

[Katerina89]

Hey minde!!!!

cippa? e che' e' una cippa eh??????

ma nno!!! io dico che e' propio sbagliato!!!! insomma, si capisce anche poco eh.... ma quel poco e' sbagliato...

insomma, guarda questo segmento di cielo eh....



vedi? immagina di fare due misure sulle due ali dell'angelo, e immagina che la stella rossa centrale risulti la piu' vicina in entrambe.... eh.... vedi che allora ti viene un albero ke ha quattro nodifoglia e un nodononfoglia centrale. e quest'albero non e' mica binario eh....

beh se poi tu pensavi che i nodi non erano stelle come hai scritto, perche' hai propio scritto il nodo che la rappresenta è la stella più vicina secondo quella misurazione, allora forse pensavi qlcosa di giusto eh... ma mica lo hai scritto eh!!!!

cia' eh raga!!!!!!!!

[piever]

Più semplicemente (ma concettualmente non dico nulla che non sia stato gia detto):

organizziamo un torneo tra stelle ad eliminazione diretta. In ogni match gareggiano 3 stelle e ne vengono eliminate 2. Le stelle iniziali sono 99, quelle finali 1, il numero di match è la metà delle stelle eliminate, ovvero (99-1)/2=49 che è sicuramente un numero sufficiente.

Se 48 fossero sufficienti, allora esisterebbero almeno 2 componenti connesse staccate tra loro (un grafo con 96 archi e 99 vertici...). Si puo determinare la stella piu vicina di ciascuna componente connessa, ma cosi resta l'indecisione tra le "capolista" di ogni componente connessa.

[MindFlyer]

Insomma, fai n misurazioni e ti ritrovi con n alberelli binari di 3 nodi.
Poi li attacchi secondo questo criterio: se la radice di un albero A ha l'etichetta di un nodo di un altro albero B, attacchi A ad una foglia di B (senza cambiare l'etichetta della foglia). Così se c'è un albero di radice k, significa che la stella k è la più vicina tra tutte le stelle etichettate dall'albero. Nota che così perdi "l'identità" delle misurazioni nei nodi intermedi, ma non importa: forse è questo il punto che ha creato più confusione.
Se facendo questo puoi ottenere un albero binario unico, la radice ha l'etichetta della stella più vicina. Se non puoi farlo, allora le misurazioni non ti permettono di determinare la stella più vicina (dimostrare, è facilissimo.. per la precisione, non ti permettono di discriminare tra le stelle radici, nell'unico caso interessante in cui una di esse è la più vicina in assoluto).
Ma con 48 misurazioni non si può ottenere un albero con almeno 99 nodi, ergo non è possibile determinare la stella più vicina.
Chiaro adesso? Comunque a mio avviso la soluzione di Katerina è più pulita, ma resta il fatto che la mia funzioni (sebbene nel primo post fosse espressa malissimo, come ho già ammesso: mea culpa, ho pensato che dando quei pochi elementi si riuscisse a ricostruire facilmente).

[SkZ]

passiamo ad altro:
Pino adesso vorrebbe trovare la stella piu' distante utilizzando lo stesso strumento

(se Ponnamperuma e' d'accordo, s'intende )

[MindFlyer]

Eh, però per risolvere il problema della stella più lontana, lo strumento a 3 stelle non funziona più! Nel senso che non riuscirà mai a discriminare tra le 2 stelle più lontane in assoluto. L'unica soluzione sarebbe ammettere misurazioni a 2 sole stelle, ma così il problema perde interesse..

[Ponnamperuma]

Beh, le mie carenze abissali e deprecabili in teoria dei grafi mi obbligheranno a rimuginare molto a lungo su quanto scritto...
Ma vi ringrazio tutti per la disponibilità!

passiamo ad altro:
Pino adesso vorrebbe trovare la stella piu' distante utilizzando lo stesso strumento

(se Ponnamperuma e' d'accordo, s'intende )

No, non posso proprio tollerarlo! Credo che abbandonerò il forum, se porterai avanti questa tua bislacca idea!!

Ciao!