Homura said that she uses applied statistics in witch hunts

The cast of Mahou Shoujo Madoka Magica are students of Mitakihara Middle School. Even though it is merely a middle school, coursework in Mitakihara can be quite challenging. The following are Math problems that have appeared thus far in the show, and their solutions:

## Episode 1

Episode one Math question 1

### Question 1

Any integer divided by 14 will have a remainder between 0 and 13. Given that $a$ has a remainder of 6 and $b$ has a remainder of 1 when divided by 14, what is the remainder of $x$ when divided by 14, given $x$ is an integer solution to $x^2-2ax+b=0$?

Solution:

This problem can be solved simply with modular arithmetic:

• $a \equiv 6 \pmod{14}$;
• $b \equiv 1 \pmod{14}$.
• $\displaystyle{x^2 - 2ax + b = 0}$ implies
• $x^2 - 12x + 1 \equiv 0 \pmod{14}$
• $x^2 + 2x + 1 \equiv 0 \pmod{14}$ (because $-12 \equiv 2 \pmod{14}$)
• $(x + 1)^2 \equiv 0 \pmod{14}$
• $x + 1 \equiv 0 \pmod{14}$ (because 14 is square-free)
• $x \equiv 13 \pmod{14}$ (because $-1 \equiv 13 \pmod{14}$).

Second Solution:

Homura used in Episode 1 a basic approach with usual integer arithmetic.

Let $\displaystyle{x = 14q + r, a = 14s + 6, b = 14t + 1}$.

Substitute into $\displaystyle{x^2 - 2ax + b = 0}$ to get after some calculations

$\displaystyle{x^2 - 2ax + b = 14c + (r+1)^2 = 0} \mbox{ with } \displaystyle{c = 14q^2 + 2q - 28qs - 2rs - 12q + t - r}$

14 divides $14c$ and 0, hence it also divides $(r+1)^2$. This implies that $r+1$ is divisible by 14.

The question asks for a remainder $r$ between 0 and 13, so we obtain $r = 13$.

### Question 2

Episode one Math question 2

Assuming that $p$ is a prime number and $n$ is an arbitrary natural number, prove that $(1+n)^p - n^p - 1 \,$ is divisible by $p$.

Solution:

By Fermat's Little Theorem, for any prime $p$ and integer $a$,

$a^p \equiv a \pmod{p} \,$

Thus:

$(1+n)^p - n^p - 1 \pmod{p} \,$ is equivalent to

$(1+n) - n - 1 \pmod{p} \,$ is equivalent to

$0 \pmod{p} \,$

So the overall expression is divisible by $p$.

Second solution:

The problem can be solved with the binomial theorem:

For $a, b$ not equal to $0$ and nonnegative integer $p$ it holds that:

$\displaystyle (a + b)^p = \sum_{k=0}^{p} \binom{p}{k} a^{p-k} b^k$

where the binomial coefficient $\binom{p}{k}$ is the integer $\frac{p(p - 1) \cdots (p - k + 1)}{k(k-1) \cdots 1}$ for $0 \leq k \leq p$.

Therefore,

$\displaystyle (1 + n)^p = \sum_{k=0}^{p} \binom{p}{k} n^k$

and

$\displaystyle (1 + n)^p - n^p - 1 = \sum_{k = 1}^{p - 1} \binom{p}{k} n^k$

since $\binom{p}{0} = \binom{p}{p} = 1$.

It holds that $\binom{p}{1} = p$. Since $p$ is a prime number, the factor $p$ in $\binom{p}{k}$ is not divisible by $k, k-1,\ldots, 2$ for $2 \leq k \leq p-1$. Therefore, $p$ divides $\binom{p}{k}$ for $1 \leq k \leq p-1$.

Since each summand on the right side is divisible by $p$, the whole sum, i.e. the left side is also divisible by $p$.

### Question 3

Episode one Math question 3

Find the integer solutions $(a,b)$ with $(a^3 + a^2 - 1) - (a - 1)b = 0 \,$.

Solution:

Episode one Math solution to question 3

