match paradossali in campionato di calcio

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

match paradossali in campionato di calcio

Messaggio da piever » 25 set 2008, 21:59

n squadre giocano un campionato di calcio, con regole leggermente diverse. I possibili risultati di una partita sono: vittoria o sconfitta. Ogni squadra incontra ogni altra squadra una e una sola volta. Si prende un punto per la vittoria e zero per la sconfitta. Una partita si dice paradossale se la squadra che perde finisce il torneo con più punti di quella che vince. (Ovvero il match tra A e B è vinto da A, ma a fine torneo A ha totalizzato j punti e B ne ha totalizzati k, con k>j).

Si provi che la percentuale di partite paradossali è minore del 75%

(cioè che il rapporto: (partite paradossali)/(partite totali) è minore di 3/4)

Bonus1: Tra le stime che non dipendono da n, 75% è la migliore possibile?

Bonus2: Qual è la stima migliore (ovvero sia qual è il sup di (partite paradossali)/(partite totali) al variare dei campionati possibili) ?

Non conosco la risposta alle due domande bonus.

Buona fortuna.
"Sei la Barbara della situazione!" (Tap)

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: match paradossali in campionato di calcio

Messaggio da Mist » 10 gen 2011, 14:31

Definizioni: $|P_n| = |\cup_{r=1}^{n}A_r| = \frac{n(n-1)}{2} = \mbox{Insieme delle partite giocate}$ dove $A_r = \mbox{Insieme delle partite giocate dalla squadra r}$ e $n$ è il numero delle squadre in gioco
$v(x) =0$ se $x$ è una partita perdente, $1$ se la partita è vincente. Inoltre definiscio $v(A_{r}) = \sum_{x\in A_r}v(x)$. Ogni squadra gioca $n-1$ partite. Posso assumere WLOG che $ \not \exists A_{m} \in P:n: v(A_m) =0$ poichè se esistesse tale squadra sempre perdente si ha che questa non ha mai fatto partite paradossali e che quindi è ininfluente nel nostro calcolo: ergo possiamo toglierla eliminando una vittoria ( o $k$ vittorie, tante quante osno le squadre che hanno solo perso) da ogni altra squadra. A questo punto si nota che una squadra ( la peggiore ) può essere tale che $v(A_{m}) < \lfloor \frac{n}{2} \rfloor $ ovvero $v(A_{m}) = \lfloor \frac{n}{2} \rfloor -1$ nel caso con il maggior numero di partite paradossali per questa squadra. Contate queste partite, possiamo ora eliminare la squadra peggiore e togliere da ogni altra squadra rimasta in gioco la partita che essa ha fatto con la squadra eliminata. Si discende così al caso $n-1$. Anche qui, con la squadra peggiore si hanno $v(A_{j}) = \lfloor \frac{n-1}{2} \rfloor -1$. Procedendo in questa maniera si ottiene che al massimo le partite paradossali sono
$\sum_{r=0}^{n-2}\lfloor \frac{n-r}{2}\rfloor -1$. Calcoliamo:
se $n=2k-1$ allora
$\sum_{r=0}^{2k-3}\lfloor \frac{2k+1-r}{2} \rfloor -1 = (2k-2)\cdot k -(2k-2) + \sum_{r=0}^{2k-3}\lfloor \frac{1-r}{2} \rfloor = (2k-2)(k-1)-(k-2)(k-1) = k(k-1)$. Essendo in questo caso il numero totale delle partite pari a $k(2k+1)$ si ha che il rapporto tra il numero delle partite paradossali e il numero delle partite totali nel caso in cui si hanno il massimo delle partite paradossali è $\frac{ k(k-1)}{k(2k+1)} =\frac{ k-1}{2k+1} :=f(k)$ . Si nora però che essendo $f(k) < f(k+1)$ e che $ \lim_{k \to \infty} \frac{ k-1}{2k+1} = \frac{1}{2}$ si ha che al massimo la percentuale delle partite paradossali è il 50%.

Per il caso in cui $n = 2k$, svolegndo un procedimento analogo a quello svolto sopra, si ottiene che il rapporto tra le partite paradossali e quelle totali è $\frac{k^2-2k-1}{2k^2+k}:= f(k)$-. Ma come prima $f(k) < f(k+1)$ e quindi si ha che come prima al massimo la percentuale delle partite paradossali è del 50%.

(troppo facile ?)
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

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

Re: match paradossali in campionato di calcio

Messaggio da piever » 13 gen 2011, 00:07

Io ho avuto l'impressione che nel tuo ragionamento non tieni conto del seguente fatto:

quando si elimina la squadra ultima in classifica e si trascurano i punti che le altre squadre hanno totalizzato battendola, questo fatto altera la classifica.

