## Assigned Problems 4.1

• 4.1 -- P241 18, 19, 25, 27, 33, 35, 40, 45, 47

• Problem 18 : How many positive integers with exactly 4 digits (i.e. between 1000 and 9999 inclusive) such that
1. divisible by 9
Four tasks: Pick digit 1, Pick digit 2, Pick digit 3, Pick digit 4
Restrictions: Digit 1 is from 1 - 9
Digits 2 and and 3 can be chosen abitrarily from 0 to 9
and Digit 4 must be chosen so that the result is divisible by 9
Unfortunately it depends on the choice 1 to 3 as to whether there are 1 or 2 choices for the 4 fourth digit. Therefore we can't do this with 9*10*10*?. So instead we don't worry about dividing by 9 just now. I.e. there are 9*10*10*10 = 9000 numbers between 1000 and 9999 and exactly every 9-th one is divisible by 9, So the answer is 9000/9.

2. are even. Same thing here, answer is 9000/2.
3. have distinct digits
9 choices for first digit, 10-1=9 choices for second, 10-2 choices for third, and 10-3 choices for 4th. Answer = 9*9*8*7.
4. are not divisible by 3
Count those that are divisible by three (9000/3) and then take the complement (9000-(9000/3)).
5. are divisibly by 5 or 7
9000/5=1800 of them are divisible by 5 and something like 9000/7=1285.81 are divisible by 7 but we have to do a more careful analysis to determine if it is actually 1285 or 1286. I.e. in every group 1000-1006, 1007-1013, etc there is exactly one number which is divisible by 7. The last group starts with 9995=1000+7*1285 but of course gets cut off at 9999. So it just depends on where the (0 mod 7) element sits. It turns out it is 9996 hence that group does add one more multiple of 7.
Now what is the trouble with just taking 1800+1286? Well numbers like 35, 70, ... get counted twice. More generally |A union B| is equal to |A| + |B| - |A intersect B|. A intersect B here is the multiples of 35. By the last part of this question, this quantity is 257. So the answer to this part is 1800 + 1286 - 257.
6. are not divisible by either 5 or 7
Take the complement from the previous question: i.e. (9000 - (1800 + 1286 - 257) ).
7. are divisible by 5 but not 7
This is the same as the set of those that are divisible by 5 and not 35, so we just take the number divisible by 35 away from the number that are divisible 5 (Set theoretically we can take the number that are divisible by 7 away from those that are divisible by 5 but just like with union this quantity is not the same as the difference of their numbers because not every multiple of 7 is in the set of multiples of 5). Answer is 1800 - 257.
8. are divisible by 5 and 7
I.e. divisible by 35. Again it is roughly 9000/35 but is it the next integer down or the next one up. 29*35 = 1015 and 285*35 = 9975. Every number from 29 to 285 inclusive multiplied by 35 gives one of our desired numbers. There are 285 - 29 + 1 = 257.
• Problem 19: How many 3 digit numbers such that they
1. do not contain the same digit three times
Break the list into two disjoint sets, those that contain some digit twice and those that do not. Count each of these sets and add the amounts.

Contain a digit twice: Pick that digit; Choose which spots (oops first spot can't be 0). Start again.
The double digit 0 is a special case: Pick 1 of 9 to go in first spot and stick two 0's after = 9 ways.
Other than 0 as double digit: 9 choices of digit, three choices of places not to put it but if you don't put it in spot 1, then you cannot put a 0 there, so we have (8+9+9) possible ways of putting another digit.

The total repeated digit count is 9 + 9 *(8+9+9).

Now for no repeated digits: 9*9*8

Just add: 9*9*8 + [ 9 + 9*(8+9+9) ] = 9 * ( 9*8 + (1+26)) = 9*99

Better is just 9*10*10 is number of 3 digit numbers, while there are 9 with 3 repeated digits, so the total is 9*100 - 9 = 9*(100 - 1)

2. begin with an odd digit
Easy: 5 choices first position, 10 in second and third. So we get 5*10*10. (Thanks to Lu Miao for alerting me to my earlier error).
3. have exactly two digits that are 4
Only problem here is that 0 cannot go in the first position. Break it into two disjoint cases: begin with a 4, do not begin with a 4
In first case: 8 choices to fill remaining spot (4 is not allowed) and
Second case: 7 choices to begin with.
Total is 15.
• Problem 25 : Licence plates with two letters followed by either 2 or 3 digits.
I think we are only supposed to take capital letters. So 26*26*10*10 + 26*26*10*10*10 (two disjoint sets: 2 digits or 3 digits).

Correction: I misread the question: 2 or 3 letters followed by 2 or 3 digits.

Above is the case for 2 letters followed by 2 or 3 digits. So we can just add (26)^3 * 100 + (26)^3*1000.

Total is: (26^2)*100 * ( 1 + 10 + 26 + 260) = 20077200

• Problem 27: How many 1-1 functions from five element set to one with 4,5,6, 7 elements
In our section 4.3 terminology, these are just 5-permutations, on a set with n=4, n=5, n=6, n=7 elements i.e. P(n,r) with r=5 and n = 4, 5, 6, 7.
P(4,5)=4*3*2*1*0= 4!/(4-5)!; P(5,5) = 5!/(5-5)! = 5!/0! (now you see why we need to define 0!=1); P(6,5) = 6!/1!; P(7,5)=7!/2!.
• Problem 33 : A palindrome is a string equal to its reversal. How many bit string palindromes of length n?

We can choose any value (0 or 1) we want in the first half of the positions, then the last half must be those in the opposite order. So if you think about it there are [n/2] (rounded UP) positions to choose either 0 or 1, i.e. 2^[n/2].

• Problem 35: 35 we all did it in class.
• Problem 40: Students in class are a comb. of CS major and/or Math major. 38 are CS majors, 23 Math, and 7 joints. How many in class.

Think of A as the set of CS majors and B as the set of Math majors. We know that |A union B| = |A| + |B| - |A intersect B|. We are told all the values of the right hand side, hence |A union B| = 38 + 23 -7 = 54

• Problem 45 : Arrange a,b,c,d so that a is not followed immediately by b.

If we set task 1 to be to position a, then task 2 to position b (we can't leave b till last because it might mean putting it immediately after a) and so on, the trouble is that the number of ways to do task 2 depends on how we performed task 1 (and this seems unavoidable). So split it into two disjoint sets: those that have a in the last position and those that do not. Count both those sets.
a in last position: b,c,d go anywhere, so there are 3*2*1 ways.
a goes in one of 3 places, b goes in one of 2, c in one of remaining 2 and d in last: 3*2*2*1.
Add the results: 6 + 12 =18.

• Problem 47: Tree diagram of those subsets of {3,7,9,11,24} whose sum is less than 28. I'll try drawing it downwards, and we will list the members of the subsets in increasing order. When we get to a leaf or terminal node, we'll collect all the elements together and put { } around the resulting set.

```                                       root
/             |        \       \       \
3                7         9     {11}    {24}
/      /   |      \      |   \      |
7       9  {3,11} {3,24}   9  {7,11}  {9,11}
/     |       |                  |
{3,7,9}  {3,7,11}  {3,9,11}          {7,9,11}

```