Staffetta tdn

[jordan]

Problema 91. Fissato un intero $ n>2 $ quante radici intere ha il polinomio $ p(x):=n!x^n+(n^2+n+1)x^{n-1}-(n!+1)x+(2n)!+3 $?[/quote]

[jordan]

Risposta qui:

Essendo $ n! $ pari, $ n^2+n+1 $ dispari, $ n!+1 $ dispari, $ (2n)! $ pari, $ 3 $ dispari, x dispari non va bene; ma osservando nemmeno x pari va bene.
Quindi non ci sono soluzioni intere.

[Anér]

Da qui il problema 92

Trovare le soluzioni intere positive:
$ x^y=y^{17}-1 $
(senza usare Mihailescu)

e la sua soluzione

$ x^y=y^{17}-1 $

Ragiono mod 4.

1)$ y\equiv 0 $-->$ y^{17}-1\equiv -1 $ e y è pari, ma allora x elevato a un numero pari non potrebbe mai essere congruo a -1.
2)$ y\equiv 1 $-->$ y^{17}-1\equiv 0 $ . Lo analizzo sotto.
3)$ y\equiv 2 $-->$ y^{17}-1\equiv -1 $---> impossibile, per lo stesso motivo del caso 1)
4)$ y\equiv 3 $-->$ y^{17}-1\equiv 2 $---> Vuol dire che $ x $ è pari, e divisibile per al massimo 2. Questo è valido solo per $ x\equiv 2 $ e $ y=1 $, che dà come unica soluzione $ (0,1) $

Analizzo il caso 2):
$ y^{17} \equiv 1 \mod 4 $ e $ x\equiv 0 \mod 4 $. Allora $ x=2k $ con k intero (per y>1) e riscrivo l'equazione come:

$ 2^y*k^y=(y-1)(y^{16}+y^{15}+y^{14}....+y+1) $. (con y>1)

chiamo $ (y^{16}+y^{15}+y^{14}....+y+1)=M $. Se analizzo M mod 4, tenendo conto che $ y\equiv 1 $, ottengo che $ M\equiv y\equiv 1 \mod 4 $.
Ma allora per forza $ 2^y|(y-1) $ e ciò non accade per nessuna $ y>1 $.

Mi rimane da analizzare il caso per y=1, che mi dà per prova diretta la soluzione (0,1).



L'unica soluzione SAREBBE quindi $ (0,1) $, ma siccome il problema chiede soluzioni intere positive, non ci sono soluzioni.

Qui invece sta il problema 93

Problema 93. Dimostrare che la frazione $ \frac {21n+4}{14n+3} $ è irriducibile per ogni numero naturale $ n $.

[jordan]

Soluzione problema 93:

, quando si fa le cose di fretta. Provo a farmi perdonare: nella soluzione uso più volte il fatto : $ gcd( n ; m ) = gcd ( n-am ; m ) $ con a intero.

$ gcd(21n+4 ; 14n+3) = gcd ( 21n+4 -1(14n+3) ; 14 n +3 ) = gcd ( 7n+1 ; 14n+3 ) = gcd (7n+1 ; 14n+3 -(7n+1))= $

$ = gcd (7n+1 ; 7n+2 ) = gcd ( 7n+1 ; 1 ) = 1 $

Problema 94 da qui

Trovare tutti gli interi non negativi $ p $ , $ q $ ,$ m $ e $ n $ tali che

$ \displaystyle p^{m}q^{n}= (p+q)^{2}+1 $

[jordan]

La soluzione problema 94 è stata postata qui: Problem 18. A equation in 4 non negative integers.

Problema 95 da qui:

Una generalizzazione di questa:

Problema 95 (own).
Per ogni intero $n>1$ definiamo $S(n):=\{r\in \mathbb{Z}: 2\le r\le n\text{ and }x^r-y^x=1 \text{ has no solutions in integers >1}\}$.

Dimostrare che se $n$ è sufficientemente grande allora $\displaystyle |S(n)|\ge \frac{999}{1000}n$.

[Anér]

Da qui la soluzione del problema 95:

