OliForum Matematico

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?

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.

mi sono iscritto ieri chi lo sapeva?scusa.

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

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

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

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

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

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.

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

Sono curioso di vedere cosa proporrà jordan

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

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.

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

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

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.