6 - Covers all material in lecture on chapter 6 section 2 by prof. Monica Sweat. PDF

Preview

Summary

Covers all material in lecture on chapter 6 section 2 by prof. Monica Sweat....

Description

Pidgeonhole Principle 5 pidgeonholes, 5 pidgeons Minimal number of pidgeons where it’s guarenteed that one hole will have at least 2 pidgeons -- 6 Classic interview question: sock drawer 6 colors of socks, want 1 matching pair (ceiling) (n/6) = 2

n/6 = 1

6+1=7

Guesses: 7

How many people are required to guarantee that at least 2 share the same bday (month/day). 1-1 1-2 1-3 … Dec 31 = 366 How many people to guarantee at lesat 2- have same bday (month/day). 「n/366ㄱ = 20 n/366 = 19 n = 6954 19ppl → jan 1 19ppl → jan2 … 19ppl → 2-29 … 19ppl → Dec 31 + 1 = 6955

Deck of cards = 52 cards 4 suits = {spades, hearts, clubs, diamonds} 13 ranks = {2, 3, 4, 5, 6 7, 8, 9, 10, J, Q, K} 4 cards of the same suit. How many cards would I have to be dealt for this to happen. 13

Assume that within 6 people at a party each pair of people are mutual friends or mutual enemies. Prove that there will be a 3-way friendship or 3-way enemy-ship among these 6.

800 students Form 1 team of 20 Combination: C (800, 20)...