La prima considerazione da fare è che $ 3^2-2^3=1 $, per cui 2 non appartiene a S(n), e perciò $ |S(n)|\leq n-2 $.
Vogliamo dimostrare ora che ogni altro r va bene, ossia |S(n)|=n-2.
Per assurdo abbiamo $ x^r-y^x=1 $; allora x e y hanno parità diversa e con x pari e y dispar si avrebbe un assurdo modulo 4. Dunque x è dispari e y è pari.
Ora scrivo come $ x^r=y^x+1 $. Sia p il più grande primo che divide x, e sia x=kp. Allora
$ y^x+1=(y^k)^p+1=(y^k+1)(\sum_{i=0}^{p-1} (-1)^i y^{ki}) $. Come tutti i primi del secondo fattore della scomposizione sono congrui a 1 modulo p, eccetto al più il fattore p stesso che però può comparire solo con molteplicità 1. Ma fattori congrui a 1 modulo p non sono ammissibili, perché sono maggiori di p, e quindi $ (\sum_{i=0}^{p-1} (-1)^i y^{ki}) $ può valere solo 1 oppure p. Supponiamo ora $ p\geq 5 $. Allora posso scrivere $ (\sum_{i=0}^{p-1} (-1)^i y^{ki})=y^{k(p-1)}-y^{k(p-2)}+\sum_{i=0}^{p-3} (-1)^iy^{ki}\geq (y^k-1)(y^{k(p-2)})\geq 2^{p-2}> p $, assurdo (la prima disuguaglianza è vera perché la sommatoria ha termini a segno alterno e il primo vale 1, poi ogni negativo è battuto dal positivo successivo).
Ne deriva che p=3, ossia x è una potenza di 3 perché è dispari. Se poi consideriamo che $ y^{2k}-y^k+1>3 $ se $ y^k>2 $, otteniamo $ y^k=2 $, ossia y=2 e k=1, per cui x=3. Da qui otteniamo $ 3^r-2^3=1 $ che non ha soluzioni per r>2.

Da qui il problema 96:

Dato un polinomio p(x) a coefficienti interi dimostrare che esiste un polinomio q(x) a coefficienti interi tale che p(q(x)) sia scomponibile nei polinomi a coefficienti interi.

[jordan]

Soluzione al problema 96(da qui):

Dato che nessuno continua la staffetta, provo io.. Allora, scelgo $q(x)=p(x)^2+x$. È ovviamente a coefficienti interi. Inoltre
$$p(p(x)^2+x)\equiv p(0+x)\equiv 0 \pmod {p(x)}$$
Spiego meglio quest'ultimo passaggio: se $p(x)=\sum a_i x^i$ allora
$$p(p(x)^2+x)=\sum a_i (p(x)^2+x)^i= r(x)p(x) + \sum a_i x^i = r(x)p(x) +p(x) = [r(x)+1]p(x)$$
Dove $r(x)$ è un opportuno polinomio a coefficienti interi. Ho trovato quindi che $p(x)$ ( che è a coefficienti interi) divide $p(q(x))$ e il grado è strettamente minore (ammesso che il grado di $p$ sia almeno 1). Infatti per $p(x)=3$ non funziona né la dimostrazione né la tesi

[jordan]

Testo problema 97 (da qui):

Sia $p$ un primo e $n$ un intero tali che $p\ge n>3$. Sia $S$ l'insieme delle funzioni da $\{1,2,...,n\}$ a $\{1,2,...,p\}$. Sia $A\subseteq S$ con la seguente proprietà: per ogni coppia di funzioni $f,g$ in $A$, esistono almeno tre $i\in\{1,2,...,n\}$ tali che $f(i)\neq g(i)$. Quanti elementi contiene al massimo $A$?

Soluzione 1:

Piazzo la mia soluzione, poi Cucciolo piazzerà la sua (ci siamo messi d'accordo così).
$p^{n-2}$ funzioni si fanno: prendiamo tutte quelle che soddisfano il seguente sistema di congruenze:
$\sum_{i=1}^n f(i)\equiv 0 \pmod{p}$
$\sum_{i=1}^n i\cdot f(i)\equiv 0\pmod{p}$
Queste sono tante quanti i modi di scegliere f(1), f(2), ... f(n-2) a piacere, perché gli ultimi due valori sono determinati dal sistema che diventa di due equazioni e due incognite e con determinante diverso da 0 modulo p. Inoltre se due funzioni del gruppo coincidono in n-2 punti allora sono la stessa per lo stesso motivo, ossia perché gli ultimi due valori devono essere quelli che soddisfano il sistema di due equazioni e due incognite che si crea imponendo gli n-2 valori che sappiamo essere uguali. Ancora una volta il determinante non può mai essere nullo, perché il determinante è quello di una delle sottomatrici 2 per 2 della seguente:
1 1 1 1 ... 1
1 2 3 4 ... n

Se poi avessimo $p^{n-2}+1$ funzioni reciprocamente compatibili, le divido nelle $p^{n-2}$ classi di equivalenza in base all'uguaglianza sui primi n-2 valori, ovvero metto nella stessa classe due funzioni f e g se e solo se f(1)=g(1), f(2)=g(2), ... , f(n-2)=g(n-2).
Per pigeonhole c'è una classe che contiene almeno $ \lfloor \frac{p^{n-2}+1}{p^{n-3}}\rfloor=2 $ funzioni, ma questo è assurdo perché due funzioni distinte non possono coincidere in n-2 valori, ovvero dovevamo sperare che ogni classe contenesse al più una funzione.
Quest'ultimo argomento si adatta anche al caso "funzioni diverse in almeno k punti", ma la prima parte no, non sono sicuro di poter trovare una matrice n per k tale che ogni sottomatrice k per k abbia determinante non nullo modulo p (anche se qualcosa mi dice che ci si può credere).

Soluzione 2:

Benissimo, per me puoi andare col prossimo problema. Per la prima parte io ho fatto diversamente:
Fatto: L'insieme delle funzioni da $\{1,2,...,n\} \rightarrow \{1,2,...,p\}$ è in bigezione con l'insieme dei polinomi a coefficienti in $\mathbb Z_p$ di grado $\le n-1$. Infatti per interpolazione c'è sempre uno e un solo polinomio di questo tipo tale che
$$\left\{ \begin{array}\\
P(1)=f(1)\\
P(2)=f(2)\\
...\\
P(n)=f(n)
\end{array}
\right .$$
e ovviamente ogni polinomio è una funzione.

Chiarito questo, se io prendo come insieme delle funzioni i polinomi di grado $\le n-k$, questi sono $p^{n-k+1}$ e due di loro non possono essere uguali in più di $n-k$ valori (per il grado) , ergo differiscono per almeno $k$ valori.

[jordan]

Testo problema 98 (da qui):

Dato un intero positivo $n=\prod_{i=1}^s p_i^{\alpha_i}$ chiamiamo $\Omega (n)$ il numero totale $\sum_{i=1}^s \alpha_i$ di fattori primi di $n$, contati con molteplicità. Sia $\lambda (n)=(-1)^{\Omega (n)}$ (dunque, per esempio, $\lambda (12)=\lambda (2^2\cdot 3^1)=(-1)^{2+1}=-1$).

Sia infine $S(m)=\sum_{i=1}^m \lambda (i)\cdot \lfloor\frac{m}{i}\rfloor$.

1) Si dimostri che $S(m)\geq 0$ per ogni $m$ intero positivo;
2) Sapete trovare una formula più semplice per $S(m)$?

[LukasEta]

Soluzione problema 98:

Sulla stessa strada..

Per ogni intero $ n>0 $ e primo $ q\in \mathbb{P} $ definiamo:

• $\lambda_q(n):=0$ se esiste $p\in \mathbb{P}$ tale che $q\nmid \upsilon_p^2(n)-\upsilon_p(n)$
  $\lambda_q(n):=1$ se $2\mid \left|\{p\in \mathbb{P}:\displaystyle \frac{\upsilon_p(n)-1}{q}\in \mathbb{Z}\} \right|$
  $\lambda_q(n):=-1$ se $2\nmid \left|\{p\in \mathbb{P}:\displaystyle \frac{\upsilon_p(n)-1}{q}\in \mathbb{Z}\} \right|$

