Exercises Week 8 - Combinatorics - Answers
(1.) For 2 dice, here are a total of 36 possibilities. The number of possibilities we are interested in is 30. So, 30/36=5/6.
For 3 dice, there are a total of 6x6x6=216 possibilities. The number of possibilities we are NOT interested in is 6x5x4=120 (when they are all different). The number of possibilities we are interested in is thus 6x6x6-6x5x4 = 96. The probability is thus 96/216 = 4/9.
This probability is 120/216 = 5/9.
For n <= 6, this probability is (T-B)/T. Here, T=6^n, and B=6!/(6-n)!. When n > 6, the probability is 1.
(2.) For each group, we have 23×23 + 10×10 possibilities (either two letters or two digits). The total number is then (23×23 + 10×10)^3, because we have 3 groups. The answer is 248858189.
(3.) The result is a fraction where we divide p! by (p-k)!k!. Here, both k and p-k are smaller than p. All prime factors of (p-k)!k! are therefore smaller than p, so p is not a factor of (p-k)!k!.
The general principle we use is: If we have a number A for which we have p | A and b | A (where p does not divide b), then p | (A/b). This follows directly from Eulers lemma (if p | a⋅b, then p | a or p | b, for p prime). We have p | A, so we have p | (A/b)⋅b, so according to Euler we have p | (A/b) eller p | b. The latter is impossible, so we have p | (A/q).
Since p! is divisible by p, after dividing it by (p-k)!k! it is still divisible by p.
It does not hold when p is not prime, take p=4 and k=2 for example.
(4.) Consider a bar of chocolate with N pieces in a row. We would like to hack it up into 3 parts, with x, y, and z pieces each. In this way we know that x+y+z=N. We can hack the chocolate bar at N-1 possible places (one place between each piece). We have to hack 2 times to get three pieces (2 times, at two different places). Thus, the number of ways we can divide N into x,y, and z, is the same as the number of ways we can choose 2 hack positions out of N-1. The answer is thus: \[ {N-1 \choose 2} \] If N=10 (as in the exercise), the answer is 36.
(5.) Consider the function table of the operator. How many entries does it have? For the first argument, we have n choices, for the second argument, we also have n choices. A total of \(n^2\) choices.
For each combination of argument values, we have to choose a result value. There are n possible results. We have to make this choice \(n^2\) times (once for each argument combination).
So, the final answer is \(n^(n^2)\).
(6.) The proof of the step case can be completed as follows. All congruences are (mod p).
|
(k+1)p
| |
| = kp + ...STUFF... + 1p | [ by binomial expansion ] |
| = kp + ...STUFF... + 1 | [ basic arithmetic ] |
| ≡ kp + 1 | [ all the ...STUFF... is divisable by p ] |
| ≡ k + 1 | [ I.H. (see exercise text) ] |
To see why all the ...STUFF... is divisable by p, consider exercise 3. Every term in the expansion is of the form:
( p )·kr r
where p is prime and 0 < r < p. According to exercise 3, these are all divisible by p.
To see the whole proof in text, Proof of Fermat's little theorem using the binomial theorem.
(7.)
( n ) + ( n ) k k+1
= n! + n! [ definition of choose function ] k!(n-k)! (k+1)!(n-k-1)!
= (k+1)n! + n!(n-k) [ multiply by (k+1) and (n-k), respectively ] (k+1)k!(n-k)! (k+1)!(n-k-1)!(n-k)
= (k+1)n! + n!(n-k) [ (k+1)k! = (k+1)!, and (n-k-1)!(n-k) = (n-k)! ] (k+1)!(n-k)! (k+1)!(n-k)!
= (k+1)n! + n!(n-k) [ bring together both fractions ] (k+1)!(n-k)!
= n!((k+1) + (n-k)) [ break out n! ] (k+1)!(n-k)!
= n!(n+1) [ simplification ] (k+1)!(n-k)!
= (n+1)! [ n!(n+1) = (n+1)! ] (k+1)!(n-k)!
= (n+1)! [ simple arithmetic ] (k+1)!((n+1)-(k+1))!
= ( n+1 ) k+1
(8.) There are 54 spots to deal out, divided over 9 groups. Let us pick the first person that should get a spot: you. We pick a group for you, let us call that group G1. In G1, there are 5 more spots (there were 6 and you got 1). You would like your secret love to get one of those 5 spots. There are 53 (54-1) spots left in total to give out. The probability is thus 5/53: 5 possibilities out of a total of 53 are good.
(9a.) Saying that two numbers a and b have a difference which is a multiple of 37 is the same as saying a ≡ b (mod 37). There are 37 possible equivalence classes (mod 37). (Alternatively, there are 37 possible different remainders you can get when dividing by 37.)
Since we have 100 different numbers, there must be at least one equivalence class that has two numbers in it. (The pigeons are the numbers, the holes are the equivalence classes (mod 37).)
(9b.) Divide the unit square into 4 equal sub-squares. Since we pick 5 points, 2 of these must end up in the same sub-square. The maximum distance two points in the same sub-square can have is the length of the diagonal: √((1/2)2+(1/2)2) (using Pythagoras), which equals √(1/2).
(The pigeons are the points, the holes are the 4 sub-squares.)
(10.) Consider graphs with n nodes. How many possible edges can we draw? Well, an edge is a choice of 2 nodes (out of n), so there are \[ {n \choose 2} \] possible edges to draw. Any graph with n nodes is going to choose a subset of these.
If we have a possible number of k edges, we can draw \[ 2^k \] possible graphs, because every graph is characterized by a particular subset of edges it chooses to draw, and there are 2k such subsets.
Putting these two together, given n nodes, there are \[ 2^{n \choose 2} \] possible graphs we can draw.
Here is a little table.
| n | #edges | #graphs |
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 3 | 6 |
| 4 | 6 | 64 |
| 5 | 10 | 1024 |
| 6 | 15 | 32768 |
(11.) We are talking about a directed graph where every node has one incoming edge. This means that there is no topological ordering (no node can be first in such an ordering). This means that there must be a cycle. So, the probability of a cycle is 1, or 100%.