Mi sono rimesso a pensare al problema e sono soltanto riuscito a dimostrare il bound 75%, e tuttora ignoro le risposte alle domande bonus. 50% come bound sembra anche credibile, ma la tua dimostrazione non mi ha convinto :(
"Sei la Barbara della situazione!" (Tap)

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: match paradossali in campionato di calcio

Messaggio da Mist » 13 gen 2011, 07:23

Eh, vedi, all'inizio ci avevo pensato anche io, ma poi mi son detto che non sono importanti quelle vittorie perchè sono tutte contro la stessa squadra ( ma anche qui forse c'è una pecca non indifferente...) e quindi danno punti che in fondo hanno "tutti". è un po' come se in una classe di scuola si fa una gara in cui vince chi ha la media più alta e tutti hanno lo stesso voto di condotta: se si toglie il voto di condotta dalla valutazione la classifica degli alunni rimane invariata ( :lol: lasciamo perdere la fonte che mi ha ispirato questo esempio...)!

Anche a me qeull' $\frac{1}{2}$ mi sembra palusibile oltre che "tipico di una gara umana" come ormai penso quando esce un buon risultato, ma francamente non lo so...

Beh, aspettiamo il giudizio di uno degli espertoni del forum a sto punto...
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 13 gen 2011, 14:22

EDIT: Trovato l'errore (leggendo la correzione di Piever)... anche io fo lo stesso identico errore: togliendo il primo la classifica potrebbe cambiare

Forse sto segando completamente, ma non vedo dove... Dimostro per induzione il bound del 50%:
Passo base n=2: ovvio
Passo induttivo: Prendo uno dei primi in classifica... può aver perso al massimo $\frac{n}{2}$ partite (altrimenti non sarebbe primo perchè avrebbe un punteggio sotto la media)... quindi partecipa al massimo a $\frac{n}2$ partite paradossali. Gli altri, tra loro, per ipotesi induttiva generalo al massimo $\frac{\binom{n}{2}}{2}$ partite paradossali. $\frac{\binom{n}{2}}{2}+\frac{n}2\le \frac{\binom{n+1}{2}}{2}$ che è la tesi...
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: match paradossali in campionato di calcio

Messaggio da Mist » 13 gen 2011, 15:29

Pardon, non ho capito qualcosa del tuo ragionamento, ma comunque
$\frac{\binom{n}{2}}{2} +\frac{n}{2} = \frac{\frac{n(n-1)}{2}}{2} +\frac{n}{2} = \frac{n^2-n}{4}+\frac{2n}{4} = \frac{n^2+n}{4} = \frac{\frac{n(n+1)}{2}}{2} = \frac{\binom{n+1}{2}}{2}$
e quindi forse la conclusione che trai non è valida...
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 13 gen 2011, 16:54

Mist ha scritto:Pardon, non ho capito qualcosa del tuo ragionamento, ma comunque
$\frac{\binom{n}{2}}{2} +\frac{n}{2} = \frac{\frac{n(n-1)}{2}}{2} +\frac{n}{2} = \frac{n^2-n}{4}+\frac{2n}{4} = \frac{n^2+n}{4} = \frac{\frac{n(n+1)}{2}}{2} = \frac{\binom{n+1}{2}}{2}$
e quindi forse la conclusione che trai non è valida...
Il mio ragionamento è sbagliato, ma non per quello... avevo piazzato $\le $ al posto di $=$ perchè mi serviva quello (ed è implicato dall'uguaglianza).
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: match paradossali in campionato di calcio

Messaggio da Mist » 13 gen 2011, 17:30

Oh cavolo, è vero, alcune squadre perdono una vittoria e altre ua sconfitta, quindi succede uno scombinamento...

Ma scusate, siccome stiamo trattando il caso peggiore, ce ne importa davvero se le cose si scombinano ? Forse sto dicendo una sciocchezza, ma comunque noi abbiamo visto il caso peggiroe in assoluto, quello in cui le partite paradossali sono il più possibile... A questo punto bastterebbe dimostrare che il caso (o uno dei casi) in cui ci sono più partite paradossali è quello in cui la squadra alla posizione $h$ ha $n-h+1$ vittorie ( che mi sembra abbastanza vero) così si avrebbe che scendendo di caso la classifica rimane invariata...
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 13 gen 2011, 18:52

EDIT: Ok, anche questa è una bella minchiata... il punto è che arrivo a dimostrare un fatto STRAOVVIO, che non implica nulla 8)