Definita $\displaystyle S(m):=\sum_{1\le i\le m}{\lambda_q(i)\lfloor \frac{m}{i}\rfloor}$, allora vale $S(m)=\lfloor \sqrt[q]{m} \rfloor$.

Problema 99 da qui:

Detto fatto, e in breve tempo

Sia $p(x)= a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0$ un polinomio di grado $n$ a coefficienti razionali, ossia con $a_n,a_{n−1},...,a_1,a_0 \in \mathbb Q$.
Sapendo che esiste un certo $m_0 \in \mathbb N$ tale che per ogni $m \in \mathbb N$, $m>m_0$, $p(m)$ è intero, dimostrare che $n!a_n \in \mathbb N$.

[LukasEta]

Soluzione problema 99:

Bon... dopo una "lunga assenza" rieccomi:
Sia $P(x)=P_0(x)$ e $P_{i+1}(x)=P_i(x+1)-P_i(x)$. Sia $D(R(x))$ il coefficiente direttivo di un polinomio R(x).
Vale abbastanza ovviamente $\forall 0\le i\le n\ deg(P_i(x))=n-i$ e anche $\forall 0\le i\le n\ D(P_{i+1}(x))=deg(P_i)\cdot D(P_i(x))$.
Unendo i 2 fatti è facile ricavare: $D(P_n(x))=n!a_n$ e $deg(P_n(x))=0$ da cui ottengo il meraviglioso $P_n(x)=n!a_n$.
Ma per la definizione questo è intero sempre se $P(x), P(x+1)\dots P(x+n)$ sono interi... basta quindi porre $x=m_0+1$ e ottenere $n!a_n=P_n(m_0+1)\in \mathbb{Z}$.
Perchè deve essere anche positivo? Beh perchè sennò definitivamente $P(x)$ sarebbe negativo (se lo è il suo coef direttivo) e ciò contraddirebbe le ipotesi di definitiva appartenenza ai naturali.

p.s. copiatissima da piever questa

Problema 100 da qui:

Esiste un $x_1\in\mathbb{Q}$ con $x_1>1$ tale che la sequenza definita da $x_{n+1}=x_n+\frac{1}{\lfloor x_n\rfloor}$ non ha neanche un elemento intero?

p.s. provate tutti è fattibile

[jordan]

