Difference between revisions of "2015 USAMO Problems"
(→Problem 6) |
|||
(4 intermediate revisions by 3 users not shown) | |||
Line 23: | Line 23: | ||
===Problem 4=== | ===Problem 4=== | ||
− | Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively, | + | Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively, or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively. |
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves. | Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves. | ||
Line 37: | Line 37: | ||
===Problem 6=== | ===Problem 6=== | ||
− | Consider <math>0<\lambda<1</math>, and let <math>A</math> be a multiset of positive integers. Let <math>A_n=\{a\in A: a\leq n\}</math>. Assume that for every <math>n\in\mathbb{N}</math>, the set <math>A_n</math> contains at most <math>n\lambda</math>numbers. Show that there are infinitely many <math>n\in\mathbb{N}</math> for which the sum of the elements in <math>A_n</math> is at most <math>\frac{n(n+1)}{2}\lambda</math>. (A multiset is a set-like collection of elements in which order is ignored, but repetition of elements is allowed and multiplicity of elements is significant. For example, multisets <math>\{1, 2, 3\}</math> and <math>\{2, 1, 3\}</math> are equivalent, but <math>\{1, 1, 2, 3\}</math> and <math>\{1, 2, 3\}</math> differ.) | + | Consider <math>0<\lambda<1</math>, and let <math>A</math> be a multiset of positive integers. Let <math>A_n=\{a\in A: a\leq n\}</math>. Assume that for every <math>n\in\mathbb{N}</math>, the set <math>A_n</math> contains at most <math>n\lambda</math> numbers. Show that there are infinitely many <math>n\in\mathbb{N}</math> for which the sum of the elements in <math>A_n</math> is at most <math>\frac{n(n+1)}{2}\lambda</math>. (A multiset is a set-like collection of elements in which order is ignored, but repetition of elements is allowed and multiplicity of elements is significant. For example, multisets <math>\{1, 2, 3\}</math> and <math>\{2, 1, 3\}</math> are equivalent, but <math>\{1, 1, 2, 3\}</math> and <math>\{1, 2, 3\}</math> differ.) |
+ | |||
+ | [[2015 USAMO Problems/Problem 6|Solution]] | ||
+ | |||
+ | {{USAMO newbox|year= 2015 |before=[[2014 USAMO]]|after=[[2016 USAMO]]}} | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 21:11, 16 December 2018
Contents
Day 1
Problem 1
Solve in integers the equation
Problem 2
Quadrilateral is inscribed in circle with and . Let be a variable point on segment . Line meets again at (other than ). Point lies on arc of such that is perpendicular to . Let denote the midpoint of chord . As varies on segment , show that moves along a circle.
Problem 3
Let , where . Each of the subsets of is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set , we then write for the number of subsets of T that are blue.
Determine the number of colorings that satisfy the following condition: for any subsets and of ,
Day 2
Problem 4
Steve is piling indistinguishable stones on the squares of an grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions for some , such that and . A stone move consists of either removing one stone from each of and and moving them to and respectively, or removing one stone from each of and and moving them to and respectively.
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.
How many different non-equivalent ways can Steve pile the stones on the grid?
Problem 5
Let be distinct positive integers such that . Show that is a composite number.
Problem 6
Consider , and let be a multiset of positive integers. Let . Assume that for every , the set contains at most numbers. Show that there are infinitely many for which the sum of the elements in is at most . (A multiset is a set-like collection of elements in which order is ignored, but repetition of elements is allowed and multiplicity of elements is significant. For example, multisets and are equivalent, but and differ.)
2015 USAMO (Problems • Resources) | ||
Preceded by 2014 USAMO |
Followed by 2016 USAMO | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.