9367 66
9367 66
Let n be any positive integer and 1<=x_1<x_2<...<x_(n+1)<=2n, where each x_i is an integer. Which of the following must be true?
I There is an x_i that is the square of an integer.
II There is an i such that x_(i+1)=x_i+1
III There is an x_i that is prime.
(Answer: B)
I is false, because 1<=2<3<5<6<7<8<10<=12, for n=6.
II is true. (I think it is the famous question that Paul Erdos asked 8yearold Posa)
Define n "boxes" as follows: 1st box can only contain {1,2}, 2nd box can only contain {3,4}, nth box can only contain {2n1,2n}.
Then when the n+1 numbers are slotted into the n boxes, by the Pigeonhole Principle, at least one box must have 2 numbers.
III Is false (why?)
I can only reason it out qualitatively that primes get rarer and rarer, as n gets bigger and bigger. So, if we choose a huge n, there is no guarantee that there is a prime among the n+1 integers.
Does anyone have a proof of III being false?
Sincere thanks.
I There is an x_i that is the square of an integer.
II There is an i such that x_(i+1)=x_i+1
III There is an x_i that is prime.
(Answer: B)
I is false, because 1<=2<3<5<6<7<8<10<=12, for n=6.
II is true. (I think it is the famous question that Paul Erdos asked 8yearold Posa)
Define n "boxes" as follows: 1st box can only contain {1,2}, 2nd box can only contain {3,4}, nth box can only contain {2n1,2n}.
Then when the n+1 numbers are slotted into the n boxes, by the Pigeonhole Principle, at least one box must have 2 numbers.
III Is false (why?)
I can only reason it out qualitatively that primes get rarer and rarer, as n gets bigger and bigger. So, if we choose a huge n, there is no guarantee that there is a prime among the n+1 integers.
Does anyone have a proof of III being false?
Sincere thanks.

 Posts: 27
 Joined: Sun Oct 17, 2010 4:57 am
Re: 9367 66
For n=5, you can pick 1, 4, 6, 8, 9, 10.

 Posts: 44
 Joined: Tue Aug 09, 2011 6:18 pm
Re: 9367 66
To discount the third option, consider the Prime Number Theorem. Let $$\pi(x)$$ denote the number of prime numbers less than $$x$$. Then
$$\pi(x) \approx \frac{x}{\ln{x}}$$.
Eventually $$\frac{2x}{\ln{2x}} << x$$ so option III is false.
$$\pi(x) \approx \frac{x}{\ln{x}}$$.
Eventually $$\frac{2x}{\ln{2x}} << x$$ so option III is false.
Re: 9367 66
Let n be a positive integer. Let 2, 3, ..., pk be a listing of all primes less than or equal to n.
Then, for i in the range [1,n], the positive integer
Q(i) = 2*3*...*pk + i
is composite.
This fact shows that there are arbitrary stretches of composite integers. This is a useful thing to remember and can easily be extended to show any number of counterexamples to III
Then, for i in the range [1,n], the positive integer
Q(i) = 2*3*...*pk + i
is composite.
This fact shows that there are arbitrary stretches of composite integers. This is a useful thing to remember and can easily be extended to show any number of counterexamples to III

 Posts: 64
 Joined: Fri Nov 04, 2011 12:34 pm
Re: 9367 66
Did you mean for i ∈ [2,n}?JohnDoe wrote:Let n be a positive integer. Let 2, 3, ..., pk be a listing of all primes less than or equal to n.
Then, for i in the range [1,n], the positive integer
Q(i) = 2*3*...*pk + i
is composite.
Also, I don't see how this can be extended to provide a counterexample for III. The density of these composite stretches doesn't seem high enough to allow for choosing n+1 composite numbers in [1, 2n]. Obviously, there do exist n+1 composite numbers in [1, 2n], but that's more a consequence of the prime number theorem than of this particular fact.
You don't even actually need the full power of the PNT. In [1, 2n], n1 integers are composite multiples of 2. All you have to do is find 2 more nonprime numbers in [1, 2n] and you're set.
Re: 9367 66
Have you ever been so far even as decided to look more like, quiquenion?quinquenion wrote:Did you mean for i ∈ [2,n}?JohnDoe wrote:Let n be a positive integer. Let 2, 3, ..., pk be a listing of all primes less than or equal to n.
Then, for i in the range [1,n], the positive integer
Q(i) = 2*3*...*pk + i
is composite.
Also, I don't see how this can be extended to provide a counterexample for III. The density of these composite stretches doesn't seem high enough to allow for choosing n+1 composite numbers in [1, 2n]. Obviously, there do exist n+1 composite numbers in [1, 2n], but that's more a consequence of the prime number theorem than of this particular fact.
You don't even actually need the full power of the PNT. In [1, 2n], n1 integers are composite multiples of 2. All you have to do is find 2 more nonprime numbers in [1, 2n] and you're set.

 Posts: 64
 Joined: Fri Nov 04, 2011 12:34 pm
Re: 9367 66
Huh?JohnDoe wrote: Have you ever been so far even as decided to look more like, quiquenion?
Edited to add: Oh, a 4chan meme. You got me there

 Posts: 44
 Joined: Tue Aug 09, 2011 6:18 pm
Re: 9367 66
I agree. Using the prime number theorem to solve this problem is like using a sledge hammer to break an egg. Your proof is quicker and more elegant. The PNT (as well quinquenion's approach) formalize yoyobarn's intuition that prime numbers are rare.quinquenion wrote: You don't even actually need the full power of the PNT. In [1, 2n], n1 integers are composite multiples of 2. All you have to do is find 2 more nonprime numbers in [1, 2n] and you're set.
Some food for thought: The prime numbers are not "too rare", so being careful doesn't hurt. By which I mean that the following series diverges: $$\sum_{\mbox{p is prime}} \frac{1}{p}$$ . However $$\sum_{n \in \mathbb{N}} \frac{1}{n^2}$$ converges.
This was noted by Euler, who wrote somewhat ambiguously $$\frac{1}{2} + \frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11} + \dots = \log ( \log( \infty))$$
Last edited by Topoltergeist on Thu Jan 12, 2012 10:50 am, edited 1 time in total.
Re: 9367 66
Some more food for thought: the primes do get rarer and rarer however for every n > 1 there is always at least one prime p such that n < p < 2n, this is Bertrand's postulate. I actually thought that III was equivalent to this while I first did this question. Which goes to show that knowing more might actually hurt on the GRE.
Also you have the twin prime conjecture: there are infinitely many pairs of primes (p, p+2). If proven correct this implies that the gaps between primes does not increase as we go towards infinity.
Also you have the twin prime conjecture: there are infinitely many pairs of primes (p, p+2). If proven correct this implies that the gaps between primes does not increase as we go towards infinity.