Poniamo $m=\lfloor x_1\rfloor$. Sia $y_i$ il primo termine della successione tale che $\lfloor y_i\rfloor\ge m+i$, per ogni $i>0$.
È facile vedere che è proprio $\lfloor y_i\rfloor = m+i$ (per ogni $i$).
Quello che facciamo sulla frazione $x_1$ è aggiungerle tanti termini $\frac{1}{m}$ finché la sua parte intera non è aumentata. A quel punto le aggiungiamo tanti $\frac{1}{m+1}$ e così via.
Quando abbiamo aggiunto l'ultimo termine $\frac{1}{m}$, $x_1$ è diventato $y_1$, che ovviamente realizza $\{y_1\}<\frac{1}{m}\ (*)$. In generale $\{y_i\}<\frac{1}{m+i-1}$.
$y_2$ sarà $y_1$ più un certo numero $k$ di termini $\frac{1}{m+1}$. Quanto è $k$?
$k$ è il massimo numero tale che $\{y_1\}+\frac{k-1}{m+1}<1$ (cioè tale che $\lfloor y_1+\frac{k-1}{m+1}\rfloor=\lfloor y_1\rfloor$), ma essendo $\{y_1\}<\frac{1}{m}$ otteniamo $k\ge\frac{m^2+m-1}{m}$. Dunque $k=m-1$ oppure $k=m$.
Generalizzando, è $y_{i+1}=y_i+\frac{k_i}{m+i}$, con $k_i=m+i-1$ o $k_i=m_i$. Notiamo che $k_i=m+i-1$ sse $\{y_i\}\ge\frac{1}{m+i}$, mentre se è $\{y_i\}<\frac{1}{m+i}$ abbiamo $y_{i+1}=y_i+1$.
In conclusione la successione $\{y_1\},\{y_2\},\{y_3\},\ldots$ è debolmente decrescente e le variazioni ci sono quando a $\{y_i\}$ posso sottrarre $\frac{1}{m+i}$.
Se consideriamo $z=\{y_1\}$, i termini di quest'ultima successione (a meno di ripetizioni) si ottengono così:
prendiamo il più piccolo $m'>m$ tale che $z\ge\frac{1}{m'}$ e poniamo $z'=z-\frac{1}{m'}$. Osserviamo ora che il vincolo $m'>m$ è sempre verificato ($z<\frac{1}{m}$ per la $(*)$), dunque è proprio $m'=\left\lceil\frac{1}{z}\right\rceil$.
Inoltre è $z'<\frac{1}{m'}$: per mostrarlo basta ottenere $z<\frac{2}{\left\lceil\frac{1}{z}\right\rceil}$, che segue dalla disuguaglianza (verificabile a mano) $z<\frac{2}{\frac{1}{z}+1}$. Perciò trasformando $z\mapsto z',\ m\mapsto m'$ abbiamo di nuovo $z<\frac{1}{m}$ e possiamo ripetere l'algoritmo senza problemi. Come già detto i vari $z$ che otteniamo nei vari passi sono i termini della successione $\{y_1\},\{y_2\},\{y_3\},\ldots$.
Il numeratore di $z$ diminuisce sempre ogni volta che applichiamo l'algoritmo: infatti, se $z=\frac{a}{b}$ (con $a<b$), è $z'=\frac{m'a-b}{b}$, cioè il nuovo numeratore è al massimo $m'a-b$, ma $m'a-b<a$ (essendo $m'=\left\lceil\frac{b}{a}\right\rceil<1+\frac{b}{a}$).
Quindi prima o poi $z$ si annulla, cioè esiste un termine $y_i$ intero.

[jordan]

Problema 101 da qui:

Abbiamo un numero razionale $x=\frac{p}{q}$, con $p>q>0$ e $(p,q)=1$, e sappiamo che esiste un reale $\alpha$ tale che, per ogni $n\in\mathbb{N}$ sufficientemente grande, $|\{x^n\}-\alpha|\le\frac{1}{2(p+q)}$. Trovate tutti i possibili valori di $x$.

N.B.: $\{x\}$ indica la parte frazionaria di $x$; in altre parole, se $x\ge 0$ vale $\{x\}=x-\lfloor x\rfloor$

Ok, metto la soluzione (di piever):
Ogni $x$ intero positivo è valido. Supponiamo $q>1$. Per ogni $n$ abbastanza grande possiamo scrivere $x^n = a_n + \alpha + b_n$, con $a_n=\left\lfloor x^n\right\rfloor\in\mathbb{N}$ e $|b_n|\le \frac {1}{2(p + q)}$.
Il caso di uguaglianza $|\beta_n| = \frac {1}{2(p + q)}$ è possibile solo per un numero finito di $n$, quindi per $n$ sufficientemente grande $|\beta_n| < \frac {1}{2(p + q)}$.
Ora $a_n+\alpha+b_n=\frac{p}{q}(a_{n-1}+\alpha+b_{n-1})\Rightarrow qa_n-pa_{n-1}=(p-q)\alpha+pb_{n - 1}-qb_n$, dunque $(p-q)\alpha+pb_{n - 1}-qb_n$ è intero.
Per $n$ grande, per la disuguaglianza triangolare $pb_{n - 1}-qb_n<\frac{1}{2}$ quindi $(p-q)\alpha+pb_{n - 1}-qb_n$ è l'intero più vicino a $(p-q)\alpha$, che è unico e non dipende da $n$! Quindi se lo chiamiamo $c$ abbiamo che da un certo punto in poi $qa_n = pa_{n - 1} + c$.
Eliminiamo $c$ con il solito trucco: scrivendo $b_n = (p - q)a_n + c$ abbiamo $qb_n = pb_{n - 1}$, da cui $b_n=\frac{p}{q}b_{n-1}$, ma i termini di questa successione non possono essere interi oltre un certo $n$.

