Difference between revisions of "1983 USAMO Problems/Problem 5"
(I'll leave my progress up for anyone who wants to finish the problem. I have a solution sketch in mind, but I need sleep now.) |
(→Solution) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | + | Let <math>I</math> be an open interval of length <math>1/n</math> and <math>F_n</math> the set of fractions <math>p/q\in I</math> with <math>p,q\in\mathbb{Z}</math>, <math>\gcd(p,q)=1</math> and <math>1\leq q\leq n</math>. | |
− | + | Assume that <math>\frac{p}{q}\in F_n</math>. If <math>k\in\mathbb{Z}</math> is such that <math>1\leq kq\leq n</math>, and <math>p'\in\mathbb{Z}</math> is such that <math>\gcd(p',kq)=1</math>, then | |
+ | <cmath>\left|\frac{p}{q}-\frac{p'}{kq}\right|\geq\frac{1}{kq}\geq \frac{1}{n}</cmath> | ||
+ | Therefore <math>\frac{p'}{kq}\notin I\supset F_n</math>. This means that <math>\frac{p}{q}</math> is the only fraction in <math>F_n</math> with denominator <math>q</math> or multiple of <math>q</math>. | ||
− | + | Therefore, from each of the pairs in <math>P=\left\{(k,2k):\ 1\leq k\leq \left\lfloor\frac{n+1}{2}\right\rfloor\right\}</math> at most one element from each can be a denominator of a fraction in <math>F_n</math>. | |
− | {{ | + | Hence <math>|F_n|\leq |P|\leq\frac{n+1}{2}</math> |
== See Also == | == See Also == |
Latest revision as of 10:23, 7 December 2022
Problem
Consider an open interval of length on the real number line, where is a positive integer. Prove that the number of irreducible fractions , with , contained in the given interval is at most .
Solution
Let be an open interval of length and the set of fractions with , and .
Assume that . If is such that , and is such that , then Therefore . This means that is the only fraction in with denominator or multiple of .
Therefore, from each of the pairs in at most one element from each can be a denominator of a fraction in .
Hence
See Also
1983 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
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.