Answer to Question #256427 in Discrete Mathematics for Mico

Question

Exercise # 3 a. Ten persons have first names Alice, Billy, and Charlie and last names Lee, Mendoza and Navarro. Show that at least two persons have the same first and last names. b. In any group of 367 people, at least two people must have the same birthday. c. What is the largest number of points that can be placed in a square whose side has length two, in such a way that no two points are a distance of 2 or less from each other?

Answer 1

a. The first name can be selected in three ways, the last name in three ways too. Then the maximum number of people with different first name or last name is $3 \cdot 3 = 9$ . So, according to the Dirichlet principle, there are at least two people with the same first name and last name Q.E. D.

b. Since a year contains a maximum of 366 days, then, according to the Dirichlet principle, all people cannot have birthdays on different days. Therefore, at least two people have the same birthdays. Q. E. D.

c. We have a 2x2 square. We want to split this into 4 1x1 squares, simply by joining the centres of opposite sides. This creates a small grid.

Now imagine we want to insert our 5 points into these 4 1x1 squares. Here we apply the Dirichlet principle. Since we have more points than squares to place them, we know that some square must end up containing at least 2 points. So, largest number of points is 4.

Answer: 4