Penso di aver trovato una dimostrazione del bound 50% ma anche questa mi puzza un pochino :?
Ordino i tizi in base al punteggio (se 2 hanno lo stesso punteggio chissenefrega). Ora dico che l'i-esimo ha perso $a_i$ partite paradossali.
Definisco $X(k)=\frac{\sum_{i=0}^{k}a_{n-k}}{k+1}$
Ora piglio l' $(n-k)-esimo$ egli ha come punteggio al massimo $n-1-a_{n-k}$. La media dei punteggi di quelli sotto l'$n-k\ esimo$ è sicuramente $\le $ di quella dell'$(n-k)\ esimo$. Inoltre sicuramente i sottostanti fanno ALMENO $a_{n-k}+a_{n-k+1}+\dots +a_{n-1}+a_n$ per la definizione degli $a_i$ ottengo quindi:
Fatto di notte: $\displaystyle n-1-a_{n-k}\ge X(k)$

Ora dimostro per induzione su k che $X(k)\le \frac12(n-1)$:
Passo base: Se k=0 è ovvio che $X(0)=0$ -> vero
Passo induttivo: Assumo per assurdo $\frac{X(k+1)}{k+2}> \frac{1}{2}(n-1)$. Di conseguenza, per il fatto di notte, ottengo $a_{n-(k+1)}<X(k+1)$ ma allora, per le proprietà delle medie $X(k+1)<X(k)\le \frac12(n-1)$
p.s. sono piuttosto convinto di aver segato perchè facendola su un foglio mi veniva che riuscivo a dimostrare soltanto il bound dei 3/4 in questo modo... ma scrivendola qui mi è parso che funzionasse anche per il 50%... boh, non capisco dove sbaglio :roll:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

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

Re: match paradossali in campionato di calcio

Messaggio da piever » 14 gen 2011, 00:54

E bravo dario2994... Finalmente mi si è risolto un dubbio che avevo dal 2008 :D

A parte tutto, la soluzione mi sembra corretta, interessante e bella: complimenti!
"Sei la Barbara della situazione!" (Tap)

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 14 gen 2011, 14:56

piever ha scritto:E bravo dario2994... Finalmente mi si è risolto un dubbio che avevo dal 2008 :D

A parte tutto, la soluzione mi sembra corretta, interessante e bella: complimenti!
:? Ironico??? :? La soluzione è segata :roll:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: match paradossali in campionato di calcio

Messaggio da Mist » 14 gen 2011, 15:05

Ma scusate, se noi dimostriamo che il caso col maggior numero di partite paradossali è quelli in cui il ptimo ha solo vittorie, il secondo ha solo una sconfitta,e in generale l'h-esimo ha n-h+1 sconfitte allore le dimostrazioni mie e di dario sono ok, no ? Ma questo fatto è ovvio, poichè ogni sconfitta genera una partita paradossale così facendo. Oltretutto in quel caso eliminando una squadra non si modifica la classifica, e quindi tutto ok, le nostre dimostrazioni vanno bene...

Mi sbaglio ?
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 14 gen 2011, 15:09

Mist ha scritto:Ma scusate, se noi dimostriamo che il caso col maggior numero di partite paradossali è quelli in cui il ptimo ha solo vittorie, il secondo ha solo una sconfitta,e in generale l'h-esimo ha n-h+1 sconfitte allore le dimostrazioni mie e di dario sono ok, no ? Ma questo fatto è ovvio, poichè ogni sconfitta genera una partita paradossale così facendo. Oltretutto in quel caso eliminando una squadra non si modifica la classifica, e quindi tutto ok, le nostre dimostrazioni vanno bene...

Mi sbaglio ?
Ma questo fatto è falso mi pare di capire, da come lo scrivi, che quella che tu ritieni la situazione migliore sia in realtà la situazione peggiore... come dici tu mi pare si generino ben 0 partite paradossali :?
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: match paradossali in campionato di calcio

Messaggio da Mist » 14 gen 2011, 15:11

Che cretino, è vero, per un attimo ho invertito tutte le cose :oops: :oops: :lol: va beh, ci penso meglio eh..
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

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

Re: match paradossali in campionato di calcio

Messaggio da piever » 14 gen 2011, 16:55

dario2994 ha scritto:
piever ha scritto:E bravo dario2994... Finalmente mi si è risolto un dubbio che avevo dal 2008 :D

A parte tutto, la soluzione mi sembra corretta, interessante e bella: complimenti!
:? Ironico??? :? La soluzione è segata :roll:

Oddio, mi sono accorto adesso che anziché migliorare 75% con 50%, lo peggiori con un ridente 100%, mi ero perso un fattore 1/2 ... Peccato però, perché l'idea sembrava carina...

Se vuoi continuare a tentare con 50% ok, anch'io sono convinto "a intuito" che debba essere vero, però ne ignoro dimostrazioni...

Quindi dai, dopo 2 anni e qualche mese ancora zero soluzioni, chi si cimenta?

Quando volete ditemelo che metto la soluzione o qualche hint...
"Sei la Barbara della situazione!" (Tap)

Rispondi