Math Challenge - December 2020

[fresh_42]

Anyhow, could you please take a look and my original post? Thanks @fresh_42

The rest will hopefully follow soon...

I will, but I'll be busy the next two days, so it will take a while.

 

[member 587159]

It surprises me that nobody solved 5 yet.

For those who are interested and too lazy to look up the definition: A Hamilton group is a non-abelian group in which all subgroups are normal.

 

[cbarker1]

Problem 10 is called a derangement. Derangement is when the objects of the permutation is not placed in the exact spot.

 

[fishturtle1]

Spoiler: Problem 5

Proof: First we show $Q_8$ is non abelian. We know $ijk = -1$. Multiplying by $ji$ on the left gives $k = -ji$. Similarly, multiplying by $k$ on the right gives $-ij = -k$. So, $(-j)i = k \neq i(-j)$.

We note that if $G$ is a group and $H$ is a subgroup of $G$ with index $2$, then $H$ is normal in $G$. It seems clear that any nontrivial subgroup of $Q_8$ is generated by a single element of $Q_8$. Any subgroup generated by $\pm i, \pm j, \pm k$ has index $2$ and is therefore normal. The subgroup generated by $-1$ is the center of $Q_8$ and therefore is normal. So, $Q_8$ is Hamiltonian.

Next we note from Wikipedia: Let $N$ be a normal subgroup of $G$ and $H$ a subgroup of $G$. We say $G$ is the semi direct product written $N \rtimes H$ if $G = NH$, and these subgroups intersect trivially.

Let $A, B$ be two non trivial subgroups of $G$. Then $A \cap B \neq \lbrace 1 \rbrace$ since $-1 \in A \cap B$. And so the only way to write $Q_8$ as a semi direct product is $Q_8 = 1 \rtimes Q_8$. []
[\SPOILER]

 

[fresh_42]

It surprises me that nobody solved 5 yet.

For those who are interested and too lazy to look up the definition: A Hamilton group is a non-abelian group in which all subgroups are normal.

... where the latter are Dedekind groups. Thus a Hamilton group is a non abelian Dedekind group.

 

[fresh_42]

Proof: First we show $Q_8$ is non abelian. We know $ijk = -1$. Multiplying by $ji$ on the left gives $k = -ji$. Similarly, multiplying by $k$ on the right gives $-ij = -k$. So, $(-j)i = k \neq i(-j)$.

We note that if $G$ is a group and $H$ is a subgroup of $G$ with index $2$, then $H$ is normal in $G$. It seems clear that any nontrivial subgroup of $Q_8$ is generated by a single element of $Q_8$. Any subgroup generated by $\pm i, \pm j, \pm k$ has index $2$ and is therefore normal. The subgroup generated by $-1$ is the center of $Q_8$ and therefore is normal. So, $Q_8$ is Hamiltonian.

Why is the center the only possible subgroup of index $4$?

Next we note from Wikipedia: Let $N$ be a normal subgroup of $G$ and $H$ a subgroup of $G$. We say $G$ is the semi direct product written $N \rtimes H$ if $G = NH$, and these subgroups intersect trivially.

Let $A, B$ be two non trivial subgroups of $G$. Then $A \cap B \neq \lbrace 1 \rbrace$ since $-1 \in A \cap B$. And so the only way to write $Q_8$ as a semi direct product is $Q_8 = 1 \rtimes Q_8$. []

 

[fresh_42]

Spoiler: “CLT half of #9”

I think I've got the first half done ok: CLT.

From the Central Limit Theorem (CLT) we have that $Z=\tfrac{np - \mu _{p^{\prime}}}{\sigma _{p^{\prime}}}=1.645$ where the value $Z=1.645$ comes from the $95%$ confidence level from a Z-table, $\mu _{p^{\prime}} =np$ is the population mean, and $\sigma _{p^{\prime}} = \sqrt{\tfrac{p(1-p)}{n}}$ because it's CLT for a proportion and here $p=.48$ is the probability of heads for the sample of biased coin flips and we get

