BDMO national 2016, junior 10

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
dshasan
Posts: 66
Joined: Fri Aug 14, 2015 6:32 pm
Location: Dhaka,Bangladesh

BDMO national 2016, junior 10

Unread post by dshasan » Wed Jan 18, 2017 2:05 pm

$a, b, c, d$ are four positive integers where $a < b < c < d$ and the sum of any three of them is divisible by the fourth. Find all possible values of $(a, b, c, d)$
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.

- Charles Caleb Colton

User avatar
ahmedittihad
Posts: 147
Joined: Mon Mar 28, 2016 6:21 pm

Re: BDMO national 2016, junior 10

Unread post by ahmedittihad » Tue Jan 31, 2017 7:32 pm

Note that this is equivalent to $a,b,c,d\mid a+b+c+d$ or $\text{lcm}(a,b,c,d)\mid a+b+c+d$. Letting $\text{lcm}(a,b,c,d)=X$, we want, $\dfrac{a}{X}+\dfrac{b}{X}+\dfrac{c}{X}+\dfrac{d}{X}=\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=k\in\mathbb{Z}^+$. The denominators are all integers so we have only four cases: $k=1, 2, 3, 4$ and this becomes a classic Diophantine problem...

If $k=4$ then $X/a=X/b=X/c=X/d=1$ so $a=b=c=d$ so they are not distinct, contradiction.

If $k=3$ then WLOG $X/a=X/b=1$, $X/c=X/d=2$ so $a=b$ which is also bad.

If $k=2$ then $X/a\le 2$ else $\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{4}{3} < 2$.
If $X/a=2$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{3}{2}$ where $X/b \le 2$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le 1 < \dfrac{3}{2}$. However this contradicts $X/a < X/b$ so no solutions.
Then we must have $X/a=1$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=1$ where $X/b \le 3$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{3}{4} < 1$.
If $X/b=3$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{2}{3}$ implies $2X/c\cdot X/d - 3X/c-3X/d =0 $implies $(2X/c-3)(2X/d-3)=9$ which has the solutions $X/c=2, X/d=6$ which doesn't work as $X/b > X/c$ or $X/c=X/d=3$ which doesn't work as $c=d$.
Thus $X/b=2$ which gives $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{2}$ implies $(X/c-2)(X/d-2)=4$ which has solutions $(X/c, X/d)=(3, 6), (4,4)$ and the last solution doesn't work since $c=d$.
Finally $X/b \le 1$ doesn't work as $a=b$.

$k=1$ is the interesting and tedious case. WLOG $X/a\le X/b\le X/c\le X/d$, then $X/a\le 4$ else $\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{4}{5} < 1$. If $X/a=4$ then $X/b=X/c=X/d=4$ which is bad because non-distinct.
If $X/a=3$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{2}{3}$, for which $X/b\le 4$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} = \dfrac{3}{5} < \dfrac{2}{3}$.
If $X/b = 4$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d} = 5/12$ and so $5\cdot X/c\cdot X/d -12X/c-12X/d =0$ implies $ (5X/c-12)(5X/d-12)=144$ and after bashing factors (eww) the only solutions are $5X/c-12=3,5X/d-12=48$ and $5X/c-12=8, 5X/d-12=18$ for which $X/c=3$ and $X/d=12$ which doesn't work as $X/a=X/c$, or $X/c=4$ and $X/d=6$ which also doesn't work as $X/b=X/c$.
If $X/b=3$ then $a=b$ which doesn't work, and if $X/b < 3$ then $X/b < X/a$ which defies the condition.
Thus $X/a=2$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{2}$ for which $X/b \le 6$, else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{3}{7} < \dfrac{1}{2}$.
If $X/b=6$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d} = 1/3 $implies $X/c\cdot X/d -3X/c-3X/d=0 $implies $(X/c-3)(X/d-3)=9$ which has the solutions $X/c-3=1$, $X/d-3=9$ which gives $X/c=4$, $X/d=12$ which doesn't work as $X/c < X/b$ or $X/c-3=3$, $X/d-3=3$ which doesn't work as $c=d$.
If $X/b=5$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{3}{10}$ implies $3\cdot X/c\cdot X/d - 10X/c-10X/d=0$ implies $(3X/c-10)(3X/d-10)=100$ which only has the solutions $3X/c-10 =2, 3X/d-10 = 50$ or $X/c=4$ and $X/d=20$ which doesn't contradicts $X/b < X/c$; and $3X/c-10=5, 3X/d-10=20$ which gives $X/c=5$ and $X/d=10$ which gives $b=c$ which doesn't work.
If $X/b=4$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{4}$ so $(X/c-4)(X/d-4)=16$ which has solutions $(X/c,X/d)=(5,20), (6, 12), (8,8)$ the last which gives $c=d$ which is bad.
If $X/b=3$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{6}$ so $(X/c-6)(X/d-6)=36$ which has solutions $(X/c, X/d)=(7,42), (8,24), (9, 18), (10, 15), (12, 12)$, the last of which gives $c=d$ which is bad.
$X/b \le 2$ gives contradiction with $X/b > X/a$.
$X/a=1$ is impossible as $X/b, X/c, X/d=0$ so we have exhausted all solutions.