\begin{align} (&a^3 + a^2 - 1) - (a - 1)b \\ & = (a^3 - 1) + (a^2 - 1) + 1 - (a - 1)b \\ & = (a - 1)(a^2 + a + 1) + (a - 1)(a + 1) + 1 - (a - 1)b \\ & = (a - 1)(a^2 + 2a - b + 2) + 1 = 0 \end{align}

Therefore,
$(a - 1)(a^2 + 2a - b + 2) = -1 \,$

$a, b$ are integers, therefore the factors $a - 1$ and $a^2 + 2a - b + 2 \,$ are integers too. Since the product is $-1$, one of the factors must be equal to $-1$, the other to $1$.

If $a - 1 = -1$ then $a = 0$ and from $a^2 + 2a - b + 2 = 1 \,$ we obtain $b = 1$.

If $a - 1 = 1$ then $a = 2$ and $a^2 + 2a - b + 2 = -1 \,$ implies that $b = 11$.

There are two integer solutions: $(a,b) = (0,1) \,$ or $(a,b) = (2,11) \,$.

Second Solution

The question can also be solved by polynomial division.

$(a^3 + a^2 - 1) - (a - 1)b = 0 \,$

$b = \frac{a^3 + a^2 - 1}{a - 1} = a^2 + 2a + 2 + \frac{1}{a - 1} \,$

As $b \in \mathbb{Z}$, $a^2 + 2a + 2 + \frac{1}{a - 1} \in \mathbb{Z}$, so $\frac{1}{a - 1} \in \mathbb{Z}$

As $1$ has only two factors: $1$ and $-1$,

$a-1 = 1 \,$ or $a-1 = -1 \,$

$a = 2 \,$ or $a = 0 \,$

Substituting the above values into the equation to find the corresponding $b$, we have

$(a, b) = (0, 1) \,$ or $(2, 11)$.

### Question 4

Episode one Math question 4

Given $\displaystyle F(x) = \frac{4x + \sqrt{4x^2 - 1}}{\sqrt{2x + 1} + \sqrt{2x-1}}$,

find the sum of $\displaystyle{F(1)+F(2)+F(3)+...+F(60)}$.

Solution:

Episode one Math, partial solution to question 4. Note that there are errors.

Simplying the fraction:

Notice that for any variables $a$ and $b$:

$\displaystyle{(a-b)(a+b) = a^2-b^2}$.

Let $\displaystyle{a = \sqrt{2x + 1}}$ and $\displaystyle{b = \sqrt{2x - 1}}$.

Multiply $\displaystyle{F(x)}$ by 1 or $\displaystyle{\frac{a-b}{a-b}}$ which is equal to $\displaystyle{\frac{\sqrt{2x + 1} - \sqrt{2x - 1}}{\sqrt{2x + 1} - \sqrt{2x - 1}}}$. The denominator becomes:

\begin{align} &(\sqrt{2x + 1} + \sqrt{2x - 1})(\sqrt{2x + 1} - \sqrt{2x - 1})\\ &= (2x + 1) - (2x - 1)\\ &= 2 \end{align}

The numerator becomes:

\begin{align} &(4x + \sqrt{4x^2 - 1} ) (\sqrt{2x + 1} - \sqrt{2x - 1})\\ &=(4x + \sqrt{(2x)^2 - 1)}) (a - b)\\ &=(4x + \sqrt{2x - 1} \sqrt{2x + 1} ) (a-b)\\ &=(4x + a b ) (a - b)\\ &=4x (a - b) + a^2 b - a b^2\\ &=4x (a - b) + (2x + 1) b - a (2x - 1)\\ &=4x (a - b) - 2x (a - b) + a + b\\ &=2x ( a - b) + a + b\\ &=(2x + 1) a - (2x - 1) b\\ &=a^3 - b^3 \end{align}

Therefore:

$\displaystyle {F(x) = \frac{a^3 - b^3 }{2}}$

Note that when $\displaystyle{ x = 1, 2, 3, 4, \ldots, 60}$;

