Difference between revisions of "1984 USAMO Problems/Problem 2"
Mrdavid445 (talk | contribs) (Blanked the page) |
(Added solution (aops111 don't worry your solution is great)) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
+ | == Problem == | ||
+ | The geometric mean of any set of <math>m</math> non-negative numbers is the <math>m</math>-th root of their product. | ||
+ | <math>\quad (\text{i})\quad</math> For which positive integers <math>n</math> is there a finite set <math>S_n</math> of <math>n</math> distinct positive integers such that the geometric mean of any subset of <math>S_n</math> is an integer? | ||
+ | |||
+ | <math>\quad (\text{ii})\quad</math> Is there an infinite set <math>S</math> of distinct positive integers such that the geometric mean of any finite subset of <math>S</math> is an integer? | ||
+ | |||
+ | ==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 == | ||
+ | {{USAMO box|year=1984|num-b=1|num-a=3}} | ||
+ | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 03: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.