Staffetta tdn

[tenaciousR]

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?

[amatrix92]

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.

[tenaciousR]

mi sono iscritto ieri chi lo sapeva?scusa.

[jordan]

Benvenuto nel forum. La prossima datti una letta almeno ai primi post dei thread in cui posti.. Aspettiamo dario2994 per il problema62.

[dario2994]

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

[jordan]

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

[dario2994]

Jordan... non ho capito la tua soluzione xD più che altro non ho capito come quello implichi la tesi xD

[jordan]

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

[dario2994]

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.

[kn]

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

Sono curioso di vedere cosa proporrà jordan

[jordan]

Ho editato l'ipotesi del corollario2, kn ha fatto gentilmente il resto

[kn]

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.

[kn]

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

[jordan]

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 $. []

[jordan]

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.