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.