Here is the probability tree associated with the random experiment described in the problem.

(We are showing part of the tree due to space constraints.)

• \(\Pr[B]\): The event consists of outcomes \((H,3,3), (H,2,4)\) and \((T,3,3).\) The first two outcomes have probability \(\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{1}{4}\) and the last event takes place with probability \(\frac{2}{3} \cdot \frac{1}{3} \cdot \frac{1}{3}.\) In total, \(\Pr[B] = 7/54.\)

• \(\Pr[C]\): The event consists of outcomes \((H,1,1), (H,2,2), (H,3,3)\) and \((T,1,1)\), \((T,2,2)\), \((T,3,3)\). The first three events occur with probability \(\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{1}{4}\) and the last three occur with probability \(\frac{2}{3} \cdot \frac{1}{3} \cdot \frac{1}{3}.\) In total, we can compute \(\Pr[C] = 11/36.\)

• \(\Pr[B \cup C ]\): The only outcome that is in \(B \setminus C\) is \(\{(H,2,4)\}\). Since this outcome occurs with probability \(\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{1}{4}\), we can conclude that \(\Pr[B \cup C ] = \Pr[C \cup \{(H,2,4)\}] = \Pr[C] + \Pr[\{(H,2,4)\}] = \frac{1}{3}\).

• \(\Pr[B \; | \;A]\) and \(\Pr[A \; | \;B]\): The only outcome that belongs to \(A \cap B\) is \((T,3,3)\). Therefore, \(\Pr[A \cap B] = \frac{2}{3} \cdot \frac{1}{3} \cdot \frac{1}{3} = 2/27\). Using the definition of conditional probability and \(\Pr[A] = 2/3\), we have \(\Pr[B \; | \;A] = \Pr[A \cap B] / \Pr[A] = 1/9\). Similarly, \(\Pr[A \; | \;B] = \Pr[A \cap B] / \Pr[B] = 4/7\).

• \(\Pr[C \; | \;A]\) and \(\Pr[A \; | \;C]\): Note that \(A \cap C = \{(T,1,1), (T,2,2), (T,3,3)\}\). So \(\Pr[A \cap C] = \frac{6}{27} = \frac{2}{9}\). Using the definition of conditional probability, \(\Pr[A \; | \;C] = \Pr[A \cap C] / \Pr[C] = 8/11\) and \(\Pr[C \; | \;A ] = \Pr[A \cap C ] / \Pr[A] = 1/3\).

1. Let \(G\) denote the event that the griddle doesn’t burn the blini. Let \(M\) denote the event that Méré doesn’t burn the blini. Then the problem statement tells us that \(\Pr[G] = 2/3\) and \(\Pr[M \; | \;G] = 3/4\). \[\begin{aligned} &~\Pr[\text{blini is burnt}]\\ =&~1 - \Pr[\text{blini is not burnt}]\\ =&~1 - \Pr[G \cap M]\\ =&~1 - \Pr[G] \cdot \Pr[M \; | \;G]\\ =&~1 - \frac{2}{3} \cdot \frac{3}{4}\\ =&~\frac{1}{2}. \end{aligned}\]

2. Implicit in the problem description is the following: Whether a blini is burnt by the griddle or not, is not effected by whether previous blinis made by the griddle are burnt.

   There are \(2^3=8\) possible outcomes, each of which happen with probability \(\left(\frac{1}{2}\right)^3 = \frac{1}{8}\). Of those outcomes, \(7\) of them result in at least one blini burning, and of those, one of them results in all the blinis burning. Thus, the probability we are looking for is \[\frac{1\cdot\frac{1}{8}}{7\cdot\frac{1}{8}} = \frac{1}{7}.\]

3. This pretty much follows from two definitions. The law of total probability says that the denominator on the right equals \(\Pr[B]\). And the numerator is \(\Pr[B \cap A]\). So we want to show that \(\Pr[A \; | \;B] = \frac{ \Pr[ B \cap A ]}{\Pr[B]}\), which is again just by definition.

4. Let \(A\) be the event that Méré made the blini, and let \(B\) be the event that the blini burns. We want to compute \(Pr[\overline{A} \; | \;B]\). We have \[\Pr[A] = \frac{1}{3}, \quad \Pr[\overline{A}] = \frac{2}{3}, \quad \Pr[B \; | \;A] = \frac{1}{2}, \quad \Pr[B \; | \;\overline{A}] = \frac{1}{5}.\] By Bayes’ Theorem, \[Pr[\overline{A} \; | \;B] = \frac{\Pr[B \; | \;\overline{A}] \cdot \Pr[\overline{A}]}{\Pr[B \; | \;A] \cdot \Pr[A] + \Pr[B \; | \;\overline{A}] \cdot \Pr[\overline{A}]} = \frac{\frac{1}{5}\cdot\frac{2}{3}}{\frac{1}{2}\cdot\frac{1}{3} + \frac{1}{5}\cdot\frac{2}{3}} = \frac{4}{9}.\]

We will write \(\mathbf{X}\) as a sum of indicator random variables and then apply linearity of expectation to compute \(\mathbb E[\mathbf{X}]\).

