- #1
lovemake1
- 149
- 1
Homework Statement
Pidgeonhole principle: If kn+1 objects are placed in n pigeonholes, then some pigeohoe contains atleast k+1 objects.
Homework Equations
The Attempt at a Solution
I completely understand this problem but I am not sure where or how to start.
If there are n = 5 holes and we set k to be 2.
then there are 11 objects in total and according to the principle, some pidgeonhole would occupy (2)+1 = 3 objects in one hole.
Do we use induction?
Assume k, n is natural:
Assume kn + 1 is nautral:
Then kn+1 > k + 1
Then kn > k
n > 1 ?
...
Can someone please give me a hint?
Helps appreciated.