Math Challenge - December 2020

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
14,117
11,371
Summary: Circulation, Number Theory, Differential Geometry, Functional Equation, Group Theory, Infinite Series, Algorithmic Precision, Function Theory, Coin Flips, Combinatorics.


1. (solved by @etotheipi ) Given a vector field
$$
F\, : \,\mathbb{R}^3 \longrightarrow \mathbb{R}^3\, , \,F(x,y,z)=\begin{pmatrix}x-y^2\\x^2\\z\end{pmatrix}
$$
Calculate the circulation of ##F## along the mathematically positive oriented unit circle in the ##(x,y)##-plane
(a) by using the curl of a vector field.
(b) directly by an appropriate path.

2. An odd prime ##p## can be written as ##p=x^2+y^2## with integers ##x,y\in \mathbb{Z}## if and only is ##p\equiv 1 \mod 4.##

3. Let ##\mathbb{T}^n :=\mathbb{R}^n/\mathbb{Z}^n## equipped with the quotient topology according to the projection
$$
\pi\, : \,\mathbb{R}^n \longrightarrow \mathbb{T}^n\, , \,\pi(a)=a+\mathbb{Z}^n.
$$
Show that ##\mathbb{T}^n## is a topological manifold.

4. Let ##\alpha\in \mathbb{R}-\{0\}.## Determine all functions ##f:\mathbb{R}_{>0}\longrightarrow \mathbb{R}_{>0}## which satisfy for all ##x,y\in \mathbb{R}_{>0}##
$$
f(f(x)+y)=\alpha x+\dfrac{1}{f\left(\dfrac{1}{y}\right)}
$$

5. (solved by @fishturtle1 ) Show that the quaternion group ##G=\{\pm 1,\pm i,\pm j,\pm k\}## is a Hamilton group, and cannot be written as a semidirect product in a nontrivial way.

6. (solved by @LCSphysicist and @etotheipi )
(a) Calculate
$$
\dfrac{1}{2}-\dfrac{1}{12}+\dfrac{1}{40}-\dfrac{1}{112} \mp \ldots=\sum_{k=0}^{\infty}(-1)^k\dfrac{1}{(2k+1)2^{k+1}}\,.
$$
6. (b) Prove ##\dfrac{1}{2!}+\dfrac{2}{3!}+\dfrac{3}{4!}+\ldots=1\,.##

7. Prove
$$
\tan^{-1}(1/2)+\tan^{-1}(1/3)=\pi/4=4\tan^{-1}(1/5)-\tan^{-1}(1/239)
$$
and use the power series representation
$$
\tan^{-1}(x)=x-\dfrac{x^3}{3}+\dfrac{x^5}{5}-\dfrac{x^7}{7} \mp \ldots=\sum_{k=0}^{\infty}(-1)^k\dfrac{x^{2k+1}}{2k+1}
$$
to determine how many terms would it take to compute ##\pi## up to ##100## digits by ##\pi=4\tan^{-1}(1)## and by the formulas above.

8. (solved by @Gaussian97 ) Calculate the following integrals
(a) ##\displaystyle{\int_0^{2\pi}e^{(e^{it})}\,dt}##
(b) ##\displaystyle{\int_{|z|=1}\dfrac{\sin(z^2)}{(\sin z)^2}\,dz}##
(c) ##\displaystyle{\int_{|z|=1}\sin \left(e^{1/z}\right)\,dz}##
(d) ##\displaystyle{\int_{-\infty}^\infty \dfrac{1}{x^2-2x+2}\,dx}##

9. Suppose someone gives you a coin and claims that this coin is biased; that it lands on heads only ##48\%## of the time with an error margin of ##2\%##. You decide to test the coin for yourself. If you want to be ##95\%## confident that this coin is indeed biased, how many times must you flip the coin? Compare the estimations by the weak law of large numbers and by the central limit theorem!

10. (solved by @Gaussian97 ) A hat-check boy at a congress held at Hilbert's hotel completely loses track of which of hats belong to which owners, and hands them back at random to their owners as the latter leave. What is the probability ##P## that nobody receives their own hat back?




1606835746499.png


High Schoolers only

11.
(solved by @lekh2003 ) Prove that
$$
\dfrac{1}{1+x+\dfrac{1}{y}}+\dfrac{1}{1+y+\dfrac{1}{z}}+\dfrac{1}{1+z+\dfrac{1}{x}}\leq 1
$$
for all positive real numbers ##x,y,z.##

12. Which is the smallest natural number greater than one such that the following statement holds:
In any set of ##n## natural numbers are at least two numbers, whose sum or difference is dividable by seven.

13. Determine
$$
\left[ \dfrac{1}{\sqrt{1}+\sqrt{2}} + \dfrac{1}{\sqrt{3}+\sqrt{4}} + \dfrac{1}{\sqrt{5}+\sqrt{6}}+ \ldots + \dfrac{1}{\sqrt{n^2-4}+\sqrt{n^2-3}} +\dfrac{1}{\sqrt{n^2-2}+\sqrt{n^2-1}} \right]
$$
for any odd natural number ##n\geq 3## where ##[n]=\lfloor n\rfloor ## is the greatest integer smaller or equal ##n.##

14. (solved by @YoungPhysicist ) Given a point ##P## inside an equilateral triangle ##\triangle ABC## with area ##1.## Show that for the lengths ##x,y,z## of the perpendiculars of ##P## onto the sides of the triangle holds ## x+y+z=\sqrt[4]{3}.##

1606835569513.png



15. Prove: If for the edges of a tetrahedron ##ABCD## holds
$$
\overline{AD}=\overline{BD}=\overline{CD}=1 \text{ and } \overline{AB}=\overline{BC}=\overline{CA}\,,
$$
then its surface is smaller than ##\dfrac{3\sqrt{3}}{2}.##
 
Last edited:
  • Like
Likes JD_PM, YoungPhysicist, Greg Bernhardt and 1 other person

Answers and Replies

  • #2
etotheipi
Gold Member
2020 Award
3,156
2,110
Firstly, just by doing the explicit line integral$$\begin{align*}

