1984 USAMO Problems/Problem 2

Revision as of 03:12, 23 October 2022 by Circling (talk | contribs) (Added solution (aops111 don't worry your solution is great))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

The geometric mean of any set of $m$ non-negative numbers is the $m$-th root of their product.

$\quad (\text{i})\quad$ For which positive integers $n$ is there a finite set $S_n$ of $n$ distinct positive integers such that the geometric mean of any subset of $S_n$ is an integer?

$\quad (\text{ii})\quad$ Is there an infinite set $S$ of distinct positive integers such that the geometric mean of any finite subset of $S$ is an integer?

Solution

a) We claim that for any numbers $p_1$, $p_2$, ... $p_n$, $p_1^{n!}, p_2^{n!}, ... p_n^{n!}$ will satisfy the condition, which holds for any number $n$.

Since $\sqrt[n] ab = \sqrt[n] a * \sqrt[n] b$, we can separate each geometric mean into the product of parts, where each part is the $k$th root of each member of the subset and the subset has $k$ members.

Assume our subset has $k$ members. Then, we know that the $k$th root of each of these members is an integer (namely $p^{n!/k}$), because $k \leq n$ and thus $k  |  n!$. Since each root is an integer, the geometric mean will also be an integer.

b) If we define $q$ as an arbitrarily large number, and $x$ and $y$ as numbers in set $S$, we know that ${\sqrt[q]{\frac{x}{y}}}$ is irrational for large enough $q$, meaning that it cannot be expressed as the fraction of two integers. However, both the geometric mean of the set of $x$ and $q-1$ other arbitrary numbers in $S$ and the set of $y$ and the same other $q-1$ numbers are integers, so since the other numbers cancel out, the geometric means divided, or ${\sqrt[q]{\frac{x}{y}}}$, must be rational. This is a contradiction, so no such infinite $S$ is possible.

-aops111 (first solution dont bully me)

Solution 2

(i) The solution is the same as in the first solution

(ii) Let $p$ and $q$ be some prime numbers, and let $v_p(n)$ be the largest number such that $p^{v_p(n)}$ divides $n$. $v_p(n)$ is also the exponent of $p$ in the prime factorization of $n$ (or $0$, if $p$ isn't a divisor of $n$). Then, because $S$ is infinite, we can choose $q-1$ numbers $a_1, a_2, ... a_{q-1}$ in $S$ such that $v_p(a_i)$ all give the same remainder when divided by $q$. (Otherwise, because $v_p(n) \mod q$ has $q$ distinct values, $S$ could contain at most $q(p-2)$ numbers, which is finite.) Call that remainder $r$.

Now take some integer $b$ in $S$, not part of the other $q-1$ values. Together, their product must be a $q$th power, meaning $q|v_p(a_1a_2...a_{q-1}b)$ Thus, $v_p(a_1a_2...a_{q-1}b) \equiv 0 \pmod q$. It can be seen easily that for two positive integers $x$ and $y$ we have $v_p(ab) = v_p(a) + v_p(b)$, and by definition $v_p(a_i) \equiv r \pmod q$, so we can write $v_p(b) + (q-1)r \equiv 0 \pmod q$. Adding $r$ to both sides we have $v_p(b) \equiv v_p(b) + qr \equiv r \pmod q$.

The choice of $b$ was arbitrary, meaning for all numbers $n$ in $S$, $v_p(n)$ modulo $q$ is the constant $r$, whether part of $a_1, a_2... a_{q-1}$ or not. The choice of $q$ was also arbitrary, thus for two integers $m$ and $n$ in $S$, $v_p(m) = v_p(n)$. Otherwise, we could pick $q$ larger than both values, and get a contradiction. Thus for all numbers $n$ in $S$, $v_p(n)$ is constant. The choice of $p$ was also arbitrary, meaning any two distinct numbers in $S$ have the same prime factorization. By the fundamental theorem of arithmetic, this means the two numbers are the same, contradicting with them being distinct. Thus, no such $S$ exists.

-Circling

See Also

1984 USAMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png