Thus, our solutions are: $(X/a, X/b, X/c, X/d)=(1, 2, 3, 6), (2, 4, 5, 20), (2, 4, 6, 12), (2, 3, 7,42), (2, 3, 8, 24), (2, 3, 9, 18), (2, 3, 10, 15)$ for which $(2,4,6,12)$ doesn't work because it doesn't give $X$ as the LCM.

These solutions correspond to: $$\boxed{(a,b,c,d)= (6k, 3k, 2k, k),(10k, 5k, 4k, k), (21k, 14k, 6k, k), (12k, 8k, 3k, k), (9k, 6k, 2k, k), (15k, 10k, 3k, 2k)}$$ for $k\in\mathbb{Z}^+$
Frankly, my dear, I don't give a damn.

User avatar
Kazi_Zareer
Posts: 86
Joined: Thu Aug 20, 2015 7:11 pm
Location: Malibagh,Dhaka-1217

Re: BDMO national 2016, junior 10

Unread post by Kazi_Zareer » Tue Jan 31, 2017 10:01 pm

ahmedittihad wrote:Note that this is equivalent to $a,b,c,d\mid a+b+c+d$ or $\text{lcm}(a,b,c,d)\mid a+b+c+d$. Letting $\text{lcm}(a,b,c,d)=X$, we want, $\dfrac{a}{X}+\dfrac{b}{X}+\dfrac{c}{X}+\dfrac{d}{X}=\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=k\in\mathbb{Z}^+$. The denominators are all integers so we have only four cases: $k=1, 2, 3, 4$ and this becomes a classic Diophantine problem...

If $k=4$ then $X/a=X/b=X/c=X/d=1$ so $a=b=c=d$ so they are not distinct, contradiction.

If $k=3$ then WLOG $X/a=X/b=1$, $X/c=X/d=2$ so $a=b$ which is also bad.

If $k=2$ then $X/a\le 2$ else $\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{4}{3} < 2$.
If $X/a=2$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{3}{2}$ where $X/b \le 2$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le 1 < \dfrac{3}{2}$. However this contradicts $X/a < X/b$ so no solutions.
Then we must have $X/a=1$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=1$ where $X/b \le 3$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{3}{4} < 1$.
If $X/b=3$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{2}{3}$ implies $2X/c\cdot X/d - 3X/c-3X/d =0 $implies $(2X/c-3)(2X/d-3)=9$ which has the solutions $X/c=2, X/d=6$ which doesn't work as $X/b > X/c$ or $X/c=X/d=3$ which doesn't work as $c=d$.
Thus $X/b=2$ which gives $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{2}$ implies $(X/c-2)(X/d-2)=4$ which has solutions $(X/c, X/d)=(3, 6), (4,4)$ and the last solution doesn't work since $c=d$.
Finally $X/b \le 1$ doesn't work as $a=b$.

$k=1$ is the interesting and tedious case. WLOG $X/a\le X/b\le X/c\le X/d$, then $X/a\le 4$ else $\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{4}{5} < 1$. If $X/a=4$ then $X/b=X/c=X/d=4$ which is bad because non-distinct.
If $X/a=3$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{2}{3}$, for which $X/b\le 4$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} = \dfrac{3}{5} < \dfrac{2}{3}$.
If $X/b = 4$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d} = 5/12$ and so $5\cdot X/c\cdot X/d -12X/c-12X/d =0$ implies $ (5X/c-12)(5X/d-12)=144$ and after bashing factors (eww) the only solutions are $5X/c-12=3,5X/d-12=48$ and $5X/c-12=8, 5X/d-12=18$ for which $X/c=3$ and $X/d=12$ which doesn't work as $X/a=X/c$, or $X/c=4$ and $X/d=6$ which also doesn't work as $X/b=X/c$.
If $X/b=3$ then $a=b$ which doesn't work, and if $X/b < 3$ then $X/b < X/a$ which defies the condition.
Thus $X/a=2$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{2}$ for which $X/b \le 6$, else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{3}{7} < \dfrac{1}{2}$.
If $X/b=6$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d} = 1/3 $implies $X/c\cdot X/d -3X/c-3X/d=0 $implies $(X/c-3)(X/d-3)=9$ which has the solutions $X/c-3=1$, $X/d-3=9$ which gives $X/c=4$, $X/d=12$ which doesn't work as $X/c < X/b$ or $X/c-3=3$, $X/d-3=3$ which doesn't work as $c=d$.
If $X/b=5$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{3}{10}$ implies $3\cdot X/c\cdot X/d - 10X/c-10X/d=0$ implies $(3X/c-10)(3X/d-10)=100$ which only has the solutions $3X/c-10 =2, 3X/d-10 = 50$ or $X/c=4$ and $X/d=20$ which doesn't contradicts $X/b < X/c$; and $3X/c-10=5, 3X/d-10=20$ which gives $X/c=5$ and $X/d=10$ which gives $b=c$ which doesn't work.
If $X/b=4$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{4}$ so $(X/c-4)(X/d-4)=16$ which has solutions $(X/c,X/d)=(5,20), (6, 12), (8,8)$ the last which gives $c=d$ which is bad.
If $X/b=3$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{6}$ so $(X/c-6)(X/d-6)=36$ which has solutions $(X/c, X/d)=(7,42), (8,24), (9, 18), (10, 15), (12, 12)$, the last of which gives $c=d$ which is bad.
$X/b \le 2$ gives contradiction with $X/b > X/a$.
$X/a=1$ is impossible as $X/b, X/c, X/d=0$ so we have exhausted all solutions.

