Newsgroup: it.hobby.enigmi
Titolo: La festa (difficile)

Le persone presenti ad una festa sono state scelte in modo che prese
comunque due persone, tra quelle rimanenti ce n'e esattamente una che
conosce entrambi.
Dimostrare che c'e' una persona che conosce tutti.
?manu*

Emanuele Paolini wrote:

Ah, forse un problema piu' facile e' trovare un controesempio nel caso
che le persone alla festa siano infinite!!
?manu*


Notazione: x->y,z significa: x conosce y e z
Assumo che se x->y, y->x
Per n=3, si vede facilmente che
a->b,c
b->a,c
c->a,b
in questo caso tutti conoscono tutti
_Suppongo_ che per n invitati, x->a,b,c,... (tutti). Noto che se x->a,
a puo' conoscere solo un b oltre ad x, cioe' a->x,b e b->x,a. Non puo'
essere che ci sia y t.c. y->x e basta: la coppia (x,y) non la
conoscerebbe nessuno. Se a->x,b,c allora la coppia (b,c) e' conosciuta
da x e da a, e quindi non puo' essere per ipotesi (una coppia e'
conosciuta da piu' d'uno). Questo per ogni a.
Se arriva w (l'elemento n+1), allora per quanto detto prima w deve
essere conosciuto da x per forza, cioe' x conosce tutti.
Se infatti ci fosse y t.c. y->x,k,w (quindi w->y) la coppia (y,w) non
la conoscerebbe nessuno. Se k->x,y,w la coppia (y,w) sarebbe
conosciuta da k, ma quella (k,y) sia da x che da w.
Stefano Costa
^^^^^^^^^^^^^
sco...@enjoy.it
cos...@odino.unipv.it

Devo fare una precisazione.
Se arrivasse w da solo, sarebbe w->x da quanto ho detto, e cio' non va
bene in quanto la coppia (w,x) poi non la conosce nessuno. Percio'
dovranno arrivare w1 e w2, tali che w1->x,w2 e w2->x,w1.
Quindi da n passiamo a n+2. Alla festa possono solo esser presenti
persone in numero _dispari_. In effetti se fossero in numero pari, ci
sarebbe un w con w->x, e la coppia (w,x) non la conosce nessuno.


Nessuno si prende la briga di controllare la mia dimostrazione
(Emanuele?) o di proporne altre? Ero l'unico che non conosceva il
gioco?


 [...]
Ciao, mi pare che il tuo ragionamento per induzione sia sbagliato.
Infatti quando consideri le n+1 persone stai supponendo che togliendo una
persona (w) quelle rimanenti verifichino ancora le ipotesi del
problema.Cioe' la condizione data ("prese comunque due persone ce n'e'
una che conosce entrambe") e' vera soltanto quando sono arrivati TUTTI
gli invitati (nel tuo caso n+1), e non quando l'ultimo (w) non e' ancora
arrivato.
Ciao,
Em.

 ?manu*
A me sembra che per n pari sia proprio impossibile cio' che dici!
Se una persona (x) conosce tutti, allora ogni altro invitato DEVE conoscere
almeno un'altro oltre ad x ma NON PUO'conoscerne un terzo altrimenti
avrebbe due conoscenti in comune con x. Quindi deve conoscerne ESATTAMENTE
due, x ed un altro. Allora ogni partecipante e' accoppiato ad un altro e,
se n fosse pari, ci sarebbe un partecipante escluso da queste coppie. Per n
dispari la condizione e' sufficiente (tutte coppie marito e moglie ed il
prete che le ha sposate...), per la necessita' ci penso un po'.
Ciao, Silvio

 il prete che le ha sposate...), per la necessita' ci penso un po'.
Credo di aver provato anche la necessita':
Individuiamo il piu' popolare della festa, lo chiameremo P, e sia n il
numero dei suoi conoscenti. Sia X una persona sconosciuta a P. Allora X
conosce direttamente uno degli n amici di P e, per interposta persona gli
altri n-1. Ma dato che gli amici di P non hanno altre conoscenze comuni
oltre a P, queste interposte persone sono tutte distinte. Allora X conosce
gia' n persone (e la leadership di P vacilla...). Ma non dimentichiamo che
X conosce direttamente un amico di P, col quale deve pure condividere una
conoscenza. Chi sara' l'amico comune? Non un amico di P (X avrebbe due
amici in comune con P), non una delle interposte persone (che gia' conosce
un altro degli amici di P), quindi deve essere una ulteriore conoscenza.
Cio' e' impossibile in quanto avevamo ipotizzato che P fosse il piu'
popolare.
Ciao, Silvio

