Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
tenaciousR
Messaggi: 23
Iscritto il: 30 mar 2010, 13:16

Messaggio da tenaciousR » 31 mar 2010, 14: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?
Better Dead Than Normal

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 » 31 mar 2010, 14:24

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.

tenaciousR
Messaggi: 23
Iscritto il: 30 mar 2010, 13:16

Messaggio da tenaciousR » 31 mar 2010, 14:25

mi sono iscritto ieri chi lo sapeva?scusa.
Better Dead Than Normal

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 31 mar 2010, 15:09

Benvenuto nel forum. La prossima datti una letta almeno ai primi post dei thread in cui posti.. Aspettiamo dario2994 per il problema62.
The only goal of science is the honor of the human spirit.

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

Messaggio da dario2994 » 31 mar 2010, 17:34

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) $
...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

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 31 mar 2010, 18:03

Mi sa che non ci hai pensato molto :o
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.

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

Messaggio da dario2994 » 31 mar 2010, 18:07

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

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 31 mar 2010, 18:19

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. []
Ah, scusami ^^
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.

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

Messaggio da dario2994 » 31 mar 2010, 19:33

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.
...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

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 31 mar 2010, 20:12

dario2994 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)} $
???
Sì, è una generalizzazione di questo lemma
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 :wink:

Sono curioso di vedere cosa proporrà jordan :twisted:
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)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 31 mar 2010, 20:13

Ho editato l'ipotesi del corollario2, kn ha fatto gentilmente il resto :)
The only goal of science is the honor of the human spirit.

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 01 apr 2010, 14:38

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} $
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 $.
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)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 01 apr 2010, 15:49

Sperando che sia tutto giusto..

Problema 64. Sia S(n) la somma delle cifre di un intero positivo n. Quanto vale al massimo $ \displaystyle~\frac{S(n)}{S(16n)} $?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 01 apr 2010, 19:05

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.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 01 apr 2010, 19:12

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.

Rispondi