Given a list of integers from $1$ to $1000$ inclusive, what is the smallest $k$ numbers you pick such that it has $3$ consecutive numbers?

Question

I was going through the textbook and I stumbled upon this question regarding the pigeonhole principle. Kindly advise if I did it correctly?

Given a list of integers from $1$ to $1000$ inclusive, if you pick $k$ numbers from this list, what is the smallest $k$ so that no matter which $k$ numbers you pick from this list, it would guarantee that they contain $3$ consecutive numbers?

Pigeons: $1000$

Pigeonholes: How do I define the pigeonholes?

$$(1000 \div 3) = 334$$

$$2 < 1000 / 334$$

$$1000 – (999 / 3) = 667$$

$k$ will be $667 + 1$?

Answer 1

Proof there can be no more than $667$ numbers selected:

Consider the set of $333$ pigeonholes of the form $\{3k+1,3k+2,3k+3\}$ with $k\in \{0,1,\dots,332\}$.

If there are $668$ or more values there must be at least $667$ values inside the $333$ pigeonholes, so one must contain three values. This would give us three consecutive values.

You can construct an example with exactly $667$ values by taking the first two values of each pidgenhole along with $1000$

Answer 2

Don't know how to explain using pigeonhole principle in this task. But your anwser is right. The worst case if we put Pigeons in Pigeonholes so that now have every Pigeonholes with position 3k (where k in integer > 0) empty. The last have position 999. Thus we spread 2*333=666 pigeons. We can Now add one to the 1000 position. And else one to get triple. => 666 + 1 + 1 = 668

Answer 3

I'm going to try to explain this in a basic way: The pigeonhole principle works by choosing the "worst-case scenario". To not get any $3$ consecutive numbers, the "worst-case scenario" would be to remove every third number.

So the numbers can be any of: $$1,2,4,5,7,8,10...998,1000$$ $$2,3,5,6,8,9,11...998,999$$ $$1,3,4,6,7,9,10...999,1000$$ Again, the "worst-case scenario" among these would be the one with maximum number of numbers, i.e. the first or third one.

Each of these has $333+334=667$ numbers. Add one to get the minimum number of numbers required to satisfy the condition. So the answer is $668$.