You are not logged in.
Pages: 1
The Question: If S is a subset of {1,2,...,n} having size 2n+1 prove S contains 3 consecutive numbers. Show that this is best possible by exhibiting a set of size 2n for which the conclusion is false.
My Answer: Suppose S has no consecutive elements, and label its elements k(0), k(1), ..., k(2n - 1), k(2n) in order, so that
k(0) < k(1) < ... < k(2n - 1) < k(2n).
Since these aren't consecutive, we have that k(i) - k(i - 1) ≥ 2 for i = 1, 2, ..., 2n. Thus
k(2n) - k(0) ≥ [k(2n) - (k(2n - 1)] + [k(2n - 1) - k(2n -2)] + ... + (k(2) - k(1)) + (k(1) - k(0)) ≥ 2n * 2 = 4n.
Since the smallest k(0) can be is 1 and k(2n) can be no larger than 3n, it follows that 3n ≥ k(2n) ≥ k(0) + 4n = 4n + 1, which is contradiction. Hence S must contain some consecutive elements.
I need to use the pigeonhole principle in my answer (says the teacher). I'm not sure how I can use it in this case. I thought i did, but.... Any ideas??
Offline
Pages: 1