Todai Entrance Exam: Math 2018 – Problem 3

Problem link

(1) We prove z_{2k + 1} = i^{2m + 1} = \pm i and z_{2k} = i^{2m} = \pm 1 (note that i^{2} = -1 and i^{4} = 1, I doubt if zero can be considered as an even number though).

Base case:

  • z_{0} = 1 = i^{2 \times 0 }.
  • z_{1} = i \times z_{0} = i^{2 \times 0 + 1} if a red card was taken.
  • z_{1} = -i \times z_{0}  = -i^{2 \times 0 + 1} =  i^{2 \times 1 + 1} if a white card was taken.

So z_{2k + 1} = i^{2m + 1} = \pm i and z_{2k} = i^{2m} = \pm 1 are true for k = 0.

Induction step: Let z_{n} = z_{2k + 1} = i^{2m + 1}.

  • z_{n + 1} = z_{2(k + 1)} = iz_{n} = i^{2(m + 1)} if a red card was taken.
  • z_{n + 1} = z_{2(k + 1)} = -iz_{n} = -i^{2(m + 1)} =  i^{2(m + 2)} if a white card was taken.

So z_{n + 1} =  z_{2(k + 1)} = i^{2a} (with a = m + 1 or a = m + 2).

  • z_{n + 2} = z_{2(k + 1) + 1} = iz_{n + 1} = i^{2a + 1} if a red card was taken.
  • z_{n + 2} = z_{2(k + 1) + 1} = -iz_{n + 1} = i^{2(a + 1) + 1} if a red card was taken.

So z_{n + 2} = z_{2(k + 1) + 1} = i^{2b + 1} (with b = a = m + 1 or b = a + 1 = m + 2).

So the statement follows.

(2) From (1), we proved that P_{n} = 0 if n = 2k + 1 and it is already given that P_{0} = 1 (because z_{0} = 1). Now we prove that P_{n} = P_{n - 2}P_{2} + (1 - P_{n - 2})(1 - P_{2}) for n = 2k with k \geq 1.

Base case:

  • There are 4 possible combinations of card colours pulled in the first and second times which lead to different values of z_{2}:
First pullRedWhite
Second pull
Red-11
White1-1
  • We have: P(\text{Red} | \text{First pull}) = \frac{2}{3} and P(\text{White} | \text{First pull}) = \frac{1}{3}. Therefore, P_{2} = P(z_{2} = 1) = 2\frac{1}{3}\frac{2}{3} and P(z_{2} = -1) = 1 - P_{2}.

So P_{2} = P_{0}P_{2} + (1 - P_{0})(1 - P_{2}) = P_{2} = 2\frac{1}{3}\frac{2}{3}.

Induction step: Given P_{n}, prove that P_{n + 2} = P_{n}P_{2} + (1 - P_{n})(1 - P_{2}).

z_{n + 2} = z_{n} \times \text{i or -i based on the color of the card pulled in (n)th time} \times \text{i or -i based on the color of the card pulled in (n + 1)th time} = z_{n} \times a.

There are 2 possible values of z_{n}: 1 (probability: P_{n}) and - 1 (probability: (1 - P_{n})).

There are 4 possible combinations of card colours pulled in the (n + 1)th and (n + 2)th time yielding 2 possible values of product a: 1 (probability: P_{2}) and -1 (probability: (1 - P_{2})).

z_{n + 2} = 1 if and only if z_{n} and a both equals 1 or z_{n} and a both equals - 1.

Probability of z_{n} and a both equals 1: P_{n}P_{2}.

Probability of z_{n} and a both equals - 1: (1 - P_{n})(1 - P_{2}).

So the statement follows: P_{n + 2} = P_{n}P_{2} + (1 - P_{n})(1 - P_{2}).