\oint_C \vec{F} \cdot \vec{r}'(\theta) d\theta &= \int_0^{2\pi} \vec{F} \cdot \hat{\theta}(\theta) d\theta \\


&= \int_0^{2\pi} \left( -\sin{\theta} \left[ \cos{\theta} - \sin^2{\theta} \right] + \cos^3{\theta} \right) d\theta \\

&= \int_0^{2\pi} \left( \sin^{3}(\theta) + \cos^3{\theta} - \frac{1}{2} \sin{2\theta} \right) d \theta \\

& = \int_0^{2\pi} \left( \frac{3}{4} \left[ \sin{\theta} + \cos{\theta} \right] + \frac{1}{4} \left[ \sin{3\theta} + \cos{3\theta} \right] - \frac{1}{2} \sin{2\theta} \right) d\theta \\

&= \left[ \frac{3}{4} \left[\sin{\theta} - \cos{\theta} \right] + \frac{1}{12} \left[ \sin{3\theta} - \cos{3\theta} \right] + \frac{1}{4} \cos{2\theta} \right]_0^{2\pi} = 0


\end{align*}$$Secondly, by using Stokes' theorem,$$\int_C \vec{F} \cdot d\vec{r} = \int_A (\nabla \times \vec{F}) \cdot d\vec{S} = \int_A 2(x+y) dS$$But since ##g(x,y) \equiv 2(x+y)## satisfies ##g(x,y) = -g(-x,-y)##, and the region ##A## is the unit circle, by symmetry this must be zero.
 
Last edited:
  • #3
etotheipi
Gold Member
2020 Award
3,156
2,110
For the first identity$$\tan{\left(\arctan{\left(\frac{1}{2} \right)} + \arctan{\left(\frac{1}{3} \right)} \right)} = \frac{1/2 + 1/3}{1-1/6} = 1$$and for the latter$$
\begin{align*}
\tan{\left( 4\arctan{\left( \frac{1}{5} \right)} - \arctan{\left( \frac{1}{239} \right)} \right)} &= \frac{ \tan{ \left( 4\arctan{\left( \frac{1}{5} \right)} \right) } }{1 + \frac{1}{239} \tan{ \left( 4\arctan{\frac{1}{239}} \right)}}

\\



\end{align*}
$$but we know that $$\tan{\left( 4\arctan{\frac{1}{5}} \right)} = \frac{2\tan{\left(2\arctan{\frac{1}{5}} \right)}}{1- [\tan{\left( 2\arctan{\frac{1}{5}} \right) }]}$$and also that$$\tan{ \left( 2\arctan{\left( \frac{1}{5} \right)} \right) = \frac{2\tan{\left(\arctan{\frac{1}{5}} \right)}}{1- [\tan{\left( \arctan{\frac{1}{5}} \right) }]}} = \frac{5}{12}$$which impies that $$\tan{ \left( 4\arctan{\left( \frac{1}{5} \right)} \right) } = \frac{120}{119}$$and we can finally substitute these back in,$$\tan{ \left( 4\arctan{\left( \frac{1}{5}\right)} - \arctan{\left( \frac{1}{239} \right)} \right)} = \frac{120/119 - 1/239}{1 + (1/139) \times (120/119)} = 1$$

Now for our estimations, for ##\pi = 4\arctan{1}##, the general term is$$|u_k| = \frac{4}{2k-1}$$so we require ##\frac{4}{2k-1} < 5 \times 10^{-101}##. For ##\pi = 4\arctan{\frac{1}{2}} + 4\arctan{\frac{1}{3}}##, the general term is $$|v_k| = \frac{4\left [ \frac{1}{2}^{2k-1} + \frac{1}{3}^{2k-1}\right]}{2k-1}$$whilst for ##\pi = 16\arctan{\frac{1}{5}} - 4\arctan{\frac{1}{239}}##, the general term is $$|w_k| = \frac{16 \left( \frac{1}{5} \right)^{2k-1} - 4\left( \frac{1}{239} \right)^{2k-1}}{2k-1}$$you can figure out ##k## by plugging some numbers in, so that ##|v_k| < 5\times 10^{-101}## and ##|w_k| < 5 \times 10^{-101}## respectively, but I'm too tired now.
 
  • Haha
Likes sysprog
  • #4
LCSphysicist
2020 Award
393
80
a)
This expression is rather similar to the expansion of arc tan:

$$\frac{1/2}{1} - \frac{1/4}{3} + \frac{1/8}{5} + ...$$
but the terms in the denominator is really interesting, it follow this rule:
$$x^{2N+1} = 2^{-(N+1)}

Exp: N = 0 -> x = 1/2$$

So that this sum is he expansion of ##tan^{-1}(\frac{(2^{-(N+1)})}{2N+1})##

Now we got a problem, it is not constant, but we can make the things be better, you can realize that if ##x^{2N+1} = 2^{-(N+1/2)}##, we can cut off the term 2N+1, so to do that, we just need to multiply and divide all the series by some number, well... the square of two in fact, so that:
$$\frac{1/2}{1} - \frac{1/4}{3} + \frac{1/8}{5} + ...$$
become
$$1/\sqrt{2}(\frac{\sqrt{2}/2}{1} - \frac{\sqrt{2}/4}{3} + \frac{\sqrt{2}/8}{5} + ...)$$
Now our first expression, in fact, become
$$x^{2N+1} = 2^{-(N+1/2)} $$
That's the end, the series is now:
$$1/\sqrt{2}(\frac{\sqrt{2}/2}{1} - \frac{\sqrt{2}/4}{3} + \frac{\sqrt{2}/8}{5} + ... = \frac{tan^{-1}(\sqrt{2}^{-1})}{\sqrt{2}})$$

b)

B is easier, we are just summing ##n/n! - 1/n! = 1/(n-1)! - 1/n!##

This is the trivial exponential series, so that
sum (from n = 2 to infty) ##1/(n-1)! - 1/n! = (e - 1 ) - (e - 1 - 1) = 1##
 
  • #5
14,117
11,371
Firstly, just by doing the explicit line integral$$\begin{align*}

\oint_C \vec{F} \cdot \vec{r}'(\theta) d\theta &= \int_0^{2\pi} \vec{F} \cdot \hat{\theta}(\theta) d\theta \\


&= \int_0^{2\pi} \left( -\sin{\theta} \left[ \cos{\theta} - \sin^2{\theta} \right] + \cos^3{\theta} \right) d\theta \\

&= \int_0^{2\pi} \left( \sin^{3}(\theta) + \cos^3{\theta} - \frac{1}{2} \sin{2\theta} \right) d \theta \\

& = \int_0^{2\pi} \left( \frac{3}{4} \left[ \sin{\theta} + \cos{\theta} \right] + \frac{1}{4} \left[ \sin{3\theta} + \cos{3\theta} \right] - \frac{1}{2} \sin{2\theta} \right) d\theta \\

&= \left[ \frac{3}{4} \left[\sin{\theta} - \cos{\theta} \right] + \frac{1}{12} \left[ \sin{3\theta} - \cos{3\theta} \right] + \frac{1}{4} \cos{2\theta} \right]_0^{2\pi} = 0


\end{align*}$$Secondly, by using Stokes' theorem,$$\int_C \vec{F} \cdot d\vec{r} = \int_A (\nabla \times \vec{F}) \cdot d\vec{S} = \int_A 2(x+y) dS$$But since ##g(x,y) \equiv 2(x+y)## satisfies ##g(x,y) = -g(-x,-y)##, and the region ##A## is the unit circle, by symmetry this must be zero.
You could have elaborated the second part a bit for readers who are less familiar with the concept or are learning it, but o.k., the definition of the curl can be looked up and the cross product can be done in mind, but I missed the normal. You silently moved from a vector to a scalar without any explanations.

And you confused first and second part - just mentioning it for those who wonder.
 
Last edited:
  • #6
etotheipi
Gold Member
2020 Award
3,156
2,110
I missed the normal. You silently moved from a vector to a scalar without any explanations.
I used area element ##d\vec{S} = dS \hat{z}##, and then that ##\hat{z}^2 = 1## :smile:
 
  • #7
14,117
11,371
For the first identity$$\tan{\left(\arctan{\left(\frac{1}{2} \right)} + \arctan{\left(\frac{1}{3} \right)} \right)} = \frac{1/2 + 1/3}{1-1/6} = 1$$and for the latter$$
\begin{align*}
\tan{\left( 4\arctan{\left( \frac{1}{5} \right)} - \arctan{\left( \frac{1}{239} \right)} \right)} &= \frac{ \tan{ \left( 4\arctan{\left( \frac{1}{5} \right)} \right) } }{1 + \frac{1}{239} \tan{ \left( 4\arctan{\frac{1}{239}} \right)}}

\\



\end{align*}
$$but we know that $$\tan{\left( 4\arctan{\frac{1}{5}} \right)} = \frac{2\tan{\left(2\arctan{\frac{1}{5}} \right)}}{1- [\tan{\left( 2\arctan{\frac{1}{5}} \right) }]}$$and also that$$\tan{ \left( 2\arctan{\left( \frac{1}{5} \right)} \right) = \frac{2\tan{\left(\arctan{\frac{1}{5}} \right)}}{1- [\tan{\left( \arctan{\frac{1}{5}} \right) }]}} = \frac{5}{12}$$which impies that $$\tan{ \left( 4\arctan{\left( \frac{1}{5} \right)} \right) } = \frac{120}{119}$$and we can finally substitute these back in,$$\tan{ \left( 4\arctan{\left( \frac{1}{5}\right)} - \arctan{\left( \frac{1}{239} \right)} \right)} = \frac{120/119 - 1/239}{1 + (1/139) \times (120/119)} = 1$$

Now for our estimations, for ##\pi = 4\arctan{1}##, the general term is$$|u_k| = \frac{4}{2k-1}$$so we require ##\frac{4}{2k-1} < 5 \times 10^{-101}##. For ##\pi = 4\arctan{\frac{1}{2}} + 4\arctan{\frac{1}{3}}##, the general term is $$|v_k| = \frac{4\left [ \frac{1}{2}^{2k-1} + \frac{1}{3}^{2k-1}\right]}{2k-1}$$whilst for ##\pi = 16\arctan{\frac{1}{5}} - 4\arctan{\frac{1}{239}}##, the general term is $$|w_k| = \frac{16 \left( \frac{1}{5} \right)^{2k-1} - 4\left( \frac{1}{239} \right)^{2k-1}}{2k-1}$$you can figure out ##k## by plugging some numbers in, so that ##|v_k| < 5\times 10^{-101}## and ##|w_k| < 5 \times 10^{-101}## respectively, but I'm too tired now.
You are sloppy. O.k. I know why and I understand it, as well as I feel bad to request a bit more rigor: I did not ask for the tangent of the solution, and the tangent function isn't even injective!

I think it is easier and more transparent using complex numbers and polar coordinates which gets you automatically on the correct branch.

Anyway, this wasn't the important part. The important part was the algorithm accuracy given by the three different formulas and a rigorous estimation of the series to achieve the 100 digits in each case. But as you are sloppy and I do not want to argue about correct limits, I recommend to leave this problem for someone who appreciates strict estimations. The clue however, was the significantly different numbers of steps in order to demonstrate that the same algorithm (the Taylor series) has totally different run times depending on how it is used.
 
  • #8
14,117
11,371
a)
This expression is rather similar to the expansion of arc tan:

$$\frac{1/2}{1} - \frac{1/4}{3} + \frac{1/8}{5} + ...$$
but the terms in the denominator is really interesting, it follow this rule:
$$x^{2N+1} = 2^{-(N+1)}

Exp: N = 0 -> x = 1/2$$

So that this sum is he expansion of ##tan^{-1}(\frac{(2^{-(N+1)})}{2N+1})##