$$Z= \tfrac{0.48n-0.5n}{\sqrt{ n(0.48)(0.52) }} = 1.645 \Rightarrow n=\left( 1.645 \tfrac{\sqrt{ (0.48)(0.52)}}{0.02} \right) ^{\tfrac{2}{3}} = 12$$

where the ceiling function was applied because $n$ is integer.

Here's where it get fuzzy...

According to the weak law of large numbers, in particular the associated Chebyshev's inequality we have

$$P\left( \left| \bar{x}_n - \mu\right|\geq \epsilon\right)\leq \tfrac{\sigma ^2}{n\epsilon ^2}$$

From the margin of error we have $\epsilon =.02,$ and since it's binomial trials we have that $\sigma ^2 = np(1-p),$ here $p$ is the probability of heads for the sample being $p=0.48$. Hence
$$P\left( \left| p - \mu\right|\geq .02\right)\leq \tfrac{ n(0.48)(0.52)}{ n(0.02)^2}=0.05$$
since we are testing at the 95% confidence level--and freaking $n$ cancels instead of letting us solve for it: was I supposed to have used $\sigma _{p^{\prime}} ^2 = \tfrac{p(1-p)}{n}$ as in the CLT version? It might be wrong it's been a long while since my last stats course, and I'm kinda stoned so may have gremlins mucking about, speaking of which $n=12$ seems low.

You have to calculate $P\left(\dfrac{S_n}{n};0.5\right) = P(Z<0.02)$ for CLT and $P\left(\left| \bar{X}-0.48 \right|>0.02\right)\leq \dfrac{0.2496}{n(0.02)^2}$ for WLLN.

 

[YoungPhysicist]

#14:

Spoiler

An equilateral triangle with area 1 has the side length$\frac{2}{\sqrt[4]3}$, and the triangle can be divided into 3 smaller triangles by connecting PA, PB and PC, with x,y and z being their height respectively.

$\frac{2}{\sqrt[4]3}\cdot(x+y+z)\cdot\frac{1}{2}=1$
$x+y+z = \sqrt[4]3$

 

[fresh_42]

Subgroups which contain at least one pure quaternion have at least $4$ elements $\{\pm 1, \pm i\}$ hence index $2$ or less. And the center has index $4$. Other indices are not possible except for $Q_8$ and $\{1\}$. So the only question is: what are the subgroups of index $4$? (Or you could simply conjugate elements and calculate what happens, but your idea is nicer.)

Edit: I just saw that I answered the question ...

 

[fishturtle1]

They have $4$ elements $\{\pm 1, \pm i\}$ hence index $2$. And the center has index $4$. Other indices are not possible except for $Q_8$ and $\{1\}$. So the only question is: what are the subgroups of index $4$? (Or you could simply conjugate elements and calculate what happens, but your idea is nicer.)

I think the only subgroup of index $4$ is the center $\lbrace \pm1 \rbrace$. Any subgroup of order $2$ must be generated by an element of order $2$. There is only one element of order $2$ in $Q_8$, namely $-1$, and so there can only be one subgroup of order $2$. Equivalently, there is only one subgroup of index $4$ which we have found.

Since every element in the center commutes with any element in the group, we see the center is normal in $Q_8$.

 

[lekh2003]

I sort of brute forced this hopefully its fine.

Spoiler: Question 11

I solved simply added up the fractions and expanded everything out until I got the inequality:
$$
y^2z+y^2zx^2+2y^2zx+y^2z^2x+2yz+2yzx^2+yz^2x^2+yx^2+6yzx+2yz^2x+2yx+y+z+z^2x+2zx+x

\leq

zy^2+2zy+2zy^2x+4zyx+2zyx^2+2z^2yx+z^2yx^2+zy^2x^2+z^2y^2x+z^2y^2x^2+2yx+yx^2+y+z+2zx+z^2x+x+1$$