$\displaystyle{ a^3 = 3^\frac{3}{2}, 5^\frac{3}{2}, 7^\frac{3}{2}, 9^\frac{3}{2}, \ldots, 119^\frac{3}{2}, 121^\frac{3}{2}}$;

$\displaystyle{ b^3 = 1^\frac{3}{2}, 3^\frac{3}{2}, 5^\frac{3}{2}, 7^\frac{3}{2}, 9^\frac{3}{2}, \ldots, 119^\frac{3}{2} }$;

Taking the sum over $\displaystyle{F(x)}$ for $\displaystyle{x}$ between $1$ and $60$, observe that the majority of the terms in $\displaystyle{a^3}$ and $\displaystyle{b^3}$ cancel out, leaving:

\begin{align} \sum_{x=1}^{60}F(x) &= \frac{121^\frac{3}{2} - 1^\frac{3}{2}}{2}\\ &=\frac{(11^2)^\frac{3}{2} - 1}{2}\\ &= 665 \end{align}

Thus, sum of $\displaystyle{F(x)}$ for $\displaystyle{x}$ between $1$ and $60$ is $665$. The solution can be generalized as equal to $\displaystyle{\frac{a(x_{\max}^3) - b(x_{\min}^3)}{2}}$. Where $\displaystyle{a}$ and $\displaystyle{b}$ are interpreted as functions of $\displaystyle{x}$.

## Episode 8

Homura predicted the location of Walpurgis Night to be the clock tower using statistics. The material Homura presents to Kyoko shows what looks like a sinusoidal regression, where a time series data is assumed to be following a sine curve over time and the properties (amplitude, frequency, phase) of the sine wave is predicted through statistics. For the purpose of predicting the location of Walpurgis Night, statistics done this way would use geographic coordinates (longitude and latitude) as observed data points and attempt to fit two different sine waves to data, one for longitude and one for latitude. The fact that a large pendulum exists in Homura's room may be viewed as supporting this interpretation that what Homura used was a sinusoidal regression, because the mechanical movement of a pendulum also follows a sinusoidal pattern.

Irrespective of what type of statistics was used, the fact that Walpurgis Night actually appeared at the predicted location indicates that the model fitted the data very well with only a negligible amount of error.

## Episode 9

Fibonacci sequence question that appeared in Episode 9

This advanced Algebra problem previously appeared in the first Tokyo University Entrance Exam:

### Problem

A number sequence $\displaystyle{ \{F(n)\} }$ that can be defined as $\displaystyle{F(1) = 1, F(2) = 1}$, $\displaystyle{F(n+2) = F(n) + F(n+1)}$ (where $\displaystyle{n \in \mathbb{N}}$) is called the Fibonacci sequence and its general solution is given by,

$\displaystyle{F(n) = \frac{\varphi^{n} - (-1/\varphi)^{n}}{\sqrt{5}}}$

$\displaystyle{\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887 \dots}$

Answer the following questions by using this fact if needed:

Define a sequence of natural numbers $\displaystyle{ \{X(n)\} }$ (where n is any natural number), in which each digit is either 0 or 1, set by the following rules:

(i) $\displaystyle{X(1) = 1}$

(ii) We define $\displaystyle{X(n+1)}$ as a natural number, which can be obtained by replacing the digits of $\displaystyle{X(n)}$ with 1 if the digit is 0, and with 10 if the digit is 1.

For example, $\displaystyle{X(1) = 1, X(2) = 10, X(3) = 101, X(4) = 10110, X(5) = 10110101, \ldots}$

Anecdote: $\displaystyle{X(n)}$ can be considered a clever analogy to the show, where Episode 10 should replaces Episode 1 and Episode 1 replaces Episode 0 in the viewer's next viewing.

(1) Find $\displaystyle{A(n)}$, defined as the number of digits of $\displaystyle{X(n)}$.

(2) Find $\displaystyle{B(n)}$, defined as the numbers of times '01' appears in $\displaystyle{X(n)}$? For example, $\displaystyle{B(1) = 0, B(2) = 0, B(3) = 1, B(4) = 1, B(5) = 3, \ldots}$

