Here are some answers for the exercises.

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. This means that there is no prime factor q of (p-k)!k! that divides p. Since p! is divisible by p, after dividing it by (p-k)!k! it is still divisible by p.

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	)
	2

5. The general answer is:

(	n	)
	k

When n=5 and k=3 (as in the exercise), the answer is 10.

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

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.

9. 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	)
	2

If we have a possible number of k edges, we can draw

2^k

Putting these two together, given n nodes, there are

2	(	n	)
		2

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

10. 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%.