# Challenge Micromass' big July Challenge

Tags:
1. Jul 8, 2016

### micromass

Staff Emeritus
In this thread, I present a few challenging problems from all kinds of mathematical disciplines.

RULES:
1. In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
2. It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3. If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4. You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
5. Some of the solutions of (parts of) the following questions are not known to the author of this thread. So it might be that the question is unsolvable. No, I will not tell you which questions.

1. SOLVED BY andrewkirk Let's work in the unit square $[0,1]\times [0,1]$. I pick two numbers at random from this unit square (with uniform distribution). What is the average length between these two numbers? What is the median length? What is the modus?

2. SOLVED BY QuantumQuest Find the sum of the reciprocals of a) the triangular numbers b) the square numbers c) the pentagonal numbers.

3. SOLVED BY mfb A man who owns $r$ umbrellas wanders back and forth between home and office, taking along an umbrella (if there is one at hand) in rain (it rains with probability $p$), but not in sunshine (which happens with probability $1-p$). Interpret and show the following statement: five umbrellas will protect the man at the $5\%$ level against again climate (i.e.\ any $p$).

4. SOLVED BY Erland Consider on $\mathbb{R}$ the smallest class $\mathcal{B}$ of functions $f:\mathbb{R}\rightarrow \mathbb{R}$ containing all continuous functions and closed under pointswise limits. Show that $\mathcal{B}$ consists exactly of the Borel measurable functions.

5. SOLVED BY fresh_42 Find all groups of order $p^2$ where $p$ is a prime number. Do the same for groups of order $p^3$.

6. SOLVED BY mfb, PeroK What is the probability that in a village with $2016$ inhabitants, every day is a birthday. Ignore leap years. Approximate solutions are acceptable, if you show that the approximation holds true in the limit.

7. SOLVED BY fresh_42 The set of $2\times 2$ matrices with integer entries and determinant $1$ is denoted by $SL_2(\mathbb{Z})$. Show that this group is generated by the matrices

$$s = \left(\begin{array}{cc} 0 & -1\\ 1 & 0\end{array}\right)~\text{and}~s = \left(\begin{array}{cc} 1 & 1\\ 0 & 1\end{array}\right)$$

Show furthermore that the group cannot be generated by a single element.

8. SOLVED BY fresh_42 Show that $SO_3(\mathbb{R})$ contains free groups of arbitrary finite orders.

9. SOLVED BY fresh_42 Let $H$ and $K$ be (not necessarily normal!) subgroups of a group $G$. Show that
$$|HK|\cdot |H\cap K| = |H|\cdot |K|$$
where $HK = \{hk~\vert~h\in H,~k\in K\}$.

10. SOLVED BY Infrared Let $(X,d)$ be a metric space. Show that $X$ is compact if and only if for every continuous function $f:X\rightarrow \mathbb{R}$ holds that $f(X)$ is bounded.

Last edited: Jul 17, 2016
2. Jul 8, 2016

### Staff: Mentor

Doesn't the second matrix here have determinant $-1$, not $1$?

3. Jul 8, 2016

### Infrared

I'll try to do number 10.

If $X$ is compact and $f$ is continuous, then $f(X)$ is a compact subset of $\mathbb{R}$ (continuous maps preserve compactness) and hence is bounded.

For the other direction, suppose $X$ is not compact. By lack of sequential compactness, there is a sequence $\{x_n\}_{n\in\mathbb{N}}$ with no convergent subsequence, in particular having no limit point. The set of these $x_n$ is therefore a closed subset of $X$ containing infinitely many points (otherwise there would be a constant convergent subsequence). If the distinct elements are $y_i$ and the set of all them denoted by $Y$, then the function $f:Y\to Y$ defined by $f(y_j)=j$ is continuous (since $Y$ is discrete, having no limit points) and hence may be extended to all of $X$ by the Tietze extension theorem since $Y$ is closed.

For number 8, what do you mean by a free group with finite order?

Last edited: Jul 8, 2016
4. Jul 8, 2016

### Staff: Mentor

He edited that post to fix the 2nd matrix. The bottom row is now 0 and 1.

5. Jul 8, 2016

### Staff: Mentor

So we pick one element of [0,1] × [0,1]? Denote it as (x,y).

If the first number is x, then the average length for this x is x*x/2 + (1-x)*(1-x)/2 = 1/2 (x^2 + (1-x)^2) where the first term comes from the other number being smaller, and the second term from the other number being larger. Integrate x from 0 to 1 to get 1/3 as average length.