### Solution

#### Part 1

Let $\displaystyle{A(n)}$ equal to the number of digits in $X(n)$, which consists solely of 1s and 0s. Let's suppose $\displaystyle{x(n)}$ is the number of 0s in $\displaystyle{X(n)}$ at the n-th iteration (poor choice of variable by the student). Let's suppose $\displaystyle{y(n)}$ is the number of 1s in $\displaystyle{X(n)}$ in the n-th iteration, then $\displaystyle{x(n) + y(n) = A(n)}$. Since

• Every time a 0 appears, it is replaced with 1 at the next iteration, contributing to a single 1 in $\displaystyle{X(n+1)}$.
• Every time a 1 appears, it is replaced with 10 at the next iteration, contributing to a single 1 and a single 0 in $X(n+1)$.

it follows that the number of 0s in the next iteration is equal to the number of 1s previously:

$\displaystyle{x(n+1)= y(n)}$ ;

and the number of 1s in the next iteration is equal to the number of 0s AND the numbers of 1s previously:

$y(n+1)= \displaystyle{x(n)+y(n)}$ .

Next, prove that $x(n)$ is a Fibonacci sequence, since we know that:

• $\displaystyle{y(n+1) = x(n) + y(n)}$ ;
• $\displaystyle{x(n+2) = y(n+1)}$ ;
• $\displaystyle{x(n+1) = y(n)}$ ;

by substition we can show,

\begin{align} &x(n+2)\\ &= y(n+1)\\ &= x(n) + y(n)\\ &= x(n) + x(n+1) \end{align}

Hence, $\displaystyle{x(n+2) = x(n+1) + x(n)}$.

Thus $\displaystyle{x(n)}$ fits the definition of a Fibonacci sequence. Since $\displaystyle{x(n)}$ is a Fibonacci sequence, it follows that $\displaystyle{y(n)}$ is also a Fibonacci sequence (given that $\displaystyle{x(n+1) = y(n)}$). Therefore, since it has already been shown that:

• $\displaystyle{x(n+2)=x(n+1)+x(n)}$
• $\displaystyle{y(n+2)=y(n+1)+y(n)}$

It follows that $\displaystyle {x(n+2)+y(n+2)=x(n+1)+y(n+1)+x(n)+y(n)}$.

Recall that $\displaystyle{A(n)=x(n)+y(n)}$, therefore

$\displaystyle{A(n+2)=A(n+1)+A(n)}$ .

Since, $\displaystyle{X(1) = 1, X(2) = 10, X(3) = 101, X(4) = 10110, X(5) = 10110101, \ldots}$

It follows that $\displaystyle{A(1) = 1, A(2) = 2, A(3) = 3, A(4) = 5, A(5) = 8, \ldots}$

Recall by definition of the Fibonacci sequence: $\displaystyle{\{F(n)\} = \{1, 1, 2, 3, 5, 8, \ldots\}}$. Therefore $\displaystyle{A(n) = F(n+1)}$, or

$\displaystyle{A(n) = F(n+1) = \frac{\varphi^{n+1} - (-1/\varphi)^{n+1}}{\sqrt{5}}}$

#### Part 2

Let $B(n)$ be the number of times the sequence $01$ appears in $X(n)$. Any two digits in $X(n)$ may be $00$, $01$, $10$, $11$, and the corresponding digits in the next iteration $X(n+1)$ will be

• $00 \rightarrow 11$
• $01 \rightarrow 110$
• $10 \rightarrow 101$
• $11 \rightarrow 1010$

Thus, any two digit sequence in $X(n)$ that begins with 1* will contribute to a $01$ sequence in the next iteration. In other words, $B(n+1)$ equals $y(n)$, except when unit digit of $X(n)$ is 1, or:

$B(n+1) = y(n) - odd(X(n))$

where

• $odd(n) = 1$ if $n$ is odd (unit digit is 1)
• $odd(n) = 0$ if $n$ is even (unit digit is 0)

