Staffetta tdn

[Nabir Albar]

Provo io, ispirato dall'avatar di PubTusi
Con una cosa del tipo $ \sum^* $ indicherò che la somma riguarda solo i dispari.

Conto. $ 1^2+3^2+\ldots+(2n-1)^2=\frac{n(2n+1)(2n-1)}{3} $
Infatti $ 1^2+2^2+\ldots+(2n-1)^2+(2n)^2=\frac{(2n)(2n+1)(4n+1)}{6}\ \ (A) $, mentre $ 1^2+2^2+\ldots+(n-1)^2+n^2=\frac{n(n+1)(2n+1)}{6}\ \ (B) $. $ 4\cdot(B) $ dà la somma dei quadrati dei pari, dunque $ (A)-4\cdot(B) $ dà la tesi.

Lemma. Sia $ x=2^{n+1}(2^{n+1}-1)\cdots(2^n+1) $. Allora $ \frac{x}{2^{\upsilon_2(x)}}=(2^{n+1}-1)!! $.
Infatti stiamo privando $ x $ di tutti i suoi fattori 2, quindi possiamo toglierli a bosco fino ad arrivare a un numero dispari:
$ 2^{n+1}(2^{n+1}-1)\cdots(2^n+1)=[(2^{n+1}-1)(2^{n+1}-3)\cdots(2^n+1)][2^{n+1}(2^{n+1}-2)\cdots(2^n+2)] $
$ \to[(2^{n+1}-1)(2^{n+1}-3)\cdots(2^n+1)][2^n(2^n-1)\cdots(2^{n-1}+1)] $. Ripetendo lo stesso procedimento alla seconda parentesi (e così via) arriviamo alla tesi.

