This is a simple application of the pigeonhole principle. If you have k pigeonholes and k+1 pigeons, then one pigeonhole will contain more than one pigeon.

## 3 is definitely right.

This is a simple application of the pigeonhole principle. If you have k pigeonholes and k+1 pigeons, then one pigeonhole will contain more than one pigeon.