It can be seen that $odd(n) = odd(X(n))$ for all $n$. To prove this inductively: observe that $odd(X(1)) = odd(1)$. Now let $odd(X(n)) = odd(n)$, then if $n$ is even, $X(n)$ is even, thus $X(n)$ ends with 0, which gets mapped to 1, making $X(n+1)$ odd and so $odd(X(n+1)) = odd(n+1)$. And if $n$ is odd, then $X(n)$ is odd, thus $X(n)$ ends with 1, which gets mapped to 10, making $X(n+1)$ even, and so $odd(X(n+1)) = odd(n+1)$.

$y(n)$ is a fibonacci sequence with starting values: $y(1) = 1$, $y(2) = 1$, $y(3) = 2$, thus $y(n) = F(n)$

$B(n+1) = F(n) - odd(n)$

$B(n) = F(n-1) - odd(n-1)$, or

$\displaystyle{B(n) = F(n-1) - odd(X(n-1)) = \frac{\varphi^{n-1} - (-1/\varphi)^{n-1}}{\sqrt{5}} - odd(X(n-1))}$

## Episode 10

Same as Episode 1.

## Episode 11

Pieces of papers floats by Homura as she faces Walpurgis Night. On it are calculations done by hand by Homura. Most likely, these are ballistics of the big guns. Two pairs of Xs and Ys on each of the four pieces of paper, making it 8 shots in all.

## Movie 3: Rebellion

### Problem A

The first problem posed, (a), was to calculate $\int\frac{\arcsin^3x}{\sqrt{1-x^2}}\,dx$

We can perform the substitution $u=\arcsin x \longrightarrow \frac{du}{dx}=\frac{1}{\sqrt{1-x^2}}$ and so rewrite the integral as $\int u^3\,du$

This can be easily solved via basic integration formulas: $\int u^3\,du=\frac{1}{4}u^4+C$

Undoing the substitution we get the solution: $\frac{1}{4}\arcsin^4x + C$

### Problem B

The second problem, (b), was to calculate $\int x\ln(x^2+y)\,dx$ In order to solve it we'll assume $\displaystyle y$ to be a parameter independent from the value of $\displaystyle x$ and $\displaystyle\ln x$ to denote the natural logarithm of $\displaystyle x$.

Performing the substitution $u=x^2+y\longrightarrow\frac{du}{dx}=2x$ we can rewrite the integral as $\frac{1}{2}\int\ln u\,du$

This can be solved integrating by parts: $\frac{1}{2}\int \ln u\,du=\frac{1}{2}(u\ln u - \int1\,du)=\frac{1}{2}u(\ln u - 1)$

And the final answer in obtained undoing the substitution: $\frac{1}{2}(x^2+y)\ln((x^2+y)-1)+C$

### Problem C

One of the problems posed, (c), was to calculate $\int\frac{x^3+2x^2+10x}{x^2-x+1}\, dx$.

The answer is to first simplify the function: $\frac{x^3+2x^2+10x}{x^2-x+1} = x + 3 + \frac{12x - 3}{x^2-x+1} = x + 3 + 6\frac{2x - 1}{x^2-x+1} + \frac{3}{x^2-x+1}$. Note that $x^2-x+1$ has only simple complex zeros.

It holds $\int x + 3 \, dx = \frac{1}{2}x^2 + 3x + C$.

The general formula $\int\frac{f'(x)}{f(x)}\, dx = \ln|f(x)| dx + C$ can be used to calculate $\int \frac{2x - 1}{x^2-x+1} \, dx = \ln(x^2-x+1) + C$.

For the last term, $\int\frac{dx}{a^2 + x^2} = \frac{1}{a}\arctan \frac{x}{a} + C$ can be used (with some additional calculations) to obtain the solution

$\int\frac{x^3+2x^2+10x}{x^2-x+1}\, dx = \frac{1}{2}x^2 + 3x + 6\ln(x^2-x+1) + 2\sqrt{3} \arctan \frac{2x-1}{\sqrt{3}} + C$