Suppose a, b, c, and d are distinct positive integers such that ab divides bc, bc divides cd, and cd divides da. (a) Is it possible to determine which of the numbers a, b, c, d is the smallest? (b) Is it possible to determine which of the numbers a, b, c, d is the largest?
Problem
Source: XIX Olimpíada Matemática Rioplatense (2010)
Tags: inequalities, number theory, number theory unsolved
Binomial-theorem
22.10.2011 22:11
ab|bc|cd|da is given.
Lemma 1: ab|bc⟹ a>b<c or c<b>a, besides for when a|b or b|a.
Proof: This is directly true from gcd(ab,bc)=gcd(a,b)min{b,c}∀a\cancel|b,b\cancel|a, which is an extension to a Lemma in Problems of Number Theory in Mathematical Competitions
Proof of this: Let gcd(a,b)=m for some integer m. Hence, we get m|a and m|b. Let a=km and b=lm for some integers k and l. Note that gcd(k,l)=1, because if gcd(k,l)≠1, then we would have gcd(a,b)>m. Now note that gcd(ab,bc)=gcd((km)b,(lm)c))=mmin(b,c)gcd(kb,lc), which can be found using the lemma gcd(ad,bd)=dgcd(a,b) from Problems of Number Theory in Mathematical Competitions . From here, use the third and final Lemma from Problems of Number Theory in Mathematical Competitions, which is gcd(k,l)=1⟹gcd(kb,lc)=1, which can be proven by noting that if k and l share no common divisors, then continuing to multiply the numbers won't result in having any common divisors. Hence, gcd(kb,lc)=1, and we get gcd(a,b)=gcd((km)b,(lm)c))=mmin(b,c).
Note that this equation does not hold true for when a|b or when b|a, because, for example when we have a=kb for some k, we have gcd(kb,b)=bgcd(k,1)=b. Now note that gcd(a,b)min(b,c) is not necessarily going to be equal to b, because we would have to have min(b,c)=1 for this to be true. ◻.
Hence since we want gcd(ab,bc)=ab, hence we have gcd(a,b)min{b,c}=ab. Make the observation that when b<c, we have gcd(a,b)b=ab⟹gcd(a,b)=a⟹a|a and b|a, hence a≥b<c. When b>c, we have gcd(a,b)c=ab, which implies that a|gcd(a,b). This is true ⟺a|b, hence we have c<b≥a in this case. Since b≠a, we must have c<b>a in the second case, and a>b<c in the first case.
Lemma 2: bc|cd⟹ b>c<d or d<c>b, besides for when b|c or c|b
Proof: There are no restrictions on a,b,c from Lemma 1, besides for a\cancel|b and b\cancel|a, that do not apply here, hence from Lemma 1, this is true.
Lemma 3: Further note that cd|da implies c>d<a or a<d>c, besides for when c|d or d|c.
Proof: Lemma 2
Note that inequality c>d<a from Lemma 3 is satisfied ⟺d<c>b from Lemma 2, which is true ⟺a>b<c from Lemma 1. From this, we have a>b,c>b,c>d,a>d. Hence, we know that a and c are greater than b and d respectively in this case, but we don't have any comparison between a and c.
Now, note that if we use the inequality a<d>c from Lemma 3, we have to have b>c<d from Lemma 2, and we must have c<b>a from Lemma 1. Hence, we have d>a,d>c,b>c,b>a, hence we must have d and b being greater than both c and a, but we have no comparison between d and b and c and a respectfully.
Because in both case 1 and case 2, we can't determine the maximum and minimum of a,b,c,d, it is impossible to find the maximum/minimum of a,b,c,d for this case.
We now account for when a|b or b|a, and b|c or c|b, and c|d or d|c.
Note that it is impossible to determine which number is greatest/smallest in this case, because a|b implies that b>a (because b≠a), and b|a implies that a>b. Creating all the inequalities gives us:
b>a or a>b
c>b orb>c
d>c or c>d
From these inequalities, we can find that b can be the maximum, (with case 1, 2, 2), c could be the maximum (cases 1, 1, 2), a could be the maximum (cases 2,2,2), or d could be the maximum (cases 1,1, 1).
Also, we could have a being the minimum (1, 1, 1), b being the minimum (cases 2, 1, 1), c being the minimum (cases 2, 2, 1), or d being the minimum (cases 2, 2,2).
Because in both cases that we have, and we have proven it is impossible to find the maximum/minimum in both cases, we are done ◻
Remark: Thanks a lot to Problems of Number Theory in Mathematical Competitions for the Lemma used in Lemma 1, which I extended to use in Lemma 1. Also, thanks to my dad for some help on this problem (mainly the case 2 inequalities). Remark 2: Changed some things in solution, some recommended by dragon96/realized something was incorrect.
littletush
04.12.2011 07:08
I will give an example for (2),and (1) is analogous. for a max:a=pt+3,b=pt,c=pt+1,d=pt+2; for d max:a=pt−1,b=p,c=ptp,d=pt where p is a prime,t sufficiently large.