Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1984 USAMO Problems/Problem 2"

m
(Added solution (aops111 don't worry your solution is great))
 
(One intermediate revision by one other user not shown)
Line 7: Line 7:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
a) We claim that for any numbers <math>p_1</math>, <math>p_2</math>, ... <math>p_n</math>, <math>p_1^{n!}, p_2^{n!}, ... p_n^{n!}</math> will satisfy the condition, which holds for any number <math>n</math>.
 +
 
 +
Since <math>\sqrt[n] ab = \sqrt[n] a * \sqrt[n] b</math>, we can separate each geometric mean into the product of parts, where each part is the <math>k</math>th root of each member of the subset and the subset has <math>k</math> members.
 +
 
 +
Assume our subset has <math>k</math> members. Then, we know that the <math>k</math>th root of each of these members is an integer (namely <math>p^{n!/k}</math>), because <math>k \leq n</math> and thus <math>k  |  n!</math>. Since each root is an integer, the geometric mean will also be an integer.
 +
 
 +
b) If we define <math>q</math> as an arbitrarily large number, and <math>x</math> and <math>y</math> as numbers in set <math>S</math>, we know that <math>{\sqrt[q]{\frac{x}{y}}}</math> is irrational for large enough <math>q</math>, meaning that it cannot be expressed as the fraction of two integers. However, both the geometric mean of the set of <math>x</math> and <math>q-1</math> other arbitrary numbers in <math>S</math> and the set of <math>y</math> and the same other <math>q-1</math> numbers are integers, so since the other numbers cancel out, the geometric means divided, or <math>{\sqrt[q]{\frac{x}{y}}}</math>, must be rational. This is a contradiction, so no such infinite <math>S</math> is possible.
 +
 
 +
-aops111 (first solution dont bully me)
 +
 
 +
==Solution 2==
 +
(i) The solution is the same as in the first solution
 +
 
 +
(ii)
 +
Let <math>p</math> and <math>q</math> be some prime numbers, and let <math>v_p(n)</math> be the largest number such that <math>p^{v_p(n)}</math> divides <math>n</math>. <math>v_p(n)</math> is also the exponent of <math>p</math> in the prime factorization of <math>n</math> (or <math>0</math>, if <math>p</math> isn't a divisor of <math>n</math>). Then, because <math>S</math> is infinite, we can choose <math>q-1</math> numbers <math>a_1, a_2, ... a_{q-1}</math> in <math>S</math> such that <math>v_p(a_i)</math> all give the same remainder when divided by <math>q</math>. (Otherwise, because <math>v_p(n) \mod q</math> has <math>q</math> distinct values, <math>S</math> could contain at most <math>q(p-2)</math> numbers, which is finite.) Call that remainder <math>r</math>.
 +
 
 +
Now take some integer <math>b</math> in <math>S</math>, not part of the other <math>q-1</math> values. Together, their product must be a <math>q</math>th power, meaning
 +
<math>q|v_p(a_1a_2...a_{q-1}b)</math> Thus, <math>v_p(a_1a_2...a_{q-1}b) \equiv 0 \pmod q</math>. It can be seen easily that for two positive integers <math>x</math> and <math>y</math> we have <math>v_p(ab) = v_p(a) + v_p(b)</math>, and by definition <math>v_p(a_i) \equiv r \pmod q</math>, so we can write <math>v_p(b) + (q-1)r \equiv 0 \pmod q</math>. Adding <math>r</math> to both sides we have <math>v_p(b) \equiv v_p(b) + qr \equiv r \pmod q</math>.
 +
 
 +
The choice of <math>b</math> was arbitrary, meaning for all numbers <math>n</math> in <math>S</math>, <math>v_p(n)</math> modulo <math>q</math> is the constant <math>r</math>, whether part of <math>a_1, a_2... a_{q-1}</math> or not. The choice of <math>q</math> was also arbitrary, thus for two integers <math>m</math> and <math>n</math> in <math>S</math>, <math>v_p(m) = v_p(n)</math>. Otherwise, we could pick <math>q</math> larger than both values, and get a contradiction. Thus for all  numbers <math>n</math> in <math>S</math>, <math>v_p(n)</math> is constant. The choice of <math>p</math> was also arbitrary, meaning any two distinct numbers in <math>S</math> 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 <math>S</math> exists.
 +
 
 +
-Circling
  
 
== See Also ==
 
== See Also ==

Latest revision as of 03:12, 23 October 2022

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 (Problems • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1984_USAMO_Problems/Problem_2&oldid=179374"