Problems

---

Solution: With \(n=1\) line, the plane is divided in half. With \(n=2\) lines the plane is divided into four pieces. (Each of the previous pieces are split in half) With \(n=3\) lines the plane is divided into up to \(7\) pieces. (The new line crosses two lines in two places dividing \(3\) regions into \(2\), thus increasing the number of regions by \(3\)). With \(n=4\) lines the plane is divided into \(11\) pieces. (The new line crosses three lines in three places doubling the number of regions of \(4\) places). Claim: With \(n\) lines the plane is divided into \(\frac12(n^2+n+2)\) regions. Proof: (By induction) (Base case) When \(n=1\) clearly the line is divided into \(2\) regions, and \(\frac12 (1^2 + 1^2 + 2) = 2\) so the base case is true. (Inductive step) Suppose our formula is true for \(n=k\), so we have placed \(k\) lines in general position and divided the plane into \(\frac12(k^2+k+2)\) regions. When we place a new line it will meet those \(k\) lines in \(k\) places (since no lines are parallel) and there will be k+1 regions the line will run through (since no three lines meet at a point). Each of those \(k+1\) regios is now split in half, so there are \(k+1\) "new regions". Therefore there are now \(\frac12(k^2+k+2)+(k+1) = \frac12(k^2+k+1+2k+2) = \frac12 ((k+1)^2+(k+1)+1)\) regions, ie our hypothesis is true for \(n=k+1\). (Conclusion) Therefore since our statement is true for \(n=1\) and since if it is true for some \(n=k\) it is true for \(n=k+1\) by the principle of mathematical induction it is true for all \(n \geq 1\) Proof: (Alternative). There are \(\binom{n}{2}\) places where the lines meet. Each intersection is the most extreme point (say lowest) for one region (if two are tied, rotate by a very small amount) so this is a unique mapping. There will be \(n+1\) regions which are infinite and don't have a most extreme point, hence \(\binom{n}{2} + n+1 = \frac12(n^2-n)+n+1 = \frac12(n^2+n+2)\)

---

Solution: Consider the \(5\) segements radiating from \(A\). By the pigeonhole principle, at least \(3\) of them must be the same colour (say gold and say reaching \(B,C,D\)). If any of the segments joining any of \(B,C,D\) are gold then we have found a monochromatic gold triangle. But if none of them are gold, they are all silver, therefore \(BCD\) is a monochromatic silver triangle.

---

Solution: \begin{align*} \mathbb{P}(\text{exactly }k\text{ faults after test}) &= \mathbb{P}(k\text{ faults in non-tested, 0 in batch})+\mathbb{P}(k-1\text{ faults in non-tested, 1 in batch}) \\ &=\binom{N}{k}(1-p)^{N-k}p^k\binom{n}{0}(1-p)^n+\binom{N}{k-1}(1-p)^{N-k+1}p^{k-1}\binom{n}{1}(1-p)^{n-1}p \\ &= (1-p)^{N-k+n}p^k \cdot \left ( \binom{N}{k}+n\binom{N}{k-1} \right) \\ &= (1-p)^{N-k+n}p^k \cdot \left (\frac{N!}{k!(N-k)!}+\frac{N!n}{(k-1)!(N-k+1)!}\right) \\ &= (1-p)^{N-k+n}p^k \frac{N!}{k!(N-k+1)!} \cdot \left ((N-k+1)+nk \right) \\ &= \frac{\left[N+1+k\left(n-1\right)\right]N!}{\left(N-k+1\right)!k!}p^{k}\left(1-p\right)^{N+n-k} \end{align*} When \(k = N+1\) we get: \begin{align*} \frac{(N+1)n N!}{(N+1)!} p^{N+1}(1-p)^{N+n-k} &= np^{N+1}(1-p)^{N+n-k} \end{align*} and the probability is: \begin{align*} \mathbb{P}(\text{exactly }N+1\text{ faults after test}) &= \mathbb{P}(N\text{ faults in non-tested, 1 in batch}) \\ &= \binom{N}{N}p^N \cdot \binom{n}{1}p(1-p)^{N-1} \\ &= np^{N+1}(1-p)^{N+n-k} \end{align*} So the formula does work for \(k = N+1\). \begin{align*} \mathbb{E}(faults) &= \sum_{k=0}^{N+1} k \cdot \mathbb{P}(\text{exactly }k\text{ faults after test}) \\ &= \sum_{k=0}^{N+1} k \cdot \frac{\left[N+1+k\left(n-1\right)\right]N!}{\left(N-k+1\right)!k!}p^{k}\left(1-p\right)^{N+n-k} \\ &= \sum_{k=1}^{N+1} \frac{\left[N+1+k\left(n-1\right)\right]N!}{\left(N-k+1\right)!(k-1)!}p^{k}\left(1-p\right)^{N+n-k} \\ &= \sum_{k=1}^{N+1} \left[N+1+k\left(n-1\right)\right] p(1-p)^{n-1}\binom{N}{k-1}p^{k-1}\left(1-p\right)^{N-k+1} \\ &= p(1-p)^{n-1} \cdot \left ( (N+1+n-1)\sum_{k=1}^{N+1} \binom{N}{k-1}p^{k-1}\left(1-p\right)^{N-k+1}+ (n-1)\sum_{k=1}^{N+1} (k-1)\binom{N}{k-1}p^{k-1}\left(1-p\right)^{N-k+1} \right) \\ &= p(1-p)^{n-1} \left ((N+1+n-1) + (n-1)pN \right) \\ &= \left[N+n+pN(n-1)\right]p(1-p)^{n-1} \end{align*}