[jordan]

Problema 102 da qui:

Sia $b>5$ un intero. Sia $x_n$ il numero che in base $b$ si scrive come $\underbrace{11\cdots1}_{n - 1}\underbrace{22\cdots2}_{n}5$.
Allora $x_n$ è un quadrato perfetto per ogni $n$ sufficientemente grande sse $b=10$

Inizio scrivendo che $\underbrace{11\cdots1}_{n - 1}\underbrace{22\cdots2}_{n}5 = 3+\dfrac{b^{n+1}-1}{b-1}+\dfrac{b^{2n}-1}{b-1}$. Se $b=10$ è semplice verificare che $3+\dfrac{10^{n+1}-1}{9}+\dfrac{10^{2n}-1}{9} = \left(2+3\dfrac{10^n-1}{9}\right)^2$, e quindi se $b=10$, $x_n$ è un quadrato per ogni $n$ naturale, e una freccia è andata.

Ora faccio l'altra. Per ipotesi esiste un certo $M$ tale che per ogni $n\geq M$, allora $x_n$ è un quadrato. Voglio mostrare che allora $x_n$ è un quadrato anche con $n<M$. Per fare ciò, lavoro con i primi $p>max(M,b)$. Ora, per ipotesi so che, per ogni $1\leq k\leq M-1<p-1$, esiste un certo $n\geq M$, e $n \equiv k \pmod{p-1}$, tale che $x_n$ è un quadrato. Ma allora analizzando modulo $p$, si ha che $x_n \equiv 3+\dfrac{b^{n+1}-1}{b-1}+\dfrac{b^{2n}-1}{b-1} \equiv 3+\dfrac{b^{k+1}-1}{b-1}+\dfrac{b^{2k}-1}{b-1} \pmod p$. Quindi per tutti i $1 \leq i \leq M$, si ha che $x_i$ è un residuo quadratico modulo tutti i primi maggiori di $max(M,b)$.

A questo punto vorrei dimostrare che se un numero $a$ è residuo quadratico modulo tutti i primi maggiori di una certa costante, allora $a$ è un quadrato.
Suppongo che non lo sia: Sia $a=p_1^{a_1}\cdot p_2^{a_2}\cdot \dots p_n^{a_n}$ la sua fattorizzazione. Per la moltiplicatività del simbolo di Legendre dato un certo primo $q$ $\left(\dfrac{a}{q}\right) = \displaystyle\prod_{i=1}^n \left(\dfrac{p_i}{q}\right)^a_i$. Non essendo $a$ un quadrato, ci sarà sicuramente un $a_i$ dispari. Scelgo, allora, $q$ in modo che $\left(\dfrac{p_i}{q}\right) = -1$ e faccia $1$, invece, con tutti i $p_j$, con $j\neq i$ (questo lo posso fare con la reciprocità quadratica, ad esempio). Allora avrò che $\left(\dfrac{a}{q}\right)=-1$ per alcune condizioni $q \equiv k_1\pmod{p_1}\dots q\equiv k_n \pmod{p_n}$. Allora per il teorema cinese del resto, $q=A \pmod{\displaystyle\prod_{i=1}^n p_i}$ per una certa $A$ e siccome per Dirichlet esistono infiniti di questi $q$, ne esisteranno infiniti maggiori di una certa costante, e quindi assurdo, perché per questi primi $a$ non sarebbe residuo.

Ora so che $x_n$ è sempre un quadrato. Allora sia $p|b-1$ un primo. E' chiaro che $x_n \equiv 3n+4 \pmod p$ per ogni $n$. Ciò vuol dire che per ogni $n$, $3n+4$ è un residuo quadratico modulo $p$. Se $p=3$ siamo a posto, ma se $p\neq 3$, allora sicuramente $3n+4$ è un sistema completo di residui modulo $p$, quindi non può essere sempre residuo quadratico. Dunque $b=3^k+1$ per qualche $k$. [Continua nell'altro post]

Concludo (spero!): Dei fatti precedenti qui riutilizzo che $b=3^k+1$, e che sono tutti quadrati. Ora scelgo $p>b$, prendo $n \equiv -1 \pmod{p-1}$ e ho che $x_n \equiv 3 + \dfrac{b^{n+1}-1}{b-1} + \dfrac{b^{2n}-1}{b-1} \equiv 3 + \dfrac{\frac{1}{b^2}-1}{b-1} \equiv 3 - \dfrac{b^2-1}{b^2(b-1)} \equiv 3 - \dfrac{b+1}{b^2} \equiv x^2 \pmod p$ per qualche $x$. Allora posso moltiplicare per $b^2$ essendo invertibile e ottengo $3b^2-b-1 \equiv (bx)^2 \pmod p$. Quindi, $3b^2-b-1$ è quadrato per infiniti primi, e allora $3b^2-b-1$ è un quadrato per quanto detto prima. Ora sostituendo si ha $3(3^k+1)^2-(3^k+1)-1=3(3^{2k}+2\cdot 3^k +1) - 3^k - 2 = 3^{2k+1}+5\cdot 3^k + 1 = y^2$. Dunque $3^k(3^{k+1} + 5) = (y+1)(y-1)$. Siccome $\gcd(y+1,y-1)|2$, allora si possono avere due casi:
-Caso 1: $y+1=3^k\cdot t$ e $y-1=\dfrac{3^{k+1}+5}{t}$. Quindi $3^kt -2 = \dfrac{3^{k+1}+5}{t}$. Suppongo $t\geq 3$. Allora $3^kt-2 \geq 3^{k+1}-2$ e $\dfrac{3^{k+1}+5}{t} \leq 3^k + 2$. Quindi, grazie all'uguaglianza ottengo $3^{k+1}-2 \leq 3^k+2 \Leftrightarrow 2\cdot 3^k \leq 4$. Quindi $k=0$, che dà $b=2$, contro le ipotesi. Ora se $t=1$ si ha $3^k-2=3^{k+1}+5$ che non ha soluzione. Se $t=2$ si ha $4\cdot 3^k - 4 = 3^{k+1}+5$, ovvero $3^k=9$, che dà $b=10$, che funziona sempre.
-Caso 2: $y-1=3^k\cdot t$ e $y+1=\dfrac{3^{k+1}+5}{t}$. Quindi $3^k\cdot t + 2=\dfrac{3^{k+1}+5}{t}$. Se $t\geq 3$ come prima ho $3^k+2\geq 3^{k+1}+2$, assurdo. Rimangono i casi $t=1$, che non dà soluzioni, e $t=2$ che dà $4\cdot 3^k + 4 = 3^{k+1}+5$, da cui $k=0$ che dà $b=2$, assurdo per le ipotesi.

Spero sia chiaro (la parte in cui dimostro che tutti gli elementi della successione sono dei quadrati è un di più, perché $x_n \equiv 3n+4$ è anche un quadrato definitivamente, quindi non mi servono che tutti sia quadrati).

Spero sia corretta

[jordan]

Problema 103 da qui:

Scusate per il titolo, ma non sapevo che scrivere Ecco il problema della staffetta (non ne avevo di migliori e ho messo questo).

$\textbf{Problema 103}$:
Dato $n$ un numero naturale, sia $x=\left|\left\{0\leq k \leq n \mid \displaystyle\binom{n}{k} \equiv 1 \pmod 3\right\}\right|$ e $y=\left|\left\{0\leq k \leq n \mid \displaystyle\binom{n}{k} \equiv - 1 \pmod 3\right\}\right|$. Dimostrare che $x-y$ è una potenza di due (quale?).

