89. Parti intere troppo lineari (Staffetta)
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
89. Parti intere troppo lineari (Staffetta)
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\} $
-
- Messaggi: 358
- Iscritto il: 31 lug 2010, 10:35
Re: 89. Parti intere troppo lineari (Staffetta)
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$
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$
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re: 89. Parti intere troppo lineari (Staffetta)
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$
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.
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:
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.
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re: 89. Parti intere troppo lineari (Staffetta)
Questo è il nuovo problema: Problema 90