Micromass' big July Challenge

[micromass]

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.

 

[PeterDonis]

7. 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\\ 1 & 0\end{array}\right)
$$

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

 

[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?

(BTW, please check your PMs)

 

[Mark44]

7. 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\\ 1 & 0\end{array}\right)
$$

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

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

 

[mfb]

1.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?

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.

 

[micromass]

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.

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

 

[mfb]

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.

 

[fresh_42]

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.$

 

[micromass]

These are subgroups of the Dieder group $D_4$ of order $2$.

How did you define this

 

[fresh_42]

How did you define this

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>$.

 

[micromass]

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>$.

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

 

[fresh_42]

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

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.

 

[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}.$

 

[fresh_42]

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].$

 

[fresh_42]

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

 

[mfb]

Umbrellas:

3. 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 prbability $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$).

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.

 

[fresh_42]

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).

 

[Infrared]

5.
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.

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).

 

[fresh_42]

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

 

[micromass]

There is no way to establish a relation $R_φ^{n_1}R_ψ^{n_2}R_φ^{n_3}R_ψ^{n_4}... = 1.$

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

 

[Biker]

First time participating :p,

In 6, Can I assume independence between days? because if you are looking for an approximation, this will give you a good approximation if N > 2000

Some basic probability, To not have a birthday everyday it is just (364/365)^N and the other way around is just 1-(364/365)^N.

For the year, It is just (1-(364/365)^N)^365.

So an approximation is: 0.234757
When the answer might be: 0.229

 

[andrewkirk]

Hold on, silly mistake in here - needs fixing.

 

[micromass]

First time participating :p,

In 6, Can I assume independence between days? because if you are looking for an approximation, this will give you a good approximation if N > 2000

Some basic probability, To not have a birthday everyday it is just (364/365)^N and the other way around is just 1-(364/365)^N.

So this last number would give us the probability that someone has a birthday on a specific day. But I don't think these events are independent for different days.

 

[Biker]

So this last number would give us the probability that someone has a birthday on a specific day. But I don't think these events are independent for different days.

Yes, I know that they are not independent and they shouldn't. It is just this method gives a good approximation as N grows up.

The actual solution( I think): Shouldn't we just use stirling numbers of second kind ?

 

[PeroK]

I have an estimate for #6. First, refer to the Big Probability Challenge, problem 9:

https://www.physicsforums.com/threads/micromass-big-probability-challenge.872528/page-4#post-5479076

What we can get from this is the expected number of days that are not birthdays. Using this calculation, I get an expected number of $7$ days without a birthday after 1441 people. The reason I chose $7$ is just that I had tested out my calculations on $n$ people and days of the week. The estimate would be better the larger the number remaning. And, to be exact, you go all the way to 365 remaining with 2016 left.

So, if we take this a typical scenario: the question is the probablity that the remaining $7$ days are covered by $575$ people. My calculation for this is 0.20.

That's my best estimate at this stage, in any case!

PS I'll try to work on an algorithm and post that.

 

[PeroK]

The algortithm for #6 is:

If there are $n$ people and $d$ days, then for $x = 1$ to $d$:

The probablity that all $n$ people have birthdays in the first $x$ days is:

$q_x = (\frac{x}{d})^n$

The probability that all $n$ people have birthdays covering precisely the first $x$ days:

$p_1 = q_1$

And, for $x > 1$:

$p_x = q_x - \binom{x}{1}p_1 - \binom{x}{2}p_2 \dots - \binom{x}{x-1}p_{x-1}$

The probability that $n$ people have birthdays covering precisely (any) $x$ days is:

$P_x = \binom{d}{x}p_x$

The probability that every day is a birthday is:

$P = 1 - P_1 - P_2 \dots - P_{d-1}$

Alternatively:

$P = P_d = p_d = 1 - \binom{d}{1}p_1 - \binom{d}{2}p_2 \dots - \binom{d}{d-1}p_{d-1}$

 

[PeroK]

I claim the solution to number 6 is:

$P = 1 - \sum_{i=1}^{d-1} \binom{d}{i} [(\frac{i}{d})^n - \sum_{j=1}^{i-1} \binom{i}{j} (\frac{j}{d})^n]$

With $d = 365$ and $n = 2016$

I took another look at this and, sadly, the formula is not right.

 

[mfb]

Birthday problem:

For a fixed date, we have a probability of x=0.00396 that no one has their birthday there. That leads to an expectation value of 365x=1.44633 days without birthdays. If the days were independent, we would get a binomial distribution which we approximate as Poisson distribution, for an expectation value of 1.44633 the probabilities are:
=0 days: 0.235
=1 day: 0.341
=2 days: 0.246
= 3 days: 0.119
= 4 days: 0.043
= 5 days: 0.012
>= 6 days: 0.004
Let's check how accurate the approximation is - this is also the first step for the more accurate estimate.