Now we got a problem, it is not constant, but we can make the things be better, you can realize that if ##x^{2N+1} = 2^{-(N+1/2)}##, we can cut off the term 2N+1, so to do that, we just need to multiply and divide all the series by some number, well... the square of two in fact, so that:
$$\frac{1/2}{1} - \frac{1/4}{3} + \frac{1/8}{5} + ...$$
become
$$1/\sqrt{2}(\frac{\sqrt{2}/2}{1} - \frac{\sqrt{2}/4}{3} + \frac{\sqrt{2}/8}{5} + ...)$$
Now our first expression, in fact, become
$$x^{2N+1} = 2^{-(N+1/2)} $$
That's the end, the series is now:
$$1/\sqrt{2}(\frac{\sqrt{2}/2}{1} - \frac{\sqrt{2}/4}{3} + \frac{\sqrt{2}/8}{5} + ... = \frac{tan^{-1}(\sqrt{2}^{-1})}{\sqrt{2}})$$

b)

B is easier, we are just summing ##n/n! - 1/n! = 1/(n-1)! - 1/n!##

This is the trivial exponential series, so that
sum (from n = 2 to infty) ##1/(n-1)! - 1/n! = (e - 1 ) - (e - 1 - 1) = 1##
You have the correct solutions, but a horrible way to present them! Reading it is like having to solve it alone again in a different matter, which I did not do.

If anyone else wants to try: the calculation trick (for both) hasn't been found, yet, so a second solution is still possible,
 
  • Like
Likes LCSphysicist
  • #9
etotheipi
Gold Member
2020 Award
3,156
2,110
@fresh_42 here's another solution for 6b. Define $$f(x) \equiv \frac{x^2}{2!} + \frac{2x^3}{3!} + \frac{3x^4}{4!} + \dots$$Then$$f'(x) = \frac{1}{0!}x + \frac{1}{1!}x^2 + \frac{1}{2!} x^3 + \dots$$and consequently$$\frac{1}{x} f'(x) = 1 + x + \frac{1}{2!}x^2 + \frac{1}{3!} x^3 + \dots = e^x$$To find ##f(x)##, we need to solve$$f'(x) = xe^x \implies f(x) = \int xe^x dx = xe^x - \int e^x dx = (x-1)e^x + C$$Since ##f(0) = 0## (from the first line), we must have ##C=1##. The series we're after is ##f(1)##, which is$$f(1) = 0 \cdot e^0 + 1 = 1$$
 
  • Like
Likes fresh_42
  • #10
14,117
11,371
@fresh_42 here's another solution for 6b. Define $$f(x) \equiv \frac{x^2}{2!} + \frac{2x^3}{3!} + \frac{3x^4}{4!} + \dots$$Then$$f'(x) = \frac{1}{0!}x + \frac{1}{1!}x^2 + \frac{1}{2!} x^3 + \dots$$and consequently$$\frac{1}{x} f'(x) = 1 + x + \frac{1}{2!}x^2 + \frac{1}{3!} x^3 + \dots = e^x$$To find ##f(x)##, we need to solve$$f'(x) = xe^x \implies f(x) = \int xe^x dx = xe^x - \int e^x dx = (x-1)e^x + C$$Since ##f(0) = 0## (from the first line), we must have ##C=1##. The series we're after is ##f(1)##, which is$$f(1) = 0 \cdot e^0 + 1 = 1$$
That's the idea! It works for the series and the tangent in part (a), too. It's a nice useful trick to calculate series.
 
  • Like
Likes etotheipi
  • #11
14,117
11,371
It's even a bit nicer in part (a) since you do not need to know the series for the tangent function, only an integral:
\begin{align*}
f(x)&:=\dfrac{x}{2}-\dfrac{x^3}{12}+\dfrac{x^5}{40}-\dfrac{x^7}{112} \mp \ldots=\sum_{k=0}^{\infty}(-1)^k\dfrac{x^{2k+1}}{(2k+1)2^{k+1}}\\
f'(x)&=\dfrac{1}{2}-\dfrac{x^2}{4}+\dfrac{x^4}{8}-\dfrac{x^6}{16} \mp \ldots=\sum_{k=0}^{\infty}(-1)^k\dfrac{x^{2k}}{2^{k+1}}=\dfrac{1}{2+x^2}
\end{align*}
As ##f(0)=0## we get
\begin{align*}
f(1)&=\sum_{k=0}^{\infty}(-1)^k\dfrac{1}{(2k+1)2^{k+1}}\\&=f(1)-f(0)=\int_0^1f'(x)\,dx\\&=\int_0^1 \dfrac{dx}{2+x^2}=\left[\dfrac{1}{\sqrt{2}}\cdot\tan^{-1}\left(\dfrac{x}{\sqrt{2}}\right)\right]_0^1\\
&=\dfrac{1}{\sqrt{2}}\cdot\tan^{-1}\left(\dfrac{1}{\sqrt{2}}\right)\approx 0.43521
\end{align*}

So one does not have to identify the series to apply the trick!
 
  • Wow
  • Like
Likes lekh2003, LCSphysicist and etotheipi
  • #12
benorin
Homework Helper
Insights Author
Gold Member
1,293
98
9. Suppose someone gives you a coin and claims that this coin is biased; that it lands on heads only 48% of the time with an error margin of 2%. You decide to test the coin for yourself. If you want to be 95% confident that this coin is indeed biased, how many times must you flip the coin? Compare the estimations by the weak law of large numbers and by the central limit theorem!
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.
 
  • #13
mathwonk
Science Advisor
Homework Helper
2020 Award
11,091
1,291
hint for 2, try the only if direction. (the other direction is a theorem due to fermat; you might enjoy tackling it, but do not be discouraged if it is elusive.)
 
  • #14
etotheipi
Gold Member
2020 Award
3,156
2,110
Yeah I think the "if ##p = x^2 + y^2## then ##p \equiv 1 \, \, (\text{mod}\,\, 4)##" direction is fine, because ##x^2, y^2 \equiv 0,1 \, \, (\text{mod}\,\, 4) \implies x^2 + y^2 \equiv 0,1,2 \, \, (\text{mod}\,\, 4)## but then since ##p## is odd, ##p = x^2 + y^2 \equiv 1 \, \, (\text{mod}\,\, 4)##, but I have no idea how to go the other way...
 
  • #15
