Fall 2016 COT 3100 Section 1 Homework 5 Assigned: 10/28/2016 Due: 11/4/2016 Note: Please justify your answers and why you use each formula. 1) Consider an ant that is walking on a Cartesian grid, starting at (0,0) and ending at (20, 12). The ant always chooses to walk exactly one unit either up or to the right (towards his destination) whenever he arrives at a Lattice point. (A Lattice point is a point with integer coordinates.) Thus, from (0,0) he either walks to (1, 0) or (0, 1). If the ant is not allowed to go to the points (10, 5) and (12, 8), how many different paths can he take on his walk? 2) This question considered permutations of \"HILLARYCLINTON\". a) How many permutations are there total? b) How many permutations start and end with vowels? c) How many permutations do NOT have consecutive vowels in them? d) How many permutations are the letters in alphabetical order? e) How many permutations contain the substring \"RANT\"? 3) A class contains 25 girls and 22 boys. For all parts of this question, each boy and girl are distinguishable from one another. Answer the following questions: a) In how many ways can a committee of one boy and one girl be chosen? b) In how many ways can a committee of five students be chosen? c) In how many ways can a committee of four girls and three boys be chosen? d) In how many ways can a committee of six students be chosen such that all the students on the committee are the same sex? e) In how many ways can the girls and boys form a line where no two boys are standing next to one another? f) How many committees of seven students contain at least two girls? 4) How many solutions does the equation a + b + c + d + e + f = 25 have if each variable must be a nonnegative integer and a 4, b 6 and d 5? 5) How many solutions does the equation a + b + c + d + e + f + g 30 have if each variable must be a non-negative integer? 6) There are N users and M servers with M N. Each user can send a request to any of the servers. Determine the number of situations in which at least one collision occurs, i.e., there is at least one pair of users that send the request to the same server. 7) How many integers in between 1 and 107 are divisible by 2, 5 or 11? 8) How many permutations of 3 As, 5 Bs and 7 Cs don't have any consecutive Bs in them? Problem: How many permutations of AABBCCDDEEFFGG do not contain any consecutive letters. Solution: let f(n) be the solution for n pairs of matching letters. We can choose the first letter in the permutation to be any one of the n letters. Then, we can select any of 2n-2 slots for the second copy of that letter - anything BUT the second slot. What remains is to recursively fill in 2(n-1) slots with the remaining letters, which can be done in f(n-1) ways. Thus, we've derived the equation: () = (2 2)( 1) We can quickly note that f(2) = 2 since the two valid arrangements of AABB are ABAB and BABA. Now, we can plug in for n = 7 to solve the given query: (3) = 3 4 (2) = 12 2 = 24 (4) = 4 6 (3) = 24 24 = 576 (5) = 5 8 (4) = 40 576 = 23040 (6) = 6 10 (5) = 60 23040 = 1382400 (7) = 7 12 (6) = 84 1382400 = 116121600 Thus, there are 116,121,600 permutations of AABBCCDDEEFFGG without 2 of the same letter appearing consecutively. What is the flaw in this approach? Conceptually, is this approach overcounting or undercounting? 10) How many positive integer solutions does the equation a + b + c = 100 have if we require a < b < c