Suppose n + 1 pigeons are in n cages. Then at least one cage has at least 2 pige
ID: 3282462 • Letter: S
Question
Suppose n + 1 pigeons are in n cages. Then at least one cage has at least 2 pigeons Follow template on the next page Let P(n) be the statement of the Pigeon Hole Principle for the case of n cages and n+ 1 pigeons Base case: n??. So we have?? cage(s) and?? pigeons. If the pigeons must be in a cage, they are together in one cage Induction step: Suppose the statement P(n) is true for n = k I. Show the statement holds for n-?? 4. The statement P(k)-"If??, then??'" The statement P(k + 1)-"If ??, then ??" 6. Suppose now, that we have k + 1 cages and ?? pigeons. So relative to the case ofn -k we have one more?? and one more ??. Find the cage with the new pigeon, and consider two cases: (a) the new pigeon has a "cagemate", (b) the new pigeon has no "cagemate". 8. If the new pigeon has a "cagemate", we are?? Because we found a cage with?? If then new pigeon is by itself in the cage, then the remaining?? pigeons are in the remaining?? cages 10. In this case we can apply?? to conclude that there exist at least on cage with?? 11. Thus in either case we have a cage with??Explanation / Answer
It is simply a process to prove pigeon hole principle by induction. We fill in the missing parts of proof as follows:
2. n=1,one cage and two pigeons
3. n=k+1
4. k cages then k+1 pigeon
5. k+1 cages then k+2 pigeons
6. k+2 pigeons one more cage and one more pigeon
7. -
8. Done because we found a cage with two pigeons
9. k+1 pigeons are in remaining k cages
10. Induction hypothesis to conclude that there exists atleast one cage with two pigeons
11. Two pigeons