89. Parti intere troppo lineari (Staffetta)

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Nabir Albar
Messaggi: 62
Iscritto il: 22 nov 2010, 19:09
Località: Sto ca... Stoccarda!

89. Parti intere troppo lineari (Staffetta)

Messaggio da Nabir Albar » 18 dic 2010, 17:32

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

paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: 89. Parti intere troppo lineari (Staffetta)

Messaggio da paga92aren » 30 dic 2010, 21:08

visto che la staffetta si è bloccata scrivo la mia idea:

Posto $a=a_0+0,a_1a_2a_3\dots a_n$ e lo stesso per $b,c,d$ ($n$ può tendere all'infinito per i numeri periodici) voglio dimostrare che $a_k+b_k=c_k+d_k$:
Per induzione estesa:
PB pongo $n=1$ e ottengo $\lfloor a\rfloor= a_0$
PI se $a_i+b_i=c_i+d_i$ per ogni $i\geq k$ allora:
Pongo $n=10^{k+1}$ e ottengo che $a_0a_1\dots a_ka_{k+1}+b_0b_1\dots b_kb_{k+1}=c_0c_1\dots c_kc_{k+1}+d_0d_1\dots d_kd_{k+1}$ da cui semplifico tutti i termini diversi da $k+1$ (posso farlo per ipotesi del passo induttivo) e ottengo la tesi.

Ora rimane da dimostrare che o $a_n+b_n$ o $a_n-c_n$ o $a_n-d_n$ sono nulli per ogni $n$

Nabir Albar
Messaggi: 62
Iscritto il: 22 nov 2010, 19:09
Località: Sto ca... Stoccarda!

Re: 89. Parti intere troppo lineari (Staffetta)

Messaggio da Nabir Albar » 05 gen 2011, 00:22

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.
Ultima modifica di Nabir Albar il 07 gen 2011, 11:37, modificato 3 volte in totale.

Nabir Albar
Messaggi: 62
Iscritto il: 22 nov 2010, 19:09
Località: Sto ca... Stoccarda!

Re: 89. Parti intere troppo lineari (Staffetta)

Messaggio da Nabir Albar » 05 gen 2011, 00:33

Questo è il nuovo problema: Problema 90 :D

Rispondi