Post by anbra1Ho letto su ihe che sul post
"Il corso di specializzazione" del 27.6
hai una "dimostrazione
lunghina ma facile" (cit.)
Se puoi postala che mi farebbe piacere
conoscerla
Grazie
Ciao anbra1, scusa per il ritardo ma ora ti spiego.
L'altro ieri leggendo il tuo post ho perso una mezzoretta per
trascrivere la dimostrazione col blocco note (per fortuna avevo
conservato i foglietti di carta dove più che altro avevo scritto degli
appunti al volo). Senonchè orgoglioso (diciamolo) del mio "lavoro"
vado per trascrivere l'ultimissimo passaggio e... orrore e tragedia:
mi accorgo che non è valido. Insomma per dirla in breve ho provato per
un po (soprattutto ieri) a completare il ragionamento in altro modo ma
non ci sono riuscito.
Anche se a questo punto risulta inutile, ti posto lo stesso la
sequenza dei ragionamenti fatti che ormai, ripeto, purtroppo credo che
non porti da nessuna parte.
Affermazione 1) Se esiste una persona che conosce in tutto altre n
persone (1 <= n <= 4), allora detto M il numero massimo di persone che
frequentano il corso: M <= 1 + 4n
Dimostrazione. Sono quattro casi; facciamoli tutti uno per uno.
caso n = 1. Cioè esiste una persona x che conosce solo un'altra
persona y. Tutti i componenti del gruppo diversi da x e y non possono
conoscere per ipotesi x e quindi devono necessariamente essere
collegati ad esso tramite y; ma y conosce già x e quindi può conoscere
al massimo altre 3 persone. Quindi il gruppo non può avere più di 5
persone = 4n + 1
Caso n = 2) Esiste un x che conosce solo y e z. y può conoscere
tutt'al più atre 3 persone e così anche z. Nel caso più favorevole
queste altre 3 + 3 persone sono tutte diverse tra loro e quindi il
gruppo ha 9 = 4n + 1 persone.
Caso 3 e 4) Risparmiatemeli... l'idea è sempre la stessa.
Fine dimostrazione
Affermazione 2) La soluzione a 17 persone è impossibile.
Dimostrazione. Per assurdo. Supponiamo che il gruppo sia formato da 17
persone, allora per quanto detto prima ogni persone del gruppo deve
conoscere esattamente altre 4 persone. Affinchè il gruppo abbia 17
elementi, deve necessariamente esistere almeno una persona x percui
valga il seguente schema (perchè altrimenti se non esistesse il gruppo
avrebbe meno di 17 elementi):
- x conosce y1, y2, y3, y4
- y1 conosce x, y11, y12, y13
- y2 conosce x, y21, y22, y23
- y3 conosce x, y31, y32, y33
- y4 conosce x, y41, y42, y43
con tutti i 17 elementi elencati distinti tra loro.
Per quanto riguarda x, y1, y2, y3, e y4 il grafo è completo, cioè
ognuno di loro conosce già altre 4 persone. Adesso mancano solo 3
collegamenti per ogni yij (con i tra 1 e 4 e j tra 1 e 3).
Per brevità chiamiamo G l'insieme di tutti i 17 elementi, A l'insieme
dei soli yij e Ai l'insieme {yi1, yi2, yi3}.
Notiamo che essendo i collegamenti degli y1, y2, y3, y4 già completi,
si ha che yij conosce direttamente solo yi e nessun altro yk con k
diverso da i.
Consideriamo ora ad esempio y11. Questo non può conoscere direttamente
y2, y3, y4 in quanto questi come appena detto conoscono già 4 persone
diverse da lui, quindi li deve conoscere necessariamente in modo
indiretto. L'unico modo per farlo, visto che anche x è al completo, è
di conoscere un elemento di ognuno degli insiemi A2, A3, A4. Questo è
possibile in quanto ad y11 mancano altre tre persone da conoscere,
però in questo modo esaurisce il numero di conoscenti diretti. Il
ragionamento fatto con y11 vale per tutti gli altri yij; ripetiamolo:
dato yij questo deve conoscere esattamente un elemento per ogni Ak con
k diverso da i.
Se ci si pensa bene allora, quanto appena detto equivale a dire che
dati due diversi yij e yih di Ai, gli elementi di Ak (k diverso a i)
che essi conoscono devono essere diversi (in quanto se fosse lo
stesso, chiamiamolo ykl questo non soddisfarrebbe l'ipotesi di
conoscere solo un elemento per ogni Ax).
Bene, il mio ragionamento conclusivo ma ERRATO era il seguente:
visto che yij conosce solo ykh di Ak, questo deve essere in qualche
modo collegato tramite un'altra persona agli altri due elementi di Ak,
ma questo è impossibile.
Questa ultima impossibilità in realtà è falsa, infatti sono arrivato
anche a costruire degli esempi concreti percui la cosa risulta invece
possibile (anche se poi questi esempi non sono risultati validi ai
fini della soluzione del problema per altri motivi).
Ad ogni modo, se la cosa ti può interessare ho trovato anche i
seguenti fatti:
1. Avevo detto che deve esistere un x tale che valga lo schema
- x conosce y1, y2, y3, y4
- y1 conosce x, y11, y12, y13
- y2 conosce x, y21, y22, y23
- y3 conosce x, y31, y32, y33
- y4 conosce x, y41, y42, y43
con tutti gli elementi diversi tra loro.
Ma in realtà se ci si riflette un attimo, questo deve essere vero per
ogni persona x del gruppo.
Osservando nel grafo di sopra il sottografo dato dai collegamenti tra
x, y1, y2, y3, y4 (per i quali il grafo è già completo) si vede che
non esistono "triangoli" cioè non può essere che a conosce b che
conosce c che conosce a. Inoltre per il fatto appena detto che ogni
persona del gruppo può essere pensata come l'inizio di questo grafo
(cioè come la x), risulta che l'intero grafo, se esiste, non ammette
triangoli.
Ok, ho scritto tutto al volo pechè nel frattempo m'hanno chiamato a
lavorare (sono reperibile) e devo correre.
Spero di non aver fatto altri errori. Ciao.