14,117
11,371
Yeah I think the "if ##p = x^2 + y^2## then ##p \equiv 1 \, \, (\text{mod}\,\, 4)##" direction is fine, because ##x^2, y^2 \equiv 0,1 \, \, (\text{mod}\,\, 4) \implies x^2 + y^2 \equiv 0,1,2 \, \, (\text{mod}\,\, 4)## but then since ##p## is odd, ##p = x^2 + y^2 \equiv 1 \, \, (\text{mod}\,\, 4)##, but I have no idea how to go the other way...
Consider involutions on ##\{\,(x,y,z)\in \mathbb{N}^3\,|\,x^2+4yz=p\,\}## and their fixed points, or alternatively Minkowski's lattice theorem.
 
Last edited:
  • #17
14,117
11,371
@fresh_42 I assume you wrote #9, how was my attempt?
I haven't checked since you said you did only half of it. I thought you would do the rest, too.
 
  • Like
Likes benorin
  • #18
479
257
10. A hat-check boy at a congress held at Hilbert's hotel completely loses track of which of hats belong to which owners, and hands them back at random to their owners as the latter leave. What is the probability ##P## that nobody receives their own hat back?
Well, let me try, I think I might overcomplicate it a little, but here comes my attempt:
To start, let's assume that ##n## persons go to the congress.
Then mathematically then, giving the hats at random is equivalent to do a permutation over a set of ##n## elements. So we must compute the number of permutations ##\sigma \in S_n## such that $$\sigma(i)\neq i, \quad \forall i$$
I think it's easier to compute the other way, so compute the number of permutations ##\sigma \in S_n## such that
$$\exists i: \sigma(i) = i$$
let's call it ##N_n##.

We can start by computing the number of permutations for which ##\exists i_1: \sigma(i_1)=i_1##.
Once fixed the value ##i_1## there are ##(n-1)!## such permutations, and since there are ##n## values to choose for ##i_1## we could think that ##N_n = n (n-1)!##.

This, of course, is not true, because some of the permutations are counted more than once. In fact, a permutation such that ##\sigma(i_1)=i_1,\ \sigma(i_2)=i_2## is counted twice, so we need to subtract all such permutations. Now, for fixed values of ##i_1, i_2## there are ##(n-2)!## permutations, and we have ##n \choose 2## ways to choose ##i_1, i_2##. So we could expect
$$N_n = n (n-1)! - {n \choose 2} (n-2)!$$
But now we have subtracted some permutations more than once, so we need to add all the permutations
$$\sigma(i_1)=i_1,\quad\sigma(i_2)=i_2,\quad\sigma(i_3)=i_3$$
which there are ##n \choose 3## options for the index and ##(n-3)!## permutations for each choice.
Repeating this process until we finish we obtain that
$$N_n = n (n-1)! - {n \choose 2} (n-2)! + {n \choose 3}(n-3)! - ... = \sum_{k=1}^n (-1)^{k+1}{n\choose k}(n-k)!$$
Since this argument may not be completely rigorous, I provided a more complete proof of this:
Let's define
$$n_{i_1\ldots i_k} = \text{Number of permutatios with } i_1\ldots i_k \text{ fixed} = (n-k)!$$
$$N_{k} = \text{Number of permutations with some } i\leq k \text{ fixed}$$
And, for ##k < m##
$$N_{k|m} = \text{Number of permutations with some } i\leq k \text{ fixed with } m \text{ fixed}$$
To compute ##N_1## is easy, because by definition must be the number of permutations with ##\sigma(1)=1##, i.e., ##n_1##.
Then to compute ##N_2## we need to add all the permutations that fix 2, but without all the ones which fix 1 (which are already counted)
$$N_2 = N_1 + n_2 - N_{1|2} = n_1 + n_2 - n_{12}$$
Again, to compute ##N_3## we add all the permutations that fix 3, but without all the ones that fix 1 or 2:
$$N_3 = N_2 + n_3 - N_{2|3} = n_1 + n_2 - n_{12} + n_3 - n_{13} - n_{23} + n_{123}$$
In general, we can prove by induction that
$$N_{k} := N_{k-1} + n_{k} - N_{k-1|k} = -\sum_{j=1}^{k} (-1)^{j}{k\choose j} n_{12\ldots j}$$
In fact, the case ##k=1 ## is trivial, and
$$N_{k+1} = N_{k} + n_{k+1} - N_{k|k+1} = -\sum_{j=1}^{k} (-1)^{j}{k\choose j} n_{12\ldots j} + n_{k+1} +\sum_{j=1}^{k} (-1)^{j}{k\choose j} n_{12\ldots j(k+1)} $$
Using the fact that ##n_{k+1}=n_1## and ##n_{12\ldots j(k+1)} = n_{1\ldots (j+1)}## we can rewrite it as
$$N_{k+1} =k n_{1} -\sum_{j=2}^{k} (-1)^{j}{k\choose j} n_{12\ldots j}+ n_{1} -\sum_{j=1}^{k} (-1)^{j+1}{k\choose j} n_{1\ldots (j+1)}$$
$$N_{k+1} =(k+1) n_{1} -\sum_{j=2}^{k} (-1)^{j}{k\choose j} n_{12\ldots j} -\sum_{j=2}^{k+1} (-1)^{j}{k\choose j-1} n_{1\ldots j}$$
$$N_{k+1} =-(-1)^1{k+1\choose 1} n_{1} -\sum_{j=2}^{k} (-1)^{j}\left({k\choose j}+{k\choose j-1}\right) n_{12\ldots j} -(-1)^{k+1}{k\choose k} n_{1\ldots (k+1)}$$
which finally, using ##{k\choose j}+{k\choose j-1} = {k+1\choose j}## and ##{k\choose k}={k+1\choose k+1}## we obtain
$$N_{k+1} =-\sum_{j=1}^{k+1} (-1)^{j}{k+1\choose j}n_{12\ldots j}$$
As we wanted to prove.

Now we just need to modify some things, first remembering that
$${n\choose k}=\frac{n!}{k!(n-k)!} \Longrightarrow N_n = -n! \sum_{1}^n \frac{(-1)^k}{k!}$$
And because we want to compute the probability of a permutation having no fixed elements, such probability is
$$P_n = 1-\frac{N_n}{n!} = 1 + \sum_{1}^n \frac{(-1)^k}{k!} = \sum_{0}^n \frac{(-1)^k}{k!}$$
And finally, for the Hilber hotel we just need to take the limit ##n \to \infty##
$$P = \lim P_n = e^{-1} \approx 36,79\%$$
is the probability nobody receives their own hat.
 
  • Like
Likes PeroK and fresh_42
  • #19
14,117
11,371
Well, let me try, I think I might overcomplicate it a little, but here comes my attempt:
To start, let's assume that ##n## persons go to the congress.
Then mathematically then, giving the hats at random is equivalent to do a permutation over a set of ##n## elements. So we must compute the number of permutations ##\sigma \in S_n## such that $$\sigma(i)\neq i, \quad \forall i$$
I think it's easier to compute the other way, so compute the number of permutations ##\sigma \in S_n## such that
$$\exists i: \sigma(i) = i$$
let's call it ##N_n##.

We can start by computing the number of permutations for which ##\exists i_1: \sigma(i_1)=i_1##.
Once fixed the value ##i_1## there are ##(n-1)!## such permutations, and since there are ##n## values to choose for ##i_1## we could think that ##N_n = n (n-1)!##.

This, of course, is not true, because some of the permutations are counted more than once. In fact, a permutation such that ##\sigma(i_1)=i_1,\ \sigma(i_2)=i_2## is counted twice, so we need to subtract all such permutations. Now, for fixed values of ##i_1, i_2## there are ##(n-2)!## permutations, and we have ##n \choose 2## ways to choose ##i_1, i_2##. So we could expect
$$N_n = n (n-1)! - {n \choose 2} (n-2)!$$
But now we have subtracted some permutations more than once, so we need to add all the permutations
$$\sigma(i_1)=i_1,\quad\sigma(i_2)=i_2,\quad\sigma(i_3)=i_3$$
which there are ##n \choose 3## options for the index and ##(n-3)!## permutations for each choice.
Repeating this process until we finish we obtain that
$$N_n = n (n-1)! - {n \choose 2} (n-2)! + {n \choose 3}(n-3)! - ... = \sum_{k=1}^n (-1)^{k+1}{n\choose k}(n-k)!$$
Since this argument may not be completely rigorous, I provided a more complete proof of this:
Let's define
$$n_{i_1\ldots i_k} = \text{Number of permutatios with } i_1\ldots i_k \text{ fixed} = (n-k)!$$
$$N_{k} = \text{Number of permutations with some } i\leq k \text{ fixed}$$
And, for ##k < m##
$$N_{k|m} = \text{Number of permutations with some } i\leq k \text{ fixed with } m \text{ fixed}$$
To compute ##N_1## is easy, because by definition must be the number of permutations with ##\sigma(1)=1##, i.e., ##n_1##.
Then to compute ##N_2## we need to add all the permutations that fix 2, but without all the ones which fix 1 (which are already counted)
$$N_2 = N_1 + n_2 - N_{1|2} = n_1 + n_2 - n_{12}$$
Again, to compute ##N_3## we add all the permutations that fix 3, but without all the ones that fix 1 or 2:
$$N_3 = N_2 + n_3 - N_{2|3} = n_1 + n_2 - n_{12} + n_3 - n_{13} - n_{23} + n_{123}$$
In general, we can prove by induction that
$$N_{k} := N_{k-1} + n_{k} - N_{k-1|k} = -\sum_{j=1}^{k} (-1)^{j}{k\choose j} n_{12\ldots j}$$
In fact, the case ##k=1 ## is trivial, and
$$N_{k+1} = N_{k} + n_{k+1} - N_{k|k+1} = -\sum_{j=1}^{k} (-1)^{j}{k\choose j} n_{12\ldots j} + n_{k+1} +\sum_{j=1}^{k} (-1)^{j}{k\choose j} n_{12\ldots j(k+1)} $$
Using the fact that ##n_{k+1}=n_1## and ##n_{12\ldots j(k+1)} = n_{1\ldots (j+1)}## we can rewrite it as
$$N_{k+1} =k n_{1} -\sum_{j=2}^{k} (-1)^{j}{k\choose j} n_{12\ldots j}+ n_{1} -\sum_{j=1}^{k} (-1)^{j+1}{k\choose j} n_{1\ldots (j+1)}$$
$$N_{k+1} =(k+1) n_{1} -\sum_{j=2}^{k} (-1)^{j}{k\choose j} n_{12\ldots j} -\sum_{j=2}^{k+1} (-1)^{j}{k\choose j-1} n_{1\ldots j}$$
$$N_{k+1} =-(-1)^1{k+1\choose 1} n_{1} -\sum_{j=2}^{k} (-1)^{j}\left({k\choose j}+{k\choose j-1}\right) n_{12\ldots j} -(-1)^{k+1}{k\choose k} n_{1\ldots (k+1)}$$
which finally, using ##{k\choose j}+{k\choose j-1} = {k+1\choose j}## and ##{k\choose k}={k+1\choose k+1}## we obtain
$$N_{k+1} =-\sum_{j=1}^{k+1} (-1)^{j}{k+1\choose j}n_{12\ldots j}$$
As we wanted to prove.

Now we just need to modify some things, first remembering that
$${n\choose k}=\frac{n!}{k!(n-k)!} \Longrightarrow N_n = -n! \sum_{1}^n \frac{(-1)^k}{k!}$$
And because we want to compute the probability of a permutation having no fixed elements, such probability is
$$P_n = 1-\frac{N_n}{n!} = 1 + \sum_{1}^n \frac{(-1)^k}{k!} = \sum_{0}^n \frac{(-1)^k}{k!}$$
And finally, for the Hilber hotel we just need to take the limit ##n \to \infty##
$$P = \lim P_n = e^{-1} \approx 36,79\%$$
is the probability nobody receives their own hat.
I couldn't avoid counting either.
 
  • #20
mathwonk
Science Advisor
Homework Helper
2020 Award
11,091
1,291
In #2, obviously one must assume p > 0. (I make this absurdly obvious comment since x,y are allowed to be negative integers, and to some of us, the commutative algebra definition of a prime integer includes -3 as a prime congruent to 1, mod 4, for which the result fails. Actually I make it because I only just noticed it myself, and up until now I have been stating this result incorrectly.)

Detailed hint: Introduce the "Gaussian integers" Z[ i ], of form n +mi, with n,m integers, i^2 = -1.
0) show that an integer which is a sum of two squares, can be factored in the gaussian integers.
1) Show that if the prime integer p>0 is congruent to 1 mod 4, then p is not prime in the Gaussian integers, in the sense that there are Gaussian integers z,w such that p divides zw, but p does not divide either z or w. (by 0), it suffices to find an appropriate sum of two squares that is divisible by p, e.g. of form n^2+1. (see infrared's next hint.))
2) Show (or assume) that Z[ i ] is a "euclidean domain", hence enjoys unique factorization. (I.e. there is a division
algorithm with remainder smaller than the divisor, as measured by the squared absolute value.)
3) Conclude that a (≠0) non - prime, non unit, in Z[ i ] must be factorable into two non - unit factors.
4) Deduce that a prime integer p >0 and congruent to 1 mod 4, is a sum of two positive integer squares.
 
Last edited:
  • Like
Likes member 587159
  • #21
Infrared
Science Advisor
Gold Member
858
469
@mathwonk Try including spaces like [ i ]. Without spaces, it gets interpreted as the italics command.

I think even step (1) in the hint is pretty tricky. I'll give a hint to your hint: the standard trick is to count solutions to ##x^2=-1## in ##\mathbb{Z}[ i ]/(p)##.
 
  • Like
Likes mathwonk
  • #22
479
257
8. Calculate the following integrals
(a) ##\displaystyle{\int_0^{2\pi}e^{(e^{it})}\,dt}##
(b) ##\displaystyle{\int_{|z|=1}\dfrac{\sin(z^2)}{(\sin z)^2}\,dz}##
(c) ##\displaystyle{\int_{|z|=1}\sin \left(e^{1/z}\right)\,dz}##
(d) ##\displaystyle{\int_{-\infty}^\infty \dfrac{1}{x^2-2x+2}\,dx}##
We first see that this integral can be rewritten using complex variables as:
$$\int_{|z|=1} \dfrac{e^z}{iz}\,dz$$
This can be seen because using the parametrization of the path given by ##z = e^{it}## which implies ##dz = i z dt## we get the original integral. Now using the fact that ##e^z## is a holomorphic function we can use Cauchy's Integral Formula and write
$$\int_{|z|=1} \dfrac{e^z}{iz}\,dz = 2 \pi e^{0} = 2 \pi$$
First, because ##\sin{z}## and ##z^2## are holomorphic functions and the composition of holomorphic functions is holomorphic both ##\sin{z^2}## and ##\sin^2{z}## are holomorphic, also, because the only ##0## of ##\sin^2{z}## in the region ##|z| < \pi## is ##z=0## the function ##f(z)=\dfrac{\sin(z^2)}{(\sin z)^2}## is holomorphic in some open set ##U## that includes the ##|z|\leq 1## region, except for the point ##z=0##, in which the function is not defined, defining ##f(0):=1## we can see that ##f(z)## is differentiable at ##z=0## and therefore holomorphic in the open set ##U##:

In fact, doing the limit by Taylor expanding the functions:
$$f'(0)=\lim_{z\to 0}\dfrac{f(z)-1}{z} = \lim_{z\to 0}\dfrac{\dfrac{z^2}{z^2-\frac{1}{3}z^4}-1}{z} = \lim_{z\to 0}\dfrac{1+\frac{1}{3}z^2-1}{z}=0$$

Therefore by Cauchy's integral theorem, the integral is zero
$$\displaystyle{\int_{|z|=1}\dfrac{\sin(z^2)}{(\sin z)^2}\,dz}=0$$
Start by doing the change of variables ##w = z^{-1}##, ##dw = -w^2 dz##, also ##|z|=1 \Longleftrightarrow |w|=1## so the integral is
$$-\int_{|w|=1}\dfrac{\sin \left(e^{w}\right)}{w^2}\,dw$$
Notice that, if before the path was covered counterclockwise, now it is covered clockwise, i.e. the previous parametrization ##z=e^{i\theta}## is now translated to the parametrization ##w = e^{-i\theta}##.
Using Cauchy's integral formula with ##f(z)=\sin{\left(e^z\right)}## we get
$$\int_{|w|=1}\dfrac{\sin \left(e^{w}\right)}{w^2}\,dw = - 2\pi i f'(0) = -2\pi i \cos{1}$$
where the - is to account for the clockwise orientations of the curve, and therefore
$$\int_{|z|=1}\sin \left(e^{1/z}\right)\,dz = 2\pi i \cos{1} \approx 3,395 i$$
Finally, let's factorize the denomiator. Usign the quadratic formula is easy to see
$$x^2-2x+2 = (x-1-i)(x-1+i)$$
So, to compute this integral, let's compute first the same but with complex argument
$$\int_{\gamma} \frac{1}{(z-1-i)(z-1+i)}\, dz$$
where the path ##\gamma## is defined by the parametrization
$$\gamma(\theta)=\lim_{R\to \infty} \begin{cases}Re^{i\theta}&\theta \in [0,\pi] \\ R\cos{\theta} & \theta \in (\pi, 2\pi]\end{cases}$$
Now, inside the region delimited by the path the integrand has only a pole at ##z=1+i##, so, using Cauchy's integral formula we get
$$\int_{\gamma} f(z)=\frac{2\pi i}{(1+i)-1+i}=\pi$$
Now, defining the paths ##\gamma_1 = \gamma([0,\pi])## and ##\gamma_2 = \gamma([\pi, 2\pi])##, we have ##\gamma = \gamma_1 + \gamma_2## so the integral can be splitted into
$$\int_\gamma f(z)=\int_{\gamma_1} f(z) + \int_{\gamma_2} f(z)$$
The first integral is zero, because ##f(z)## decreases as ##R^{-2}## while the contour of the integral increases as ##R##.
And the second integral is precisely the integral we want, so
$$\int_{-\infty}^\infty \dfrac{1}{x^2-2x+2}\,dx = \pi$$
Actually, I have computed the Principal Value of the integral, but it's not difficult to prove that the integral is convergent and therefore its value coincides with its principal value.
 
  • Like