problema.
Io NON sto supponendo di togliere w.
Il mio ragionamento e' questo:
suppongo che per un gruppo di n persone la cosa sia valida, e aggiungo
due (vedi la mia correzione alla dim.) persone w1 e w2 ALLO STESSO
GRUPPO e vedo che necessariamente x, che e' quello che conosce tutti
(il padrone di casa?) deve conoscere entrambi; inoltre w1 deve
conoscere w2 e viceversa.
In pratica la struttura di un gruppo del genere _deve_ essere questa:
n persone (con n dispari), e:
a   c
|\ /|
| x |
|/ \|
b   d
come un "fiore" con al centro x e tanti "petali" di 2 persone che si
conoscono tra loro (nel disegno 2 petali).
Mi piacerebbe sentire il parere di altri. Ciao,



E' vero!Ma non ho mai detto che alla festa ci fosse un numero pari di
persone...
?manu*

 Ciao, Silvio
Ciao,
?manu*


Questo si', a posteriore e' vero.
Ciao,
    ?manu*


Forse non ho ben capito il problema ma, dal mio punto di vista, la
soluzione è possibile per tutti i valori di n.
Si immagini un poligono (ovvero un solido, per avere tutte le
possibilita') di n lati dove i vertici corrispondono alle persone
invitate (meno 1). Si prenda ora un punto all'interno del poligono (o
solido) che rappresenta la persona che conosce tutti. Unendo il punto
centrale con i vertici si puo' facilmente vedere che si soddisfano le
condizioni.
Es:
invitati=7
	A-----B 
       / \   / \
      /   \ /   \
     C-----X-----D
      \   / \   /
       \ /   \ /
        E-----F
(le linee rappresentano il rapporto di conoscenza tra i soggetti)
Per quanto riguarda la dimostrazione (sempre dal mio punto di vista)
ci si puo' accontentare delle soluzioni date anche se io avrei optato
per la seguente:
ipotiziamo un gruppo di 6 persone che vengono suddivise in due
sottogruppi A e B
Utilizzando lo schema sopra esposto
     Sottogruppo A          Sottobruppo B
	a--b--c                d--e--f
Per far si che vengano soddisfatte le condizioni gli invitati indicati
con le lettere "b" ed "e" devono essere la stessa persona.
(Spero di essere stato chiaro nell'esposizione)
Ciao Oro

Capisco quello che vuoi dirmi. In effetti il procedimento d'induzione
dice che data P(n) come ipotesi, P(n+1) deve seguire come tesi (P(n+1)
e' deducibile da P(n), ovvero P(n+1) e' vera ogni volta che e' vera
P(n)).
Secondo te, insomma, basterebbe mandare alla festa due signori che non
conoscono x e la cosa sarebbe morta li'.
Il fatto che pero' io abbia usato il procedimento d'induzione (e che
mi sembrasse corretto) e' dovuto al fatto che questi due signori
devono comunque rispettare le regole della festa (presi comunque due a
caso etc etc); da qui vedo che allora x deve conoscere anch'essi;
cioe' non potremmo mandare due signori che x non conosce perche'
varieremmo le regole del gioco!
E' come dire: la somma dei primi n numeri _naturali_ e' n(n+1)/2; io
non posso pero' utilizzare come n un numero reale (a parte il fatto
che: _quali_ sono i primi n numeri reali?).
Per quanto riguarda il tuo problemino, basta prendere A che conosce B
e B che conosce A; C che conosce D e D che conosce C, e si vede subito
che non e' vero che tutti conoscono tutti; ma ti faccio notare che per
applicare il procedimento d'induzione va posta molta cura nella scelta
della Proposizione che funfe da "base" della catena; se si sbaglia
qui, crolla tutto in quanto dal falso si puo' dedurre ogni cosa, ed il
vero in particolare. Qui non puoi scegliere come base una o due
persone, ma almeno tre, e verificare se per esse la cosa e' vera (e
non lo e').
Io la vedo cosi'; se sto ancora sbagliando per favore correggimi.
Beh, comunque ormai ho capito come e' formata questa combriccola; mi
dai la soluzione "corretta"?


 (Spero di essere stato chiaro nell'esposizione)
Beh, in verita' a me non risulta molto chiaro questo discorso... anche
perche' e' stato effettivamente provato in un post precedente (Silvio)
che n non puo' essere pari (quindi non e' possibile che ci siano 6
persone alla festa)
Ciao,
    ?manu*

 riesce a concludere come volevi...
