Foto di gruppo

[edriv]

I membri di una gloriosa classe di liceo si ritrovano per una cena a 10 anni dalla matura. Dopo tutto questo tempo, non sono ancora tutti amici... però le cose non sono andate male, e per lo meno possiamo dire che ad ognuno sono amiche più di metà delle persone restanti!

Dopo la pizza, vogliono fare una foto di gruppo tutti in riga, ciascuno con le mani sulle spalle di quelli a fianco. Però ognuno vorrebbe comparire vicino a un suo amico... ma sì, alla fine un modo per disporsi lo troveranno no?

[edriv]

Si ritrovano dopo 20 anni.
Ora le amicizie si sono affievolite ancora di più, c'è qualcuno che conosce meno della metà delle persone che vede... diciamo che quello che ha perso i contatti più di tutti conosce solo k persone.
Anzi, qualcuno addirittura non è stato invitato alla cena! L'iniziativa è partita da Mattia, che ha chiamato quelli che conosceva, loro han chiamato quelli che conoscevano e così via... l'invito si è diffuso solo per passaparola.
E di nuovo, nella foto ognuno vuole apparire solo accanto a persone che conosce, ovviamente. Dimostrare che questa volta, magari non riescono a farci stare tutti in una foto, però almeno 2k sì.

[Tibor Gallai]

Dopo la pizza, vogliono fare una foto di gruppo tutti in riga, ciascuno con le mani sulle spalle di quelli a fianco. Però ognuno vorrebbe comparire vicino a un suo amico... ma sì, alla fine un modo per disporsi lo troveranno no?

E dopo la foto, si rollano una canna e si siedono tutti in cerchio a fumarla. Ognuno fa un tiro rievocando i bei tempi andati, dopodiché la passa al suo compagno di sinistra (in entrambe le accezioni*), ma solo se è un suo amico! Dimostrare che possono disporsi in modo che la canna faccia il giro completo e torni a colui che l'ha rollata.

Non vale rispondere che la canna li fa diventare tutti amici. Sebbene sia plausibile, cercate di astrarre un minimo...

-----------

* Volevo dire "in entrambi i sensi", ma ciò avrebbe conferito un doppio senso anche alla roba tra parentesi, uno dei quali avrebbe compromesso la comprensione del problema.

[Roy]

Grande Tibor Gallai hai trasformato un problema in una figataaaa

[antosecret]

Premetto che sono nuovo del forum e che quindi sono ancora molto inesperto.
Ogni consiglio o suggerimento è quindi ben accetto.

Dopo la pizza, vogliono fare una foto di gruppo tutti in riga, ciascuno con le mani sulle spalle di quelli a fianco. Però ognuno vorrebbe comparire vicino a un suo amico... ma sì, alla fine un modo per disporsi lo troveranno no?

Procediamo per induzione indicando con n il numero totale degli alunni della classe.
(Suppongo che se a è amico di b, allora anche b sarà amico di a).

Passo base:
- Se n è minore di 3 il problema è banale.
- Se n = 3 ognuno conoscerà almeno 2 persone, cioè in qualunque modo gli amici si dispongano ognuno avrà accanto 2 amici.

Passo induttivo:
ammettiamo di avere una classe di n persone che sono già sistemate in riga e pronte per la foto. Aggiungiamo una n+1esima persona.
Essa avrà un numro di amici $ m > \frac{n}{2} $
(Suppongo che se a è amico di b, allora anche b sarà amico di a).

Ora, questa persona deve trovare posto tra 2 suoi amici.
Poichè ci sono n "posti in fila" e almeno $ \frac{n}{2}+1 $ amici ci saranno almeno 2 amici seduti vicini. Quindi le sarà sufficiente sistemarsi tra questi 2.

Giusto???? In particolare, il pigeon hole applicato nel passo induttivo è esauriente o bisogna scriverlo in modo diverso????

[edriv]