Thus, our solutions are: $(X/a, X/b, X/c, X/d)=(1, 2, 3, 6), (2, 4, 5, 20), (2, 4, 6, 12), (2, 3, 7,42), (2, 3, 8, 24), (2, 3, 9, 18), (2, 3, 10, 15)$ for which $(2,4,6,12)$ doesn't work because it doesn't give $X$ as the LCM.

These solutions correspond to: $$\boxed{(a,b,c,d)= (6k, 3k, 2k, k),(10k, 5k, 4k, k), (21k, 14k, 6k, k), (12k, 8k, 3k, k), (9k, 6k, 2k, k), (15k, 10k, 3k, 2k)}$$ for $k\in\mathbb{Z}^+$
Frankly, my dear, did you type this whole solution?! Great patience indeed, man! :)
We cannot solve our problems with the same thinking we used when we create them.

dshasan
Posts: 66
Joined: Fri Aug 14, 2015 6:32 pm
Location: Dhaka,Bangladesh

Re: BDMO national 2016, junior 10

Unread post by dshasan » Tue Jan 31, 2017 10:19 pm

ahmedittihad wrote:Note that this is equivalent to $a,b,c,d\mid a+b+c+d$ or $\text{lcm}(a,b,c,d)\mid a+b+c+d$. Letting $\text{lcm}(a,b,c,d)=X$, we want, $\dfrac{a}{X}+\dfrac{b}{X}+\dfrac{c}{X}+\dfrac{d}{X}=\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=k\in\mathbb{Z}^+$. The denominators are all integers so we have only four cases: $k=1, 2, 3, 4$ and this becomes a classic Diophantine problem...

If $k=4$ then $X/a=X/b=X/c=X/d=1$ so $a=b=c=d$ so they are not distinct, contradiction.

If $k=3$ then WLOG $X/a=X/b=1$, $X/c=X/d=2$ so $a=b$ which is also bad.

If $k=2$ then $X/a\le 2$ else $\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{4}{3} < 2$.
If $X/a=2$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{3}{2}$ where $X/b \le 2$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le 1 < \dfrac{3}{2}$. However this contradicts $X/a < X/b$ so no solutions.
Then we must have $X/a=1$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=1$ where $X/b \le 3$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{3}{4} < 1$.
If $X/b=3$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{2}{3}$ implies $2X/c\cdot X/d - 3X/c-3X/d =0 $implies $(2X/c-3)(2X/d-3)=9$ which has the solutions $X/c=2, X/d=6$ which doesn't work as $X/b > X/c$ or $X/c=X/d=3$ which doesn't work as $c=d$.
Thus $X/b=2$ which gives $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{2}$ implies $(X/c-2)(X/d-2)=4$ which has solutions $(X/c, X/d)=(3, 6), (4,4)$ and the last solution doesn't work since $c=d$.
Finally $X/b \le 1$ doesn't work as $a=b$.

