S is subset, prove it has consecutive numbers?

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.

I think I'm going to be using pigeonhole principle (placing more than kn objects in n classes puts more than k objects into some class.) which means i'll have to partition the objects into classes???? oh boy.

Apologies... Let S be a subset of {1,2,...,3n} having size 2n+1...

Answer 1

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 a contradiction. Hence S must contain some consecutive elements.

***
Note: if you're happy using sigma notation for sums, then we can write part of this more neatly:

k(2n) - k(0) >= ∑ [ k(i) - k(i - 1) ]

where the sum is taken from i = 1 to i = 2n.

Answer 2

I don't understand the question. If the set is of size n, then how is your subset going to be of size 2n or 2n+1? I assume that the n in your set and the n in the subset size must be different, but since that's such an important part of the problem, you may wish to clarify that.

Answer 3

I'm sorry, but your question makes no sense.
Suppose S is a subset of {1,2}. How can a subset
have size 5?? Did you mean 2k+1, perhaps?
or by {1,2,...,n) do you mean Z?
In any case, there aren't 3 consecutive integers in {1,2}.
I think you ought to clarify your question a bit.

Answer 4

sturdy question. Upon genuine remark there are countless probabilities of the cost of infinity. relatively infinity is a concept fairly than a value that we use to describe numerical or spatial innovations that are (probably) with out end. interior the main ordinary version we predict of of counting numbers or the area to the tip of the universe or time, yet once you contain the fractional and decimal distances between entire numbers there is particularly no end to the place it stops. issues could desire to continually be measured on an infinitely greater or smaller scale.