Page 1 of 1

9367 66

Posted: Wed Dec 21, 2011 4:35 am
by yoyobarn
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 8-year-old 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 {2n-1,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.

Re: 9367 66

Posted: Wed Dec 21, 2011 8:09 am
by fireandgladstone
For n=5, you can pick 1, 4, 6, 8, 9, 10.

Re: 9367 66

Posted: Wed Dec 21, 2011 9:09 am
by yoyobarn
Thanks a lot!

Re: 9367 66

Posted: Wed Dec 21, 2011 12:30 pm
by Topoltergeist
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.

Re: 9367 66

Posted: Mon Jan 02, 2012 3:38 pm
by JohnDoe
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

Re: 9367 66

Posted: Mon Jan 02, 2012 4:47 pm
by quinquenion
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.
Did you mean for i ∈ [2,n}?

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], n-1 integers are composite multiples of 2. All you have to do is find 2 more non-prime numbers in [1, 2n] and you're set.

Re: 9367 66

Posted: Mon Jan 02, 2012 6:05 pm
by JohnDoe
quinquenion wrote:
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.
Did you mean for i ∈ [2,n}?

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], n-1 integers are composite multiples of 2. All you have to do is find 2 more non-prime numbers in [1, 2n] and you're set.
Have you ever been so far even as decided to look more like, quiquenion?

Re: 9367 66

Posted: Mon Jan 02, 2012 6:16 pm
by quinquenion
JohnDoe wrote: Have you ever been so far even as decided to look more like, quiquenion?
Huh?

Edited to add: Oh, a 4chan meme. You got me there :P

Re: 9367 66

Posted: Wed Jan 11, 2012 2:03 pm
by Topoltergeist
quinquenion wrote: You don't even actually need the full power of the PNT. In [1, 2n], n-1 integers are composite multiples of 2. All you have to do is find 2 more non-prime numbers in [1, 2n] and you're set.
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.

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))$$

Re: 9367 66

Posted: Thu Jan 12, 2012 1:02 am
by apap
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.