For all \(1 \leq i \leq m-1\), \(1 \leq j \leq n-1\), define the following indicator random variables. \[\mathbf{I}_{i,j} = \begin{cases} 1 & \text{if the $2\times2$ pane with the $(i,j)$-th square in the top left corner is monochromatic,}\\ 0 & \text{otherwise.} \end{cases}\] Then observe that \(\mathbf{X} = \sum_{i=1}^{m-1} \sum_{j=1}^{n-1} \mathbf{I}_{i,j}\). Therefore by linearity of expectation, \[\mathbb E[\mathbf{X}] = \mathbb E\left[\sum_{i=1}^{m-1} \sum_{j=1}^{n-1} \mathbf{I}_{i,j} \right] = \sum_{i=1}^{m-1}\sum_{j=1}^{n-1} \mathbb E[\mathbf{I}_{i,j}].\] The expectation of an indicator random variable is equal to the probability that the random variable is 1. Therefore, \[\begin{aligned} \mathbb E[\mathbf{I}_{i,j}] &= \Pr[\text{all four squares are black}] + \Pr[\text{all four squares are white}]\\ &= \left(\frac{1}{2}\right)^4 + \left(\frac{1}{2}\right)^4 \\ &= \frac{1}{8}.\end{aligned}\] We can plug this into our expression for \(\mathbb E[\mathbf{X}]\) above and conclude that \(\mathbb E[\mathbf{X}] = \frac{(m-1)(n-1)}{8}\).

Let \(A\) and \(B\) be the number of heads Alice and Bob gets respectively. Let \(A'\) be the number of heads Alice gets on the first \(n\) flips, and let \(L\) be the event that Alice’s last flip lands heads. By the law of total probability, \[\begin{aligned} \Pr[A>B] & = \Pr[A'\geq B \; | \;L] \cdot \frac{1}{2} + \Pr[A'>B] \cdot \frac{1}{2}\\ & = \frac{1}{2}\left(\Pr[A'\geq B] + \Pr[A'>B]\right)\\ & = \frac{1}{2}\left(\Pr[A'\geq B] + \Pr[A'<B]\right) \tag{by symmetry}\\ & = \frac{1}{2}\cdot1 = \frac{1}{2}.\end{aligned}\]

The probability of the game ending after exactly \(r\) rolls is \(\frac{1}{7} \cdot \left(\frac{6}{7}\right)^{r-1}\) (geometric random variable). Let \(A\) be the event that the game ends after an odd number of rolls. Then adding up the probabilities of all the outcomes in \(A\), we have \(\Pr[A] = \frac{1}{7} \sum_{i=0}^\infty \left(\frac{6}{7}\right)^{2i}\). Similarly, let \(B\) be the event that the game ends after an even number of rolls and note that \(\Pr[B] = \frac{1}{7} \sum_{i=0}^\infty \left(\frac{6}{7}\right)^{2i+1}\). Now subtract the two and see that \[\Pr[A] - \Pr[B] = \frac{1}{7} \sum_{i=0}^\infty \left(\frac{6}{7}\right)^{2i} - \left(\frac{6}{7}\right)^{2i+1}.\] Each term in the sum is positive, so the whole thing is strictly positive, meaning that \(A\) is more likely than \(B\) after all.

Here is the algorithm.

Input: n
- Create array A[1..n]
- Initialize A[i] = i for all i in {1,...,n}.
- For i = 1 to n:
-     k = RandInt(n - (i - 1)) + (i - 1)
-     Swap(A[i], A[k])
- Return A

We claim that the above algorithm produces a permutation uniformly at random. Fix \(\pi\) to be an arbitrary permutation, and let \(E_i\) be the event \[E_i \; = \; (A[1]= \pi(1) ) \; \wedge \; (A[2] = \pi(2)) \; \wedge \; \dots \; \wedge \; (A[i]=\pi(i)).\]

Claim: At the end of the \(i\)’th iteration, \[\Pr[E_i] = \frac{1}{n} \cdot \frac{1}{n-1} \dots \frac{1}{n-i+1}. \quad (*)\]

We now prove this claim by induction on \(i\).

Base Case: At the end of the first iteration, \(A[1]\) is simply a uniformly random element from \(\{1, \dots, n\}\). Therefore \(\Pr[E_1] = 1/n\) as desired.

Induction Step: Suppose the claim holds at the end of all iterations up to \(i-1\). At the end of iteration \(i-1\), we assume \[\Pr[E_{i-1}] = \frac{1}{n} \cdot \frac{1}{n-1} \cdots \frac{1}{n-i+2}.\] Conditioning on the event \(E_{i-1}\), \(\Pr[A[i]= \pi(i) \; | \;E_{i-1}] = \frac{1}{n-i+1}\). This is because \(A[i,\dots,n]\) contains the elements \(\{1,\dots, n\} \setminus \{\pi(1),\dots, \pi(i-1)\}.\) Since \(A[i]\) is chosen uniformly random from this set, it has probability \(\frac{1}{n-i+1}\) of choosing element \(\pi(i)\). Thus, we can conclude that \(\Pr[E_{i-1} \wedge (A[i] = \pi(i))] = \Pr[E_{i-1}] \cdot \Pr[ (A[i]=\pi(i)) \; | \;E_{i-1}].\) This has value \(\frac{1}{n} \cdot \frac{1}{n-1} \dots \frac{1}{n-c+1}\). Hence, \((*)\) holds true after the \(i\)’th iteration.

Since we have shown that \((*)\) holds true after each iteration, at the end of the program, the probability that \(A = \pi\) is exactly \(\frac{1}{n!}.\) As \(\pi\) was an arbitrary permutation, we output every permutation uniformly at random.