$k=1$ is the interesting and tedious case. WLOG $X/a\le X/b\le X/c\le X/d$, then $X/a\le 4$ else $\dfrac{1}{X/a}+\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{4}{5} < 1$. If $X/a=4$ then $X/b=X/c=X/d=4$ which is bad because non-distinct.
If $X/a=3$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{2}{3}$, for which $X/b\le 4$ else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} = \dfrac{3}{5} < \dfrac{2}{3}$.
If $X/b = 4$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d} = 5/12$ and so $5\cdot X/c\cdot X/d -12X/c-12X/d =0$ implies $ (5X/c-12)(5X/d-12)=144$ and after bashing factors (eww) the only solutions are $5X/c-12=3,5X/d-12=48$ and $5X/c-12=8, 5X/d-12=18$ for which $X/c=3$ and $X/d=12$ which doesn't work as $X/a=X/c$, or $X/c=4$ and $X/d=6$ which also doesn't work as $X/b=X/c$.
If $X/b=3$ then $a=b$ which doesn't work, and if $X/b < 3$ then $X/b < X/a$ which defies the condition.
Thus $X/a=2$ then $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{2}$ for which $X/b \le 6$, else $\dfrac{1}{X/b}+\dfrac{1}{X/c}+\dfrac{1}{X/d} \le \dfrac{3}{7} < \dfrac{1}{2}$.
If $X/b=6$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d} = 1/3 $implies $X/c\cdot X/d -3X/c-3X/d=0 $implies $(X/c-3)(X/d-3)=9$ which has the solutions $X/c-3=1$, $X/d-3=9$ which gives $X/c=4$, $X/d=12$ which doesn't work as $X/c < X/b$ or $X/c-3=3$, $X/d-3=3$ which doesn't work as $c=d$.
If $X/b=5$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{3}{10}$ implies $3\cdot X/c\cdot X/d - 10X/c-10X/d=0$ implies $(3X/c-10)(3X/d-10)=100$ which only has the solutions $3X/c-10 =2, 3X/d-10 = 50$ or $X/c=4$ and $X/d=20$ which doesn't contradicts $X/b < X/c$; and $3X/c-10=5, 3X/d-10=20$ which gives $X/c=5$ and $X/d=10$ which gives $b=c$ which doesn't work.
If $X/b=4$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{4}$ so $(X/c-4)(X/d-4)=16$ which has solutions $(X/c,X/d)=(5,20), (6, 12), (8,8)$ the last which gives $c=d$ which is bad.
If $X/b=3$ then $\dfrac{1}{X/c}+\dfrac{1}{X/d}=\dfrac{1}{6}$ so $(X/c-6)(X/d-6)=36$ which has solutions $(X/c, X/d)=(7,42), (8,24), (9, 18), (10, 15), (12, 12)$, the last of which gives $c=d$ which is bad.
$X/b \le 2$ gives contradiction with $X/b > X/a$.
$X/a=1$ is impossible as $X/b, X/c, X/d=0$ so we have exhausted all solutions.

Thus, our solutions are: $(X/a, X/b, X/c, X/d)=(1, 2, 3, 6), (2, 4, 5, 20), (2, 4, 6, 12), (2, 3, 7,42), (2, 3, 8, 24), (2, 3, 9, 18), (2, 3, 10, 15)$ for which $(2,4,6,12)$ doesn't work because it doesn't give $X$ as the LCM.

These solutions correspond to: $$\boxed{(a,b,c,d)= (6k, 3k, 2k, k),(10k, 5k, 4k, k), (21k, 14k, 6k, k), (12k, 8k, 3k, k), (9k, 6k, 2k, k), (15k, 10k, 3k, 2k)}$$ for $k\in\mathbb{Z}^+$
Thanks that you took your time and wrote down the whole solution. A question, how long did it take?
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.

- Charles Caleb Colton

User avatar
ahmedittihad
Posts: 147
Joined: Mon Mar 28, 2016 6:21 pm

Re: BDMO national 2016, junior 10

Unread post by ahmedittihad » Tue Jan 31, 2017 10:49 pm

I knew this problem was pretty much bland and disgusting. So, I just copied the solution from AOPS. Just copying took me 15 minutes. Allah knows how much time it took for the person to write. :P
Frankly, my dear, I don't give a damn.

dshasan
Posts: 66
Joined: Fri Aug 14, 2015 6:32 pm
Location: Dhaka,Bangladesh

Re: BDMO national 2016, junior 10

Unread post by dshasan » Tue Jan 31, 2017 11:07 pm

ahmedittihad wrote:I knew this problem was pretty much bland and disgusting. So, I just copied the solution from AOPS. Just copying took me 15 minutes. Allah knows how much time it took for the person to write. :P
Cheeky :mrgreen:
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.

- Charles Caleb Colton

User avatar
Kazi_Zareer
Posts: 86
Joined: Thu Aug 20, 2015 7:11 pm
Location: Malibagh,Dhaka-1217

Re: BDMO national 2016, junior 10

Unread post by Kazi_Zareer » Wed Feb 01, 2017 12:55 am

ahmedittihad wrote:I knew this problem was pretty much bland and disgusting. So, I just copied the solution from AOPS. Just copying took me 15 minutes. Allah knows how much time it took for the person to write. :P
Haha! :lol: It may be a well known NT problem. So sad that in bdmo national 2016 Junior Category's some problems(especially, The art gallery problem) were given from various well known resources.
We cannot solve our problems with the same thinking we used when we create them.

Post Reply