La festa

[Pachito1]

Dimostrare che ad una festa ci sono almeno 2 persone che conoscono lo stesso numero di invitati. Si supponenga reciproca la conoscenza (se io conosco te, tu conosci me).

[EUCLA]

Supponiamo che un invitato B conosca solo chi lo ha invitato A. Ma A conosce tutti e quindi conosce B oltre a C,D.....Escludendo le altre persone C,D dalla lista colui che invita A conoscerà sempre lo stesso numero di invitati dell'invitato B.

[Pachito1]

Non mi pare che ci siamo, anche se non ho capito bene quello che hai scritto.

[Nekao]

Supponiamo che il numero minimo di persone che partecipano alla festa sia 2. Di queste due persone una invita e l'altra è invitata. Dunque si conoscono e alla festa vi sono due persone che conoscono esattamente il numero di invitati (entrambi sanno che vi è un invitato, sempre che in realtà non si pensi a partecipanti alla festa, caso in cui anche l'invitante sarebbe da conteggiare e quindi entrambi sapreppero che vi sono due 'invitati'). ma se si fosse più di due persone, quindi più di un invitato la situazione si potrebbe replicare tra l'invitante e il nuovo invitato aumentando così il numero di partecipanti alla festa ma lasciando inalterato il numero minimo di persone che si conosco..sempre almeno due.
Ho azzardato troppo?

[jack110]

ma allora in linea di principio, a una festa di n persone, tutti sanno che ci sono n invitati...anche se magari non si conoscono fra loro...

[Pachito1]

Anora non ci siamo.

[signor.nessuno1]

[Nekao]

@Jack
il problema non è sapere che ad una festa di n persone ci sono n invitati, ma quante di quelle n persone si conoscono reciprocamente. Si chiedeva di dimostrare che comunque (e dovunque) fosse la festa, almeno due persone (tra i partecipanti) si conoscono. Almeno così io ho inteso il testo

[asdf4]

Mamma mia che macello! Io avevo capito di dimostrare che ESISTONO sempre almeno due persone che conoscono lo stesso numero di persone presenti a quella festa. Ad esserne capaci, è studiabile, come saggiamente suggeriva signor.nessuno, con la matrice di incidenza di un grafo e le sue magnifiche proprietà (a(ik) vale 1 se esiste un ramo che connette il nodo i e k, 0 se non esiste. É simmetrica, perchè ogni punto è connesso con se stesso e allora ha tutti 1 sulla diagonale principale)... Dimostrando che in una matrice fatta così esistono almeno due righe la cui somma degli elementi sia uguale il problema è risolto. Qualcuno sa aiutarmi?

[jack110]

mi è venuta in mente una cosa...consideriamo da una parte gli invitati e dall' altra colui che invita...mettiamo che gli invitati conoscano tutti un numero differente di persone, quindi ognuno conoscerà un numero di persone che va da 1 a n invitati (considerando n il nuumero degli invitati più quello che invita); mettiamo adesso che ogni invitato conosca chi invita...vediamo che chi invita conosce n-1 persone (cioè tutti tranne lui....cioè lui si conosce, ma questo non conta [:)]); però c'è già chi conosce n-1 invitati, fra gli invitati(poichè essi conoscono da 1 a n persone, e ognuno conosce un numero diverso di persone)! perciò almeno due persone conoscono lo stesso numero di invitati...e inoltre queste due persone si conoscono reciprocamente....
non sono sicuro di questa soluzione (mi sembra un po' troppo ad hoc),giudicate voi...
ciao

[signor.nessuno1]

[jack110]

per la mia pseudo-dimostrazione, mi sono aiutato un po' con i grafi...infatti per capire come ragionare, ho disegnato una specie di triangolo, mettendo gli invitati allineati(ovviamente gli invitati sono espressi da punti), e quello che invita al di fuori da questa retta...poi ho detto...lasciamo da parte quello che invita, e consideriamo gli altri...male che vada ognuno conoscerà un numero diverso di persone...beh, il resto è scritto sopra...
insomma, tutto questo per dire, che non ne so molto di grafi(dopo il problema dei ponti di konigsberg, ho molte lacune...), però il suggerimento di asdf è stato utile...
ciao

[Pachito1]

signor.nessuno ha dato una risposta esatta. Per la matrice di incidenza di un grafo e le sue magnifiche proprietà non so che dire, ma sarei molto interessato se qualcuno approfondisse.
Ciao

[asdf4]

quote:

---

Originally posted by Crook

Anche a me farebbe piacere se qualcuno approfondisse l'incidenza di un grafo e le sue proprietà. La risposta di signor.nessuno mi sembra abbastanza elegante; Pachito, avevi in mente una più elegante? Sarei interessato di vederla..

---

Anche a me interesserebbe tantissimo approfondire la teoria dei grafi; quelle pochissime cose che so non sono sufficienti ad affrontare problemi del genere; però è una teoria affascinante che ha tra l'altro grandi risvolti pratici ( analisi di circuiti, economia, urbanistica...). E anche problemi come quello della festa sono formulabili in termini di grafi... Qualcuno ne sa qualcosa di più?

[signor.nessuno1]

[asdf4]

Grazie infinite per il link: era proprio quello che cercavo!
Ciao!