Please help me out with these questions from discrete Math. Thanks :) 1. In a cl
ID: 2967455 • Letter: P
Question
Please help me out with these questions from discrete Math. Thanks :)
1. In a classroom of 40 students, show that there are at least two students with the birthdays on the same day of the month (by day of the month we mean Bob was born on the 1st and Cathy was born on the 1st. Another example would be Marta is born on the 15th and Jeremy is born on the 15th. The month is not important, just the day number). 2. Twenty busses are use to transport 157 employees to a training site. Show that there is some bus with at least 8 people on it. Section 7.1: 1. Eight runners are in a race in which first, second and third place will be awarded. Assuming that there are no ties, how many different outcomes are possible? 2. Twenty five photographs are entered in a photo competition. How many ways are there to award the top four places? 3. Two math students and four computer science students come to class late. (a.) There are six students in total. How many ways can the six students walk in through the door late (i.e. 1st, 2nd, 3rd. etc)? (b.) How many ways can the students come in, if a math student must be first?Explanation / Answer
1. There are 31 possible "days of the month". There are 40 students. Since there are more students than days of the month, by the pigeonhole principle, at least one day of the month represents the birthday of more than one student. Put another way, if each of the 40 students had his/her birthday on a distinct day of the month, we would require there to exist 40 possible days of the month. However only 31 such days exist, so there must exist at least 2 students who share a birthday on the same day of the month.
2. Suppose that each bus carries at most 7 workers. Then in total, at most 7 x 20 = 140 workers could be transported. However, we know 157 workers are transported, so this is a contradiction. Thus there must exist a bus that contains at least 8 workers.
1. We have 8 choices for first place, then only 7 choices for second place, and then only 6 choices for third place (we must not award more than one prize to the same person). Thus there are 8 x 7 x 6 = 336 possible ways to award the prizes.
2. Here it is 25 choices for 1st, 24 for 2nd, 23 for 3rd, and 22 for 4th, so there are 25 x 24 x 23 x 22 = 303600 ways to award the prizes.
3.
(a) There are 6 choices for the 1st student. 5 for the second, ... 2 for the 5th and 1 for the 6th. So there are
6 x 5 x 4 x 3 x 2 x 1 = 6! = 720 possible ways for the students to walk in late.
(b) If a math student must be first, then there are only 2 choices for the first student, then there are 5! ways for the rest of the students to come in, so there are 2 x 5! = 2 x 120 = 240 ways for the students to come in.