1 = P(=0 days) + P(=1day) + P(=2days) + P(=3days) + P(=4days) + P(>=5days)
= P(=0 days) + 365*P(=1. January free) + (356 choose 2)*(=1. and 2. January free) + ...
= P₃₆₅(=0 days) + 365*x*P₃₆₄(=0 days) + (356 c 2)*x²*P₃₆₃(=0 days) + ...
where P_n is the equivalent problem in a year with n days. We can estimate this via a Poisson distribution as well:

P₃₆₄(=0 days) = 0.242
P₃₆₃(=0 days) = 0.248
P₃₆₂(=0 days) = 0.254
P₃₆₁(=0 days) = 0.261
P₃₆₀(=0 days) = 0.267

We expect all those numbers to be a bit wrong due to correlations: If one day is free, the others are a bit less likely to be free, thus reducing the probability of multiple free days - for a given exact expectation value this also reduces the probability of no free day. But that correlation effect is similar for 365 to 361 days: all the values are off by about the same factor. We can use the equation to estimate this factor. The sum of all contributions up to 5 free days is 1.031, but it should be 0.996 (taking the 0.004 from >=6 days without correction). That gives a correction factor of 0.966. The first estimate was too high by about 3%.

The improved value is 0.227 probability that all birthdays occur at least once.

Edit: Didn't see PeroK's posts. I looked into some inclusion/exclusion principle as well but that didn't work properly.

 

[fresh_42]

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

8.
Here's the shortest version I could think of without getting into coordinates and so on.

Assume we have some relation $\mathcal{R}$ in $SO_3(ℝ).$
Since $SO_3(ℝ)$ is the covering group of $SU_2(ℂ) \; , \; \mathcal{R}$ becomes a relation in $SU_2(ℂ).$
Now we may consider two of the generating matrices $R(φ) = \begin{pmatrix} \cos φ& \sin φ \\ -\sin φ & \cos φ \end{pmatrix}$ and $R(ψ) = \begin{pmatrix} \cos ψ& i \sin ψ \\ i \sin ψ & \cos ψ \end{pmatrix}$ and choose $φ = \arccos \frac{1}{2 π} \; , \; ψ = \arccos \frac{1}{11 e}.$
Thus $\cos φ = \frac{1}{2π} \; , \; \cos ψ = \frac{1}{11 e} \; , \; \sin φ = \frac{\sqrt{4 \pi^2 - 1}}{2 \pi} \; , \; \sin ψ = \frac{\sqrt{121 e^2 - 1}}{11 e}.$

Since all entries of $\mathcal{R}$ are polynomials in those numbers, $\pi$ and $e$ being not algebraic guarantees that it cannot be non-trivial. The third generator can be chosen $\begin{pmatrix} e^{iχ} & 0 \\ 0 & e^{-iχ} \end{pmatrix}$ which would deliver even more transcendent numbers from the square roots but we need only two free generators.
The statement now follows by Nielsen-Schreier.

(It is probably the same argument without the covering group, but that brought me to the idea and it looks somehow more "computational". And the transcendent numbers won't be necessary either, but it makes the argument look more obvious.)

 

[fluidistic]

I ran a python simulation for problem 6.
I did the experiment 10k times, and all days were birthdays 2327 times.

 

[mfb]

Then something is wrong with your simulation. Edit: Sorry, misread the post, the result is fine.

I did it the long way: make a huge 365x2016 matrix, keep track of the probability that N days are birthdays for M persons. The result: 0.230987
Directly between my the estimates in my previous post. For reference, here are the other relevant options for k days that are not birthdays:
>5 days: 0.0031978085
5 days: 0.0115619723
4 days: 0.0419113291
3 days: 0.1193038793
2 days: 0.2500413533
1 days: 0.3429964758
0 days: 0.2309871816

 

[Clever Penguin]

I think 6. may have something to with combinations, permutations, and factorials?

 

[micromass]

Since $SO_3(ℝ)$ is the covering group of $SU_2(ℂ)$

Isn't it the other way around? $SU_2(\mathbb{C})$ is the universal covering group of $SO_3(\mathbb{R})$.

 

[fluidistic]

Then something is wrong with your simulation.
(...)
0 days: 0.2309871816

This is not that much different from the result I obtained. I don't understand why my simulation is wrong, I only did 10k trials. Had I done more, it would have converged toward the real ratio. My ratio is 0.2327 and you got 0.2310.

 

[fresh_42]

Isn't it the other way around? $SU_2(\mathbb{C})$ is the universal covering group of $SO_3(\mathbb{R})$.

As I saw my mistake it had been too late to edit it. But the quotient is $\{± I\}$ so it was not that important.