Now comes to Q_{n}, we see that z_{n} = i = 1 \times i = -1 \times -i. Therefore, for n = 2k + 1 with k \geq 0:

    \[ Q_{n} = P(\text{red} | \text{(n)th pull})P(z_{n-1} = 1) + P(\text{white} | \text{(n)th pull})P(z_{n-1} = -1) = \frac{2}{3}P_{n-1} + \frac{1}{3}(1 - P_{n-1}) \]

We also proved from (1) that Q_{n} = 0 for n = 2k.

So in summary:

    \[ \begin{Bmatrix} P_{0} = 1 & & \\  P_{n} = P_{n - 2}P_{2} + (1 - P_{n - 2})(1 - P_{2}) & \text{if} & n = 2k, k \geq 1\\  P_{n} = 0 & \text{if} & n = 2k + 1, k \geq 0\\  Q_{n} = \frac{2}{3}P_{n-1} + \frac{1}{3}(1 - P_{n-1}) & \text{if} & n = 2k + 1, k \geq 0\\ Q_{n} = 0 & \text{if} & n = 2k, k \geq 0\\  \end{matrix} \]

(3) We find the closed form of P_{n} = P_{n - 2}P_{2} + (1 - P_{n - 2})(1 - P_{2}) (thanks to my labmate for the closed form solution).

    \[ P_{n} = P_{n - 2}P_{2} + (1 - P_{n - 2})(1 - P_{2}) = (2P_{2} - 1)P_{n-2} + 1 - P_{2} \]

    \[ P_{n} - \frac{1}{2} = (2P_{2} - 1)(P_{n-2} - \frac{1}{2}) = (2P_{2} - 1)^{\frac{n}{2}}\left (P_{0} - \frac{1}{2} \right ) \]

    \[ P_{n} = \frac{1}{2}\left ( -\frac{1}{9} \right )^{\frac{n}{2}} + \frac{1}{2} \]

  • Probability of z_{n} = 1: P_{n} = \frac{1}{2}\left ( -\frac{1}{9} \right )^{\frac{n}{2}} + \frac{1}{2} if n is even, 0 otherwise.
  • Probability of z_{n} = -1: 1 - P_{n} = \frac{1}{2} - \frac{1}{2}\left ( -\frac{1}{9} \right )^{\frac{n}{2}} if n is even, 0 otherwise.
  • Probability of z_{n} = i: Q_{n} = \frac{1}{6}\left ( -\frac{1}{9} \right )^{\frac{n-1}{2}} + \frac{1}{2} if n is odd, 0 otherwise.
  • Probability of z_{n} = -i: 1 - Q_{n} = \frac{1}{2} - \frac{1}{6}\left ( -\frac{1}{9} \right )^{\frac{n-1}{2}} if n is odd, 0 otherwise.

(4) If n is even, then:

    \[ \mathbb{E}(z_{n} | n=2k, k \in \mathbb{N}) = (+1)P_{n} + (-1)(1 - P_{n}) = \frac{1}{2}\left ( -\frac{1}{9} \right )^{\frac{n}{2}} + \frac{1}{2} - \frac{1}{2} + \frac{1}{2}\left ( -\frac{1}{9} \right )^{\frac{n}{2}} = \left ( -\frac{1}{9} \right )^{\frac{n}{2}} = \left ( \frac{i}{3} \right )^{n} \]

If n is odd, then:

    \[ \mathbb{E}(z_{n} | n=2k+1, k \in \mathbb{N}) = (+i)Q_{n} + (-i)(1 - Q_{n}) = i\left ( \frac{1}{6}\left ( -\frac{1}{9} \right )^{\frac{n-1}{2}} + \frac{1}{2} \right ) -i\left ( \frac{1}{2} - \frac{1}{6}\left ( -\frac{1}{9} \right )^{\frac{n-1}{2}} \right ) = i\frac{1}{3}\left ( -\frac{1}{9} \right )^{n-1} =  \left ( \frac{i}{3} \right )^{n}\]

