Re: match paradossali in campionato di calcio
Inviato: 16 gen 2011, 10:54
Con immonda soddisfazione sono finalmente riuscito a dimostrare il bound del 75% E questa soluzione mi pare anche giusta
Ordino i giocatori da $1$ a $n$ in modo che se $i<j$ allora il giocatore $i$-esimo ha un punteggio $\ge$ del $j$-esimo.
Siano $d_i$, $v_i$, $p_i$ rispettivamente il punteggio, il numero di partite paradossali vinte, il numero di partite paradossali perse dell' $i$-esimo giocatore.
Sia $P$ il numero delle partite paradossali.
Definisco $x=\max\{i|d_i\ge i\}$
Ora parto con la dimostrazione, iniziando da 2 simpatici lemmi...
Fatto di notte n.2 $\ i\le x\ \Rightarrow \ v_i\le i-1\ \wedge p_i\le n-1-x$
Tutte le partite paradossali che vince l'$i$-esimo giocatore le deve giocare con giocatori più in alto di lui in classifica, che sono $i-1$ quindi $v_i\le i-1$.
Sicuramente vale $d_i\ge d_x\ge x$ quindi l'$i$-esimo giocatore non può perdere più di $n-1-x$ partite da cui $p_i\le n-1-x$
Fatto di notte n.3 $\ i>x\ \Rightarrow \ v_i\le x\ \wedge\ p_i\le n-i$
Sicuramente vale $d_i\le d_{x+1}$ ma per la definizione di $x$ vale anche $d_{x+1}\le x$ quindi $d_i\le x$. Da questo deriva ovviamente $v_i\le x$.
Tutte le partite paradossali perse dall'$i$-esimo giocatore le deve giocare con giocatori più in basso di lui in classifica, che sono $n-i$ quindi $p_i\le n-i$
E ora la dimostrazione (che sfrutta inizialmente i 2 fatti di notte, poi un AM-GM e poi una disuguaglianza ovvia $n-1<n$ )
$\displaystyle 2P=\sum_{i=1}^xv_i+p_i+\sum_{i=x+1}^nv_i+p_i\le \sum_{i=1}^x(i-1)+(n-1-x)+\sum_{i=x+1}^n(x)+(n-i)=$
$\displaystyle =(n-1-x)x+\frac{x(x-1)}{2}+(n-x)x+\frac{(n-x)(n-x-1)}{2}=$
$\displaystyle =nx-x-x^2+nx-x^2+\frac{x^2-x+n^2-nx-n-nx+x^2+x}{2}=$
$\displaystyle =nx-x-x^2+nx-x^2+x^2-nx+\frac{n^2-n}{2}=nx-x^2-x+\binom{n}{2}=$
$\displaystyle =\left[\sqrt{x((n-1)-x)}\right]^2+\binom{n}{2}\le \left[\frac{x+(n-1)-x}{2}\right]^2+\binom{n}{2}=$
$\displaystyle =\frac 12\cdot \frac{(n-1)^2}{2}+\binom{n}{2}< \frac 12\binom n2 +\binom n2=\frac 32\binom n2$
Da cui ottengo dividendo per 2 $P<\frac 34\binom n2$ che è proprio il bound del 75%
EDIT: Inoltre tentando approcci del genere è impossibile migliorare il bound, poichè se si assume che le partite paradossali possano essere anche fra giocatori con lo stesso punteggio (cosa che ho fatto impliciatamente nella dimostrazione) c'è un esempio che realizza "quasi" il 75%... basta prendere n dispari, fare in modo che ogni giocatore perda con i $\frac{n-1}{2}$ giocatori dopo di lui in classifica (almeno con quelli esistenti), vinca con i $\frac{n-1}{2}$ giocatori prima di lui in classifica (almeno con quelli esistenti) e con gli altri faccia partite non paradossali... così facendo si ottiene un numero di partite paradossali che al crescere di n è praticamente $\frac{3}{4}\binom n2$. Quindi se si vuole migliorare il bound bisogna anche sfruttare l'ipotesi che una partita paradossale è tra giocatori con punteggio diverso, che complica immensamente le cose, perchè è tostissima da sfruttare
Ordino i giocatori da $1$ a $n$ in modo che se $i<j$ allora il giocatore $i$-esimo ha un punteggio $\ge$ del $j$-esimo.
Siano $d_i$, $v_i$, $p_i$ rispettivamente il punteggio, il numero di partite paradossali vinte, il numero di partite paradossali perse dell' $i$-esimo giocatore.
Sia $P$ il numero delle partite paradossali.
Definisco $x=\max\{i|d_i\ge i\}$
Ora parto con la dimostrazione, iniziando da 2 simpatici lemmi...
Fatto di notte n.2 $\ i\le x\ \Rightarrow \ v_i\le i-1\ \wedge p_i\le n-1-x$
Tutte le partite paradossali che vince l'$i$-esimo giocatore le deve giocare con giocatori più in alto di lui in classifica, che sono $i-1$ quindi $v_i\le i-1$.
Sicuramente vale $d_i\ge d_x\ge x$ quindi l'$i$-esimo giocatore non può perdere più di $n-1-x$ partite da cui $p_i\le n-1-x$
Fatto di notte n.3 $\ i>x\ \Rightarrow \ v_i\le x\ \wedge\ p_i\le n-i$
Sicuramente vale $d_i\le d_{x+1}$ ma per la definizione di $x$ vale anche $d_{x+1}\le x$ quindi $d_i\le x$. Da questo deriva ovviamente $v_i\le x$.
Tutte le partite paradossali perse dall'$i$-esimo giocatore le deve giocare con giocatori più in basso di lui in classifica, che sono $n-i$ quindi $p_i\le n-i$
E ora la dimostrazione (che sfrutta inizialmente i 2 fatti di notte, poi un AM-GM e poi una disuguaglianza ovvia $n-1<n$ )
$\displaystyle 2P=\sum_{i=1}^xv_i+p_i+\sum_{i=x+1}^nv_i+p_i\le \sum_{i=1}^x(i-1)+(n-1-x)+\sum_{i=x+1}^n(x)+(n-i)=$
$\displaystyle =(n-1-x)x+\frac{x(x-1)}{2}+(n-x)x+\frac{(n-x)(n-x-1)}{2}=$
$\displaystyle =nx-x-x^2+nx-x^2+\frac{x^2-x+n^2-nx-n-nx+x^2+x}{2}=$
$\displaystyle =nx-x-x^2+nx-x^2+x^2-nx+\frac{n^2-n}{2}=nx-x^2-x+\binom{n}{2}=$
$\displaystyle =\left[\sqrt{x((n-1)-x)}\right]^2+\binom{n}{2}\le \left[\frac{x+(n-1)-x}{2}\right]^2+\binom{n}{2}=$
$\displaystyle =\frac 12\cdot \frac{(n-1)^2}{2}+\binom{n}{2}< \frac 12\binom n2 +\binom n2=\frac 32\binom n2$
Da cui ottengo dividendo per 2 $P<\frac 34\binom n2$ che è proprio il bound del 75%
EDIT: Inoltre tentando approcci del genere è impossibile migliorare il bound, poichè se si assume che le partite paradossali possano essere anche fra giocatori con lo stesso punteggio (cosa che ho fatto impliciatamente nella dimostrazione) c'è un esempio che realizza "quasi" il 75%... basta prendere n dispari, fare in modo che ogni giocatore perda con i $\frac{n-1}{2}$ giocatori dopo di lui in classifica (almeno con quelli esistenti), vinca con i $\frac{n-1}{2}$ giocatori prima di lui in classifica (almeno con quelli esistenti) e con gli altri faccia partite non paradossali... così facendo si ottiene un numero di partite paradossali che al crescere di n è praticamente $\frac{3}{4}\binom n2$. Quindi se si vuole migliorare il bound bisogna anche sfruttare l'ipotesi che una partita paradossale è tra giocatori con punteggio diverso, che complica immensamente le cose, perchè è tostissima da sfruttare