La cosa che vuoi dimostrare per induzione su n è "se ognuno è amico di almeno metà dei restanti allora possono fare la foto".
Supponi che sia vero per n persone.
Ora, ti si presentano n+1 persone. Ne togli una, e ne restano n. Quelle n possono disporsi per fare la foto. Posso aggiungere quell'una in modo che tutte ed n+1 possano fare la foto.
L'errore è tra la seconda e la terza frase: all'inizio sai che tra le n+1 persone ognuno è amico di almeno metà dei restanti, ma quando ne hai tolta una, non puoi essere sicuro che tra le n restanti l'ipotesi sia ancora valida, quindi non puoi dedurre che quelle n si possano disporre per una foto.

Leggiti pure questo:
http://en.wikipedia.org/wiki/Horse_paradox

[antosecret]

Credo di aver capito l'errore... praticamente quando inserisco l'n+1esima persona sto aumentando la generalità dell'ipotesi, aumentando il numero di amici di ogni persona. Giusto????


E' comunque possibile dimostrare la cosa x induzione o devo tentare un'altra strada?

[edriv]

Non capisco cosa vuol dire aumentare la generalità dell'ipotesi...
Se hai capito l'errore, bene, altrimenti chiedi.

Per quanto riguarda la soluzione... non escludo nessuna strada, non escluderla nemmeno tu, e poi l'induzione è un po' ovunque, quindi non posso rispondere.

[antosecret]

in effetti mi sono espresso molto male! cercherò dimigliorare anche in questo.

Ci ho provato un pochetto e nelle dimostrazioni che sembrano funzionare c'è sempre lo stesso errore dipoco fa...

Ho dimostrato qualche altro caso banale ma non riesco a generalizzare...
Se qualcuno mi da una dritta ci riprovo...
altrimenti credo che lascerò risolvere il problema a qualcuno più bravo...

[edriv]

Ok, se qualcuno vuole una dritta per il problema di Tiberio:
Prendere il ciclo più grande e cercare in tutti i modi di allargarlo

[darkcrystal]

"Problema della Canna"
Per uno o due persone la cosa è abbastanza ovvia.
Ragioniamo per una specie di assurdo+induzione. Prendiamo il più grande ciclo che riusciamo a trovare nel nostro grafo, e diciamo che contenga l < n vertici. Vediamo ora quanti lati possono collegare i vertici "dentro" (=quelli nel ciclo lungo l) con i vertici "fuori" (=gli altri). Se per caso uno dei vertici fuori ha almeno $ \lceil \frac{l}{2} \rceil $ lati che vanno a vertici dentro, allora ha due lati che vanno a due vertici adiacenti nel ciclo, dunque possiamo "aprire" il ciclo in corrispondenza di quei due vertici e infilarlo in mezzo, aumentando così la lunghezza del ciclo, assurdo perchè abbiamo supposto che fosse il più lungo possibile.
Ma allora ogni vertice fuori manda ai vertici dentro al massimo $ \lfloor \frac{l}{2} \rfloor $ lati, dunque manda ad altri vertici fuori almeno $ \lceil \frac{n}{2} \rceil - \lfloor \frac{l}{2} \rfloor \geq \lceil \frac{n-l}{2} \rceil $ lati. Ma allora l'insieme dei vertici fuori è un grafo con meno di n vertici e rispetta l'ipotesi sul grado dei vertici, perciò per ipotesi induttiva posso fare un ciclo che li prenda tutti. Abbiamo perciò partizionato il grafo in due cicli, uno lungo l e uno n-l. Ora, evidentemente $ l \geq \frac{n}{2} $, ed inoltre nel ciclo "minore" ogni vertice ha - con gli altri vertici dello stesso ciclo - al più (n-l-1) collegamenti; perciò ogni vertice del ciclo minore ha almeno $ \lceil \frac{n}{2} \rceil -n+l+1 $ collegamenti verso vertici del ciclo maggiore, e dunque in totale il ciclo piccolo ha almeno $ (n-l)(\lceil \frac{n}{2} \rceil -n+l+1) $ collegamenti verso quello grosso. Siccome quel numeraccio lì è $ \geq \lceil \frac{n}{2} \rceil $, ci saranno due collegamenti che vanno a due vertici che nel ciclo maggiore sono adiacenti. Ma allora possiamo aprire il ciclo maggiore in corrispondenza di questi due vertici e infilare una "catena" presa dall'altro ciclo ed aumentare così la lunghezza del ciclo maggiore, nuovamente assurdo (cerco di spiegare meglio questo punto: siano A e B i vertici adiacenti nel ciclo maggiore. Partiamo da A, ci spostiamo nel ciclo esterno, lo percorriamo fino a che non arriviamo al vertice che è connesso a B e poi passiamo a B. Quello che abbiamo ottenuto è ancora un ciclo, solo che è più lungo di quello che abbiamo supposto essere il massimo!). L'unica assunzione che abbiamo fatto è stata l < n, dunque concludiamo che il ciclo maggiore ha effettivamente lunghezza n.

