CISC 102 Lecture Notes - Lecture 25: Minestrone, Complex Instruction Set Computing, Pigeonhole Principle

• School: Queen's University
• Department: Computing
• Course: CISC 102
• Professor: D. Rappaport

Document Summary

Suppose we have the same mains and deserts as mentioned in the previous lecture. We can also choose a soup or salad, where the soups are: Gives a total of 3+2 = 5 choices. For non-empty intersections, we use the principle of inclusion and exclusion. Suppose event e can occur m ways, and a second event f can occur in n ways, and the two events do not occur at once, then e or f can occur in m + n ways. Think of counting the number of meals we can make when choosing. 4 mains and 3 deserts is: (3 + 2)(4)(3) = 60 different meals. If there are n pigeons that all must sleep in a pigeon hole and n-1 pigeon holes, then there is at least one pigeon hole were a min of 2 pigeons sleep. We can prove it using the pigeon hole principle. The population of the gta is > 6 million.