BOMC-2012 Test Day 2 Problem 1

[*Mahi*]

$a_0,a_1,\ldots$ and $b_0,b_1,\ldots$ are arithmetic progressions of integers such that $a_1-a_0$ and $b_1-b_0$ share no common factor greater than $1$. Prove that for any integer $n$ there exist $i,j$ such that $a_i-b_j=n$.

[nafistiham]

Used Diophantine equation.

[*Mahi*]

Used Diophantine equation.

I think you mean solutions to the equation $d_1x+d_2y =1$.
Diophantine equation is a lot more general term, which is used to express a set of equations which allows integer solutions only, and where the number of equations are less than the number of variables.
Source http://en.wikipedia.org/wiki/Diophantine_equation

[Phlembac Adib Hasan]

The same as Tiham Vaia.But this problem is not completely true.If one sequence is increasing and other is decreasing then it is not necessarily true for all integer $n$.

[Nadim Ul Abrar]

I disproved the statement ... Was I right ??

[*Mahi*]

I disproved the statement ... Was I right ??

No you were not... you can see the proof here http://www.matholympiad.org.bd/forum/vi ... =10#p10359

[Nadim Ul Abrar]

I disproved the statement ... Was I right ??

No you were not... you can see the proof here http://www.matholympiad.org.bd/forum/vi ... =10#p10359

*Mahi* Are You sure that you are right ..???
look at the fifth line of your solution that , $d_a,d_b \geq 1$ is it right ????

[*Mahi*]

It should have been $|d_a|,|d_b| \geq 1$, but the basic idea is right.

[nafistiham]

Used Diophantine equation.

I think you mean solutions to the equation $d_1x+d_2y =1$.
Diophantine equation is a lot more general term, which is used to express a set of equations which allows integer solutions only, and where the number of equations are less than the number of variables.
Source http://en.wikipedia.org/wiki/Diophantine_equation

What term could have I used

[Nadim Ul Abrar]

*Mahi* vai ...


Please check this and show me the right path ...

Let $a_1-a_0=d_1$ , $b_1-b_0=d_2$

In the progressions $a_0,a_1...$ and $b_0,b_1...$
$a_i=a_0+d_1i$ ,$b_j=b_0+d_2j$; $(i,j=0,1,2,3...)$

According to the statement ,
If $n$ be an integer , then we can find $i,j$ such that
$n=a_i-b_j=a_0+d_1i-b_0-d_2j$ $.... (i)$

Let $d_2$ be negative , And $d_1$ positive .
then $d_2=-|d_2|$
So $|d_1|i+|d_2|j=n+b_0-a_0$ $....(ii)$

Since $i,j \geq 0$ , $|d_1|i+|d_2|j \geq 0$ .

Put $n=a_0-b_0-k$
For any natural values of $k$ ,
$n+b_0-a_0=-k<0$ (contradiction with $(ii)$)

So not for all but for some $n$'s there exist $i,j$ such that $a_i - b_j=n$