Passando al problema, ponendo $ s=2^n!\binom{2^{n+1}}{2^n}=2^{n+1}(2^{n+1}-1)\cdots(2^n+1) $ e $ t=2^n!\binom{2^n}{2^{n-1}}=[2^n(2^n-1)\cdots(2^{n-1}+1)]^2 $, la nostra tesi è $ \upsilon_2\left(\frac{s-t}{2^n!}\right)=3n\ \ (*) $.
Per la formula di de Polignac abbiamo
$ \upsilon_2\left(\binom{2^{n+1}}{2^n}\right)=\upsilon_2\left(\frac{2^{n+1}!}{2^n!^2}\right)=\sum_{j=1}^{+\infty}\left(\left\lfloor\frac{2^{n+1}}{2^j}\right\rfloor-2\left\lfloor\frac{2^n}{2^j}\right\rfloor\right)=\sum_{j=1}^n(2^{n+1-j}-2\cdot2^{n-j})+1=1 $. Analogamente $ \upsilon_2\left(\binom{2^n}{2^{n-1}}\right)=1 $.
Dunque, se in $ (*) $ togliamo al numeratore tutti i fattori 2 del denominatore, per il Lemma possiamo dire che
$ \upsilon_2\left(\frac{s-t}{2^n!}\right)=\upsilon_2\left(\frac{s}{2^{\upsilon_2(2^n!)}}-\frac{t}{2^{\upsilon_2(2^n!)}}\right)=\upsilon_2\left(2\cdot\frac{s}{2^{\upsilon_2(s)}}-2\cdot\frac{t}{2^{\upsilon_2(t)}}\right)=\upsilon_2(2\cdot(2^{n+1}-1)!!-2[(2^n-1)!!]^2) $.
Per avere la tesi basta quindi far vedere che $ \cdot(2^{n+1}-1)!!-[(2^n-1)!!]^2\equiv2^{3n-1}\pmod{2^{3n}} $, ma tanto per cominciare $ (2^{n+1}-1)!!-[(2^n-1)!!]^2=(2^n-1)!![(2^n+1)(2^n+3)\cdots(2^n+(2^n-1))-(2^n-1)(2^n-3)\cdots(2^n-(2^n-1))] $, quindi basta far vedere che $ (2^n+1)(2^n+3)\cdots(2^n+(2^n-1))-(2^n-1)(2^n-3)\cdots(2^n-(2^n-1))\equiv2^{3n-1}\pmod{2^{3n}} $.
Considerando il primo membro come polinomio in $ 2^n $ e sviluppando, visto che tutti i termini in $ (2^n)^i,\ i\ge3 $ sono $ \equiv0\pmod{2^{3n}} $, otteniamo dalle relazioni radici-coefficienti
$ (2^n+1)(2^n+3)\cdots(2^n+(2^n-1))-(2^n-1)(2^n-3)\cdots(2^n-(2^n-1))\equiv(2^n-1)!!+2^n\sum_{i}^*\frac{(2^n-1)!!}{i}+2^{2n}\sum_{i<j}^*\frac{(2^n-1)!!}{ij} $
$ -(-1)^{2^{n-1}}[(2^n-1)!!-2^n\sum_{i}^*\frac{(2^n-1)!!}{i}+2^{2n}\sum_{i<j}^*\frac{(2^n-1)!!}{ij}]\equiv 2^{n+1}\sum_{i}^*\frac{(2^n-1)!!}{i}\pmod{2^3n} $, dove ho usato implicitamente che $ (-1)^{2^{n-1}}=1 $ (segue da $ n\ge 2 $).
La nuova tesi quindi è $ 2^{n+1}\sum_{i}^*\frac{(2^n-1)!!}{i}\equiv2^{3n-1}\pmod{2^{3n}} $, cioè $ \sum_{i}^*\frac{(2^n-1)!!}{i}\equiv2^{2n-2}\pmod{2^{2n-1}} $, che ci ricorda un caro vecchio amico.. Usiamo il solito trucco di accoppiare il primo termine con l'ultimo, il secondo col penultimo etc.:
$ \frac{(2^n-1)!!}{1}+\frac{(2^n-1)!!}{3}+\ldots+\frac{(2^n-1)!!}{2^n-3}+\frac{(2^n-1)!!}{2^n-1}=\left(\frac{(2^n-1)!!}{1}+\frac{(2^n-1)!!}{2^n-1}\right)+\left(\frac{(2^n-1)!!}{3}+\frac{(2^n-1)!!}{2^n-3}\right)+\ldots $
$ +\left(\frac{(2^n-1)!!}{2^{n-1}-1}+\frac{(2^n-1)!!}{2^n-(2^{n-1}-1)}\right)=\frac{2^n(2^n-1)!!}{1(2^n-1)}+\frac{2^n(2^n-1)!!}{3(2^n-3)}+\ldots+\frac{2^n(2^n-1)!!}{(2^{n-1}-1)(2^n-(2^{n-1}-1))} $.
In ultima analisi basta dimostrare che $ \frac{(2^n-1)!!}{1(2^n-1)}+\frac{(2^n-1)!!}{3(2^n-3)}+\ldots+\frac{(2^n-1)!!}{(2^{n-1}-1)(2^n-(2^{n-1}-1))}\equiv2^{n-2}\pmod{2^{n-1}} $, che è esattamente $ (2^n-1)!![1(2^n-1)]^{-1}+(2^n-1)!![3(2^n-3)]^{-1}+\ldots+(2^n-1)!![(2^{n-1}-1)(2^n-(2^{n-1}-1))]^{-1}\equiv2^{n-2}\pmod{2^{n-1}} $. Essendo $ (2^n-1)!! $ dispari, la tesi è del tutto equivalente a $ [1(2^n-1)]^{-1}+[3(2^n-3)]^{-1}+\ldots+[(2^{n-1}-1)(2^n-(2^{n-1}-1))]^{-1}\equiv2^{n-2}\pmod{2^{n-1}} $.
Ma se $ a\equiv a'\pmod m $ allora $ a^{-1}\equiv a'^{-1}\pmod m $ e pure $ (ab)^{-1}\equiv a^{-1}b^{-1}\pmod m $ (ovviamente con a e b coprimi con m), quindi ci riduciamo a dimostrare che $ (1^{-1})^2+(3^{-1})^2+\ldots+[(2^{n-1}-1)^{-1}]^2\equiv2^{n-2}\pmod{2^{n-1}} $ (ho moltiplicato per -1 implicitamente). Per finire, essendo $ x^{-1} $ invertibile (la funzione inversa è lei stessa), deduciamo che è bigettiva, quindi gli inversi dei dispari non sono altro che una permutazione dei dispari stessi. In definitiva il primo membro è congruo a
$ 1^2+3^2+\ldots+(2^{n-1}-1)^2=\frac{2^{n-2}(2\cdot2^{n-2}+1)(2\cdot2^{n-2}-1}{3} $ (per il Conto), da cui la tesi.

[dario2994]

Perfetto

[Nabir Albar]

86. Sia $ f(n)=\sum_{k=1}^{n}(k,n) $.
a) Mostrate che $ f(mn)=f(m)f(n) $ se $ (m,n)=1 $
b) Mostrate che $ \forall a\ \ f(x)=ax $ ha una soluzione
c) Trovate tutti gli $ a $ tali che $ f(x)=ax $ ha un'unica soluzione

[gatto_silvestro]

86.
Possiamo riscrivere $ f(n)=\sum_{d|n}d\phi(\frac{n}{d}) $
a)Essendo $ \phi(m) $ moltiplicativa allora senz'altro f(n) è moltiplicativa

b) $ f(2^{\alpha})=\sum_{i=0}^{\alpha-1}2^i\cdot2^{\alpha-i-1}+2^{\alpha}=(\alpha+2)2^{\alpha-1} $ dà soluzione $ \forall a $ se pongo $ \alpha=2a-2 $
c) $ f(3^{\beta})=\sum_{i=0}^{\beta-1}3^i(3^{\beta-i}-3^{\beta-i-1})+3^{\beta}=(2\beta+3) 3^{\beta-1} $ da cui ottengo una seconda sol per $ f(x)=dx $ con d dispari e per la moltiplicatività ho una seconda sol. $ \forall n $ non potenza di 2.