OK, considerando solo X arrivo a scoprire che X conosce n persone: P1,
X2,.. ,Xn
Ora consideriamo la coppia Xn,Pn: si conoscono tra loro ma non c'e' nessuno
degli invitati finora considerati che li conosce entrambi, allora deve
esserci un altro invitato, lo chiameremo Y.
Finora sappiamo che Y ha amici in comune con P (e' Xn), con Pn (Xn), con X
(Pn), con Xn (Pn), con quello tra gli Xi che conosce Xn, (lo ribatteziamo
X2), e con P2 (Pn)
Non ha invece amici in comune con: P1,P3,..,Pn-1,X3,..,Xn-1, ovvero con
2n-5 persone. A me sembra che queste 2n-5 persone debbano essere distinte
tra loro (e distinte da quelli gia' considerati, non ripetero' l'errore
precedente ;) ) e che Y avra' quindi 2n-3 conoscenti, quindi e' piu'
popolare di P e X che conoscevano solo n persone (e' vero per n>3!)
Che ne dici?
Ciao, Silvio

 tra loro
Mi sembra di no... questo Y potrebbe conoscere un certo Yk che conosce sia Pk
che Xk cosi' invece che 2n-5 ne conoscerebbe solo n-5 di persone...
Ciao,
    ?manu*

 che Xk cosi' invece che 2n-5 ne conoscerebbe solo n-5 di persone...
E' la seconda volta che mi smonti la dimostrazione dimostrandomi che il mio
candidato a mister polpolarita' e' solo uno dei tanti! Ogni volta che
aumento di un invitato, questo come per magia sembra calamitarne altri n-1.
A questo punto mi viene il sospetto che gli invitati seguano una legge di
accrescimento esponenziale e che l'unico modo per evitare l'esplosione e'
rimanere a parlare col proprio partner, o al massimo col padrone di casa!
Se in questa mesta compagnia si presenta un imbucato, il suo amico e'
costretto a presentarlo agli altri, ma non potendolo fare di persona
(tranne sua moglie e il padrone di casa non li conosce  proprio), e'
costretto a ricorrere ad amici comuni, i quali a lora volta devono invitare
qualche conoscenza comune per non trovarsi in difficolta' con le
presenntazioni... insomma si innesca una reazione a catena di presentazioni
finche' il padrone esasperato non caccia tutti di casa a pedate...
Ciao, Silvio

 Dimostrare che c'e' una persona che conosce tutti.
Ho rintracciato il problema nell'archivio di rec.puzzles, dove sono
proposte due soluzioni. Una utilizza la teoria dei grafi ed e' semplice
tranne per una questione tecnica utilizzata nell'analisi di un caso, la
seconda utilizza l'induzione ed e', a sentire il solutore, facile. Secondo
me e' sbagliata.
Ma ecco il testo:
Here is an easy solution by induction. Let P be the set of people in the
party, and n the size of P. If n=2 or 3, the result is trivial. Suppose now
that n>3 and that the result is true for n-1. 
For any two distinct x,y in P, write x & y to mean that `x is a friend of
y', and x ~& y to mean that `x is not a friend of y'. 
Take q in P. The hypothesis on the relation & is still satisfied on P-{q};
by induction, the result is thus true for P-{q}, and there is some p in
P-{q} such that p & x for any x in P-{p,q}. We have two cases: 
# gia' qui non capisco cosa vuol dire: se facciamo uscire una persona dalla
festa,
# e' vero che per ipotesi induttiva vale la proposizione, ma questa diceva
che SE
# ogni coppia ha un unico conoscente comune allora c'e' un invitato che
conosce
# tutti. SE. In questo caso NON E' VERO che in P-{q} ogni coppia ha un
unico
# conoscente comune, perche' le coppie il cui comune amico e' quello che e'
uscito
# NON HANNO amici in comune
1.p & q. Then the result holds for P with p.
2.p ~& q. By hypothesis, there is a unique r in P-{p,q} such that p & r &
q. 
For any x in P-{p,q}, if x & q, then p & x & q, and so x=r. Thus r is the
unique friend of q. Now for any s in P-{q,r} there exists some x such that
s & x & q, and so x=r. This means that r & s for any s in P-{q,r}, and as r
& q, the results holds in P with r. 
Sara'...
Qualcuno piu' ferrato di me in inglese puo' spiegarmela?
Ciao, Silvio

 me e' sbagliata.
Anche a me pare sia sbagliata. Ho gia' discusso della soluzione data poco fa
da Stefano Costa, che e' molto simile a questa.
?manu*


Oh, certo che puoi scegliere una o due persone come base :)))) Su quelle,
il teorema e' vero a vuoto.
E con tre persone, l'affermazione e' verissima... infatti, A deve
conoscere almeno una persona, poniamo B. Anche C deve conoscere almeno una
persona, e sia che sia A, sia che sia B, la catena e' chiusa e tutti
conoscono tutti...
ma mi devo essere perso qualcosa, vero? :)
Ciauz, Gabry :-)
-- 
 _                        _   _
( )                      ( ) ( )   
http://poisson.dm.unipi.it/~stilli/
| |                      | |/ /
| |                      |   <
| |__                    | |\ \
(____)   I   G   H   T   (_) (_)   N   I   G   H   T


Effettivamente devo dire che non avevo capito il problema.
Faccio pertanto "mea culpa" e chiedo umilmente venia.
	Oro