How to prove that if $68$ numbers are selected from the set $\{1, 2, 3, \ldots, 100\}$, then at least three must be consecutive

Question

I need to prove this and find a group without three consecutive numbers. I've tried to come with a solution by pigeonhole principle, but I think I am not close to that. I having a hard time to provide a combinatorial solution and declaring what is the pigeonholes and what is the pigeon number. Help please.

Prove that each subgroup of size $68$ of $\{100, \ldots, 2, 1\}$ has three consecutive numbers. Find a subgroup of size $67$ that does not have three consecutive numbers.

Answer 1

It seems pretty obvious that the best you can do to get as many numbers without getting three consecutive numbers is to pick $1,2,4,5,7,8,10,11,$ etc. This ends with $97,98,100$, which gives a total of $67$ numbers. You could also end with $97,99,100$, and in fact you can ‘shift’ numbers in quite a few ways, so there are many solutions with $67$ numbers

Now, why exactly can't you add one more number and get to $68$? Well, consider that the sequence as indicated has exactly $2$ numbers out of every consecutive $3$ ... So, that's really the maximum you can get.

Answer 2

Consider the the $33$ groups $A_k=(3k-2, 3k -1, 3k)$ for $k= 1.....33$. You can only pick at most $2$ from each $A_k$. If you pick all $3$ from $A_k$ then the numbers in $A_k$ are three consecutive numbers.

So you can only pick at most $2*33=66$ numbers out of the numbers between $1$ and $99$. If you pick $100$ you can pick at most the number $100$ and $66$ others for $67$ maximum numbers.

Answer 3

You can easily construct sets of $67$ elements having no $3$ consecutive numbers. Now, consider the following, $$(1,2,3)$$ $$(4,5,6)$$ $$.$$ $$.$$ $$.$$ $$(97,98,99)$$ Suppose you have a set of $68$ elements such that no $3$ elements are consecutive. Remaining elements are $32$ and above written are $33$ triplets. Hence, by pigeonhole principle, there must be a triplet no element of which is remaining. Hence, there must be $3$ consecutive numbers in this set. Contradiction !

Hope it helps:)

Answer 4

You can choose at most 2 out of every three consecutive numbers to avoid it. But,that only chooses 66 numbers. Add in one of the end points (in the easiest case 100). That makes 67. okay. That means in every set of three, we have 2, and a single set of 1. If we try adding one more to our 67, we hit that we would have to get one from the numbers not chosen in the 33 sets of 3 before. This will end up using up all of at least one of the sets of 3. but those 3 are 3 consecutive numbers. Contradiction.