To get the median length, consider the square [0,1] × [0,1] with the function |x-y|. The lines of equal value are parallel to the diagonal, we have to find the difference where the two diagonal corners have a combined area of 1/2. This happens at a distance of 1/sqrt(2) from the |x-y| = 1 corners, for a difference = median length of 1-1/sqrt(2).

The modus, looking at the square from above, would be the longest pair of diagonals - but those don't exist, they get longer the closer to |x-y| we get, and a length 0 is less likely than a length of some very small value. I don't think there is a well-defined modus.

I like the umbrella question, but I don't have a solution so far.I guess we have to assume that there is no correlation between the different trips.

6. Jul 8, 2016

### micromass

Staff Emeritus
No, we pick two numbers from $[0,1]\times [0,1]$, namely $(x,y)$ and $(x',y')$ and compute the distance between them.

7. Jul 8, 2016

### Staff: Mentor

That's interesting, I saw that problem earlier today and thought "it would make a nice puzzle here". It requires a different approach, but as I know how to approach that I'm out.

8. Jul 8, 2016

### Staff: Mentor

9.
Let $H = < a = \begin{pmatrix} 1 && 0 \\ 0 && -1\end{pmatrix} >$ and $K = < b = \begin{pmatrix} 0 && -1 \\ -1 && 0\end{pmatrix}>$.
These are subgroups of the Dieder group $D_4$ of order $2$. In addition they only share the identity. However, $ab = \begin{pmatrix} 0 && -1 \\ 1 && 0\end{pmatrix} \; , \; bab = \begin{pmatrix} -1 && 0 \\ 0 && 1\end{pmatrix}\; , \; abab = \begin{pmatrix} -1 && 0 \\ 0 && -1\end{pmatrix}$ and so on are already more than four elements in $<HK>$, which implies
$8 \cdot 1 = |HK| \cdot |H \cap K| > |H| \cdot |K| = 2 \cdot 2 = 4$ disproving the assertion.

The formula becomes true, if - say $H$ - is normal. Then there is a epimorphism $φ: K → HK / H$ with kernel $H \cap K.$ Normality of one of the subgroups is necessary for $φ$ being surjective in order to sort the elements in $HK.$

9. Jul 8, 2016

### micromass

Staff Emeritus
How did you define this

10. Jul 8, 2016

### Staff: Mentor

By matrix multiplication. $a$ is the reflexion at the $x$-axis and $b$ at $y=-x$. $<.>$ denotes "generated by all".
Is that what you meant?

$H = < a= ..$ was sloppy and incorrect. I should have written $a = ..$ and then $H = <a>$.

11. Jul 8, 2016

### micromass

Staff Emeritus
Check the updated exercise, I clarified. Note that $HK$ is not necessarily a subgroup.

12. Jul 8, 2016

### Staff: Mentor

In this case my proof holds. $φ:K → HK/H$ defined by $φ(k) = Hk$ is a surjective mapping: $φ^{-1}(Hhk) = k \in K.$ The set $\{k \in K \, | \, φ(k) \in H\} = K \cap H$ its kernel, i.e. $φ^{-1}(H) = H \cap K.$ The bijection $K / (H \cap K) ↔ HK / H$ then gives the formula $\frac{|K|}{|H \cap K|} = \frac{|HK|}{|H|}.$ The definition of equivalence classes is still possible. Missing normality or a group structure on $HK$ isn't necessary. This only implies, that the classes themselves don't build a group. Counting their elements is still possible and the equivalence guarantees that all classes have the same cardinality.

Surjectivity requires the elements of $HK$ to be ordered for otherwise they could generate the whole group as in my example.

13. Jul 8, 2016

### QuantumQuest

Problem 2

1. We can write the reciprocal of a triangular number as a difference of fractions

$\frac{2}{n(n+1)} = \frac{2}{n} - \frac{2}{n + 1}$ . Then the requested sum of the reciprocals is the series

$(\frac{2}{1} - \frac{2}{2}) + (\frac{2}{2} - \frac{2}{3}) + ( \frac{2}{3} - \frac{2}{4}) + ...$

Leaving out $\frac{2}{1}$ and taking the rest in pairs we have

$\frac{2}{1} + (- \frac{2}{2} + \frac{2}{2}) + (- \frac{2}{3} + \frac{2}{3}) + ...$

$= \frac{2}{1} + 0 + 0 + \cdots$

So, the sum is 2. The series is convergent and we can easily see this, if we take the first and last terms $2 - \frac{2}{n + 1} \rightarrow 2$.

2. We can use the Riemann zeta function

$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^{s}}$ for any complex number with real part > 1.

For $s = 2$ , $\zeta(2) = \sum_{n=1}^{\infty} \frac{1}{n^{2}} = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \cdots = \frac{\pi^2}{6} \approx. 1.6449..$

