Ecco qui un problemino... forse andava in combinatoria, ma qui sta meglio :)
Siano $ $(m,n)\in\mathbb{N}^2 $ con $ $gcd(m,n)=1 $ e $ $m<n $; definisco $ $M=\{1,2,3,\dots , n-2,n-1\} $. Coloro tutti gli elementi di M con vari colori. Inoltre per ogni $ $i\in M $ $ $i $ e $ $n-i $ sono dello stesso colore. Se $ $m\not=i $ anche $ $i,|m-i| $ sono dello stesso colore.
Sapendo che 1 è rosso, dimostrare che tutti gli elementi di M sono rossi.
Colorazione dei numeri<n (IMO 1985 es 2)
Colorazione dei numeri<n (IMO 1985 es 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
Che carino! 
Associamo a ogni $ \displaystyle~x\in M $ due interi $ \displaystyle~a_x $ e $ \displaystyle~b_x $ tali che $ \displaystyle~a_xm+b_xn=x $ in modo che la quantità $ \displaystyle~|a_x|+|b_x| $ sia la minima possibile (esistono per Bézout). Prendiamo per buono che questa associazione è unica (*) (l'ho dimostrato sotto per ordine). Possiamo quindi porre $ \displaystyle~f(x)=|a_x|+|b_x| $. Ora se un numero $ \displaystyle~x\in M $ è tale che $ \displaystyle~f(x)>1 $ esiste un $ \displaystyle~y\in M $ dello stesso colore con $ \displaystyle~f(y)<f(x) $ (**). Infatti se $ \displaystyle~x=a_xm+b_xn $ con $ \displaystyle~|a_x|+|b_x|=f(x)>1 $, dato che $ \displaystyle~a_x $ e $ \displaystyle~b_x $ non possono essere entrambi $ \displaystyle~\le 0 $, abbiamo tre casi:
- $ \displaystyle~a_x>1 $, allora per la (*) $ \displaystyle~x\neq m $ e quindi anche $ \displaystyle~y=|m-(a_xm+b_xn)|=|-(a_x-1)m-b_xn| $ è dello stesso colore, con $ \displaystyle~f(y)\le|a_x-1|+|b_x|<f(x) $.
- $ \displaystyle~b_x>0 $, allora poniamo $ \displaystyle~y=n-(a_xm+b_xn)=-a_xm-(b_x-1)n $ che è dello stesso colore, da cui di nuovo $ \displaystyle~f(y)<f(x) $ come voluto.
- $ \displaystyle~a_x=1 $: allora $ \displaystyle~|b_x|>0 $, quindi $ \displaystyle~x\notin M $, assurdo..
Quindi essendo $ \displaystyle~1 $ rosso in un numero finito di passaggi arriviamo a un $ \displaystyle~z\in M $ con $ \displaystyle~f(z)\le 1 $. Evidentemente $ \displaystyle~z=m $. A questo punto sia $ \displaystyle~N $ l'insieme di elementi non rossi e supponiamo per assurdo che non sia vuoto. Prendiamo un $ \displaystyle~t\in N $ tale che $ \displaystyle~f(t)\le f(u)~\forall u\in N $. Per la (**) $ \displaystyle~f(t)\le 1 $, dunque di nuovo $ \displaystyle~t=m $, ma $ \displaystyle~m $ è rosso, assurdo.
Dimostrazione della proposizione (*):
Supponiamo $ \displaystyle~x=am+bn=a'm+b'n\in M $ per due coppie distinte $ \displaystyle~(a,b) $ e $ \displaystyle~(a',b') $ con $ \displaystyle~|a|+|b|=|a'|+|b'|=f(x) $. Ora ovviamente $ \displaystyle~a>0\Leftrightarrow b\le 0 $ e $ \displaystyle~b>0\Leftrightarrow a\le 0 $ (essendo $ \displaystyle~0<x<n $). Segue $ \displaystyle~|a|+|b|=|a-b| $. Altrettanto vale ovviamente per $ \displaystyle~a' $ e $ \displaystyle~b' $. Ora da $ \displaystyle~am+bn=a'm+b'n $ segue $ \displaystyle~n\mid am-a'm $, cioè $ \displaystyle~a-a'=jn $ e $ \displaystyle~b-b'=km $. Sostituendo otteniamo $ \displaystyle~j=-k $, cioè $ \displaystyle~a'=a+kn $ e $ \displaystyle~b'=b-km $. Essendo $ \displaystyle~|a-b|=|a'-b'|=|a-b+k(m+n)| $ e $ \displaystyle~k\neq 0 $, deve valere $ \displaystyle~a-b+k(m+n)=-(a-b) $, da cui $ \displaystyle~m+n\mid a-b $. Dunque $ \displaystyle~m+n\le |a-b| $ (essendo $ \displaystyle~a-b\neq 0 $), da cui due casi:
- $ \displaystyle~a-b>0 $, da cui $ \displaystyle~b\le 0\le a $ e $ \displaystyle~a-b\ge m+n $. Dunque $ \displaystyle~an-bn>n(m+n) $, che sommato a $ \displaystyle~am+bn>0 $ dà $ \displaystyle~a(m+n)>n(m+n) $, ovvero $ \displaystyle~a>n $. Inoltre otteniamo anche $ \displaystyle~bm-am<-m(m+n) $, che sommato a $ \displaystyle~am+bn<n $ dà $ \displaystyle~b(m+n)<-m(m+n)+n<-m(m+n)+(m+n) $. Quindi $ \displaystyle~b<-m+1 $, cioè $ \displaystyle~b\le -m $. Segue che $ \displaystyle~b<b+m\le 0 $ e $ \displaystyle~0<a-n<a $, da cui $ \displaystyle~f(x)=f((a-n)m+(b+m)n)\le |a-n|+|b+m|<|a|+|b| $, assurdo.
- $ \displaystyle~b-a>0 $, da cui $ \displaystyle~a\le 0\le b $ e $ \displaystyle~b-a\ge m+n $. Dunque $ \displaystyle~an-bn<-n(m+n) $, che sommato a $ \displaystyle~am+bn<n $ dà $ \displaystyle~a(m+n)<-n(m+n)+n<-n(m+n)+(m+n) $. Quindi $ \displaystyle~a<-n+1 $, cioè $ \displaystyle~a\le -n $. Inoltre otteniamo anche $ \displaystyle~bm-am>m(m+n) $, che sommato a $ \displaystyle~am+bn>0 $ dà $ \displaystyle~b(m+n)>m(m+n) $, ovvero $ \displaystyle~b>m $. Segue che $ \displaystyle~a<a+n\le 0 $ e $ \displaystyle~0<b-m<b $, da cui $ \displaystyle~f(x)=f((a+n)m+(b-m)n)\le |a+n|+|b-m|<|a|+|b| $, assurdo.
Te come l'hai risolto?
Associamo a ogni $ \displaystyle~x\in M $ due interi $ \displaystyle~a_x $ e $ \displaystyle~b_x $ tali che $ \displaystyle~a_xm+b_xn=x $ in modo che la quantità $ \displaystyle~|a_x|+|b_x| $ sia la minima possibile (esistono per Bézout). Prendiamo per buono che questa associazione è unica (*) (l'ho dimostrato sotto per ordine). Possiamo quindi porre $ \displaystyle~f(x)=|a_x|+|b_x| $. Ora se un numero $ \displaystyle~x\in M $ è tale che $ \displaystyle~f(x)>1 $ esiste un $ \displaystyle~y\in M $ dello stesso colore con $ \displaystyle~f(y)<f(x) $ (**). Infatti se $ \displaystyle~x=a_xm+b_xn $ con $ \displaystyle~|a_x|+|b_x|=f(x)>1 $, dato che $ \displaystyle~a_x $ e $ \displaystyle~b_x $ non possono essere entrambi $ \displaystyle~\le 0 $, abbiamo tre casi:
- $ \displaystyle~a_x>1 $, allora per la (*) $ \displaystyle~x\neq m $ e quindi anche $ \displaystyle~y=|m-(a_xm+b_xn)|=|-(a_x-1)m-b_xn| $ è dello stesso colore, con $ \displaystyle~f(y)\le|a_x-1|+|b_x|<f(x) $.
- $ \displaystyle~b_x>0 $, allora poniamo $ \displaystyle~y=n-(a_xm+b_xn)=-a_xm-(b_x-1)n $ che è dello stesso colore, da cui di nuovo $ \displaystyle~f(y)<f(x) $ come voluto.
- $ \displaystyle~a_x=1 $: allora $ \displaystyle~|b_x|>0 $, quindi $ \displaystyle~x\notin M $, assurdo..
Quindi essendo $ \displaystyle~1 $ rosso in un numero finito di passaggi arriviamo a un $ \displaystyle~z\in M $ con $ \displaystyle~f(z)\le 1 $. Evidentemente $ \displaystyle~z=m $. A questo punto sia $ \displaystyle~N $ l'insieme di elementi non rossi e supponiamo per assurdo che non sia vuoto. Prendiamo un $ \displaystyle~t\in N $ tale che $ \displaystyle~f(t)\le f(u)~\forall u\in N $. Per la (**) $ \displaystyle~f(t)\le 1 $, dunque di nuovo $ \displaystyle~t=m $, ma $ \displaystyle~m $ è rosso, assurdo.
Dimostrazione della proposizione (*):
Supponiamo $ \displaystyle~x=am+bn=a'm+b'n\in M $ per due coppie distinte $ \displaystyle~(a,b) $ e $ \displaystyle~(a',b') $ con $ \displaystyle~|a|+|b|=|a'|+|b'|=f(x) $. Ora ovviamente $ \displaystyle~a>0\Leftrightarrow b\le 0 $ e $ \displaystyle~b>0\Leftrightarrow a\le 0 $ (essendo $ \displaystyle~0<x<n $). Segue $ \displaystyle~|a|+|b|=|a-b| $. Altrettanto vale ovviamente per $ \displaystyle~a' $ e $ \displaystyle~b' $. Ora da $ \displaystyle~am+bn=a'm+b'n $ segue $ \displaystyle~n\mid am-a'm $, cioè $ \displaystyle~a-a'=jn $ e $ \displaystyle~b-b'=km $. Sostituendo otteniamo $ \displaystyle~j=-k $, cioè $ \displaystyle~a'=a+kn $ e $ \displaystyle~b'=b-km $. Essendo $ \displaystyle~|a-b|=|a'-b'|=|a-b+k(m+n)| $ e $ \displaystyle~k\neq 0 $, deve valere $ \displaystyle~a-b+k(m+n)=-(a-b) $, da cui $ \displaystyle~m+n\mid a-b $. Dunque $ \displaystyle~m+n\le |a-b| $ (essendo $ \displaystyle~a-b\neq 0 $), da cui due casi:
- $ \displaystyle~a-b>0 $, da cui $ \displaystyle~b\le 0\le a $ e $ \displaystyle~a-b\ge m+n $. Dunque $ \displaystyle~an-bn>n(m+n) $, che sommato a $ \displaystyle~am+bn>0 $ dà $ \displaystyle~a(m+n)>n(m+n) $, ovvero $ \displaystyle~a>n $. Inoltre otteniamo anche $ \displaystyle~bm-am<-m(m+n) $, che sommato a $ \displaystyle~am+bn<n $ dà $ \displaystyle~b(m+n)<-m(m+n)+n<-m(m+n)+(m+n) $. Quindi $ \displaystyle~b<-m+1 $, cioè $ \displaystyle~b\le -m $. Segue che $ \displaystyle~b<b+m\le 0 $ e $ \displaystyle~0<a-n<a $, da cui $ \displaystyle~f(x)=f((a-n)m+(b+m)n)\le |a-n|+|b+m|<|a|+|b| $, assurdo.
- $ \displaystyle~b-a>0 $, da cui $ \displaystyle~a\le 0\le b $ e $ \displaystyle~b-a\ge m+n $. Dunque $ \displaystyle~an-bn<-n(m+n) $, che sommato a $ \displaystyle~am+bn<n $ dà $ \displaystyle~a(m+n)<-n(m+n)+n<-n(m+n)+(m+n) $. Quindi $ \displaystyle~a<-n+1 $, cioè $ \displaystyle~a\le -n $. Inoltre otteniamo anche $ \displaystyle~bm-am>m(m+n) $, che sommato a $ \displaystyle~am+bn>0 $ dà $ \displaystyle~b(m+n)>m(m+n) $, ovvero $ \displaystyle~b>m $. Segue che $ \displaystyle~a<a+n\le 0 $ e $ \displaystyle~0<b-m<b $, da cui $ \displaystyle~f(x)=f((a+n)m+(b-m)n)\le |a+n|+|b-m|<|a|+|b| $, assurdo.
Te come l'hai risolto?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Premetto di non aver letto quella di kn perchè dovrei uscire a momenti..
m e n-m hanno lo stesso colore, e se 0<x<m allora (x,m-x,n-m+x) hanno lo stesso colore, quindi in Z/nZ tutti gli -m-km sono dello stesso colore per k intero, ma {-m-km} è un sistema completo di residui (non nulli per k=0,1,...,n-2). []
[Edit: dario cosi come l'hai scritta la tua soluzione prenderebbe credo un 5 punti, visto che {1-an} è si un sistema completo di residui, ma non deve contenere lo 0]
m e n-m hanno lo stesso colore, e se 0<x<m allora (x,m-x,n-m+x) hanno lo stesso colore, quindi in Z/nZ tutti gli -m-km sono dello stesso colore per k intero, ma {-m-km} è un sistema completo di residui (non nulli per k=0,1,...,n-2). []
[Edit: dario cosi come l'hai scritta la tua soluzione prenderebbe credo un 5 punti, visto che {1-an} è si un sistema completo di residui, ma non deve contenere lo 0]
Ultima modifica di jordan il 29 nov 2009, 15:36, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Uhm... mi pare giusto, solo che nel terzo caso dai per scontato $ $x\not=m $ si risolve in un attimo comunque ;) (forse mi sono perso il pezzo dove analizzavi questo caso)
La mia soluzione è completamente diversa :)
Alur... se x è di un colore allora tutti gli $ $y\equiv x\pmod{m} $ sono dello stesso colore.
Si dimostra partendo dal massimo $ $y\in M $ che sia congruo a x, poi si nota che anche y-am è dello stesso colore (purchè sia positivo) quindi ho il lemma.
Chiamo f(x) la funzione che manda $ $x\le m $ in $ $a\le m $ e tale che $ $a\equiv n-x\pmod{m} $. È facile notare che x,f(x) sono dello stesso colore (si sfrutta il lemma precedente e la proprietà i,n-i dello stesso colore).
Ora chiamo g(x) la funzione che manda $ $x\le m $ in $ $a\le m $ con $ $a\equiv -x\pmod{m} $. È facile notare che x,g(x) sono dello stesso colore (si sfrutta il lemma precedente e la proprietà i,m-i dello stesso colore)
Definisco $ $k(x):=g(f(x)) $
Noto che k(x) è dello stesso colore di x e inoltre $ $k(x)\equiv x-n\pmod{m} $.
In particolare $ $k^a(x)\equiv x-an\pmod{m} $ ed è sempre dello stesso colore. Fisso x=1 da cui ottengo che tutti gli $ $x\equiv 1-an\pmod{n} $ sono rossi. Ma essendo m,n coprimi 1-an assume qualsiasi valore modulo m... che è la tesi.
La mia soluzione è completamente diversa :)
Alur... se x è di un colore allora tutti gli $ $y\equiv x\pmod{m} $ sono dello stesso colore.
Si dimostra partendo dal massimo $ $y\in M $ che sia congruo a x, poi si nota che anche y-am è dello stesso colore (purchè sia positivo) quindi ho il lemma.
Chiamo f(x) la funzione che manda $ $x\le m $ in $ $a\le m $ e tale che $ $a\equiv n-x\pmod{m} $. È facile notare che x,f(x) sono dello stesso colore (si sfrutta il lemma precedente e la proprietà i,n-i dello stesso colore).
Ora chiamo g(x) la funzione che manda $ $x\le m $ in $ $a\le m $ con $ $a\equiv -x\pmod{m} $. È facile notare che x,g(x) sono dello stesso colore (si sfrutta il lemma precedente e la proprietà i,m-i dello stesso colore)
Definisco $ $k(x):=g(f(x)) $
Noto che k(x) è dello stesso colore di x e inoltre $ $k(x)\equiv x-n\pmod{m} $.
In particolare $ $k^a(x)\equiv x-an\pmod{m} $ ed è sempre dello stesso colore. Fisso x=1 da cui ottengo che tutti gli $ $x\equiv 1-an\pmod{n} $ sono rossi. Ma essendo m,n coprimi 1-an assume qualsiasi valore modulo m... 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
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