2 prublemini

colin · Messaggio da **colin** » 01 gen 1970, 01:33

Dunque mi sembra che c\'è un po\' di confusione...ma l\'hai almeno letta la dimostrazione? Sennò che domande fai?!?
 
 Comunque, supponendo tu abbia letto la dimostrazione, se questa (la dimostrazione) è vera allora la tesi, cioè esiste almeno un pollo che conosce tutti gli altri studenti, è vera!
 
 Se invece ti chiedi proprio come passare dalla dimostrazione con i P gli X e gli n al caso di un liceo di 800 alunni, allora basta partire dal presupposto che la tesi, quella di prima, sempre la stessa, è vera per il liceo fatto da 799 alunni e seguire i passaggi dell\'ultimo pezzo di dimostrazione mettendo al posto di X,Y,P,N,... i nomi degli ottocento ragazzi del liceo...
 Buona fortuna <IMG SRC="images/forum/icons/icon_razz.gif">

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Colin, l\'idea per la dimostrazione c\'è, ma sbagli ad applicare l\'induzione (essa è in realtà inutile). Infatti l\'ipotesi induttiva per il secondo passo ti garantisce che esiste un certo n tale che preso un liceo di n studenti ve ne è uno che ha n-1 conoscenti, il che però non lo puoi sfruttare nel passaggio ad n+1. Non si tratta di aggiungere uno studente e far rimanere inalterata la trama di amicizie già esistente, ma di considerare un caso del tutto nuovo. Pertanto considerato un liceo di n+1 studenti, non è detto che ne esista uno che ne conosce almeno n-1.
 Questo errore è un classico tranello dell\'induzione... ma ripeto, la tua dimostrazione è riconvertibile.

colin · Messaggio da **colin** » 01 gen 1970, 01:33

Ecco qua riveduta e corretta, almeno spero…
 
 Eliminando l’induzione, una strada potrebbe essere questa: preso un gruppo di 4 persone del liceo, chiamiamo P quello che le conosce tutte. Siano X,Y,W gli altri tre.
 Eliminiamo ora W e formiamo altri tre gruppi sostituendo di volta in volta gli alunni U, V e Z
 (i gruppi diventano PXYU,PXYV,PXYZ).
 
 Supponiamo che U conosca P e quindi il primo gruppo soddisfi l’ipotesi iniziale.
 Supponiamo inoltre che V conosca X e che Z conosca Y, ma che né Z né V conoscano P. In entrambi questi ultimi due casi, per l’ipotesi iniziale, X e Y devono conoscersi
 Tutti gli studenti del liceo rientrano in questi tre gruppi ( in relazione a P, X e Y). Disinteressiamoci di tutti gli studenti che conoscono P (quelli del tipo U) anche se dovessero avere conoscenze aggiuntive…
 Esaminiamo invece gli studenti che non conoscono P, ma che conoscono X,Y ( tipo V o Z),o anche entrambi, ai fini della dimostrazione non cambia, basta considerarli come solo conoscenti di X o di Y.
 
 
 
 
 Formiamo due gruppi (A e B)uguali da 4 studenti : X, Y, V, Z. Abbiamo due possibilità, nel primo gruppo (A), V conosce Y. Deve farlo altrimenti non si rispetta la condizione che prese 4 persone una conosca le altre tre.
 Nel secondo gruppo (B) invece Z conosce X. Stesso motivo di prima. Si noti che è ininfluente, affinché la condizione iniziale sia rispettata, che V e Z si conoscano.
 [questo pezzo non è spiegato benissimo però siccome nel resto della dimostrazione mi riferisco a quanto c\'è scritto e non ho voglia di cambiare tutto...Il senso comunque è che il gruppo da formare è ovviamente uno solo. In questo gruppo ci sono solo due possibilità che soddisfano la condizione iniziale spiegata da Azarus. Io le analizzo separatamente...ho fatto un po\' di giri inutili in più...]
 
 
 
 Se però mettiamo, nel gruppo A, P al posto di Y allora notiamo che poiché abbiamo supposto che né V né Z conoscano P anche Z, oltre già a V, deve conoscere X.
 
 Se nel gruppo B cambiamo invece X con P abbiamo che anche V deve essere conosciuto da Y per lo stesso motivo di sopra.
 
 In entrambe le possibilità si ha quindi che X e Y conoscono sia V che Z ( o meglio tutti gli studenti che non conoscono P).
 
 Ci resta da dimostrare che anche tutti gli studenti che sono conosciuti da P ( tipo U, vedi inizio dimostrazione) sono anche conosciuti tutti o da X o da Y.
 
 Per farlo basta formare il gruppo P,X,V,U. In questo gruppo l’unico modo per rispettare la condizione iniziale dello studente che conosce gli altri tre è che X conosca U poiché V non può conoscere P e quindi ci rimangono come possibili candidati o X o U ma in entrambi i casi X e U si devono conoscere…
 
 Ovviamente il ragionamento è identico se si sostituisce X con Y. Quindi è dimostrato che esiste almeno una persona che conosce tutte le altre se sono valide le condizioni iniziali…
 Ovviamente è anche possibile che non esistano nel liceo studenti tipo V o Z nel qual caso sono tutti di tipo U, cioè conoscono tutti P, e la tesi rimane dimostrata
 
 Fatemi sapere se che ne pensate
 
 Bye
 
 
 P.S.lordgauss, adesso è tutto ok?
 [ Questo Messaggio è stato Modificato da: colin il 09-01-2003 16:06 ]

massiminozippy · Messaggio da **massiminozippy** » 01 gen 1970, 01:33

Premetto che il teorema dell\'induzione nn lo conosco.
 Quindi mi risulterà un po difficile capire la dimostrazione.

colin · Messaggio da **colin** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-01-09 15:54, colin wrote:
 
 
 Eliminando l’induzione, una strada potrebbe essere questa