Staffetta tdn
-
- Messaggi: 23
- Iscritto il: 30 mar 2010, 13:16
Questo è un po' più facile
Una gallina ha 20 anni.Da quando aveva due anni fa una figlia all'anno.Da quell'anno ha iniziato a fare un uovo al giorno il primo anno,2 uova al giorno il secondo,3uova al giorno il terzo,4 uova al giorno il quarto e così via,tranne il 29 febbraio,in cui si riposa.tutte le sue figlie si comportano allo stesso identico modo.Sapendo che nessuna gallina è morta,quante uova hanno fatto negli ultimi 20 anni la gallina e le sue figlie?
Una gallina ha 20 anni.Da quando aveva due anni fa una figlia all'anno.Da quell'anno ha iniziato a fare un uovo al giorno il primo anno,2 uova al giorno il secondo,3uova al giorno il terzo,4 uova al giorno il quarto e così via,tranne il 29 febbraio,in cui si riposa.tutte le sue figlie si comportano allo stesso identico modo.Sapendo che nessuna gallina è morta,quante uova hanno fatto negli ultimi 20 anni la gallina e le sue figlie?
Better Dead Than Normal
tenaciousR, il diritto di postare un problema nella staffetta spetta a chi a risolto l'ultimo postato, e in ogni caso il tuo problema mi sembra più adatto alla sezione Combinatoria.
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.
-
- Messaggi: 23
- Iscritto il: 30 mar 2010, 13:16
Uhm... oddio. Gia la staffetta di combinatoria è ad un livello scabrosamente basso, quella di algebra sta peggiorando (io non sapevo dell'esistenza di nessuna delle 2 fino a ieri...) almeno Tdn salviamola.
Posto un problema che mi è stato proposto oggi, c'ho pensato solo mentalmente quindi non posso assicurare di avere la soluzione, ma comunque è facilotto e confido in voi per la soluzione.
Dimostrare che dati $ $a,b\in\mathbb{N}^2_* $ vale:
$ $a|\varphi(b^a-1) $
Posto un problema che mi è stato proposto oggi, c'ho pensato solo mentalmente quindi non posso assicurare di avere la soluzione, ma comunque è facilotto e confido in voi per la soluzione.
Dimostrare che dati $ $a,b\in\mathbb{N}^2_* $ vale:
$ $a|\varphi(b^a-1) $
...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
Mi sa che non ci hai pensato molto
Soluzione problema 62. $ b^a-1\mid b^{\varphi(b^a-1)}-1 $ e dal momento che $ \text{gcd}(x^m-1,x^n-1)=x^{\text{gcd}(m,n)}-1 $, abbiamo la tesi. []
Problema63. Mostrare che se $ p\in \mathbb{P}\cap (n,\frac{4}{3}n] $, dove n>0 è un intero, allora $ \displaystyle p\mid \sum_{0\le i\le n}{\binom{n}{i}^4} $
Soluzione problema 62. $ b^a-1\mid b^{\varphi(b^a-1)}-1 $ e dal momento che $ \text{gcd}(x^m-1,x^n-1)=x^{\text{gcd}(m,n)}-1 $, abbiamo la tesi. []
Problema63. Mostrare che se $ p\in \mathbb{P}\cap (n,\frac{4}{3}n] $, dove n>0 è un intero, allora $ \displaystyle p\mid \sum_{0\le i\le n}{\binom{n}{i}^4} $
The only goal of science is the honor of the human spirit.
Jordan... non ho capito la tua soluzione xD più che altro non ho capito come quello implichi la tesi xD
...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
Ah, scusami ^^jordan ha scritto:Soluzione problema 62. $ b^a-1\mid b^{\varphi(b^a-1)}-1 $ e dal momento che $ \text{gcd}(x^m-1,x^n-1)=x^{\text{gcd}(m,n)}-1 $, abbiamo la tesi. []
Allora sai che $ b^a-1=\text{gcd}(b^a-1,b^{\varphi(b^a-1)}-1)=b^{\text{gcd}(a,\varphi(b^a-1)}-1 $ per cui $ \text{gcd}(a,\varphi(b^a-1))=a $ cioè $ a\mid \varphi(b^a-1) $.
Corollario1: con lo stesso metodo se $ c\in\{x\in \mathbb{N}\cap [1,b]:\text{gcd}(x,b)=1\} $ allora $ a\mid \varphi(b^a-c^a) $.
Corollario 2: sotto gli stessi vincoli precedenti, e con l'aggiunta della condizione sufficiente $ \text{gcd}(a,b-c)=\text{gcd}(a,\varphi(b-c))=1 $ vale $ \displaystyle a\mid \varphi(\sum_{0\le i\le a-1}{b^ic^{a-i-1}}) $. (editata l'ipotesi).
Ultima modifica di jordan il 31 mar 2010, 20:14, modificato 2 volte in totale.
The only goal of science is the honor of the human spirit.
Wow Metodo figo, non conoscevo neppure il lemma...
Ma il lemma si può generalizzare a
$ $gcd(a^x-b^x,a^y-b^y)=a^{gcd(x,y)}-b^{gcd(x,y)} $
???
Se si ho mostrato il corollario 1:
$ $b^a-c^a=gcd(b^a-c^a,b^{\varphi(b^a-c^a)}-c^{\varphi(b^a-c^a)})=b^{gcd(a,\varphi(b^a-c^a))}-c^{gcd(a,\varphi(b^a-c^a))} $
In caso la congettura che ho fatto sia vera, mi puoi linkare una dimostrazione
Nel secondo corollario nell'esponente della c compare n... presumo fosse a.
Ma il lemma si può generalizzare a
$ $gcd(a^x-b^x,a^y-b^y)=a^{gcd(x,y)}-b^{gcd(x,y)} $
???
Se si ho mostrato il corollario 1:
$ $b^a-c^a=gcd(b^a-c^a,b^{\varphi(b^a-c^a)}-c^{\varphi(b^a-c^a)})=b^{gcd(a,\varphi(b^a-c^a))}-c^{gcd(a,\varphi(b^a-c^a))} $
In caso la congettura che ho fatto sia vera, mi puoi linkare una dimostrazione
Nel secondo corollario nell'esponente della c compare n... presumo fosse a.
...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
Sì, è una generalizzazione di questo lemmadario2994 ha scritto:Ma il lemma si può generalizzare a
$ $gcd(a^x-b^x,a^y-b^y)=a^{gcd(x,y)}-b^{gcd(x,y)} $
???
Se un d divide il gcd, allora puoi dire che è coprimo con a e b e a questo punto ottieni
$ \displaystyle~a^x\equiv b^x\pmod d $ e $ \displaystyle~a^y\equiv b^y\pmod d $
o anche $ \displaystyle~(ab^{-1})^x\equiv 1\pmod d $ e $ \displaystyle~(ab^{-1})^y\equiv 1\pmod d $ (l'inverso di b esiste perché b è coprimo con d).
Quindi $ \displaystyle~ord_d(ab^{-1})\mid (x,y) $, che è la tesi
Sono curioso di vedere cosa proporrà jordan
Ultima modifica di kn il 31 mar 2010, 20:14, modificato 1 volta in totale.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Lemma: Se $ \displaystyle~ak<p-1 $ con $ \displaystyle~a\in\mathbb{N},\ k\in\mathbb{N}_0 $ e p primo, allora $ \displaystyle~p\mid\sum_{i=0}^{p-1}\binom{a+i}{a}^k $.jordan ha scritto:Problema63. Mostrare che se $ p\in \mathbb{P}\cap (n,\frac{4}{3}n] $, dove n>0 è un intero, allora $ \displaystyle p\mid \sum_{0\le i\le n}{\binom{n}{i}^4} $
Essendo $ \displaystyle~a<p $, la tesi è equivalente a $ \displaystyle~\sum_{i=0}^{p-1}a!^k\binom{a+i}{a}\equiv0\pmod p $.
Ma $ \displaystyle~a!^k\binom{a+i}{a}^k=[(i+a)(i+a-1)\cdots(i+1)]^k $ è un polinomio $ \displaystyle~P(i) $ di grado ak. Se $ \displaystyle~P(t)=b_{ak}t^{ak}+b_{ak-1}t^{ak-1}+\ldots+b_0 $, la tesi diviene $ \displaystyle~\sum_{j=0}^{ak}b_j\sum_{i=0}^{p-1}i^j\equiv0\pmod p $. La tesi segue dal fatto che $ \displaystyle~\sum_{i=0}^{p-1}i^j~\forall j $, essendo $ \displaystyle~j<p-1 $ (v. qui).
Soluzione problema 63. A questo punto basta fare in modo che i binomiali nel testo abbiano la parte sotto (come si chiama?) costante:
per ogni $ \displaystyle~i<p $ $ \displaystyle~\binom{n}{i}\equiv n(n-1)\cdots(n-i+1)i!^{-1} $$ \displaystyle~\equiv(-1)^i(p-n)(p-n+1)\cdots(p-n+i-1)i!^{-1}\equiv(-1)^i\binom{p-n-1+i}{i} $$ \displaystyle~\equiv(-1)^i\binom{p-n-1+i}{p-n-1}\pmod p $
La tesi diviene $ \displaystyle~p\mid\sum_{i=0}^n\binom{p-n-1+i}{p-n-1}^4=\sum_{i=0}^{p-1}\binom{p-n-1+i}{p-n-1}^4 $, e ciò segue dal lemma essendo $ \displaystyle~4(p-n-1)<p-1 $ per ipotesi.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Soluzione problema 64. Per ogni x,y interi positivi vale $ s(x)+s(y)\ge s(x+y) $. In particolare se $ \overline{b_kb_{k-1}\ldots b_1b_0} $ è la rappresentazione decimale di un intero positivo $ a $ allora $ \displaystyle s(ax)=s\left(\sum_{0\le i\le k}{10^ib_ix}\right)\le \sum_{0\le i\le k}{s(10^ib_ix)} $ $ \displaystyle =\sum_{0\le i\le k}{s(b_ix)}\le s(x)\sum_{0\le i\le k}{b_i}=s(x)s(a) $. Sia $ \alpha:=\max\{\frac{s(i)}{s(2^4i)}\} $ per ogni $ i \in \mathbb{N}_0 $ (sempre se è possibile definirlo). Adesso abbiamo $ \alpha \ge \frac{s(5^4)}{s(10^4)}=13 $. D'altra parte per quanto detto prima vale $ s(n)=s(10^4n)\le s(5^4)s(2^4n)=13s(16n) $, per cui abbiamo vale $ \alpha $ esiste e vale esattamente $ 13 $. []
The only goal of science is the honor of the human spirit.
Problema 65. Own. Per ogni intero positivo n sia $ \pi(n) $ il numero di primi minori o uguali a n, $ \sigma_0(n) $ il numero dei divisori di n e $ s(n) $ la somma delle cifre di n. Siano fissati a,b,c interi positivi e tre polinomi non costanti p(x),q(x),r(x) a coefficienti non negativi. Mostrare che l'equazione $ \displaystyle \pi^a(p(n))= s^b(q(n))+\sigma_0^c(r(n)) $ ammette solo un numero finito di soluzioni.
The only goal of science is the honor of the human spirit.