---

Solution:

1. There are \(m \cdot n\) line segments, since each of the \(m\) points on the \(y\)-axis correspond to \(n\) points of the \(x\)-axis.
2. Every pair of points on the \(x\)-axis and pair of points on the \(y\) axis will generate \(4\) lines, but only \(1\) of those points will meet in the middle, therefore there will be \(\binom{m}{2} \binom{n}{2}\) intersections.

The segment joining the smallest \(x\) to the smallest \(y\) and the segment joining the largest \(x\) to the largest \(y\) will not meet any other segments. The segment joining the smallest \(x\) to the largest \(y\) and the segment joining the largest \(x\) to the smallest \(y\) will have the largest number of intersections. They each intersect all the other segment coming out of other points (except the ones headed for the same point) ie \((m-1)(n-1)\) each. They also intersect each other, so \(2(m-1)(n-1)-1\) points. Therefore we are interested in: \begin{align*} \frac{\binom{n}{2}\binom{n}{2} - 2(n-1)^2+1}{n^2-4} &= \frac{\frac{n^2(n-1)^2}{4} - 2n^2+4n-1}{n^2-4} \\ &= \frac{n^4-2n^3+n^2-8n^2+16n-4}{4(n^2-4)} \\ &= \frac{(n - 2) (n^3 - 7 n + 2)}{4(n^2-4)} \\ &= \frac{n^3-7n+3}{4(n+2)} \end{align*}

---

Solution:

1. \(M(0) = 0\) since if there's no space on the shelf, we wont be able to put any books on the shelf.
2. If the shelf has length \(1\) it can only fit a thin book. For a thin book to be placed on the shelf, the very first book which comes to be placed must be thin. But this happens with probability \(q\). Therefore \(M(1) = q\).
3. Suppose no books have been placed on the shelf, then with probability \(p\) a large book gets placed on the shelf, and the expected number of books to be placed on the shelf is equivalent to how many books will be placed on the shelf if the shelf only had \(n-2\) spaces. This is \(M(n-2)\). Similar if the book which arrives first is thin (with probability \(q\)) then there will be \(M(n-1)\) more books placed on the shelf in expectation. We've just added \(1\) more book, therefore \(M(n) = 1+pM(n-2) + qM(n-1)\) or rearranging \(M(n) - qM(n-1) - pM(n-2) = 1\).

Suppose \(M(n) = (-p)^n\), notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= (-p)^n - (1-p)(-p)^n - p(-p)^{n-2} \\ &= (-p)^{n-2}(p^2+(1-p)p-p) \\ &= 0 \end{align*} Suppose \(M(n) = B\), notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= B - (1-p)B - pB \\ &= 0 \end{align*} Finally, if \(M(n) = Cn\) notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= Cn - (1-p)C(n-1) - pC(n-2) \\ &= C(n(1-(1-p)+p)+(1-p)+2p) \\ &= C(1+p) \end{align*} Therefore if \(C = \frac{1}{1+p}\) we have that: \(M(n) = A(-p)^n + B + Cn\) satisfies our recurrence. We also need \(M(0) = 0\) and \(M(1) = q\) \begin{align*} 0 &= M(0) \\ &= A + B \\ 1-p &= M(1) \\ &= -pA+B \end{align*} \((1+p)A = p-1 \Rightarrow A = \frac{p-1}{1+p}, B = \frac{1-p}{1+p}\). Therefore: \[ M(n) = -\frac{1-p}{1+p}(-p)^n + \frac{1-p}{1+p} + \frac{n}{1+p} \] is a possible solution to this equation

---

Solution: There are \(\displaystyle \binom{m}{k} \binom{M-m}{n-k}\) ways to choose \(k\) red and and \(n-k\) green balls out of a total \(\displaystyle \binom{M}{n}\) ways to choose balls. Therefore the probability is: \[ \mathbb{P}(\text{exactly }k\text{ red balls in }n\text{ choices}) = \frac{\binom{m}{k} \binom{M-m}{n-k}}{ \binom{M}{n}}\]