Consideriamo il triangolo di Tartaglia e sostituiamo ogni numero con $0$ o $\pm 1$ a seconda del resto nella divisione per $3$. Chiamiamo $x_n$ e $y_n$ i numeri definiti come nel testo del problema in funzione di $n$: essi indicano rispettivamente quanti $+1$ e quanti $-1$ ci sono nella riga $n+1$. Si verifica facilmente che
$x_0-y_0=2^0$
$x_1-y_1=2^1$
$x_2-y_2=2^0$
Prima di procedere raggruppiamo i numeri in triangoli di lato $3$ (su ogni lato ci sono tre numeri) rivolti verso l'alto (per essere più chiaro: partendo dalle righe con $3k$ elementi facciamo $k$ gruppi di $3$ e procedendo verso l'alto costruiamo $k$ triangoli) e a ciascuno di essi assegniamo il numero che si trova sulla sua "punta": possiamo osservare che:
1) Questo raggruppamento esclude dei numeri che formano triangoli di lato $2$ rivolti verso il basso: essi sono tutti pari a $0$ (quindi non ci interessano per la risoluzione del problema)
2) Se a due triangoli è assegnato lo stesso numero, essi sono identici

Testo nascosto:

Lo possiamo dimostrare per induzione: diciamo per intenderci che i triangoli appartengono a degli strati di tre righe così come i singoli numeri appartengono alle singole righe e supponiamo che sotto ogni triangolo dello strato $n$ ce ne sia uno rivolto verso il basso contenente tre $0$. Chiamiamo $x$ un numero situato sulla punta di un triangolo dello strato $n+1$ e procediamo seguendo la classica regola della somma, ricordando l'ipotesi induttiva:
$0.....0.....x.....0.....0$
$...0...x....x.....0...$
$... .x....2x....x.....$
Sotto questo triangolo si troverà una coppia di $3x$ che essendo multipli di $3$ si possono sostituire con due $0$: ne segue immediatamente che è nullo anche il numero sottostante C.V.D.(1)
Inoltre, per quanto appena detto, se si conosce il numero in cima a un triangolo, esso risulta univocamente determinato (C.V.D.(2)), perciò si avrà:

Triangolo $"\pm 1"...........$Triangolo $"0"$:
$.......\pm 1.................................0$
$....\pm 1....\pm 1.......................0.......0$
$.\pm 1...\mp 1....\pm 1..............0.......0.......0$

3) I triangoli si possono "sommare" come i singoli numeri (nel senso che se a ogni triangolo si sostituisce il numero a esso assegnato, ignorando quelli del punto (1), si ottiene un nuovo triangolo di Tartaglia identico a quello iniziale)

Testo nascosto:

Come visto in precedenza, in ogni triangolo i numeri sui tre vertici sono uguali tra loro, perciò, se abbiamo due triangoli $"x"$ e $"y"$ affiancati, $x$ e $y$ sono anche i numeri che si trovano sul vertice in comune (ricordando che stiamo parlando di congruenze modulo $3$), pertanto, sulla punta del triangolo sottostante, c'è il numero $x+y$, che "dà il nome" al triangolo stesso

A questo punto ragioniamo per induzione: supponiamo che per un certo $n$ si abbia $x_i-y_i=2^k$ con $k$ naturale $\forall 0 \le i \le 3n-1$ e dimostriamo che lo stesso vale per $n+1$, ovvero per le tre righe successive:

- la riga $3n+1$ contiene le "punte" dei triangoli di lato $3$ (tutti gli altri numeri sono nulli per la (1)): per la (3), "saltando" da una punta all'altra troviamo la stessa sequenza che si avrebbe leggendo normalmente la riga $n+1$, per cui $x_{3n}-y_{3n}=x_n-y_n=2^k$ per ipotesi induttiva;

- come abbiamo visto nella dimostrazione della (2), i due numeri situati al "secondo piano" di un triangolo sono uguali a quello in cima, quindi $x_{3n+1}-y_{3n+1}=2x_{3n}-2y_{3n}=2 \cdot 2^k=2^{k+1}$;

- analogamente, alla base di un triangolo $"x"$ ci sono due $x$ e un $-x$: se in ognuna eliminiamo due numeri opposti la differenza rimane invariata e a ogni base rimane un solo numero, uguale a quello sulla cima del triangolo corrispondente, da cui ricaviamo $x_{3n+2}-y_{3n+2}=x_{3n}-y_{3n}=2^k$

Spero che sia corretta ma soprattutto comprensibile...