Now, we can show convergence bounding the $\zeta(2)$ from 1 to N : $\sum_{n=1}^{N} \frac{1}{n^{2}} \lt 1 + \sum_{n=2}^{N} \frac{1}{n(n - 1)}$

$= 1 + \sum_{n=2}^{N} (\frac{1}{n - 1} - \frac{1}{n})$ (method of difference of fractions)
$= 1 + (\frac{1}{1} - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + (\frac{1}{3} - \frac{1}{4}) + \cdots$
$= 1 + 1 + ( - \frac{1}{2}) + (\frac{1}{2}) + (\frac{1}{3}) + (\frac{1}{3}) +\cdots$
$= 1 + 1 - \frac{1}{N}$. As N goes to infinity the last sum goes to 2. But the infinite sum has only positive terms, so it converges.

3. The n - th pentagonal number is given by $\frac{n(3n - 1)}{2}$. So, the reciprocal is $\frac{2}{n(3n - 1)}$.

We can use the function $f(x) = \sum_{n=1}^{\infty} \frac{2}{n(3n - 1)} \cdot x^{3n}$

Now, $f(1) = \sum_{n=1}^{\infty} \frac{2}{n(3n - 1)}$ is the requested sum.

Taking the derivatives of $f(x)$ we have: $f'(x) =6\sum_{n=1}^\infty\frac{1}{3n-1}x^{3n-1},f''(x)=6\sum_{n=1}^\infty x^{3n-2}=\frac{6x}{1-x^3}$

Taking the double integral of the second derivative from 0 to 1 for x and from 0 to x for a variable u we set, we have

$f(1) = \int_0^1\int_0^x\frac{6u}{1-u^3}dudx$
$= \int_0^1\int_u^1\frac{6u}{1-u^3}dxdu$
$= \int_0^1\frac{6u(1-u)}{1-u^3}du$
$= \int_0^1\frac{6u}{1+u+u^2}du$
$= \int_0^1\frac{6u}{(u+\frac{1}{2})^2+(\frac{\sqrt3}{2})^2}du$
$= 3\ln3-\frac{\pi}{\sqrt3}.$

14. Jul 9, 2016

### Staff: Mentor

7.
Let $s = \left[\begin{array}{cc} 0 & -1\\ 1 & 0\end{array}\right]~\text{and }~t = \left[\begin{array}{cc} 1 & 1\\ 0 & 1\end{array}\right] .~\text{Then }~s^2 = \left[\begin{array}{cc} -1 & 0\\ 0 & -1\end{array}\right]~\text{, }~s^3 = s^{-1} = \left[\begin{array}{cc} 0 & 1\\ -1 & 0\end{array}\right]~\text{and }~t^n = \left[\begin{array}{cc} 1 & n\\ 0 & 1\end{array}\right] \; (n \in ℤ).$

Let me start with the funny part. If $SL_2(ℤ)$ were generated by a single element then it would have to be abelian.
However, $[s,t] = s^{-1}t^{-1}st = \left[\begin{array}{cc} 0 & 1\\ -1 & 1\end{array}\right] \cdot \left[\begin{array}{cc} 0 &-1 \\ 1 & 1\end{array}\right] = \left[\begin{array}{cc} 1 & 1\\ 1 & 2\end{array}\right] \neq 1$.

And now the first part. Basically it is the extended Euclidean algorithm that has to do the job. One method to model the iterations is by induction. We have to show that we can generate a matrix $\left[\begin{array}{cc} a & b\\ c & d\end{array}\right]$ with $ad-bc=1$ by $s$ and $t,$ i.e. as a word in them. The induction will be over $c \;$ because if $c=0$ we are done: $1=ad$ and our matrix is either $t^b$ or $s^2t^{-b}$.

In the case $c=1$ we have $t^as\,t^d = \left[\begin{array}{cc} 1 & a\\ 0 & 1\end{array}\right]\left[\begin{array}{cc} 0 & -1\\ 1 & 0\end{array}\right]\left[\begin{array}{cc} 1 & d\\ 0 & 1\end{array}\right] = \left[\begin{array}{cc} a & -1\\ 1 & 0\end{array}\right]\left[\begin{array}{cc} 1 & d\\ 0 & 1\end{array}\right]=\left[\begin{array}{cc} a & b\\ 1 & d\end{array}\right]$
since $1=ad-bc=ad-b.$

For the induction step we write $d=qc + r$ with $0 < r < c.$ ($r= 0$ would imply $c(aq-b) = 1$ which can't be for $c > 1.$) Now

$\left[\begin{array}{cc} a & b\\ c & d\end{array}\right]t^{-q}s \, =\, \left[\begin{array}{cc} a & b\\ c & d\end{array}\right]\left[\begin{array}{cc} -q & -1\\ 1 & 0\end{array}\right] = \left[\begin{array}{cc} -aq+b & -a\\ -cq+d & -c\end{array}\right] = \left[\begin{array}{cc} -aq+b & -a\\ r & -c\end{array}\right].$

15. Jul 9, 2016

### Staff: Mentor

7. Appendix (for completion): I have forgotten the case $c < 0$ in which case one has to multiply the matrix with $s^2$ first.

Last edited: Jul 9, 2016
16. Jul 9, 2016

### Staff: Mentor

Umbrellas:
We don’t know the initial state of the umbrella distribution, but the question apparently asks about the long-term behaviour.
We can assume that the system is in equilibrium, and every time the man goes to work or back (the problem is symmetric), the probability P(N) to have N umbrellas at his current location is the same.

There is just one option to end up at a place with 0 umbrellas: no umbrellas before (therefore 5 at the other location) and dry weather: In equilibrium, P(0)=P(5)*(1-p)
How can you end up with 1 umbrella? Either you had 4 at the origin and it does not rain, or you had 5 at work and it did rain: P(1)=P(4)*(1-p) + P(5)*p
This continues up to P(4).
How can you end up with 5 umbrellas? There was one at the origin and it rained, or there was none at the origin and we don’t have to know the weather: P(5)=P(1)*p + P(0)

One equation is redundant, but we have the additional constraint that the sum should be 1, thus for every given p, we have 6 equations for 6 unknowns and can solve the system.

Inspection of the equations shows that P(1)=P(2)=…=P(5). Therefore, P(0) = P(5)(1-p).
P(5)*(5+(1-p)) = 1, therefore $P(5)= \dots = P(1) = \frac{1}{6-p}$ and $P(0) = \frac{1-p}{6-p}$.

The average rate f of “walking through rain without umbrella” is P(0)*p: $$f = \frac{p(1-p)}{6-p}$$

This value is zero for p=0 and p=1, and has a maximum of $fmax=11-\sqrt{120} \approx 0.0455$ at $p=6-\sqrt{30} \approx 0.523$. On average, the man has to walk through the rain on less than 0.05 of the days.

It is easy to generalise the solution, just replace “6” by “n+1” where n is the number of umbrellas. The worst case is $p=n+1-\sqrt{n^2+n+1}$.

The worst case getting wet rate is then given by
$$fmax=\frac{ (n+1-\sqrt{n^2+n+1})(\sqrt{n^2+n+1}-n) }{\sqrt{n^2+n+1}} \approx \frac{1}{4n+2}$$

At n=5, the approximation has an error of just 0.1%, falling with larger n.

17. Jul 9, 2016

### Staff: Mentor

5.
I'll give it a try although one could possibly demand further examinations on the involved automorphism groups.
First let us assume a group $G$ of order $p^2$ and we pick an element $a \in G \; , \; a \neq 1.\; |a| \,, |U|$ denote the order of $a$ and the order of a subgroup $U \leq G$ resp., $\; <a>$ denotes the subgroup of $G$ generated by $a.$

If $|a| = p^2$ then $G \cong \mathbb{Z}_{p^2}.$

So let us assume $|a| = p$ , i.e. $<a> \,\cong\, \mathbb{Z}_p$
Since $a \in C := C_G(a) = \{g\in G \, | \, ga = ag \} \leq G\; ,\; C \;$ is a non-trivial subgroup of $G$.

Now $|C| = p^2$ implies $G = C$ , $a$ is a central element and $<a> \trianglelefteq G$ a normal subgroup. Hence $G \diagup <a> \,\cong\, \mathbb{Z}_p$ and $G \,\cong\, \mathbb{Z}_p \rtimes_\sigma \mathbb{Z}_p.$ Since $a$ commutes with every group element, esp. with the generator of the second factor, it is an abelian group and $G \,\cong\, \mathbb{Z}_p \times \mathbb{Z}_p \,\cong\, \mathbb{Z}^2_p \;$ a direct product in this case.

So we are left with the case $|C| = p$.
We now define a mapping $f : G \diagup C \longrightarrow \{gag^{-1} \;|\; g \in G\}$ into the set of all conjugates of $a$. Because $h \in gC$ implies $hah^{-1} = gcac^{-1}g^{-1} = gag^{-1} \; , \; f$ is well defined. It is also a bijection. But the conjugates of $a$ carry a group structure with $|G \diagup C| = \frac{p^2}{p} = p$ elements, i.e. it is isomorphic to $\mathbb{Z}_p$. Since $C$ has $p$ elements and $a \in C$ we have $G \; \cong \; <a> \rtimes_\sigma <b>$ with a conjugate $b$ of $a$.
Therefore $\sigma \in \{ 1, (a \longmapsto g_b a g_b^{-1}) \}$. The first case is the direct product again and the second results in a proper semidirect product of two copies of $\mathbb{Z}_p$ with an automorphism $\sigma$ that maps one generator to the other.

Therefore $|G| = p^2$ allows the groups $\mathbb{Z}_{p^2} \; , \; \mathbb{Z}^2_p$ and $\mathbb{Z}_p \rtimes_\sigma \mathbb{Z}_p$ with formally interchanging the two factors.

Now this formalism can be used to answer the question for $|G| = p^3$. I counted six isomorphism classes but I'm not quite sure.

For a single generator we get $G \; \cong \; \mathbb{Z}_{p^3} \;$ (case I).

For three generators $\{a_1,a_2,a_3\}$, each of order $p$ we can build $\mathbb{Z}_p \rtimes_\sigma \mathbb{Z}_p \rtimes_\tau \mathbb{Z}_p$ where $\sigma , \tau$ map the generators on each other.

For both being the identity we get the direct product $G \; \cong \; \mathbb{Z}^3_p \;$ (case II).

The permutations $(1,2,3)$ and $(1,3,2)$ as maps between the $a_i$ give two isomorphic groups with two proper semidirect products $\mathbb{Z}_p \rtimes_\sigma \mathbb{Z}_p \rtimes_\tau \mathbb{Z}_p\;$ (case III).
and the transpositions give three isomorphic copies $\mathbb{Z}_p \rtimes_\sigma \mathbb{Z}_p \times \mathbb{Z}_p \;$ (case IV).

That leaves us with two generators for $G$ which of one has order $p$ and the other order $p^2$.
Again we have $G \; \cong \; \mathbb{Z}_{p^2} \rtimes_\sigma \mathbb{Z}_p$ with the possibility for $\sigma$ either being the identity, in which case the product is direct (case V) or $\sigma$ maps the second generator of order $p$ to any element in $\mathbb{Z}_{p^2}$ of order $p \;$ (case VI).

18. Jul 9, 2016

### Infrared

There is no nontrivial semidirect product of cylic groups of order $p$ because any homomorphism $\mathbb{Z}_p\to Aut(\mathbb{Z}_p)\cong\mathbb{Z}_p^\times\cong\mathbb{Z}_{p-1}$ is zero.
I think this is also a problem for how you're treating groups of order $p^3$

(In fact there are only the two abelian groups of order $p^2$ up to isomorphism).

Last edited: Jul 9, 2016
19. Jul 9, 2016

### Staff: Mentor

8.
Given two rotations $R_φ,R_ψ$ with irrational angles $φ,ψ$, one with the $x$-axis as rotation axis, the other one with the $y$-axis as rotation axis define a free group of rank two. One may chose something like $φ=\sqrt{5} \pi \; , \; ψ=\sqrt{7} \pi$ or $φ=ψ=arccos(1 / \sqrt{11})$ to be sure. There is no way to establish a relation $R_φ^{n_1}R_ψ^{n_2}R_φ^{n_3}R_ψ^{n_4}... = 1.$
Or equivalently $f: S = \{φ,ψ\} \longrightarrow SO_3(\mathbb{R})$ with $f(φ) = R_φ\;,\;f(ψ)=R_ψ$ gives rise to a unique group homomorphism $g: F \longrightarrow SO_3(\mathbb{R})$ that extends $f$. Here $F = <φ,ψ>$ denotes the free group generated by $φ$ and $ψ.$
$g$ is defined by $g : φ^{n_1}ψ^{n_2}φ^{n_3}ψ^{n_4} \dots \longmapsto R_{φ^{n_1}}R_{ψ^{n_2}}R_{φ^{n_3}}R_{ψ^{n_4}} \dots$

The crucial part for any finite rank follows from the theorem of Nielsen-Schreier.
"Corollary 27.3: If $F$ is free of rank $r$ and $H ≤ F$ is a subgroup of finite index $n$ then $H$ is free of rank $nr − n + 1.$"
Here $r=2$ and the rank of $H$ therefore $n+1$. How to construct those cosets can also be found in:
http://people.brandeis.edu/~igusa/Math101b/NS.pdf

20. Jul 10, 2016

### micromass

Staff Emeritus
I might want to see some kind of justification for that.