Speriamo che vada tutto bene, e buona Pasqua a tutti!

[Tibor Gallai]

Prendiamo il più grande ciclo che riusciamo a trovare nel nostro grafo, e diciamo che contenga l < n vertici.

Da qui in avanti dai per scontato che l sia ben definito, ovvero che esistano cicli nel grafo. Poco male, si mette a posto in 1 riga.

Se per caso uno dei vertici fuori ha almeno $ \lceil \frac{l}{2} \rceil $ lati che vanno a vertici dentro

Qui vorresti dire $ \lfloor \frac{l}{2} \rfloor +1 $, altrimenti le deduzioni successive sono errate. Di nuovo poco male.

il ciclo piccolo ha almeno $ (n-l)(\lceil \frac{n}{2} \rceil -n+l+1) $ collegamenti verso quello grosso. Siccome quel numeraccio lì è $ \geq \lceil \frac{n}{2} \rceil $, ci saranno due collegamenti che vanno a due vertici che nel ciclo maggiore sono adiacenti.

Questo non è giustificato. Ricordati che ad uno stesso nodo del ciclo grande possono arrivare molti collegamenti dai nodi del ciclo piccolo.

Se volete un hint un po' diverso da quello di edriv, vi suggerisco di considerare il cammino più lungo, e non il ciclo. La dimostrazione che conosco è molto breve, e btw il teorema è stato scoperto e dimostrato da Dirac nel 1952.

[edriv]

Questo non è giustificato. Ricordati che ad uno stesso nodo del ciclo grande possono arrivare molti collegamenti dai nodi del ciclo piccolo.

Questo però si può anche (spero) sistemare, anche perchè darkcrystal non ha usato in nessun modo il fatto che il ciclo piccolo fosse in effetti un ciclo. (ha usato solo che è connesso).

Chiamando k il minimo numero minimo di archi che partono da un vertice del ciclo piccolo che vanno in quello grande. Se d è il grado minimo, più di n/2, allora abbiamo la stima $ ~ k + (n-l) \ge d + 1 $. Dimostrando che k è almeno 2 e prendendo due vertici adiacenti nel ciclo piccolo credo si riesca a fare una stima su l sufficiente a trovare un assurdo. Se qualcuno (tipo darkcrystal) ha voglia di portare avanti la cosa

[edriv]

Oggi ho trovato una soluzione decente. Per comodità di notazione prendiamo 2n fumatori, ciascuno è amico di almeno n.
Prendiamo il cammino più lungo, di lunghezza a. (che per ora supponiamo <2n>a, dovrà trovarsi almeno un nodo del "primo tipo" (A) accanto a destra di un nodo del "secondo tipo" (B).
Se facciamo il percorso partendo dal nodo più a sinistra, andando fino a B, poi saltando a C, procedendo verso destra fino ad A e poi saltando fuori, riusciamo ad allungare il cammino.
Quindi c'è un cammino di lunghezza 2n, di estremi X (a sinistra) e Y (a destra).

Dobbiamo trasformarlo in un ciclo. Siccome sia X che Y hanno almeno n vicini, ci sarà sicuro un vicino di X (X') che si trova accanto a destra di un vicino di Y (Y'). Andando da X ad X', poi a destra fino a Y, poi a Y', poi a sinistra fino a X, abbiamo un ciclo di lunghezza 2n.

Enjoy the joint!

[federiko97]

Qui trovi una dimostrazione alternativa decisamente più brutta, e la tua stessa soluzione ma scritta da un matematico ben più illustre....