Regalino dal WC

[julio14]

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

[kn]

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

[julio14]

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...)

[Il_Russo]

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

[julio14]

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.

[TBPL]

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

[Tibor Gallai]

E' uno delle sessioni, quindi è diffondibile...

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

[Federiko]

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!!

[stefanos]

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

[piever]

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 )...

[mitchan88]

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

Cosa dice questo teorema?

[Federiko]

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!

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à!

[stefanos]

e deciditi sull'avatar!

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

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!

[Tibor Gallai]

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.

[Oblomov]

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.