As the probability for n to be even equals the probability for n to be odd and they are \frac{1}{2}, we arrive the solution:

    \[ \mathbb{E}(z_{n}) = \frac{1}{2}\mathbb{E}(z_{n} | n=2k, k \in \mathbb{N}) + \frac{1}{2}\mathbb{E}(z_{n} | n=2k+1, k \in \mathbb{N}) = \left ( \frac{i}{3} \right )^{n} \]

Q.E.D

(5) Prove that \forall k \in \mathbb{N}, w_{2k} = z_{2k}, w_{2k + 1} = -z_{2k + 1}.

Base case:

  • w_{0} = z_{0} = 1.
  • If the red card is taken in the first pull: w_{1} = -i, z_{1} = i. So, w_{1} = - z_{1}.
  • If the white card is taken in the first pull: w_{1} = i, z_{1} = -i. So, w_{1} = - z_{1}.

So the statement holds true for k = 0.

Induction step: Given w_{2k} = z_{2k}, w_{2k + 1} = -z_{2k + 1}, prove that w_{2(k + 1)} = z_{2(k + 1)}, w_{2(k + 1) + 1} = -z_{2(k + 1) + 1}.

  • If the red card is taken in the (2(k + 1))th time: w_{2(k + 1)} = -iw_{2k + 1} = iz_{2k + 1} = z_{2(k + 1)}.
  • If the white card is taken in the (2(k + 1))th time: w_{2(k + 1)} = iw_{2k + 1} = -iz_{2k + 1} = z_{2(k + 1)}.
  • If the red card is taken in the (2(k + 1) + 1)th time: w_{2(k + 1) + 1} = -iw_{2(k + 1)} = -iz_{2(k + 1)} = -z_{2(k + 1) + 1}.
  • If the white card is taken in the (2(k + 1) + 1)th time: w_{2(k + 1) + 1} = iw_{2(k + 1)} = iz_{2(k + 1)} = -z_{2(k + 1) + 1}.

So the statement follows.

Therefore \forall k \in \mathbb{N}, \mathbb{P}(w_{2k} = z_{2k}) = 1, \mathbb{P}(w_{2k + 1} = z_{2k + 1}) = 0.

(6)

    \[ \begin{matrix} \mathbb{E}(z_{n} + w_{n}) & = \frac{1}{2}(\mathbb{E}(z_{n} | n=2k, k \in \mathbb{N}) + \mathbb{E}(w_{n} | n=2k, k \in \mathbb{N})) + \frac{1}{2}(\mathbb{E}(z_{n} | n=2k+1, k \in \mathbb{N}) + \mathbb{E}(w_{n} | n=2k, k \in \mathbb{N}))\\& =  \frac{1}{2}(\mathbb{E}(z_{n} | n=2k, k \in \mathbb{N}) + \mathbb{E}(z_{n} | n=2k, k \in \mathbb{N})) + \frac{1}{2}(\mathbb{E}(z_{n} | n=2k+1, k \in \mathbb{N}) - \mathbb{E}(z_{n} | n=2k, k \in \mathbb{N}))\\& = \left ( \frac{i}{3} \right )^{n} \end{matrix} \]

(7)

    \[ \begin{matrix} \mathbb{E}(z_{n}w_{n}) & = \frac{1}{2}\mathbb{E}(z_{n} | n=2k, k \in \mathbb{N})\mathbb{E}(w_{n} | n=2k, k \in \mathbb{N}) + \frac{1}{2}\mathbb{E}(z_{n} | n=2k+1, k \in \mathbb{N})\mathbb{E}(w_{n} | n=2k, k \in \mathbb{N})\\& = \frac{1}{2}\mathbb{E}(z_{n} | n=2k, k \in \mathbb{N})^{2} - \frac{1}{2}\mathbb{E}(z_{n} | n=2k+1, k \in \mathbb{N})^{2}\\& = 0 \\ \end{matrix} \]


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *