Sia $ $A $ un insieme di $ $n $ residui $ $\pmod{n^2} $. Dimostrare che esiste un insieme $ $B $ di $ $n $ residui $ $\pmod{ n^2} $ tale che $ $\{a+b|a\in A,\ b\in B\} $ contiene almeno la metà dei residui $ $\pmod{n^2} $.
IMO ShortList 1999 C4
La somma di coppie contiene metà dei residui mod n^2
La somma di coppie contiene metà dei residui mod n^2
...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
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
E' il primo messaggio e sto andando di fretta, mi sa che scriverò qualche idiozia...
Comunque innanzitutto definirei $ B_k=\{ a+k|a\in A \} $ (ovviamente tutto inteso mod $ n^2 $) in modo che se $ B=\{ h_1,... ,h_n \} $ allora l'insieme che cerchiamo è $ A+B=B_{h_1}\cup ... \cup B_{h_n} $. Ovvero ci serve un unione di n diversi $ B_k $ abbastanza grande. Inoltre notiamo che ogni intero "i" tra 1 e $ n^2 $ appartiene a n diversi B_k (appartiene a ogni $ B_{i-a} $ per ogni $ a\in A $). Ho cercato per un po' una scelta intelligente, una costruzione di B, ma non trovandola ho provato una strada vista in un video: stimare mediamente quanti elementi ha un unione di n B_k isperando che se questa sia maggiore di $ \frac{n^2}{2} $ in modo che ci sia un unione che abbia cardinalità almeno quanto la media, arrivando perciò alla tesi. Ora, per formalizzare un pochino definirei $ U_1, ... , U_{\binom{n^2}{n}} $ tutte le possibili unioni (che sono $ \binom{n^2}{n} $ perchè devo scegliere n diversi B_k tra n^2 possibili B_k perchè k ha senso farlo variare tra 1 e n^2). Allora con un piccolo double counting
$ \displaystyle Media=\frac{\sum \mbox{n° elementi di U_k}}{\binom{n^2}{n}}=\frac{|\{ (i,U_m)|1\le i\le n^2, i\in U_m \} |}{\binom{n^2}{n}}=\frac{\sum_{i=1}^{n^2}\mbox{n° di }U_m\mbox{ che contengono i} }{\binom{n^2}{n}} $
Ora contiamo quante unioni U_m contengono "i". Sappiamo che "i" sta in esattamente n diversi B_k e diciamo che C è l'insieme di questi B_k. Allora se c'è un elemento di C tra gli n B_k che definiscono U_m, allora $ i\in U_m $ altrimenti no. Quindi tutti gli U_m che non contengono "i" sono definiti con una scelta di n B_k di cui nessuno è in C e ci sono esattamente $ n^2-n $ tali B_k. Allora gli U_m che non contengono "i" sono $ \binom{n^2-n}{n} $ allora
$ Media=\frac{\sum_{i=1}^{n^2}\binom{n^2}{n}-\binom{n^2-n}{n}}{\binom{n^2}{n}}=\frac{n^2\binom{n^2}{n}-n^2\binom{n^2-n}{n}}{\binom{n^2}{n}} $
Ci resta da dimostrare che
$ \frac{\binom{n^2}{n}-\binom{n^2-n}{n}}{\binom{n^2}{n}}\ge \frac{1}{2}\Leftrightarrow 2\binom{n^2-n}{n}\le \binom{n^2}{n} $ e credetemi non è poi così difficile, ma ora non ho tempo.
Io ho sviluppato i binomiali, detto che $ \frac{n}{n-m}\le \frac{n-k}{n-m-k} $ e usato bernoulli per dire che frazione>2
Comunque innanzitutto definirei $ B_k=\{ a+k|a\in A \} $ (ovviamente tutto inteso mod $ n^2 $) in modo che se $ B=\{ h_1,... ,h_n \} $ allora l'insieme che cerchiamo è $ A+B=B_{h_1}\cup ... \cup B_{h_n} $. Ovvero ci serve un unione di n diversi $ B_k $ abbastanza grande. Inoltre notiamo che ogni intero "i" tra 1 e $ n^2 $ appartiene a n diversi B_k (appartiene a ogni $ B_{i-a} $ per ogni $ a\in A $). Ho cercato per un po' una scelta intelligente, una costruzione di B, ma non trovandola ho provato una strada vista in un video: stimare mediamente quanti elementi ha un unione di n B_k isperando che se questa sia maggiore di $ \frac{n^2}{2} $ in modo che ci sia un unione che abbia cardinalità almeno quanto la media, arrivando perciò alla tesi. Ora, per formalizzare un pochino definirei $ U_1, ... , U_{\binom{n^2}{n}} $ tutte le possibili unioni (che sono $ \binom{n^2}{n} $ perchè devo scegliere n diversi B_k tra n^2 possibili B_k perchè k ha senso farlo variare tra 1 e n^2). Allora con un piccolo double counting
$ \displaystyle Media=\frac{\sum \mbox{n° elementi di U_k}}{\binom{n^2}{n}}=\frac{|\{ (i,U_m)|1\le i\le n^2, i\in U_m \} |}{\binom{n^2}{n}}=\frac{\sum_{i=1}^{n^2}\mbox{n° di }U_m\mbox{ che contengono i} }{\binom{n^2}{n}} $
Ora contiamo quante unioni U_m contengono "i". Sappiamo che "i" sta in esattamente n diversi B_k e diciamo che C è l'insieme di questi B_k. Allora se c'è un elemento di C tra gli n B_k che definiscono U_m, allora $ i\in U_m $ altrimenti no. Quindi tutti gli U_m che non contengono "i" sono definiti con una scelta di n B_k di cui nessuno è in C e ci sono esattamente $ n^2-n $ tali B_k. Allora gli U_m che non contengono "i" sono $ \binom{n^2-n}{n} $ allora
$ Media=\frac{\sum_{i=1}^{n^2}\binom{n^2}{n}-\binom{n^2-n}{n}}{\binom{n^2}{n}}=\frac{n^2\binom{n^2}{n}-n^2\binom{n^2-n}{n}}{\binom{n^2}{n}} $
Ci resta da dimostrare che
$ \frac{\binom{n^2}{n}-\binom{n^2-n}{n}}{\binom{n^2}{n}}\ge \frac{1}{2}\Leftrightarrow 2\binom{n^2-n}{n}\le \binom{n^2}{n} $ e credetemi non è poi così difficile, ma ora non ho tempo.
Io ho sviluppato i binomiali, detto che $ \frac{n}{n-m}\le \frac{n-k}{n-m-k} $ e usato bernoulli per dire che frazione>2
Tira più un carro di buoi che un.. carro di cani
Complimenti tu hai mostrato un risultato più forte e interessante 
Perchè quella roba che tu dici essere maggiore di 2 è si maggiore di 2 ma è anche maggiore di $ $e $ anzi ci tende proprio ad $ $e $ quindi ottimizzando la tua dimostrazione si ottiene che almeno $ $n^2\cdot \left(1-\frac1e\right) $ residui sono raggiunti da un'accurata scelta dell'insieme B
La mia dimostrazione era costruttiva, non ve la scrivo perchè oggi ho gia scritto abbastanza latex e perchè può essere istruttivo trovarla
p.s. la dimostrazione della tendenza ad e non saprei proprio come dimostrarla... ma wolfram alpha sostiene sia vero:
http://www.wolframalpha.com/input/?i=li ... 2-x%2Cx%29
Non lo inserisco come collegamento perchè per uno strano motivo se lo fo mi si cancella tutto il messaggio...
Perchè quella roba che tu dici essere maggiore di 2 è si maggiore di 2 ma è anche maggiore di $ $e $ anzi ci tende proprio ad $ $e $ quindi ottimizzando la tua dimostrazione si ottiene che almeno $ $n^2\cdot \left(1-\frac1e\right) $ residui sono raggiunti da un'accurata scelta dell'insieme B
La mia dimostrazione era costruttiva, non ve la scrivo perchè oggi ho gia scritto abbastanza latex e perchè può essere istruttivo trovarla
p.s. la dimostrazione della tendenza ad e non saprei proprio come dimostrarla... ma wolfram alpha sostiene sia vero:
http://www.wolframalpha.com/input/?i=li ... 2-x%2Cx%29
Non lo inserisco come collegamento perchè per uno strano motivo se lo fo mi si cancella tutto il messaggio...
...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
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
tanto per completezza, quel limite si può fare così (brevemente perché non è proprio matematica olimpica):
1. Stirling
$ \displaystyle\lim_{n\to\infty} \frac{\sqrt{2\pi n}(n/e)^n}{n!}=1 $
2. Sostituendo ad ogni fattoriale l'approssimazione di Stirling ci si trova a calcolare
$ \displaystyle\lim_{n\to\infty}\frac{(n^2)^{n^2}(n^2-2n)^{n^2-2n}}{(n^2-n)^{2n^2-2n}} $
3. Raccogliamo a seconda del grado dell'esponente:
$ \displaystyle\frac{(n^2)^{n^2}(n^2-2n)^{n^2-2n}}{(n^2-n)^{2n^2-2n}}=\left(\frac{n^2}{n^2-n}\right)^{n^2}\left(\frac{n^2-2n}{n^2-n}\right)^{n^2}\left(\frac{n^2-2n}{n^2-n}\right)^{-2n} $
4. Facciamo un po' di divisioni e accorpiamo le due prime parentesi ottenendo
$ \displaystyle\left(1-\frac{1}{(n-1)^2}\right)^{n^2}\left(1-\frac{1}{n-1}\right)^{-2n} $
5. Dividiamo e moltiplichiamo
$ \displaystyle\left(1+\frac{1}{-(n-1)^2}\right)^{-(n-1)^2(- n^2)/(n-1)^2}\left(1+\frac{1}{1-n}\right)^{(1-n)2n/(n-1)} $
6. Il limite del rapporto tra due polinomi dello stesso grado è il rapporto tra i coefficienti di testa, il limite di (1+1/n)^n è e, quindi il nostro limite fa
$ e^{-1}e^{2}=e $
Contento?
PS: al posto del punto 1. si può usare la stima $ (n/3)^n\leq n!\leq (n/2)^n $, che si dovrebbe poter dimostrare per induzione, rendendo la dimostrazione praticamente quasi da 5° liceo.
1. Stirling
$ \displaystyle\lim_{n\to\infty} \frac{\sqrt{2\pi n}(n/e)^n}{n!}=1 $
2. Sostituendo ad ogni fattoriale l'approssimazione di Stirling ci si trova a calcolare
$ \displaystyle\lim_{n\to\infty}\frac{(n^2)^{n^2}(n^2-2n)^{n^2-2n}}{(n^2-n)^{2n^2-2n}} $
3. Raccogliamo a seconda del grado dell'esponente:
$ \displaystyle\frac{(n^2)^{n^2}(n^2-2n)^{n^2-2n}}{(n^2-n)^{2n^2-2n}}=\left(\frac{n^2}{n^2-n}\right)^{n^2}\left(\frac{n^2-2n}{n^2-n}\right)^{n^2}\left(\frac{n^2-2n}{n^2-n}\right)^{-2n} $
4. Facciamo un po' di divisioni e accorpiamo le due prime parentesi ottenendo
$ \displaystyle\left(1-\frac{1}{(n-1)^2}\right)^{n^2}\left(1-\frac{1}{n-1}\right)^{-2n} $
5. Dividiamo e moltiplichiamo
$ \displaystyle\left(1+\frac{1}{-(n-1)^2}\right)^{-(n-1)^2(- n^2)/(n-1)^2}\left(1+\frac{1}{1-n}\right)^{(1-n)2n/(n-1)} $
6. Il limite del rapporto tra due polinomi dello stesso grado è il rapporto tra i coefficienti di testa, il limite di (1+1/n)^n è e, quindi il nostro limite fa
$ e^{-1}e^{2}=e $
Contento?
PS: al posto del punto 1. si può usare la stima $ (n/3)^n\leq n!\leq (n/2)^n $, che si dovrebbe poter dimostrare per induzione, rendendo la dimostrazione praticamente quasi da 5° liceo.