1984 USAMO Problems/Problem 2

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

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

Page

Toolbox

Search

1984 USAMO Problems/Problem 2

Contents

Problem

Solution

Solution 2

See Also