Let $n$ be an integer such that $n > 3$. Suppose that we choose three numbers from the set $\{1, 2, \ldots, n\}$. Using each of these three numbers only once and using addition, multiplication, and parenthesis, let us form all possible combinations. (a) Show that if we choose all three numbers greater than $\frac{n}{2}$, then the values of these combinations are all distinct. (b) Let $p$ be a prime number such that $p \leq \sqrt{n}$. Show that the number of ways of choosing three numbers so that the smallest one is $p$ and the values of the combinations are not all distinct is precisely the number of positive divisors of $p - 1$.
Problem
Source: APMO 1992
Tags: combinatorics
06.05.2009 15:30
The possible combinations of $ (a,b,c)$ are $ a+b+c, c+ab, b+ca, a+bc,(b+c)a,(c+a)b,(a+b)c,abc$. If $ a<b<c$, then $ a+b+c < c+ab < b+ca < a+bc$, $ (b+c)a<(c+a)b<(a+b)c<abc$, $ b+ca<(c+a)b$, $ a+bc<(c+a)b$. So some combinations are equal iff $ a+bc = a(b+c)$. (a) If $ \frac{n}2<a<b<c\le n$, then $ a>\frac{c}2$. So $ a(b+c-1) > \frac{c}2(b+b) = bc$, i.e., $ a(b+c) > a+bc$. Thus all combinations are distinct. (b) Let $ p<b<c$ be the chosen numbers. Also let $ d$ be the positive integer such that $ b=p+d$. We have $ p+bc = p(b+c)$. Therefore $ p+ (p+d)c = p(p+c+d)$ and we get $ c = p+\frac{p(p-1)}d$. But $ b<c$, so $ p+d < p+\frac{p(p-1)}d$, i.e., $ d^2<p(p-1)$. Therefore $ d<p$. But $ d$ must divide $ p(p-1)$, so $ d$ divides $ p-1$. Clearly, for any divisor of $ p-1$, we get a satisfying triple. So we are done.
17.09.2021 10:31
Босинг брат ман хам шундай ишладим
09.05.2024 00:23
Listing out all of the possibilites with $a<b<c$, we see that the only way two combinations are equal is if $a(b+c)=a+bc$. (a) If $\tfrac{n}{2}<a<b<c<n$, we see that $a>\tfrac{c}{2}$. Thus, \[a(b+c)-a > \frac{c}{2} (b+c-1) \ge \frac{c}{2} \cdot 2b = bc.\] (b) Say the numbers are $p<q<r$, with $p+x = q$. We need \[p(p+x+r) = p+(p+x)r,\] which rearranges to \[r = \frac{p^2-p}{x}+p.\] Moreover, we know that $q<r$, so we can bound $x<p$. Thus, $x \mid p-1$, and each divisor of $p-1$ corresponds to a valid triple. $\square$