OliForum Matematico

Ad un torneo di ping-pong ci sono n partecipanti. Ognuno incontra tutti gli altri una ed una sola volta.
Dimostrare che alla fine del torneo si verifica esattamente una tra le seguenti due possibilità:
(i) i partecipanti possono essere numerati da 1 ad n in modo tale che 1 ha battuto 2, 2 ha battuto 3,...,n-1 ha battuto n e n ha battuto 1;
(ii) i partecipanti possono essere divisi in due sottoinsiemi non vuoti A e B in modo che ogni elemento di A ha battuto ogni elemento di B.

Saluti da julio14, eli9o e TBPL

basta rappresentare il problema come un grafo orientato... dopo non è difficilissimo concludere

Beh rappresentare il problema come grafo orientato mi sembra il minimo per riuscire a capirci qualcosa (anche se qualcuno è stato così masochista da provare, e riuscire, a risolverlo senza). Tuttavia da lì alla conclusione ne passa di strada. In ogni caso è vero, non è difficilissimo (rispetto allo standard a cui ci hanno abituato in questi giorni...)

Quella voce di Bobo che diceva di non postare su internet regalini dal WC l'ho sentita solo io?

Questo l'ho postato prima che lo dicesse Bobo, cioè la sera del giorno in cui abbiamo fatto combinatoria (si, avevo il computer). In ogni caso si riferiva ai problemi di oggi e ieri no? Io avevo capito solo i problemi del test. Comunque dato che c'è stata, ormai ben più di una, risposta, non posso più cancellare, e sono costretto a passare la palla ai mod.

E' uno delle sessioni, quindi è diffondibile... Se fosse stato del BST, allora non oso pensare a cosa ci avrebbe fatto Bobo

TBPL ha scritto:E' uno delle sessioni, quindi è diffondibile...

Non solo, ma è well-known (corollario di un teorema di Moon). Tenerlo segreto sarebbe un po' ridicolo.

julio14 ha scritto:Beh rappresentare il problema come grafo orientato mi sembra il minimo per riuscire a capirci qualcosa (anche se qualcuno è stato così masochista da provare, e riuscire, a risolverlo senza).

Ogni riferimento è puramente casuale, vero?! Oltretutto sono anche partito dal punto (ii) per dimostrare il punto (i), e nonostante i commenti sarcastici di Pietro ci sono riuscito!!

LOOL. Quattro pagine di parole 0.o, vero cucciolo?

Federiko ha scritto:e nonostante i commenti sarcastici di Pietro ci sono riuscito!!

Uhm, ti spiacerebbe postare su forum la tua dimostrazione? Potrebbe essere molto istruttiva...
E poi spiegherebbe a molti hn come _non_ approcciare un problema di combinatoria...
E non usare la solita scusa che hai una dimostrazione bellissima ma lo spazio a tua disposizione per scriverla è troppo ridotto (cosa che tra l'altro in questo caso potrebbe benissimo essere vera )...

Tibor Gallai ha scritto:Non solo, ma è well-known (corollario di un teorema di Moon). Tenerlo segreto sarebbe un po' ridicolo.

Cosa dice questo teorema?

stefanos (quella stoppia) ha scritto:LOOL. Quattro pagine di parole 0.o, vero cucciolo?

In realtà solo 2 pagine.. E poi io scrivo tutto come se fosse una dimostrazione per fissare le idee.. E almeno io ce l'ho fatta! Tu no, stoppia, e deciditi sull'avatar!

piever (quel maledetto facocero) ha scritto:E poi spiegherebbe a molti hn come _non_ approcciare un problema di combinatoria...

Maledetto! Scrivi i commenti in bianco!! Non posto la soluzione per ripicca e per buon gusto. Ti sembrerà strano ma anche io ho la mia dignità!

Federiko97 ha scritto: e deciditi sull'avatar!

Bello quest'ultimo, no? Prova a rispondere `no' e vedi..

Federiko97 ha scritto:Scrivi i commenti in bianco!!

In verita` sono in #DEE3E7.

PS: Vedo che hai notato che si puo` contraffarre il nome nel quote.. MALEDETTO COPIONE!

mitchan88 ha scritto:

Tibor Gallai ha scritto:Non solo, ma è well-known (corollario di un teorema di Moon). Tenerlo segreto sarebbe un po' ridicolo.

Cosa dice questo teorema?

Un torneo contiene cicli di ogni possibile lunghezza (da 3 a n) se e solo se è fortemente connesso.

Tibor Gallai ha scritto:Un torneo contiene cicli di ogni possibile lunghezza (da 3 a n) se e solo se è fortemente connesso.

Vi risparmio una googlata sul fortemente connesso:vedi qui.