Then, I subtracted from both sides until I ended up with:
$6xyz \leq 4xyz + x^2y^2z^2 + 1$

I got my final inequality: $x^2y^2z^2+1-2xyz \geq 0$ Here's kind of where I didn't know what to do, haven't studied multivariable minima and maxima, but let's try anyways. I don't really know the notation, I kind of just went along with whatever came up.

$\frac{dv}{dx} = 2z^2y^2x-2zy = 0$

The other partial derivatives are pretty much the same. You can solve and get that $x y z = 1$. Hence, the initial equation at this minimum, not sure if its local or global, would be satisfied ($1^2 + 1 - 1 \geq 0$). I think there are other possibilities where xyz = 0 and that also satisfies a minimum, local or global, in which case the inequality is also satisfied ($0^2 + 1 - 0 \geq 0$). I think that ends up covering it all.

I hope I didn't mess anything up in the original calculation, and I hope my "proof" works (yeah it's definitely not a good proof).

I'd be interested in a non-brute force method.

 

[fresh_42]

I'd be interested in a non-brute force method.

You can definitely write it in a more elegant way, because it is troublesome to proofread your solution. The key inequality comes directly from $(xyz−1)^2>0.$ If you multiply the inequality by its denominators and apply it, then things become at least readable. And of course: write down the solution in reverse order!

 

[lekh2003]

You can definitely write it in a more elegant way, because it is troublesome to proofread your solution. The key inequality comes directly from $(xyz−1)^2>0.$

Spoiler

Ahh, that is exactly what I ended up with. So, I did it? Do I need to prove that (xyz-1)^2 is >= 0?

 

[fresh_42]

Spoiler

Ahh, that is exactly what I ended up with. So, I did it? Do I need to prove that (xyz-1)^2 is >= 0?

$\geq$ is sufficient, since we have all inequalities with the possibility of being equal. And $\geq 0$ is obvious. There is another little thing to consider: $6+\ldots = 4+2+\ldots \leq 4+ xyz +\frac{1}{xyz}.$

 

[lekh2003]

Time for another half-assed proof :P I hope I interpreted the problem correctly.

Spoiler: Question 15

To maximise the area of the tetrahedron would involve maximising the area of the face ABC, which can maximise the lengths of BC, BA, and AC. This would involve taking the limit of the tetrahedron as it approaches a flat tetrahedron where the area of ABC is equal to the area of ABD+BCD+ADC. Any other type of tetrahedron will slowly reduce the area since AD, BD, CD are constant and the more spread out they are, the larger ABC's area is.

Hence, this is simply a problem of finding the area of an equilateral triangle with a distance of 1 from the center to each of the vertices. Using simple trigonometry and law of cosines, you can find the side length of this equilateral triangle. I used a triangle with tau/3 and a side of length 1 on either side. The opposite is $\sqrt 3$. That's the side length of the equilaterqal triangle. Area of an equilateral triangle is $\frac{\sqrt 3}{4}s^2$. Hence, the triangle has area $\frac{3\sqrt 3}{4}$.

Since the surface area of the tetrahedron must be double the area of this equilateral triangle (when flat, this being the limit), then the maximum limit of area is ##\frac{3\sqrt 3}{2}.

 

[lekh2003]

$\geq$ is sufficient, since we have all inequalities with the possibility of being equal. And $\geq 0$ is obvious.

Oh yeah, of course its $\geq 0$, I'm a fool.

There is another little thing to consider:

How is this related?

 

[fresh_42]

Time for another half-assed proof :P I hope I interpreted the problem correctly.

Spoiler: Question 15

To maximise the area of the tetrahedron would involve maximising the area of the face ABC, which can maximise the lengths of BC, BA, and AC. This would involve taking the limit of the tetrahedron as it approaches a flat tetrahedron where the area of ABC is equal to the area of ABD+BCD+ADC. Any other type of tetrahedron will slowly reduce the area since AD, BD, CD are constant and the more spread out they are, the larger ABC's area is.