Le potenze di 2 sono sol. uniche, infatti
$ f(x)>x \forall x>1 $

$ f(p^s) $ è dispari per ogni primo dispari (somma di un numero dispari di dispari)

Per questi due fatti e per la moltiplicatività segue la tesi

[gatto_silvestro]

Esplicito l'ultimo passaggio:
Se $ x_0 $ non fosse una potenza di 2 $ 2^n=f(x_0)/x_0=\frac {f(2^{\alpha_1})}{2^{\alpha_1}}\cdot \frac {f(p_2^{\alpha_2})}{p_2^{\alpha_2}}\dots $
Allora $ \frac {f(2^{\alpha_1})}{2^{\alpha_1}}=2^n $, ma gli altri fattori sono tutti >1 assurdo

[Nabir Albar]

Molto bene, gatto silvestro! Sei nuovo di qua?
Se ti va, segui il consiglio di fph di mettere il nuovo problema in un nuovo thread, mettendo qui un link per mantenere tutto concatenato.. Mi sembra una buona idea per usare il forum in modo più "razionale" (sennò tra un po' in Teoria dei Numeri ci sarà solo il thread della staffetta )

[Anér]

Facciamo che almeno ogni trenta pagine si cambia argomento!

[gatto_silvestro]

Ho postato il nuovo problema qui
viewtopic.php?f=15&t=15334

[jordan]

Invece che aggiungere solo il link, aggiungo il quote ai testi e soluzioni dei problemi proposti come ho proposto qui

Da qui problema 87:

Trovare tutti i polinomi in una variabile con coefficienti interi tali che se $ a $ e $ b $ sono naturali tali che $ a+b $ è un quadrato perfetto, allora anche $ p(a)+p(b) $ è un quadrato perfetto.

Do per buono un lemma dimostrato dal Gobbino al Winter Camp 2009, durante l'ultima sessione di esercizi mi pare, che non ritengo utile dimostrare di nuovo qui: se $ q(x)\in\mathbb{Z}[x] $ è un polinomio il cui valore su un intero è sempre un quadrato perfetto, allora questo polinomio è il quadrato di un polinomio a coefficienti interi.
Suppongo che da subito che p non sia costante, tanto i polinomi costanti sono tutti della forma $ 2k^2 $
Pongo $ a=(y^2-k)x^2 $ e $ b=kx^2 $ con $ y,k\in\mathbb{Z},y^2\ge k $. Chiaramente $ \forall x\in\mathbb{Z}, a+b $ è un quadrato, per cui anche $ p((y^2-k)x^2)+p(kx^2) $ è un quadrato se x è intero. Ora se fisso y e k e pongo $ q(x)=p((y^2-k)x^2)+p(kx^2) $, ho che per il lemma $ q(x)=r(x)^2 $ per un certo polinomio r a coefficienti interi. Il coefficiente direttivo di q è dunque il quadrato di quello di r che è un intero, dunque il coefficiente direttivo di q è un quadrato perfetto. Se chiamo $ c $ il coefficiente direttivo di p e $ n $ il grado di p, ho che $ =c(y^2-k)^n+ck^n $ è sempre un quadrato, qualsiasi valore assumano k e y, purché $ k\leq y^2 $. Se pongo k=0 ottengo subito che c stesso è un quadrato perfetto, dunque dividendo per c (che è un coefficiente direttivo e dunque non è nullo) ho che $ (y^2-k)^n+k^n $ è sempre un quadrato, purché $ k\leq y^2 $. Ora si presentano due casi, n pari e n dispari.
Se n è pari ponendo $ y=2d $ e $ k=2d^2 $ ho che $ 2\cdot (2d^2)^n $ è un quadrato, assurdo perché il doppio di un quadrato positivo non è mai un quadrato.
Se n è dispari pongo k=1 e ottengo che $ (y^2-1)^n+1 $ è un quadrato per ogni scelta di y, dunque è il quadrato di un polinomio a coefficienti interi in y; tuttavia se $ n\geq 3 $ ho che sviluppando secondo Newton i primi due termini sono $ y^{2n}-ny^{2n-1} $, dunque il secondo coefficiente è dispari, cosa che non capita mai elevando un polinomio a coefficienti interi al quadrato. Dunque n può valere solo 1, e per tale valore si ha p(x)=cx+f, con c quadrato perfetto (lo abbiamo già visto) e perciò p(a)+p(b)=(quadrato)+2f, da cui facendo tendere il quadrato che si ottiene all'infinito si vede che f deve valere 0.
I polinomi sono dunque $ 2k^2 $ e $ k^2x $ per qualche k intero.

[jordan]

Problema 88 proposto da Anér qui:

Problema 88
Si hanno due polinomi $ p,q\in\mathbb{Z}[x,y] $, e si sa che comunque si scelgano due interi $ a,b $ si ha che $ p(a,b)|q(a,b) $. Dimostrare che allora esiste un polinomio $ r\in\mathbb{Q}[x,y] $ tale che $ p\cdot r=q $.

Considero $ p(x,y) $ e $ q(x,y) $ come polinomi in x (cioè nella forma $ p(x,y)=\sum_{i=0}^d p_i(y)x^i $ e $ q(x,y)=\sum_{i=0}^{D} q_i(y) x^i $).
Suppongo d'ora in poi che $ p(x,y) $ non sia il polinomio nullo.
Faccio la divisione seguendo l'algoritmo e ottengo
$ \frac{q(x,y)}{p(x,y)}=\sum_{i=0}^{D-d} r_i(y)x^i + \frac{\sum_{i=0}^{d-1} r'_i(y)x^i}{p(x,y)}~(*) $, con $ r_i(y) $ e $ r'_i(y) $ funzioni razionali (e a coeff. razionali) in y. Questa equazione ovviamente vale per tutte le coppie $ (x,y) $ che non annullano $ p(x,y) $ o i denominatori delle funzioni razionali. Sicuramente ci sono infiniti $ y $ per cui $ p(x,y)\neq0 $ per infiniti $ x $ (per esempio gli $ y $ che non sono radici di $ p_d(\cdot) $) e per cui sono definite le funzioni razionali. Inoltre per questi $ y $ al più $ d $ valori di $ x $ annullano $ p(x,y) $ $ (**) $ (principio di identità dei polinomi).
Fissando un $ y\in\mathbb{Z} $ a caso tra quelli buoni, $ \sum_{i=0}^{D-d} r_i(y)x^i $ diventa un polinomio a coeff. razionali. Prendo le frazioni ai minimi termini di questi coeff. e chiamo $ m $ il loro minimo comune multiplo. Per $ x\to\infty $, $ \frac{\sum_{i=0}^{d-1} r'_i(y)x^i}{p(x,y)}\to0 $, quindi se gli $ r'_i(y) $ non sono tutti nulli fissato $ x\in\mathbb{N} $ sufficientemente grande avrò $ 0<\left|\frac{\sum_{i=0}^{d-1} r'_i(y)x^i}{p(x,y)}\right|<\frac{1}{m} $.
Ma nella $ (*) $ il primo membro è intero per ipotesi e $ \sum_{i=0}^{D-d} r_i(y)x^i=\frac{k}{m} $ per qualche $ k\in\mathbb{Z} $, assurdo! Quindi $ r'_i(y)=0 $ per ogni $ i $. Visto che posso ripetere lo stesso ragionamento per infiniti $ y $, ottengo che tutti gli $ r'_i(y) $ sono nulli come (funzioni razionali).
Ok, mi sono ridotto a $ \frac{q(x,y)}{p(x,y)}=\sum_{i=0}^{D-d} r_i(y)x^i $. Per ogni $ i $ scrivo $ r_i(y)=s_i(y)+\frac{t_i(y)}{u_i(y)} $, essendo $ t_i(y) $ un polinomio nullo o di grado minore rispetto a $ u_i(y) $.
Suppongo per assurdo che non tutti i polinomi $ t_i(y) $ siano nulli. Chiamo $ M $ il m.c.m. dei denominatori delle frazioni dei coeff. di tutti gli $ s_i(y) $. Seguendo la stessa idea di prima, deve valere $ \sum_{i=0}^{D-d} \frac{t_i(y)}{u_i(y)}\cdot x^i=\frac{k}{M} $ per qualche $ k\in\mathbb{Z} $.
Ma $ \forall i\ \lim_{y\to\infty}\frac{t_i(y)}{u_i(y)}=0 $, quindi per infiniti $ y $ abbiamo $ \left|\frac{t_i(y)}{u_i(y)}\right|<\frac{1}{m(D+1)^i(D-d+1)} $ per ogni $ i $. Preso uno di questi $ y $, ci sono almeno $ D-d+1 $ valori di $ x $ in $ \{1,2,\ldots,D+1\} $ tali che vale la $ (*) $, per il fatto $ (**) $. Dunque per questi valori di $ x $ otteniamo che $ \left|\sum_{i=0}^{D-d} \frac{t_i(y)}{u_i(y)}\cdot x^i\right|\le\sum_{i=0}^{D-d}\left|\frac{t_i(y)}{u_i(y)}\right|\cdot x^i<\sum_{i=0}^{D-d}\frac{x^i}{m(D+1)^i(D-d+1)}\le\sum_{i=0}^{D-d}\frac{1}{m(D-d+1)}=\frac{1}{m} $, ergo per quanto detto prima $ \sum_{i=0}^{D-d} \frac{t_i(y)}{u_i(y)}\cdot x^i=0 $.
Siccome questo polinomio in $ x $ si annulla per $ D-d+1 $ valori di $ x $, $ \frac{t_i(y)}{u_i(y)}=0 $ per ogni $ i $. Ripetendo il ragionamento per tanti $ yy $ a suon di principio di identità dei polinomi posso finalmente dire che $ t_i(y)=0 $ (come polinomi).
Rimane $ \frac{q(x,y)}{p(x,y)}=\sum_{i=0}^{D-d} s_i(y)x^i $, da cui $ q(x,y)-p(x,y)\sum_{i=0}^{D-d} s_i(y)x^i=0 $ per troppi valori di $ x $ e $ y $ (dovrebbe essere facile capire il perché, cmq se volete lo chiarisco).

[jordan]

Problema 89 proposto da Nabir Albar qui:

Siano dati $ a,b,c,d\in\mathbb{Q}:\lfloor na\rfloor +\lfloor nb\rfloor =\lfloor nc\rfloor +\lfloor nd\rfloor $ per ogni $ n\in\mathbb{N} $. Mostrate che c'è almeno un intero in $ \{a+b, a-c, a-d\} $

Al momento non è pervenuta alcuna soluzione completa, e dato che il problema è datato 18 dicembre 2010, invito chi l'ha proposto a fornirci una soluzione, visto che come scrissi nel primo post circa una settimana dovrebbe essere sufficiente..

[dario2994]

Problema 89 proposto da Nabir Albar qui:

Siano dati $ a,b,c,d\in\mathbb{Q}:\lfloor na\rfloor +\lfloor nb\rfloor =\lfloor nc\rfloor +\lfloor nd\rfloor $ per ogni $ n\in\mathbb{N} $. Mostrate che c'è almeno un intero in $ \{a+b, a-c, a-d\} $

Al momento non è pervenuta alcuna soluzione completa, e dato che il problema è datato 18 dicembre 2010, invito chi l'ha proposto a fornirci una soluzione, visto che come scrissi nel primo post circa una settimana dovrebbe essere sufficiente..

No spe... un altro giorno... ci sto uscendo scemo Se entro oggi ancora non mi viene mi arrendo

p.s. primo messaggio dell'anno

[jordan]

Ok dario,finchè c'è qualcuno che ci prova ci mancherebbe..
Comunque arrivi in ritardo per il primo post dell'anno

[jordan]

La soluzione al problema 89, dallo stesso Nabir Albar (da qui ):

Divido l'equazione per $n$ e per $n\to+\infty$ ottengo $a+b=c+d$. L'eq. equivale al sistema $\begin{cases}a+b=c+d\\ \{na\}+\{nb\}=\{nc\}+\{nd\}\end{cases}$. È chiaro che togliendo $\lfloor a\rfloor$ ad $a$, $\lfloor b\rfloor$ a $b$ etc. mi riduco a $\{na\}+\{nb\}=\{nc\}+\{nd\}\ (1)$ con $0\le a,b,c,d<1$.
Chiamo $a=A/M,b=B/M,c=C/M,d=D/M$, con $(A,B,C,D,M)=1$. Segue $A+B=C+D$. Voglio far vedere che se $A\neq C,D$ allora $A+B=C+D=M$. D'ora in poi suppongo per assurdo $A\neq C,A\neq D,A+B=C+D\neq M$
La (1) diventa $\{nA/M\}+\{nB/M\}=\{nC/M\}+\{nD/M\}\ (2)$.
Chiamo $d_1=(A,M),\ d_2=(B,M)$. È $q=(A,B,M)=1$, altrimenti per $n=M/q$ dalla (2) avrei $0=\{C/q\}+\{D/q\}$, cioè $q\mid C,D$, assurdo essendo $(A,B,C,D,M)=1$.
Esiste quindi $X:XA\equiv 1\pmod{d_2}$. Se $d_2>1$, per $n=XM/d_2$ ottengo $1/d_2=\{XA/d_2\}+\{XB/d_2\}=\{XC/d_2\}+\{XD/d_2\}$, da cui wlog $d_2\mid D$ e $XC\equiv 1\pmod{d_2}$, che ovviamente valgono anche per $d_2=1$. Allo stesso modo, se $d_1>1$, $1/d_1=\{X'C/d_1\}+\{X'D/d_1\}$ per qualche $X':X'B\equiv 1\pmod{d_1}$. Se fosse di nuovo $d_1\mid D$ e $X'C\equiv 1\pmod{d_1}$ esisterebbe $Y:YC\equiv 1\pmod{d_1d_2}$, quindi ponendo $n=\frac{YM}{d_1d_2}$ la (2) darebbe $\{\frac{YC}{d_1d_2}\}+\{\frac{YD}{d_1d_2}\}=\frac{1}{d_1d_2}<\{\frac{YA}{d_1d_2}\}+\{\frac{YB}{d_1d_2}\}$. Dunque $d_1\mid C,\ d_2\mid D,\ (A,D,M)=(B,C,M)=1$, che vale anche per $d_1=1$. Ripetendo lo stesso ragionamento ottengo $(C,M)\mid A$ e $(D,M)\mid B$, quindi $(A,M)=(C,M)$ e $(B,M)=(D,M)$.
Se uno tra $A,B,C,D$ fosse 0, wlog $A=0$, sarebbe $M=(A,M)\Rightarrow(C,M)=M\Rightarrow C=0$, contro l'ipotesi, quindi $0<A,B,C,D<M$.
Voglio ridurmi a $d_1=(A,M)=(C,M)=1$; siano wlog $d_1,d_2>1$. Posso scrivere $M=D_1D_2$, con $d_1\mid D_1$, $d_2\mid D_2$ e $(D_1,D_2)=1$. È $A\not\equiv C\pmod{D_1}$ o $A\not\equiv C\pmod{D_2}$ (segue da $|A-C|<D_1D_2=M$). Nel primo caso siano $A',B',C',D'$ i rappresentanti privilegiati di $A,B,C,D$ modulo $D_1$: nella (2) sostituisco $n=n'M/D_1$ ottenendo $\forall n'\ \{n'A'/D_1\}+\{n'B'/D_1\}=\{n'C'/D_1\}+\{n'D'/D_1\}$; inoltre $B'\neq D'$ e $B'\neq C'$ (essendo $(C',D_1)=d_1>1$ mentre $(B',D_1)=(B,D_1)=1$), perciò mi sono ricondotto alla (2) con $(A,B,C,D,M)=(B',A',D',C',D_1)$ e inoltre $B'+A'=D'+C'\neq D_1$ (essendo $(A',D_1)=d_1>1$ e $(B',D_1)=1$). Nel secondo caso analogamente mi riconduco alla (2) con $(A,B,C,D,M)=(A',B',C',D',D_2)$. Insomma sono tornato all'equazione di partenza con tutte le ipotesi più $(A,M)=(C,M)=1$, ottenendo di nuovo $(B,M)=(D,M)$ e $0<A,B,C,D<M$.
Cerco di ridurmi al caso $A=1$: prendo $X:XA\equiv 1\pmod M$ e considero i rappresentanti privilegiati $A'=1,B',C',D'$ di $XA,XB,XC,XD$. Per $n=n'X$ ottengo $\{n'/M\}+\{n'B'/M\}=\{n'C'/M\}+\{n'D'/M\}\ (3)$, quindi di nuovo ho un'altra eq. della forma (2) con $A=1$ e mantengo sempre le ipotesi: da $A\neq C,D$ segue $XA\not\equiv XC,XD\pmod M$, cioè $1\neq C',D'$ e dalla (3) per $n'=1$ ho $1+B'=C'+D'\neq M$ (essendo $XA+XB\not\equiv 0\pmod M$). D'ora in poi è lecito supporre $A=1$ e $1+B=C+D<M$.

Lemma Siano $s,t,u,M$, con $s,t\ge 2$ e $2\le u\le M/2$, tali che $1+u=s+t$. Se una tra queste tre
$(s,M)=(u,M)=d\ge1\wedge (t,M)=1\ \ (i)$
$(t,M)=(u,M)=d\ge1\wedge (s,M)=1\ \ (ii)$
$(s,M)=(t,M)=d>1\ \ (iii)$
è vera, allora $\exists n<M/d:\lfloor n/M\rfloor+\lfloor nu/M\rfloor\neq\lfloor ns/M\rfloor+\lfloor nt/M\rfloor$

Testo nascosto:

Dim.: Essendo le ipotesi simmetriche posso supporre wlog $s\ge t$. Parto dall'ipotesi (iii) nel caso in cui $t=d,s=vd$. Sia $n=M/d-1\ge 1$. Allora da una parte $\lfloor nt/M\rfloor=\lfloor\frac{M-d}{M}\rfloor=0$ e $\lfloor ns/M\rfloor<Ms/Md=v$, ma dall'altra $\lfloor nu/M\rfloor=\lfloor\frac{u}{d}-\frac{u}{M}\rfloor=\lfloor\frac{(v+1)d-1}{d}-\frac{u}{M}\rfloor=\lfloor v+\frac{d-1}{d}-\frac{u}{M}\rfloor\ge v$, essendo $\frac{d-1}{d}-\frac{u}{M}\ge\frac{1}{2}-\frac{1}{2}=0$. D'ora in poi considerando l'ipotesi (iii) supporrò $s,t>d$.
Sia $N=\lfloor s/t\rfloor$. Definisco $q=\lfloor\frac{NM}{s}\rfloor$ e $r=NM-sq<s$ (il resto). Voglio far vedere che per $n=q$ vale la tesi. Intanto ho che $q\le s/t<M/t$, quindi per avere $q<M/d$ basta mostrare che $t\ge d$.
Nell'ipotesi (i) ho $t=(u-s)+1$, ma $d\mid u-s$ e $t\ge 2$, quindi $t\ge d+1$. Nelle ipotesi (ii) e (iii) ho $d\mid s>0$, da cui $t\ge d$. Inoltre $r>0$, altrimenti avrei $s\mid NM$. Nelle ipotesi (i) e (iii) ho $(s,M)=d\Rightarrow\frac{s}{d}\mid N\Rightarrow\frac{s}{d}\le\lfloor\frac{s}{t}\rfloor\le\frac{s}{t}$, ma $t>d$ in entrambe le ipotesi, assurdo. Nell'ipotesi (ii) ho $(s,M)=1\Rightarrow s\mid N\Rightarrow s\le\frac{s}{t}$, di nuovo assurdo.
Posso già dire qualcosa sull'eq. della tesi: per $n=q$, $\frac{qt}{M}=\frac{t(NM-r)}{Ms}\le\frac{t}{s}\cdot\frac{s}{t}-\frac{tr}{Ms}<1$ (essendo $r>0$), quindi $\lfloor qt/M\rfloor=0$. Allo stesso modo $\lfloor\frac{qs}{M}\rfloor=\lfloor\frac{NM-r}{M}\rfloor\le\lfloor N-\frac{r}{M}\rfloor<N$.
Inoltre (cosa che permette di concludere) $\lfloor qu/M\rfloor\ge L$! Infatti $\frac{qu}{M}=\frac{q(s+t-1)}{M}=\frac{qs}{M}+\frac{q(t-1)}{M}=N-\frac{r}{M}+\frac{q(t-1)}{M}$ e basta mostrare che $q(t-1)\ge r$, che si può fare in modo molto elegante:
$(t-2)(N-1)\ge0\Rightarrow tN\ge 2N+t-2=2N-1+(t-1)$, ma $s-tN\le t-1$, dunque $tN\ge 2N-1+s-tN\Rightarrow N\ge\frac{s-1}{2(t-1)}\ (4)$; se fosse $q(t-1)<r$ avrei $q<\frac{r}{t-1}\Rightarrow NM=sq+r<\frac{sr}{t-1}+r=\frac{ur}{t-1}\le\frac{u(s-1)}{t-1}\le\frac{M(s-1)}{2(t-1)}$ (qui finalmente uso l'ipotesi $u\le M/2$), in contraddizione con la (4). Perciò per $n=q$ $\lfloor ns/M\rfloor+\lfloor nt/M\rfloor<N\le\lfloor n/M\rfloor+\lfloor nu/M\rfloor$.

Per avere l'assurdo voglio mostrare che esiste sempre $n:\lfloor n/M\rfloor+\lfloor nB/M\rfloor\neq\lfloor nC/M\rfloor+\lfloor nD/M\rfloor\ (5)$ (il lemma è un caso particolare). Intanto se $2B\ge M,2C<M,2D<M$ vale subito la tesi per $n=2$.
Se $2B\le M$ sicuramente $2C+2D\le M+2$, quindi (da $C,D>1$) $C,D<M$ e posso applicare direttamente il Lemma (con $u=B,s=C,t=D$).
Rimane il caso in cui $2B>M$ e $2C\ge M$ oppure $2D\ge M$. Sia $X=\max(C,D)$ e $Y=\min(C,D)$. Pongo $u=M-X$ e $v=M-B$ e ottengo che per ogni $n$ non divisibile per $M/(B,M)$ vale $\lfloor n/M\rfloor+\lfloor nu/M\rfloor=\lfloor n/M\rfloor+n-1-\lfloor nX/M\rfloor$, come pure $\lfloor nY/M\rfloor+\lfloor nv/M\rfloor=\lfloor nY/M\rfloor+n-1-\lfloor nB/M\rfloor$.
Quindi per questi $n$ la $(5)$ equivale a $\lfloor n/M\rfloor+\lfloor nu/M\rfloor=\lfloor nv/M\rfloor+\lfloor nY/M\rfloor$. Ma $1+u=v+Y$, $u=M-X\le M/2$ (segue da $2\max(C,D)\ge M$), $v=M-B\ge 2$ e $Y\ge 2$, quindi posso di nuovo applicare il lemma (con $s=v,t=Y$) ottenendo che esiste un $n<M/d$ (e questo $d$ in tutti i casi è $(B,M)$) e di conseguenza ho la tesi ($n$ non è divisibile per $M/d$).
Rimangono le uniche possibilità $A=C$, $A=D$ e $A+B=C+D$, cioè tornando alle notazioni iniziali ${a}={c}$, ${a}={d}$ e $a+b$ intero, che è la tesi.

[jordan]

Da qui:

Per ogni intero positivo $n$, sia $f(n)$ il numero di modi di rappresentarlo come somma di potenze di 2 con esponente naturale. Rappresentazioni che differiscono solo per l'ordine degli addendi sono considerate uguali. Per chiarire $f(4)=4$, essendo $4=2^2,2+2,2+1+1,1+1+1+1$.
Mostrare che $\forall n\ge 3\ \ 2^\frac {n^2}{4} < f(2^n) < 2^\frac {n^2}{2}$.

Elenchiamo per iniziare i primi valori di $ f(n) $:
$ f(1)=1 $
$ f(2)=f(3)=2 $
$ f(4)=f(5)=4 $
$ f(6)=f(7)=6 $
$ f(8)=f(9)=10 $...
E' immediato vedere che la funzione è crescente, e che:
- se $ n $ è dispari allora $ f(n)=f(n-1) $,poichè nella sua rappresentazione dovrà obbligatoriamente comparire almeno un 1;
- se $ n $ è pari allora $ \displaystyle f(n)=f(n-1)+f\left(\frac{n}{2}\right) $, data dalla somma del numero di combinazioni in cui compare almeno un 1 e da quelle in cui tutti i numeri della rappresentazione valgono almeno 2.

Da quanto detto possiamo quindi dedurre che:
$ \displaystyle f(2^{n+1})=f(2^{n+1}-1)+f(2^n)=f(2^{n+1}-2)+f(2^n)=f(2^{n+1}-3)+f(2^n-1)+f(2^n)=\ldots $ $ \displaystyle =\sum_{1\le i\le 2^n}{ f(i) } $.
In particolare:
$ f(16)=f(8)+2f(6)+2f(4)+2f(2)+f(1)=35 $
$ \displaystyle 2^{\frac{3^2}{4}}<f(2^3)=10<2^{\frac{3^2}{2}} $
$ \displaystyle 2^{\frac{4^2}{4}}<f(2^4)=35<2^{\frac{4^2}{2}} $
Dobbiamo quindi verificare la tesi per ogni $ n\ge 5 $:

1. Upper bound

Supponiamo che la tesi sia verificata per $ f(2^3), f(2^4), \ldots, f(2^n) $. Definiamo $ e(\cdot):\mathbb{Z}\to \{0,1\} $ tale che:
- $ e(x)=1 $ se $ x $ è dispari;
- $ e(x)=0 $ se $ x $ è pari.
Allora $ \displaystyle f(2^{n+1})=\sum_{1\le i\le 2^n}{ f(i) } < \sum_{1\le i\le 8}{ f(i) } +\sum_{4\le j\le n}{ f(2^j) 2^{j-1}}= $
$ \displaystyle =f(2^4)+\sum_{4\le j\le n}{ f(2^j) 2^{j-1}}< $
$ \displaystyle < 2^0+2^1+2^2+2^3+2^4+2^5+\sum_{4\le j\le n}{2^{\frac{(j+1)^2-3}{2}} }< $
$ \displaystyle < 2^0+2^1+2^2+2^3+2^4+2^5+\sum_{4\le j\le n}{2^{\frac{(j+1)^2-3+e(j)}{2}} }< $
$ \displaystyle <2^{\frac{(n+1)^2}{2}} $.
Infatti dati interi non negativi $ a_0<a_1<\ldots <a_k $ risulta sempre verificata $ \displaystyle \sum_{1\le i\le k}{2^{a_i}}\le 2^{a_k+1}-1<2^{a_k+1} $.


2. Lower bound

Supponiamo anche qui che la tesi sia verificata per $ f(2^3), f(2^4), f(2^5), \ldots, f(2^n) $. E osserviamo che per ogni intero $ k>0 $ vale la disuguaglianza:
$ f(2^n+2k)\ge f(2^n)+kf(2^{n-1}) $.
Per $ k=1 $ infatti otteniamo un'identità, e supposta che sia vera per un generico $ k>0 $ allora:
$ f(2^n+2k+2)=f(2^n+2k)+f(2^{n-1}+k+1) \ge f(2^n+2k)+f(2^{n-1}) \ge f(2^n)+(k+1)f(2^{n-1}) $.
Tornando alla tesi originale, abbiamo che:
$ \displaystyle f(2^{n+1})= \sum_{1\le i\le 2^n}{f(i)} > \sum_{2^{n-2}\le i\le 2^n}{ f(i) }= $
$ \displaystyle =f(2^n)+[f(2^n-1)+f(2^n-2)+\ldots+f(2^{n-1})]+[f(2^{n-1}-1)+f(2^{n-1}-2)+\ldots+f(2^{n-2})]> $
$ \displaystyle >f(2^n)+[2^{n-1}f(2^{n-1})+2f(2^{n-2})\sum_{1\le i\le 2^{n-2}-1}{i}]+2^{n-2}f(2^{n-2})> $
$ \displaystyle > 2^{\frac{n^2}{4}}+[2^{\frac{n^2+2n-3}{4}}+2^{n-2}(2^{n-2}-1)2^{\frac{(n-2)^2}{4}}]+2^{n-2}2^{\frac{(n-2)^2}{4}} $
$ \displaystyle > 2^{\frac{n^2}{4}}+2^{\frac{n^2+2n-3}{4}}+2^{\frac{n^2+4n-12}{4}}-2^{n-2}2^{\frac{(n-2)^2}{4}}+2^{n-2}2^{\frac{(n-2)^2}{4}}= $
$ \displaystyle = 2^{\frac{n^2}{4}}+2^{\frac{n^2+2n-3}{4}}+2^{\frac{n^2+4n-12}{4}}> $
$ \displaystyle >2^{\frac{(n+1)^2}{4}} $. []