Likes fresh_42
  • #23
mathwonk
Science Advisor
Homework Helper
2020 Award
11,091
1,291
With help from infrared's suggestion, I'll try again on a detailed hint for #2. I'll try to make them roughly in increasing levels of difficulty:

0) Show an odd prime integer p>0 which is a sum of two integer squares, has form 4n+1, for some integer n.

1) If the prime integer p >0 is a sum of two integer squares, then p factors as a product of two Gaussian integers.

2) Conversely, if p>0 is a prime integer that factors as a product of two Gaussian integers, other than ±1,±i, then p is a sum of two integer squares. (use the fact that the absolute value of complex numbers is multiplicative.)

Hence the problem reduces to showing that an odd prime integer p>0, can be factored non trivially in Z[ i ], if p = 4n+1, for some integer n. Equivalently we want to shown that p = z.w, for Gaussian integers z,w, where p does not divide either z or w. As a first step, try to show that such a prime integer p divides some product z.w of non zero Gaussian integers, such that p does not divide either z or w, as follows:

3) Show that if p cannot divide a non zero product z.w of Gaussian integers without dividing one of the factors, then in the quotient ring Z[ i ]/(p), the product of two non zero elements is always again non zero, i.e. this ring is then an "integral domain". (The quotient ring Z[ i ]/(p) is defined analogously to the ring of modular integers, i.e. two Gaussian integers z,w become equal in the quotient ring if p divides z-w.)

4) Show that in an integral domain, a quadratic equation can have at most two distinct solutions.

5) Show: if an odd prime p>0 has form 4n+1, then X^2+1 = 0 has more than 2 solutions in Z[ i ]/(p).
(show that this equation already has solutions in the integers mod p. e.g. mod 5 we have the multiplicative group {1,2,3,4} = {1,2,-2,-1}, whose product, since only 1 and -1 are not paired inverses, is -1. thus the product 1.2.-2.-1 = 1.2.2.1 = 1^2.2^2 = (1.2)^2 = -1. thus there is a square root of -1.)

A non zero, non unit, element of a domain is called irreducible if it cannot be factored without using a unit factor.

6) If in an integral domain R, every non zero, non unit element factors into irreducible elements, uniquely up to order and multiplication by units, (i.e. "unique factorization" holds), then show that for every irreducible element x, the quotient ring R/(x) is again an integral domain.

7) Assuming Z[ i ] has unique factorization, prove an odd integer prime p >0 of form 4n+1 can be factored in the Gaussian integers, hence can be written as a sum of two integer squares.

8) Using the squared absolute value as a size measure, show that there is a division algorithm in Z[ i ] where the remainder is smaller than the divisor. this is hard, but if you use thev fact that there is such a division algorithm in Q[ i ], you can deduce this by estimating the distances between complex numbers in the plane, at least as i recall.

9) Deduce that unique factorization holds in Z[ i ], completing problem #2.

Boy, there is a lot more to this approach than I thought. but i believe it is a valuable exercise to attempt these steps with the hints.
 
Last edited:
  • #24
14,117
11,371
Boy, there is a lot more to this approach than I thought.
Both of my solutions (see post #15: fix points of involutions or Minkowski) are shorter than your entire hint. And the involution method is shorter than Minkowski. It's a bit tricky but I think nice. Minkowski is a bit brute force.
 
  • #25
julian
Gold Member
603
120
Problem #8

I did (a), (c), and (d) the same way @Gaussian97. I was moving on to (b).

Here is a different way of performing the integral (d):

Write

\begin{align*}
I & = \int_{- \infty}^\infty \frac{1}{x^2 -2x + 2} dx \\
& = \int_{- \infty}^\infty \left( \int_0^\infty e^{- \alpha (x^2 -2x + 2)} d \alpha \right) dx \\
& = \int_0^\infty \left( \int_{- \infty}^\infty e^{- \alpha (x^2 -2x + 2)} dx \right) d \alpha \\
& = \int_0^\infty \left( \int_{- \infty}^\infty e^{- \alpha ((x - 1)^2 + 1)} dx \right) d \alpha \\
& = \int_0^\infty e^{- \alpha} \left( \int_{- \infty}^\infty e^{- \alpha x^2} dx \right) d \alpha \\
& = \int_0^\infty e^{- \alpha} \sqrt{\frac{\pi}{\alpha}} d \alpha
\end{align*}

Make the substitution ##u^2 = \alpha## and then we get

\begin{align*}
I & = \sqrt{\pi} \int_0^\infty \frac{e^{- u^2}}{u} 2 u d u \\
& = 2 \sqrt{\pi} \int_0^\infty e^{- u^2} d u \\
& = \sqrt{\pi} \int_{- \infty}^\infty e^{- u^2} d u \\
& = \pi .
\end{align*}
 
  • Like
Likes fresh_42

Related Threads on Math Challenge - December 2020

Replies
67
Views
7K
Replies
47
Views
6K
Replies
64
Views
9K
Replies
104
Views
7K
Replies
150
Views
9K
Replies
77
Views
8K
  • Last Post
3
Replies
61
Views
6K
Replies
98
Views
4K
Replies
107
Views
10K
Replies
156
Views
8K
Top