Homework Week 10

Problem 1

1. There are 18 math majors and 325 CS majors. How many ways are there to pick two representatives, one from each major?
   
2. How many ways are there to pick one representative who is either a math major or a CS major?

Problem 15

How many lowercase-letter strings have length 4 or less, excluding the empty string?

Problem 23

Positive integers from 100 to 999 inclusive:

1. How many are divisible by 7?
   
2. How many are odd?
   
3. How many have the same three decimal digits?
   
4. How many are not divisible by 4?
   
5. How many are divisible by 3 or 4?
   
6. How many are not divisible by either 3 or 4?
   
7. How many are divisible by 3 but not by 4?
   
8. How many are divisible by 3 and 4?

Problem 27

A committee has one representative from each of the 50 states; each state sends either its governor or one of its two senators. How many such committees are possible?

Problem 35

Find the number of one-to-one functions from a 5-element set to a set with:

1. 4 elements
   
2. 5 elements
   
3. 6 elements
   
4. 7 elements

Problem 37

For functions from \(\{1,2,\dots,n\}\) to \(\{0,1\}\), how many:

1. are one-to-one?
   
2. assign 0 to both 1 and \(n\)?
   
3. assign 1 to exactly one of the positive integers less than \(n\)?

Problem 47

How many ways are there to seat 6 people around a circular table, where two seatings are the same if everyone has the same two neighbors, regardless of left/right?

Problem 66

How many bit strings of length 4 have no three consecutive 0s?

Problem 1

Show that among 6 classes meeting once a week on weekdays, at least 2 meet on the same day.

Problem 5

There are 4 graduation years and 21 majors. How many students are needed to guarantee 2 students with the same year and same major?

Problem 11

What is the minimum number of students from 50 states needed to guarantee at least 100 from the same state?

Problem 17

How many numbers must be selected from \(\{1,2,3,4,5,6\}\) to guarantee some pair sums to 7?

Problem 29

Show that in any group of 10 people, there are either 3 mutual friends or 4 mutual enemies, and either 3 mutual enemies or 4 mutual friends.

Problem 33

Show that at least 6 people in California have the same 3 initials and the same birthday.

Problem 35

Paris had more than 800,000 inhabitants; no one had more than 200,000 hairs; everyone had at least 1 hair. Show that at least two Parisians had the same number of hairs, and determine a stronger lower bound from the pigeonhole principle.

Problem 39

In a network of 6 computers, show that at least 2 computers are connected to the same number of others.