Hence, this is simply a problem of finding the area of an equilateral triangle with a distance of 1 from the center to each of the vertices. Using simple trigonometry and law of cosines, you can find the side length of this equilateral triangle. I used a triangle with tau/3 and a side of length 1 on either side. The opposite is $\sqrt 3$. That's the side length of the equilaterqal triangle. Area of an equilateral triangle is $\frac{\sqrt 3}{4}s^2$. Hence, the triangle has area $\frac{3\sqrt 3}{4}$.

Since the surface area of the tetrahedron must be double the area of this equilateral triangle (when flat, this being the limit), then the maximum limit of area is ##\frac{3\sqrt 3}{2}.

This is too hand wavy with too many unproven statements. Here is an image along which you (hopefully) formalize your argument:

 

[fresh_42]

Oh yeah, of course its $\geq 0$, I'm a fool.

How is this related?

Well, since you already got the credit and the solution is in any case a kind of brute force, I think I could simply post my solution:
$0\leq (xyz-1)^2=x^2y^2z^2-2xyz+1$ and thus $2\leq xyz+\dfrac{1}{xyz}.$ Therefore
\begin{align*}
6&+2x+2y+2z+\dfrac{2}{x}+\dfrac{2}{y}+\dfrac{2}{z}+xy+yz+zx\\
&+\dfrac{1}{xy}+\dfrac{1}{yz}+\dfrac{1}{zx}+\dfrac{y}{x}+\dfrac{z}{y}+\dfrac{x}{z}\\
&\leq xyz+\dfrac{1}{xyz}+4+2x+2y+2z+\dfrac{2}{x}+\dfrac{2}{y}+\dfrac{2}{z}+xy+yz+zx\\&+\dfrac{1}{xy}+\dfrac{1}{yz}+\dfrac{1}{zx}+\dfrac{y}{x}+\dfrac{z}{y}+\dfrac{x}{z}\\
&\Longleftrightarrow \\
&\left(1+x+\dfrac{1}{y}\right)\cdot \left(1+y+\dfrac{1}{z}\right)+\left(1+y+\dfrac{1}{z}\right)\cdot\left(1+z+\dfrac{1}{x}\right)\\&+\left(1+z+\dfrac{1}{x}\right)\cdot\left(1+x+\dfrac{1}{y}\right)\\
&\leq \left(1+x+\dfrac{1}{y}\right)\cdot\left(1+y+\dfrac{1}{z}\right)\cdot\left(1+z+\dfrac{1}{x}\right)
\end{align*}

 

[Mayhem]

I know it's been solved, but I just want to give it a shot myself for fun.

8d:

The denominator is almost a perfect square. Adding "zero" we can obtain:
$$I = \int_{-\infty}^{\infty} \frac{1}{x^2-2x+2}dx = \int_{-\infty}^{\infty} \frac{1}{x^2-2x+2 - 1 + 1}dx = \int_{-\infty}^{\infty} \frac{1}{(x-1)^2+1}dx$$
Using u-substitution, we obtain (the bounds don't change in this particular case).
$$I = \int_{-\infty}^{\infty} \frac{1}{u^2+1}dx$$
This is just a standard integral:
$$I = \left [\arctan(u) \right ]^\infty_{-\infty}$$
which leaves us with the two limits
$$I = \lim_{u \rightarrow \infty} \arctan(u) - \lim_{u \rightarrow -\infty} \arctan(u) = \frac{\pi}{2} - \left(- \frac{\pi}{2}\right) = \pi$$

For my own edification, how do I prove that $\int \frac{1}{x^2+1} dx = \arctan(x) + C$ and the value of the two limits? These are the things my professor would just tell us to "look up in a table" as our math course doesn't dig very deep.

 

[fresh_42]

For my own edification, how do I prove that $\int \frac{1}{x^2+1} dx = \arctan(x) + C$...

You can differentiate $x \longmapsto \tan(x)=\dfrac{\sin(x)}{\cos(x)}$ and use it to differentiate $x\longmapsto x=(\tan \circ \operatorname{arctan})(x).$ This would be a proof by differentiation instead of a direct integration. For a direct integration I'd try to do it with a Weierstraß substitution:
https://en.wikipedia.org/wiki/Weierstrass_substitution

... and the value of the two limits?

This depends on what you take for granted. E.g. if you know the graph of the tangent function then you automatically have the graph of the inverse function by reflection at the diagonal $y=x$. Another possibility is to use approximation formulas like
$$
\operatorname{arctan} x \approx \begin{cases}
\dfrac{x}{1+0.28x^2} &\text{ if } |x|\leq 1\\
\dfrac{\pi}{2}-\dfrac{x}{x^2+0.28}&\text{ if }x>1\\
-\dfrac{\pi}{2}-\dfrac{x}{x^2+0.28}&\text{ if }x<-1
\end{cases}
$$

 

[Mayhem]

You can differentiate $x \longmapsto \tan(x)=\dfrac{\sin(x)}{\cos(x)}$ and use it to differentiate $x\longmapsto x=(\tan \circ \operatorname{arctan})(x).$ This would be a proof by differentiation instead of a direct integration. For a direct integration I'd try to do it with a Weierstraß substitution:
https://en.wikipedia.org/wiki/Weierstrass_substitution

This depends on what you take for granted. E.g. if you know the graph of the tangent function then you automatically have the graph of the inverse function by reflection at the diagonal $y=x$. Another possibility is to use approximation formulas like
$$
\operatorname{arctan} x \approx \begin{cases}
\dfrac{x}{1+0.28x^2} &\text{ if } |x|\leq 1\\
\dfrac{\pi}{2}-\dfrac{x}{x^2+0.28}&\text{ if }x>1\\
-\dfrac{\pi}{2}-\dfrac{x}{x^2+0.28}&\text{ if }x<-1
\end{cases}
$$

Can arctan(x) be differentiated using the definition of the derivative? Then you could use F'(x) = f(x) as a "proof".

 

[fresh_42]

Can arctan(x) be differentiated using the definition of the derivative? Then you could use F'(x) = f(x) as a "proof".

It might work if you write it as a power series, but I guess it is quite hard if you only have
$$
\lim_{h \to 0} \dfrac{\operatorname{arctan}(x+h)-\operatorname{arctan}(x)}{h}
$$
The problem with any proof is always: 'Where are we allowed to start?', means what do we know already. If you can show $F'(x)=f(x)$ then you have automatically proven $\int F'(x)\,dx = f(x)+C$. And even this uses the fundamental theorem of calculus.

 

[Mayhem]

It might work if you write it as a power series, but I guess it is quite hard if you only have
$$
\lim_{h \to 0} \dfrac{\operatorname{arctan}(x+h)-\operatorname{arctan}(x)}{h}
$$
The problem with any proof is always: 'Where are we allowed to start?', means what do we know already. If you can show $F'(x)=f(x)$ then you have automatically proven $\int F'(x)\,dx = f(x)+C$. And even this uses the fundamental theorem of calculus.

I think any starting point is fine as long as the starting point is 1) well defined 2) doesn't result in circular reasoning. Using the fact that $(\arctan(x))' = 1/x^2 + 1$ isn't circular, but in practice it is a bad way thinking, as guess-and-check quickly becomes unfeasible.

 

[fresh_42]

I think any starting point is fine as long as the starting point is 1) well defined 2) doesn't result in circular reasoning. Using the fact that $(\arctan(x))' = 1/x^2 + 1$ isn't circular, but in practice it is a bad way thinking, as guess-and-check quickly becomes unfeasible.