1. Note that there is nothing special about the \(i\)th ball chosen. (We could consider all draws look at the \(i\)th ball, or consider all draws apply a permutation to make the \(i\)th ball the first ball, and both would look like identical sequences). Therefore \(\mathbb{P}(X_i = 1) = \mathbb{P}(X_1 = 1) = \frac{m}{M}\).
2. Similarly we could apply a permutation to all sequences which takes the \(i\)th ball to the first ball and the \(j\)th ball to the second ball, therefore: \begin{align*} \mathbb{P}(X_i = 1, X_j = 1) &= \mathbb{P}(X_1 = 1, X_2 = 1) \\ &= \mathbb{P}(X_1 = 1) \cdot \mathbb{P}(X_2 = 1 | X_1 = 1) \\ &= \frac{m}{M} \cdot \frac{m-1}{M-1} \\ &= \frac{m(m-1)}{M(M-1)} \end{align*}

So: \begin{align*} \mathbb{E}(X) &= \mathbb{E}(\sum_{i=1}^{n}X_{i}) \\ &= \sum_{i=1}^{n}\mathbb{E}(X_{i}) \\ &= \sum_{i=1}^{n} 1\cdot\mathbb{P}(X_i = 1) \\ &= \sum_{i=1}^{n} \frac{m}{M} \\ &= \frac{mn}{M} \end{align*} and \begin{align*} \mathbb{E}(X^2) &= \mathbb{E}\left[\left(\sum_{i=1}^{n}X_{i} \right)^2 \right] \\ &= \mathbb{E}\left[\sum_{i=1}^n X_i^2 + 2 \sum_{i < j} X_i X_j \right] \\ &= \sum_{i=1}^n \mathbb{E}(X_i^2) + 2 \sum_{i < j} \mathbb{E}(X_i X_j) \\ &= \frac{nm}{M} + n(n-1) \frac{m(m-1)}{M(M-1)} \\ \textrm{Var}(X) &= \mathbb{E}(X^2) - (\mathbb{E}(X))^2 \\ &= \frac{nm}{M} + n(n-1) \frac{m(m-1)}{M(M-1)} - \frac{n^2m^2}{M^2} \\ &= \frac{nm}{M} \left (1-\frac{nm}{M}+(n-1)\frac{m-1}{M-1} \right) \\ &= \frac{nm}{M} \left ( \frac{M(M-1)-(M-1)nm+(n-1)(m-1)M}{M(M-1)} \right) \\ &= \frac{nm}{M} \frac{(M-m)(M-n)}{M(M-1)} \\ &= n \frac{m}{M} \frac{M-m}{M} \frac{M-n}{M-1} \end{align*} Note: This is a very nice way of deriving the mean and variance of the hypergeometric distribution

---

Solution:

1. \(ACB\) is not a complete tournament since no-one has won two matches.
2. \(ABB\) is not a possible complete tournament since it implies \(B\) won game 2, which is between \(A\) (winner of game 1) and \(C\) (referee of game 1).
3. \(ACBB\) is a valid tournament, \(A\) beat \(B\), then \(C\) beat \(A\), then \(B\) beat \(C\) and finally \(B\) beat \(A\) to win.

After the first game there is always someone playing for the tournament, so for there to be no result after 5 games, 4 games must have gone against the leader, so the probability is \(\frac{1}{2^4} = \frac{1}{16}\). If \(A\) wins their first game, they can either win in two games (WW) or in five games (WLRWW). The probability of this is \(\frac14 + \frac1{16} = \frac{5}{16}\). Similarly \(B\) has exactly the same chance as \(A\) since everything about them is symmetric, ie a probability of \(\frac5{16}\) of winning. Since there is a \(\frac{15}{16}\) chance the tournament is decided after 5 games, the remaining \(\frac{5}{16}\) must be \(C\)'s chance of winning. After the first game is played, there's \(3\) states for each player. King (about to win if they win, becomes Ref if they lose), Challenger (needs to win to become king) and Ref (who becomes Challenger if Challenger wins). \begin{align*} \P(\text{King wins}) &= \frac{1}{2} + \frac{1}{2}\P(\text{Ref wins})\\ \P(\text{Challenger wins}) &= \frac{1}{2} \P(\text{King wins}) \\ \P(\text{Ref wins}) &= \frac{1}{2} \P(\text{Challenger wins}) \\ \end{align*} \(p_K = \frac12 + \frac12 (\frac12 \frac12 p_K) \Rightarrow \frac78 p_K = \frac12 \Rightarrow p_K = \frac47, p_C = \frac27, p_R = \frac17\). \(A\) has \(\frac12\) of being king, \(\frac12\) of being ref after the first match, so \(\frac12 \frac47 + \frac12 \frac17 = \frac{5}{14}\). Similarly \(B\) has \(\frac5{14}\) chance of winning, but unfortunately \(C\) must be the challenger after the first match and only has \(\frac27 = \frac4{14}\) chances of winning.