9367 66

Forum for the GRE subject test in mathematics.
Post Reply
yoyobarn
Posts: 80
Joined: Sun Dec 19, 2010 7:01 am

9367 66

Post by yoyobarn » Wed Dec 21, 2011 4:35 am

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.

fireandgladstone
Posts: 27
Joined: Sun Oct 17, 2010 4:57 am

Re: 9367 66

Post by fireandgladstone » Wed Dec 21, 2011 8:09 am

For n=5, you can pick 1, 4, 6, 8, 9, 10.

yoyobarn
Posts: 80
Joined: Sun Dec 19, 2010 7:01 am

Re: 9367 66

Post by yoyobarn » Wed Dec 21, 2011 9:09 am

Thanks a lot!

Topoltergeist
Posts: 44
Joined: Tue Aug 09, 2011 6:18 pm

Re: 9367 66

Post by Topoltergeist » Wed Dec 21, 2011 12:30 pm

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.

JohnDoe
Posts: 3
Joined: Tue Dec 13, 2011 1:32 pm

Re: 9367 66

Post by JohnDoe » Mon Jan 02, 2012 3:38 pm

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

quinquenion
Posts: 65
Joined: Fri Nov 04, 2011 12:34 pm

Re: 9367 66

Post by quinquenion » Mon Jan 02, 2012 4:47 pm

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.

JohnDoe
Posts: 3
Joined: Tue Dec 13, 2011 1:32 pm

Re: 9367 66

Post by JohnDoe » Mon Jan 02, 2012 6:05 pm

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?

quinquenion
Posts: 65
Joined: Fri Nov 04, 2011 12:34 pm

Re: 9367 66

Post by quinquenion » Mon Jan 02, 2012 6:16 pm

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

Topoltergeist
Posts: 44
Joined: Tue Aug 09, 2011 6:18 pm

Re: 9367 66

Post by Topoltergeist » Wed Jan 11, 2012 2:03 pm

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))$$
Last edited by Topoltergeist on Thu Jan 12, 2012 10:50 am, edited 1 time in total.

apap
Posts: 14
Joined: Wed Oct 26, 2011 11:22 pm

Re: 9367 66

Post by apap » Thu Jan 12, 2012 1:02 am

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.



Post Reply