Suppose you go to a party with four americans and four canadians, none of whom you have met. how many people must you meet to be sure of meeting one canadian and one american?

5

You want to meet at least one American and one Canadian. When you meet the 1st person, that person will be either an American, or a Canadian and you've satisfied half of your requirement. Let's assume the person you meet is a Canadian. That leaves you 7 people you haven't met yet, 3 Canadians and 4 Americans. You meet the 2nd person, but were unlucky and it's another Canadian. There's now 6 people left, 2 Canadians, 4 Americans. So you meet a 3rd and were unlucky again. So there's 5 people left. 1 Canadian, 4 Americans. You meet a 4th person and you managed to grab a Canadian again. You now have 4 people yet to meet, and they're all Americans. So you meet the 5th person and since there are only Americans left, you finally manage to meet an American. The exact same logic applies if the 1st person you meet happens to be an American and your next 3 choices are also Americans. In order to be absolutely certain of meeting at least one American and one Canadian is to pick n+1 people where n is the larger number of the two groups. And in this problem. n = max (number of Americans, number of Canadians).