match paradossali in campionato di calcio

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 16 gen 2011, 10:54

Con immonda soddisfazione sono finalmente riuscito a dimostrare il bound del 75% 8) E questa soluzione mi pare anche giusta :o :roll:
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 :D (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 :?
...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

abc
Messaggi: 16
Iscritto il: 18 apr 2009, 14:09

Re: match paradossali in campionato di calcio

Messaggio da abc » 17 gen 2011, 00:28

data la quantità di predecessori ho come la sensazione di portare un'altra soluzione cannata :roll: . Cmq ci provo: una volta ordinati i tizi è chiaro che se a_k è il punteggio del k-esimo tizio, allora, visto che ci sono solo k-1 altri sopra di lui, allora costui ha vinto almeno a_k-k+1 partite non-paradossali. Allora se sommiamo questo da 1 a (n+1)/2 (sono tutte partite diverse) troviamo almeno (n-1)(n+1)/8 partite belle, ricordando che la somma gli a_k hanno media maggiore di n-1/2, essendo i migliori. Quindi le partite paradossali sono al max le restanti. Si vede che con questo ragionamento si spreca molto, comunque

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

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 17 gen 2011, 14:23

abc ha scritto:data la quantità di predecessori ho come la sensazione di portare un'altra soluzione cannata :roll: . Cmq ci provo: una volta ordinati i tizi è chiaro che se a_k è il punteggio del k-esimo tizio, allora, visto che ci sono solo k-1 altri sopra di lui, allora costui ha vinto almeno a_k-k+1 partite non-paradossali. Allora se sommiamo questo da 1 a (n+1)/2 (sono tutte partite diverse) troviamo almeno (n-1)(n+1)/8 partite belle, ricordando che la somma gli a_k hanno media maggiore di n-1/2, essendo i migliori. Quindi le partite paradossali sono al max le restanti. Si vede che con questo ragionamento si spreca molto, comunque
A me pare perfetta (e ridicolizza la mia :? che fa la stessa cosa aggiungendo però una marea di notazione :oops: ). Anche se di poco però, scritta così non arriva al bound del 75%, ma lo sfiora... penso si aggiusti migliorando anche solo di pochissimo qualche stima :wink:
...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 » 17 gen 2011, 17:40

Uhm, son felice che la soluzione di dario2994 sia equivalente a una mille volte più breve così non devo sorbirmi i contazzi pazzi :P

Quella di abc comunque è carina e un pochino più breve della mia che comunque mi dava l'impressione di sprecare tantissimo... Mah, un problema strano...

Complimenti a tutti e due (ad abc per la soluzione breve e a dario2994 per la perseveranza :D )
"Sei la Barbara della situazione!" (Tap)

abc
Messaggi: 16
Iscritto il: 18 apr 2009, 14:09

Re: match paradossali in campionato di calcio

Messaggio da abc » 17 gen 2011, 19:09

dario2994 ha scritto:Anche se di poco però, scritta così non arriva al bound del 75%, ma lo sfiora... penso si aggiusti migliorando anche solo di pochissimo qualche stima :wink:
Mi sembra che in realtà arrivi ad un po' meno del 75%, visto che $ n+1>n $ e quindi arriva a una lenticchia di più di 25%, il che è meglio. Cmq ora mi accorgo che ieri notte ero in uno stato strano, per stare sul forum a quell'ora e non accorgermi che c'era già una soluzione, tra l'altro semi-equivalente, tranne che per il fatto che cerca di buttare di meno definendo x (anch'io ci avevo provato, cercando un bound su x, ma poi in effetti, anche se $ a_k-k+1<0 $ chissene :lol: ).
La tua soluzione, piever, com'era?

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

Re: match paradossali in campionato di calcio

Messaggio da dario2994 » 17 gen 2011, 22:32

abc ha scritto: Mi sembra che in realtà arrivi ad un po' meno del 75%, visto che $ n+1>n $ e quindi arriva a una lenticchia di più di 25%, il che è meglio
Ops... hai ragione :oops:
...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 » 19 gen 2011, 03:24

Rispondendo ad abc, spero di essere ancora sufficientemente sveglio per non dire fesserie:

In sostanza ordino le squadre e poi a ogni squadra associo il numero di partite vinte contro squadre più deboli meno il numero di partite perse contro squadre più forti, (chiamiamo tale numero $ c_k $). Il numero di partite non paradossali è almeno $ \frac{1}{2}\sum |c_k| $

I $ c_k $ però sono una successione di interi strettamente decrescente, dunque la somma dei valori assoluti è minima quando vanno da $ \frac{n}{2} $ a $ \frac{n}{2} $ (detto un po' con le buone...) e questo ci fornisce la stima richiesta.

Spero si capisca, ma ne dubito :oops:
"Sei la Barbara della situazione!" (Tap)

Rispondi