Difference between revisions of "1984 USAMO Problems/Problem 2"
(Added solution (aops111 don't worry your solution is great)) |
|||
Line 16: | Line 16: | ||
-aops111 (first solution dont bully me) | -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 02:12, 23 October 2022
Contents
Problem
The geometric mean of any set of non-negative numbers is the -th root of their product.
For which positive integers is there a finite set of distinct positive integers such that the geometric mean of any subset of is an integer?
Is there an infinite set of distinct positive integers such that the geometric mean of any finite subset of is an integer?
Solution
a) We claim that for any numbers , , ... , will satisfy the condition, which holds for any number .
Since , we can separate each geometric mean into the product of parts, where each part is the th root of each member of the subset and the subset has members.
Assume our subset has members. Then, we know that the th root of each of these members is an integer (namely ), because and thus . Since each root is an integer, the geometric mean will also be an integer.
b) If we define as an arbitrarily large number, and and as numbers in set , we know that is irrational for large enough , meaning that it cannot be expressed as the fraction of two integers. However, both the geometric mean of the set of and other arbitrary numbers in and the set of and the same other numbers are integers, so since the other numbers cancel out, the geometric means divided, or , must be rational. This is a contradiction, so no such infinite is possible.
-aops111 (first solution dont bully me)
Solution 2
(i) The solution is the same as in the first solution
(ii) Let and be some prime numbers, and let be the largest number such that divides . is also the exponent of in the prime factorization of (or , if isn't a divisor of ). Then, because is infinite, we can choose numbers in such that all give the same remainder when divided by . (Otherwise, because has distinct values, could contain at most numbers, which is finite.) Call that remainder .
Now take some integer in , not part of the other values. Together, their product must be a th power, meaning Thus, . It can be seen easily that for two positive integers and we have , and by definition , so we can write . Adding to both sides we have .
The choice of was arbitrary, meaning for all numbers in , modulo is the constant , whether part of or not. The choice of was also arbitrary, thus for two integers and in , . Otherwise, we could pick larger than both values, and get a contradiction. Thus for all numbers in , is constant. The choice of was also arbitrary, meaning any two distinct numbers in 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 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.