Regalino dal WC

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Regalino dal WC

Messaggio da julio14 » 29 gen 2009, 21:49

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 :D
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 30 gen 2009, 22:23

basta rappresentare il problema come un grafo orientato... dopo non è difficilissimo concludere
:P :P
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 01 feb 2009, 21:23

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...)
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Il_Russo
Messaggi: 347
Iscritto il: 16 gen 2007, 16:04
Località: Pisa

Esatto

Messaggio da Il_Russo » 01 feb 2009, 22:32

Quella voce di Bobo che diceva di non postare su internet regalini dal WC l'ho sentita solo io?
Aderisci anche tu al progetto "Diamo a Nonciclopedia una sezione matematica indecente"

Presidente della commissione EATO per le IGO

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 01 feb 2009, 22:43

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.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

TBPL
Messaggi: 117
Iscritto il: 20 gen 2008, 23:19

Messaggio da TBPL » 01 feb 2009, 22:44

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

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 02 feb 2009, 05:41

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. :wink:

Avatar utente
Federiko
Messaggi: 226
Iscritto il: 15 mag 2008, 19:24
Località: Roma

Messaggio da Federiko » 02 feb 2009, 11:17

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!! :D
CUCCIOLO

stefanos
Messaggi: 229
Iscritto il: 02 giu 2008, 13:23
Località: Roma
Contatta:

Messaggio da stefanos » 03 feb 2009, 09:19

LOOL. Quattro pagine di parole 0.o, vero cucciolo?
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 03 feb 2009, 16:05

Federiko ha scritto:e nonostante i commenti sarcastici di Pietro ci sono riuscito!! :D
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 :P )...
"Sei la Barbara della situazione!" (Tap)

Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 » 03 feb 2009, 16:34

Tibor Gallai ha scritto:Non solo, ma è well-known (corollario di un teorema di Moon). Tenerlo segreto sarebbe un po' ridicolo. :wink:
Cosa dice questo teorema? :?:
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

Avatar utente
Federiko
Messaggi: 226
Iscritto il: 15 mag 2008, 19:24
Località: Roma

Messaggio da Federiko » 03 feb 2009, 16:44

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à! :x
CUCCIOLO

stefanos
Messaggi: 229
Iscritto il: 02 giu 2008, 13:23
Località: Roma
Contatta:

Messaggio da stefanos » 03 feb 2009, 18:55

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

PS: Vedo che hai notato che si puo` contraffarre il nome nel quote.. MALEDETTO COPIONE! :lol:
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 03 feb 2009, 23:29

mitchan88 ha scritto:
Tibor Gallai ha scritto:Non solo, ma è well-known (corollario di un teorema di Moon). Tenerlo segreto sarebbe un po' ridicolo. :wink:
Cosa dice questo teorema? :?:
Un torneo contiene cicli di ogni possibile lunghezza (da 3 a n) se e solo se è fortemente connesso.

Avatar utente
Oblomov
Messaggi: 284
Iscritto il: 23 ott 2005, 13:18
Località: Bologna

Messaggio da Oblomov » 06 feb 2009, 00:45

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.
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös

Rispondi