Difference between revisions of "1989 IMO Problems/Problem 5"

Latest revision as of 00:55, 24 August 2024

Problem

Prove that for each positive integer $n$ there exist $n$ consecutive positive integers none of which is an integral power of a prime number.

Solution 1

There are at most $1+\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+...+\sqrt[\left\lfloor \log_2(n)\right\rfloor]{n} \leq 1+ \sqrt n log_2(n)$ 'true' powers $m^k , k\geq 2$ in the set $\{1,2,...,n\}$ . So when $p(n)$ gives the amount of 'true' powers $\leq n$ we get that $\lim_{n \to \infty} \frac{p(n)}{n} = 0$ .

Since also $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$ , we get that $\lim_{n \to \infty} \frac{p(n)+\pi(n)}{n} = 0$ . Now assume that there is no 'gap' of lenght at least $k$ into the set of 'true' powers and the primes. Then this would give that $\frac{p(n)+\pi(n)}{n} \geq \frac{1}{k}$ for all $n$ in contrary to the above (at east this proves a bit more).

Edit: to elementarize the $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$ part: Look $\mod (k+1)!$ . Then all numbers in the residue classes $2,3,4,...,k+1$ are not primes (except the smallest representants sometimes). So when there wouldn't exist a gap of length $k$ , there has to be a 'true' power in each of these gaps of the prime numbers, so at least one power each $(k+1)!$ numbers, again contradicting $\lim_{n \to \infty} \frac{p(n)}{n} = 0$ .

This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [1]

Solution 2

By the Chinese Remainder Theorem, there exists $x$ such that: $x \equiv -1\;mod\;p_1 q_1\\ x \equiv -2\;mod\;p_2 q_2\\ x \equiv -3\;mod\;p_3 q_3\\ ...\newline x \equiv -n\;mod\;p_n q_n$ where $p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$ are distinct primes. The $n$ consecutive numbers $x+1, x+2, ..., x+n$ each have at least two prime factors, so none of them can be expressed as an integral power of a prime.

Solution 3

OG, If $n=1$ , then select any composite number $Claim:$ If $n>1$ , then the consectutive number $(2n+3)!+2, (2n+3)!+3 \cdots (2n+3)!+(n+1)$ , give the desired $n$ consecutive numbers as each of the numbers are divisible by at least 2 primes. Proof: Each of the numbers are $(2n+3)!+k, 2 \leq k \leq n+1$ , Now since $2k \leq (2n+3)! \implies k^2|(2n+3)$ , Thus $(2n+3)!+k= k(kq+1)$ , which clearly has atleast 2 prime divisors. Hence DONE, OG

@@ Line 1: / Line 1: @@
 ==Problem==
-Let <math>n\geq3</math> and consider a set <math>E</math> of <math>2n − 1</math> distinct points on a circle. Suppose that exactly <math>k</math> of these points are to be colored black. Such a coloring is “good” if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly <math>n</math> points from set <math>E</math>. Find the smallest value of <math>k</math> such that every such coloring of <math>k</math> points of <math>E</math> is good.
+Prove that for each positive integer <math> n</math> there exist <math> n</math> consecutive positive integers none of which is an integral power of a prime number.
+==Solution 1==
+There are at most <math>1+\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+...+\sqrt[\left\lfloor \log_2(n)\right\rfloor]{n} \leq 1+ \sqrt n log_2(n)</math> 'true' powers <math>m^k , k\geq 2</math> in the set <math>\{1,2,...,n\}</math>. So when <math>p(n)</math> gives the amount of 'true' powers <math>\leq n</math> we get that <math>\lim_{n \to \infty} \frac{p(n)}{n} = 0</math>.
+Since also <math>\lim_{n \to \infty} \frac{\pi(n)}{n} = 0</math>, we get that <math>\lim_{n \to \infty} \frac{p(n)+\pi(n)}{n} = 0</math>. Now assume that there is no 'gap' of lenght at least <math>k</math> into the set of 'true' powers and the primes. Then this would give that <math>\frac{p(n)+\pi(n)}{n} \geq \frac{1}{k}</math> for all <math>n</math> in contrary to the above (at east this proves a bit more).
+Edit: to elementarize the <math>\lim_{n \to \infty} \frac{\pi(n)}{n} = 0</math> part:
+Look <math>\mod (k+1)!</math>. Then all numbers in the residue classes <math>2,3,4,...,k+1</math> are not primes (except the smallest representants sometimes). So when there wouldn't exist a gap of length <math>k</math>, there has to be a 'true' power in each of these gaps of the prime numbers, so at least one power each <math>(k+1)!</math> numbers, again contradicting <math>\lim_{n \to \infty} \frac{p(n)}{n} = 0</math>.
+This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [https://aops.com/community/p372297]
+==Solution 2==
+By the [[Chinese Remainder Theorem]], there exists <math>x</math> such that:
+<math>x \equiv -1\;mod\;p_1 q_1\\
+x \equiv -2\;mod\;p_2 q_2\\
+x \equiv -3\;mod\;p_3 q_3\\
+...\newline
+x \equiv -n\;mod\;p_n q_n</math>
+where <math>p_1, p_2, ..., p_n, q_1, q_2, ..., q_n</math> are distinct primes.
+The <math>n</math> consecutive numbers <math>x+1, x+2, ..., x+n</math> each have at least two prime factors, so none of them can be expressed as an integral power of a prime.
+==Solution 3==
+OG, If <math>n=1</math>, then select any composite number
+<math>Claim:</math> If <math>n>1</math>, then the consectutive number <math>(2n+3)!+2, (2n+3)!+3 \cdots (2n+3)!+(n+1)</math>, give the desired <math>n</math> consecutive numbers as each of the numbers are divisible by at least 2 primes.
+Proof:  Each of the numbers are <math>(2n+3)!+k, 2 \leq k \leq n+1</math>, Now since <math>2k \leq (2n+3)! \implies k^2|(2n+3)</math>, Thus <math>(2n+3)!+k= k(kq+1)</math>, which clearly has atleast 2 prime divisors. Hence DONE, OG
+== See Also == {{IMO box|year=1989|num-b=4|num-a=6}}
+[[Category:Olympiad Number Theory Problems]]

1989 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search