My first suggestion should work. $(\tan x)'=\left(\dfrac{\sin x}{\cos x}\right)'=1+\tan^2 x.$ So
\begin{align*}
(id)'(x)=1&=(\tan \circ \operatorname{arctan})'(x)=(\tan y)'\cdot \operatorname{arctan }'(x)\\
&\Longrightarrow \\
\operatorname{arctan}'(x)&=\dfrac{1}{1+\tan^2(y)}=\dfrac{1}{1+\tan^2(\operatorname{arctan}(x))}=\dfrac{1}{1+x^2}
\end{align*}
but this uses $(\sin)'=\cos\, , \,(\cos)'=-\sin$ and $1=\sin^2+\cos^2$ in order to differentiate the tangent function.

I think that the direct way for $\int\frac{dx}{1+x^2}$ with the Weierstraß substitution works as well: $t:=\tan\left(\dfrac{x}{2}\right)$ which yields $dx=\dfrac{2dt}{1+t^2}.$ At least it immediately connects the rational polynomial with the tangent function.

 

[Mayhem]

My first suggestion should work. $(\tan x)'=\left(\dfrac{\sin x}{\cos x}\right)'=1+\tan^2 x.$ So
\begin{align*}
(id)'(x)=1&=(\tan \circ \operatorname{arctan})'(x)=(\tan y)'\cdot \operatorname{arctan }'(x)\\
&\Longrightarrow \\
\operatorname{arctan}'(x)&=\dfrac{1}{1+\tan^2(y)}=\dfrac{1}{1+\tan^2(\operatorname{arctan}(x))}=\dfrac{1}{1+x^2}
\end{align*}
but this uses $(\sin)'=\cos\, , \,(\cos)'=-\sin$ and $1=\sin^2+\cos^2$ in order to differentiate the tangent function.

I think that the direct way for $\int\frac{dx}{1+x^2}$ with the Weierstraß substitution works as well: $t:=\tan\left(\dfrac{x}{2}\right)$ which yields $dx=\dfrac{2dt}{1+t^2}.$ At least it immediately connects the rational polynomial with the tangent function.

I'm not super familiar with Weierstrass substitution, but it does seem to yield a useful result.

 

[Not anonymous]

Spoiler: Question 12

Answer: 5
Explanation: The modulo w.r.t. 7 of any natural number belongs to one of the 4 sets from $A=\{\{0\}, \{1, 6\}, \{2, 5\}, \{3, 4\}\}$, i.e. sets of the form $\{r, (7-r) \mod 7\}$ where $r$ belongs to the set of all possible remainders w.r.t. 7, i.e. {0, 1, 2, ..., 6}. Consider 2 distinct natural numbers $a, b$. It is easy to see that if $(a \mod 7)$ and $(b\mod 7)$ belong to 2 different sets in $A$, then neither their sum nor difference is divisible by 7. On the other hand, if they belong to the same set from within $A$, then 2 possibilities arise:

1. $(a \mod 7) = (b \mod 7)$, i.e. the remainders w.r.t. 7 of both $a$ and $b$ correspond the same element in the set. In this case, $(a - b) \equiv 0 \mod 7$, i.e. the difference is divisible by 7.
2. $(r_{a} \equiv (a \mod 7)) \neq (r_{b} \equiv (b \mod 7))$. Then, by definition of the sets, $r_{a} = (7 - r_{b}) \mod 7$. Therefore, $(r_{a} + r_{b}) = 7 \equiv 0 \mod 7 \Rightarrow (a+b) \equiv 0 \mod{7}$, i.e. the sum is divisible by 7.

Thus, for neither sum nor difference of $a, b$ to be divisible by 7, their modulo w.r.t. 7 must belong to 2 different sets from $A$. By pigeonhole principle, there can be at most 4 distinct natural numbers in a set such that the modulo w.r.t. 7 of no two of those belong to the same set from $A$. Thus, if we have a set of 5 (or more) natural numbers, at least two of those numbers will have either their sum or their difference divisible by 7.