Challenge Math Challenge - December 2021

[fresh_42]

We note that $Aut(\mathbb{Z}_2) = \lbrace id \rbrace$. So the only homomorphism $\varphi : \mathbb{Z}_3 \to Aut(\mathbb{Z}_2)$ is $\varphi: 0, 1, 2 \mapsto id$. And this implies $\mathbb{Z}_3 \ltimes_\varphi \mathbb{Z}_2 = \mathbb{Z}_3 \times \mathbb{Z}_2$. So in this case, we can write $\mathbb{Z}_3 \times \mathbb{Z}_2 = \mathbb{Z}_3 \ltimes \mathbb{Z}_2$?

Yes, or: $\mathbb{Z}_3 \ltimes_\varphi \mathbb{Z}_2$ makes no sense.

 

[QuantumSpace]

Why is 14 not solved yet?

Spoiler

I will assume $a \ne b$ and $X = \{a,b\}$.

All topologies on $X$ are
$$\{\emptyset, X \}, \{\emptyset, \{a\},X\}, \{\emptyset, \{b\}, X\}, \{\emptyset, \{a\}, \{b\}, X\}$$

Let us write $\tau_a = \{\emptyset, \{a\},X\}, \tau_b = \{\emptyset, \{b\},X\}$.

Then the map $f: (X, \tau_a)\to (X, \tau_b)$ given by $f(a) = b, f(b) = a$ is a homeomorphism since $f$ induces a bijection between the topologies (this is swiftly verified).

Thus $(X, \tau_a)\cong (X,\tau_b)$. There are no other homeomorphisms, because the topologies do not have the same cardinality.

Finally, for the indiscrete topology $\{\emptyset, X\}$ every net converges. Indeed, if $\{x_i\}_{i \in I}\subseteq \{a,b\}$ is a net, it converges to both $a$ and $b$. This is immediate from the definition of convergence:
$$x_i \to x \iff \forall V \in \mathcal{V}(x): \exists i_0 \in I: \forall i \ge i_0: x_i \in V$$
In this case, $\mathcal{V}(x) = \{X\}$ and this satisfied trivially. More generally, we can take any set $X$ with the indiscrete topology and all nets in it will converge to every point in the entire space.

 

[julian]

19.

Spoiler

We have

\begin{align*}
P_n = 2 P_{n-1} + P_{n-2} , \qquad \text{for } \; n \geq 2,
\end{align*}

with $P_0 = 0$ and $P_1 = 1$ ($P_2 = 2$).

Write

\begin{align*}
F(x) = \sum_{k=0}^\infty P_k x^k
\end{align*}

Then

\begin{align*}
F(x) & = P_1 x + P_2 x^2 + P_3 x^3 + P_4 x^4 + \cdots
\nonumber \\
2x F(x) & = \qquad \; 2 P_1 x^2 + 2P_2 x^3 + 2P_3 x^4 + \cdots
\nonumber \\
x^2 F(x) & = \qquad \qquad \qquad \quad P_1 x^3 + P_2 x^4 + \cdots
\end{align*}

and so

\begin{align*}
F(x) = 2 x F(x) + x^2 F(x) + x
\end{align*}

then

\begin{align*}
F(x) & = \frac{x}{1 - 2x - x^2}
\nonumber \\\
& = \frac{1}{2 \sqrt{2}} \left( \frac{1}{1- (1 + \sqrt{2}) x} - \frac{1}{1- (1 - \sqrt{2}) x} \right)
\nonumber \\\
& = \frac{1}{2 \sqrt{2}} \sum_{n=0}^\infty \left( (1 + \sqrt{2})^n - (1 - \sqrt{2})^n \right) x^n
\end{align*}

We read off that

\begin{align*}
P_n = \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2 \sqrt{2}}
\end{align*}

 

[fresh_42]

19.

Spoiler

We have

\begin{align*}
P_n = 2 P_{n-1} + P_{n-2} , \qquad \text{for } \; n \geq 2,
\end{align*}

with $P_0 = 0$ and $P_1 = 1$ ($P_2 = 2$).

Write

\begin{align*}
F(x) = \sum_{k=0}^\infty P_k x^k
\end{align*}

Then

\begin{align*}
F(x) & = P_1 x + P_2 x^2 + P_3 x^3 + P_4 x^4 + \cdots
\nonumber \\
2x F(x) & = \qquad \; 2 P_1 x^2 + 2P_2 x^3 + 2P_3 x^4 + \cdots
\nonumber \\
x^2 F(x) & = \qquad \qquad \qquad \quad P_1 x^3 + P_2 x^4 + \cdots
\end{align*}

and so

\begin{align*}
F(x) = 2 x F(x) + x^2 F(x) + x
\end{align*}

then

\begin{align*}
F(x) & = \frac{x}{1 - 2x - x^2}
\nonumber \\\
& = \frac{1}{2 \sqrt{2}} \left( \frac{1}{1- (1 + \sqrt{2}) x} - \frac{1}{1- (1 - \sqrt{2}) x} \right)
\nonumber \\\
& = \frac{1}{2 \sqrt{2}} \sum_{n=0}^\infty \left( (1 + \sqrt{2})^n - (1 - \sqrt{2})^n \right) x^n
\end{align*}

We read off that

\begin{align*}
P_n = \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2 \sqrt{2}}
\end{align*}

It is important to notice that your proof takes place entirely in $\mathbb{R}[[x]],$ i.e. the ring of formal real power series. $F(x)$ is neither a power series of a function nor is it a quotient of polynomials. All there is, is $\mathbb{R}^{\mathbb{N}_0}.$

One can give a purely analytical proof by the observation
\begin{align*}
L:=\lim_{n \to \infty}\dfrac{P_{n}}{P_{n-1}}&=2+\lim_{n \to \infty}\dfrac{P_{n-2}}{P_{n-1}}=2+\dfrac{1}{L}
\end{align*}
In that case, we find the same result but would have to show that $L$ actually exists.

$(P_n)_{n\in \mathbb{N}_0}$ is called Pell sequence and $L=1+\sqrt{2}$ the silver ratio.

 

[Fred Wright]

Problem #2
We have,
$$
I=\int_0^1 \frac{\log(x)}{z_1-x}dx- \int_0^1 \frac{\log(x)}{z_0+x}dx=I_1 - I_2
$$
where
$$
z_0=|a|e^{i\phi}
$$
$$
|a| < 1
$$
$$
z_1=z_0+1
$$
Integrate $I_1$ by parts:
$$
I_1=\int_0^{1}\frac{\log{x}}{z_1-x}dx
$$
$$
=-\log(z_1 -x)\log(x)|_0^1 + \int_0^{1}\frac{\log(z_1- x)}{x}dx
$$
$$
=-\log(z_1 -x)\log(x)|_0^1 + \int_0^{1}\frac{\log(z_1)}{x}dx + \int_0^{1}\frac{\log(1-\frac{x}{z_1})}{x}dx
$$
$$
=-\log(z_1 -x)\log(x)|_0^1 + \log(z_1)\log(x)|_0^1 +\int_0^{\frac{1}{z_1}}\frac{\log(1-u)}{u}du
$$
where we have made the substitution $u=\frac{x}{z_1}$ in the last term. The surface terms cancel and we are left with
$$
I_1=-Li_2(\frac{1}{z_1})
$$
where $Li_2(z)$ is the dilogarithm. In like manner we integrate $I_2$ by parts; again the surface terms cancel and making the substitution $u=-\frac{x}{z_0}$ we are left with,
$$
I_2=-Li_2(-\frac{1}{z_0})
$$
and thus,
$$
I=-(Li_2(\frac{1}{z_1})+Li_2(-\frac{1}{z_0}))=-(Li_2(\frac{1}{z_1})+Li_2(\frac{1}{1-z_1}))
$$
We make use of the property of the dilogarithm function:
$$
Li_2(1-z) + Li_2(1-\frac{1}{z})=-\frac{1}{2}\log^2(z)
$$
by making the change of variables,
$$
\frac{1}{z_1}=1-z
$$
$$
\frac{1}{1-z_1}=1-\frac{1}{z}
$$
to find,
$$
z=\frac{z_0}{z_1}
$$
$$
z=(\frac{|a|}{\sqrt{|a|^2+2\cos(\phi)|a|+1}})e^{i\tan^{-1}(\frac{|a|\sin(\phi)}{|a|+\cos(\phi)})}
$$
Thus,
$$
I=\frac{1}{2}(\log{(\frac{|a|}{\sqrt{|a|^2+2\cos(\phi)|a|+1}})}+i\tan^{-1}(\frac{|a|\sin(\phi)}{|a|+\cos(\phi)}))^2
$$

 

[fresh_42]

Problem #2
We have,
$$
I=\int_0^1 \frac{\log(x)}{z_1-x}dx- \int_0^1 \frac{\log(x)}{z_0+x}dx=I_1 - I_2
$$
where
$$
z_0=|a|e^{i\phi}
$$
$$
|a| < 1
$$
$$
z_1=z_0+1
$$
Integrate $I_1$ by parts:
$$
I_1=\int_0^{1}\frac{\log{x}}{z_1-x}dx
$$
$$
=-\log(z_1 -x)\log(x)|_0^1 + \int_0^{1}\frac{\log(z_1- x)}{x}dx
$$
$$
=-\log(z_1 -x)\log(x)|_0^1 + \int_0^{1}\frac{\log(z_1)}{x}dx + \int_0^{1}\frac{\log(1-\frac{x}{z_1})}{x}dx
$$
$$
=-\log(z_1 -x)\log(x)|_0^1 + \log(z_1)\log(x)|_0^1 +\int_0^{\frac{1}{z_1}}\frac{\log(1-u)}{u}du
$$
where we have made the substitution $u=\frac{x}{z_1}$ in the last term. The surface terms cancel and we are left with
$$
I_1=-Li_2(\frac{1}{z_1})
$$
where $Li_2(z)$ is the dilogarithm. In like manner we integrate $I_2$ by parts; again the surface terms cancel and making the substitution $u=-\frac{x}{z_0}$ we are left with,
$$
I_2=-Li_2(-\frac{1}{z_0})
$$
and thus,
$$
I=-(Li_2(\frac{1}{z_1})+Li_2(-\frac{1}{z_0}))=-(Li_2(\frac{1}{z_1})+Li_2(\frac{1}{1-z_1}))
$$
We make use of the property of the dilogarithm function:
$$
Li_2(1-z) + Li_2(1-\frac{1}{z})=-\frac{1}{2}\log^2(z)
$$
by making the change of variables,
$$
\frac{1}{z_1}=1-z
$$
$$
\frac{1}{1-z_1}=1-\frac{1}{z}
$$
to find,
$$
z=\frac{z_0}{z_1}
$$
$$
z=(\frac{|a|}{\sqrt{|a|^2+2\cos(\phi)|a|+1}})e^{i\tan^{-1}(\frac{|a|\sin(\phi)}{|a|+\cos(\phi)})}
$$
Thus,
$$
I=\frac{1}{2}(\log{(\frac{|a|}{\sqrt{|a|^2+2\cos(\phi)|a|+1}})}+i\tan^{-1}(\frac{|a|\sin(\phi)}{|a|+\cos(\phi)}))^2
$$

Oh dear, what have you done? The first term is at least near the solution (more or less), however, I do not have the second. But that might be due to the fact that my solution doesn't split into real and imaginary parts. It doesn't use complex numbers at all. The solution isn't that complicated, only a square, a logarithm, and a root.

The integral itself is rather tricky and uses two auxiliary functions which are not evident and a double integration.

 

[Fred Wright]

Oh dear, what have you done? The first term is at least near the solution (more or less), however, I do not have the second. But that might be due to the fact that my solution doesn't split into real and imaginary parts. It doesn't use complex numbers at all. The solution isn't that complicated, only a square, a logarithm, and a root.

The integral itself is rather tricky and uses two auxiliary functions which are not evident and a double integration.

From the problem statement, I assumed that $a$ is complex.

 

[fresh_42]

From the problem statement, I assumed that $a$ is complex.

Yes, but it remains $a$ throughout the calculation.

Hint: Consider
$$
F(x):=\dfrac{x\log x}{a+x}-\log(a+x)
$$
and
$$
G(x):=\dfrac{x\log x}{a+1-x}+\log(a+1-x)
$$

 

[TeethWhitener]

First of all, I wanted to thank @fresh_42 for all the work he’s done on these challenges. I don’t understand very many of them, but it’s a lot of fun and very educational to watch people tackle these problems (and occasionally to tackle a few myself).

Alright, since there are a few easy ones left, I’ll take a crack at those.

Spoiler: Problem 6

As far as I can tell, there are two approaches: 1) simply count the number of primes less than $7808000000$, or 2) we’re supposed to use the prime number theorem:
$$\pi(n)\approx\frac{n}{\ln{n}}$$
I’m guessing since the population is approximate, the answer should be approximate too. I’m also on winter break right now and am too lazy to write a script that actually counts the primes, so I’m going with method 2, which gives
$$\pi(7808000000)\approx342780659$$
We can get a little more accurate using the logarithmic integral:
$$Li(7808000000)=\int_{2}^{7808000000}{\frac{1}{\ln{x}}\text{dx}}=359364372$$

Spoiler: Problem 11

This is a straightforward calculation of the matrix exponential:
$$\exp{(H)}=\sum_{k=0}^{\infty}{\frac{1}{k!}H^k}$$
Mercifully, this series terminates rather quickly:
$$H^0=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}$$
$$H^1=
\begin{pmatrix}
0 & x_1 & x_3 \\
0 & 0 & x_2 \\
0 & 0 & 0
\end{pmatrix}$$
$$H^2=
\begin{pmatrix}
0 & 0 & x_1x_2 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{pmatrix}$$
All matrices $H^3$ and higher are the zero matrix. Add together the terms that survive and we have:
$$\exp{(H)}=
\begin{pmatrix}
1 & x_1 & x_3+\frac{x_1x_2}{2} \\
0 & 1 & x_2 \\
0 & 0 & 1
\end{pmatrix}$$

 

[fresh_42]

First of all, I wanted to thank @fresh_42 for all the work he’s done on these challenges. I don’t understand very many of them, but it’s a lot of fun and very educational to watch people tackle these problems (and occasionally to tackle a few myself).

Alright, since there are a few easy ones left, I’ll take a crack at those.

Spoiler: Problem 6

As far as I can tell, there are two approaches: 1) simply count the number of primes less than $7808000000$, or 2) we’re supposed to use the prime number theorem:
$$\pi(n)\approx\frac{n}{\ln{n}}$$
I’m guessing since the population is approximate, the answer should be approximate too. I’m also on winter break right now and am too lazy to write a script that actually counts the primes, so I’m going with method 2, which gives
$$\pi(7808000000)\approx342780659$$
We can get a little more accurate using the logarithmic integral:
$$Li(7808000000)=\int_{2}^{7808000000}{\frac{1}{\ln{x}}\text{dx}}=359364372$$

Spoiler: Problem 11

This is a straightforward calculation of the matrix exponential:
$$\exp{(H)}=\sum_{k=0}^{\infty}{\frac{1}{k!}H^k}$$
Mercifully, this series terminates rather quickly:
$$H^0=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}$$
$$H^1=
\begin{pmatrix}
0 & x_1 & x_3 \\
0 & 0 & x_2 \\
0 & 0 & 0
\end{pmatrix}$$
$$H^2=
\begin{pmatrix}
0 & 0 & x_1x_2 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{pmatrix}$$
All matrices $H^3$ and higher are the zero matrix. Add together the terms that survive and we have:
$$\exp{(H)}=
\begin{pmatrix}
1 & x_1 & x_3+\frac{x_1x_2}{2} \\
0 & 1 & x_2 \\
0 & 0 & 1
\end{pmatrix}$$

Yes. If we enumerate all humans on Earth, then a little more than there are US citizens get prime numbers.
$$
\exp{(H)}=
\begin{pmatrix}
1 & x_1 & x_3+\frac{x_1x_2}{2} \\
0 & 1 & x_2 \\
0 & 0 & 1
\end{pmatrix} \in \begin{bmatrix}
1 & * & * \\ 0 & 1 & * \\ 0 & 0 & 1
\end{bmatrix}$$
is the Heisenberg group.

The application that led Hermann Weyl to an explicit realization of the Heisenberg group was the question of why the Schrödinger picture and Heisenberg picture are physically equivalent.

 

[fishturtle1]

Spoiler: Problem 17

First we will show $n$ contains no squares. Suppose $p \vert n$. Then $p \vert \left(\frac{n}{p }- 1\right)$. Then there exists integers $k, l$ such that $n = pk$ and $\frac{n}{p} - 1 = pl$. Multiplying the second equation by $p$ on both sides gives $n - p = p^2l$. Rearranging gives $n = p(pl + 1)$. We see that $p$ does not divide $pl + 1$. We can conclude $p \vert n$, but $p^e$ does not divide $n$ for $e \ge 2$. This shows that $n$ is square free.

Next, assume by contradiction $n = pq$ for distinct primes $p$ and $q$. Since $p \vert n$, we have $p \vert \left(\frac{n}{p}- 1\right)$. But this implies $p \vert (q - 1)$. By similar reasoning, $q \vert (p-1)$. So, $$p \le q - 1 \le q \le p -1$$ which is a contradiction. We may conclude $n$ cannot be a semi prime.

 

[fresh_42]

Spoiler: Problem 17

First we will show $n$ contains no squares. Suppose $p \vert n$. Then $p \vert \left(\frac{n}{p }- 1\right)$. Then there exists integers $k, l$ such that $n = pk$ and $\frac{n}{p} - 1 = pl$. Multiplying the second equation by $p$ on both sides gives $n - p = p^2l$. Rearranging gives $n = p(pl + 1)$. We see that $p$ does not divide $pl + 1$. We can conclude $p \vert n$, but $p^e$ does not divide $n$ for $e \ge 2$. This shows that $n$ is square free.

Next, assume by contradiction $n = pq$ for distinct primes $p$ and $q$. Since $p \vert n$, we have $p \vert \left(\frac{n}{p}- 1\right)$. But this implies $p \vert (q - 1)$. By similar reasoning, $q \vert (p-1)$. So, $$p \le q - 1 \le q \le p -1$$ which is a contradiction. We may conclude $n$ cannot be a semi prime.

Correct.

Numbers with those properties are called Giuga numbers. Giuga conjectured $1950$ that a natural number is prime, if and only if
$$
\sum_{k=1}^{n-1}k^{n-1}\equiv -1 \mod n.
$$
The equation follows from Fermat's little theorem if $n$ is prime:
$$
k^{p-1}\equiv 1\mod p \Longrightarrow \sum_{k=1}^{n-1}k^{n-1}\equiv (p-1)\cdot 1=p-1 \equiv -1 \mod p
$$
It is not clear whether the other direction holds, i.e. whether there are composite numbers with this property. It is only known that such a number has at least $10,000$ decimal digits. A Carmichael number $n$ is a composite, square-free number with the additional property
$$
a^{n-1}\equiv 1 \mod n \text{ for all coprime } a \; , \;(a,n)=1.
$$
Korselt has shown $1899$ that a number $n$ is a Carmichael number, if it is not prime, square-free, and for all its prime divisors $p\,|\,n$ holds $(p-1)\,|\,(n-1).$ This result can be tightened to
$$
p\,|\,n\Longrightarrow (p-1)\,|\,\left(\dfrac{n}{p}-1\right)
$$
because $n-1=(n/p)-1+(p-1)(n/p),$ i.e. $n-1\equiv (n/p)-1\mod (p-1).$ This shows, that Carmichael numbers and Giuga numbers are closely related. Giuga's conjecture is indeed equivalent to:

No natural number is simultaneously Giuga and Carmichael number.

Another interesting theorem is, that $n$ is a Giuga number, if and only if it is a composite, square-free number and
$$
\sum_{p|n}\dfrac{1}{p} -\prod_{p|n}\dfrac{1}{p} \in \mathbb{N}.
$$
This term equals $1$ for all known Giuga numbers:
\begin{align*}
&30, 858, 1722, 66198, 2214408306, 24423128562, 432749205173838, \\&14737133470010574, 550843391309130318,\\& 244197000982499715087866346,\\& 554079914617070801288578559178,\\& 1910667181420507984555759916338506
\end{align*}

 

[PeroK]

Here's an exact answer to problem 6.

Spoiler: Problem 6

I wrote a Python script to count the prime numbers up to 10 billion. For a population of $7,808,000,000$, the exact number of primes less than this is:$$359,357,713$$

Taking the current population to be about $7,916,000,000$, then the exact number of primes less than this is: $$364,098,533$$ That said, there is a website that gives you the precise value of $\pi(n)$ for large value of $n$:

https://www.dcode.fr/prime-number-pi-count

 

[julian]

Quick go at 27.

Spoiler

As $f(x)$ is a continuous function on $[a,b]$ we have that it is bounded and attains those bounds:

\begin{align*}
m \leq f(x) \leq M
\end{align*}

for $x \in [a,b]$, where $m$ is the lower bound of $f(x)$ and $M$ is the upper bound of $f(x)$. So that

\begin{align*}
m \int_a^b g (x) \leq \int_a^b f(x) g (x) dx \leq M \int_a^b g (x)
\end{align*}

where we have used that $g(x) \geq 0$ and that $\int_a^b g(x)$ is finite (as $g(x)$ is integrable). Thus there is a number, say $N$, such that $m \leq N \leq M$ and

\begin{align*}
\int_a^b f(x) g (x) dx = N \int_a^b g (x) .
\end{align*}

As $f(x)$ is continuous on $[a,b]$ the function takes every value between $f(a)$ and $f(b)$, thus there exists $m \leq f(\xi) \leq M$ ($f(\xi)=N$) such that

\begin{align*}
\int_a^b f(x) g (x) dx = f (\xi) \int_a^b g(x) dx
\end{align*}

 

[TeethWhitener]

Spoiler: Problem 23

Edit: ignore what I wrote. I didn’t consider that the number could be prime all by itself. The first two conditions ($2\mod3$ and $3\mod4$) tell us that the solution will be an integer of the form $12n-1$. The first and third ($2\mod5$) conditions tell us that it ends in a 7. The smallest number that satisfies this is 47.

Pretty sure a little piece of code could do this much quicker, but here’s my calculator-free solution:
The smallest prime factor will be at least 7. Looking at the modular behavior of multiples of 7, we find that a family of solutions consisting of 7 multiplied by a number satisfying the following expressions simultaneously:
$$3n+2$$
$$4n+1$$
$$5n+1$$
The smallest number of this form is 41 (this is easy to find by noting that $4n+1$ and $5n+1$ together imply $20n+1$), which gives a solution of $7\times41=287$.

To check whether this is the smallest integer satisfying the equations, we note that $287<\sqrt{17}$, so the smallest prime factor of the solution will either be 7, 11, or 13. The requirements for the multipliers of 11 are:
$$3n+1$$
$$4n+1$$
$$5n+2$$
The smallest number satisfying these expressions is 37 (again, easy to find noting that $3n+1$ and $4n+1$ together imply $12n+1$), which gives the solution $11\times37=407>287$.
The requirements for multipliers of 13 are:
$$3n+2$$
$$4n+3$$
$$5n+4$$
The smallest number satisfying these expressions is 59 (the conditions are equivalent to $3n-1$, $4n-1$, and $5n-1$ together, or $60n-1$), giving $13\times59=767>287$, so our answer is in fact 287.

 

[berkeman]

I'm posting the next two challenges for @fresh_42 since he is away from the Internet for the next couple of days:

28. Consider the circle segment above $A=(-1,0)$ and $B=(1,0)$ of
$$
x^2+\left(y+\dfrac{1}{\sqrt{3}}\right)^2=\dfrac{4}{3}\,.
$$
The point $P:=\left(\dfrac{1}{\sqrt{3}},1-\dfrac{1}{\sqrt{3}}\right)$ lies on this segment. Calculate the height $h$ of the circle segment, and $|AP|+|PB|.$

29. Let $\varphi :V\longrightarrow V$ a linear mapping. Prove
$$
\operatorname{ker} (\varphi) \cap \operatorname{im}(\varphi) =\{0\} \Longleftrightarrow \operatorname{ker}(\varphi \circ \varphi )=\operatorname{ker}(\varphi )
$$

 

[ergospherical]

For 29; I can’t write latex at the moment so I’ll use f instead of phi.

In forward direction:
If v is in ker(f.f) then f(fv) = 0, therefore fv is in both ker(f) and im(f), thus fv = 0 and v is in ker(f). Similarly, if v is in ker(f) then fv = 0, therefore f(fv) = f(0) = 0 since 0 is in ker(f), and therefore v is also in ker(f.f). Hence ker(f.f) = ker(f).

In the opposite direction:
if ker(f.f) = ker(f), then fv = 0 implies that f(fv) = f(0) = 0, and therefore 0 is in both ker(f) and im(f). Consider some non-zero element q = fw of im(f), assuming one exists at all. Then fq = f(fw). But if fq = f(fw) = 0 were true, then w would be an element of ker(f.f) and therefore also of ker(f), which would imply that q = fw = 0. Therefore, 0 is the only element common to ker(f) and im(f).

 

[PeroK]

For 29; I can’t write latex at the moment so I’ll use f instead of phi.

In forward direction:
If v is in ker(f.f) then f(fv) = 0, therefore fv is in both ker(f) and im(f), thus fv = 0 and v is in ker(f). Similarly, if v is in ker(f) then fv = 0, therefore f(fv) = f(0) = 0 since 0 is in ker(f), and therefore v is also in ker(f.f). Hence ker(f.f) = ker(f).

In the opposite direction:
if ker(f.f) = ker(f), then fv = 0 implies that f(fv) = f(0) = 0, and therefore 0 is in both ker(f) and im(f). Consider some non-zero element q = fw of im(f), assuming one exists at all. Then fq = f(fw). But if fq = f(fw) = 0 were true, then w would be an element of ker(f.f) and therefore also of ker(f), which would imply that q = fw = 0. Therefore, 0 is the only element common to ker(f) and im(f).

I think that hangs together. Alternatively:

First note that, as $\phi(v) = 0 \ \Rightarrow \phi(\phi(v)) = 0$, we always have:
$$\ker(\phi) \subseteq \ker(\phi \circ \phi) \ \ (1)$$
Suppose $\ker(\phi) \cap im(\phi) = \{0\}$.

Let $v \in \ker(\phi \circ \phi)$ and $w = \phi(v)$. Note that $\phi(w) = 0$.

We have $w \in im(\phi)$ and $w \in ker(\phi)$, hence $w \in \ker(\phi) \cap im(\phi)$.

$\therefore w = 0$ and $v \in ker(\phi)$

$\therefore \ker(\phi \circ \phi)\subseteq \ker(\phi)$, and using equation (1) we have $\ker(\phi \circ \phi) = \ker(\phi)$.

Suppose $\ker(\phi \circ \phi) = \ker(\phi)$.

Let $v \in \ker(\phi) \cap im(\phi)$. Then $\phi(v) = 0$ and $v = \phi(u)$, some $u \in V$.

$\therefore \phi(\phi(u)) = 0, \ \text{hence} \ u \in ker(\phi \circ \phi)$

$\therefore u \in ker(\phi), \ \text{hence} \ v = \phi(u) = 0$

$\therefore \ker(\phi) \cap im(\phi) = \{0\}$

 

[fishturtle1]

Spoiler: Problem 22

We consider the first map first. Suppose $f(a) = f(b)$. Then $\lbrace a \rbrace =\lbrace b \rbrace$. This implies $a = b$. So, $f$ is injective. If $\vert X \vert = 1$, then $f$ is surjective. Suppose $\vert X \vert \ge 2$. Then we can write $X = \lbrace a, b, \dots \rbrace$. Then $\lbrace a, b \rbrace \in \mathcal{P}(X)$ and $f(x) \neq \lbrace a, b \rbrace$ because $\vert f(x) \vert = 1$ for all $x \in X$. So, $f$ is surjective iff $\vert X \vert = 1$. Lastly, we see $f^{-1}(\emptyset) = \lbrace x \in X : f(x) = \emptyset \rbrace = \emptyset$ because $\vert f(x) \vert = 1$ for all $x \in X$.

Next, we consider the second map. Let $X =\lbrace a ,\dots \rbrace$ and define $A = \lbrace a \rbrace$ and $B = \emptyset$. Then $$g((A,B)) = A \cup B = \lbrace a \rbrace \cup \emptyset = \lbrace a \rbrace = \emptyset \cup \lbrace a \rbrace = B \cup A = g((B,A))$$

and $(A,B) \neq (B,A)$. This shows $g$ is not injective. Let $C \in \mathcal{P}(X)$. Then $g((C,\emptyset)) = C \cup \emptyset = C$. This shows $g$ is surjective. Lastly, observe for arbitrary $A, B \in \mathcal{P}(X)$, if $A \cup B = \emptyset$, then $A \subseteq \emptyset$ and $B \subseteq \emptyset$. This implies $A = \emptyset$ and $B = \emptyset$. So, $g^{-1}(\emptyset) = \lbrace (\emptyset, \emptyset) \rbrace$. []

 

[mathwonk]

for #9, I believe that a loop is null homologous iff every holomorphic one - form integrates to zero over it. does that do it? (just throwing out an approach for complex analysts, since a topologist presumably knows that homology is a continuous invariant; or does 0 - homologue have some other meaning?)

 

[fresh_42]

The missing rest of the month is added now.

 

[fresh_42]

Spoiler: Problem 23

Edit: ignore what I wrote. I didn’t consider that the number could be prime all by itself. The first two conditions ($2\mod3$ and $3\mod4$) tell us that the solution will be an integer of the form $12n-1$. The first and third ($2\mod5$) conditions tell us that it ends in a 7. The smallest number that satisfies this is 47.

Pretty sure a little piece of code could do this much quicker, but here’s my calculator-free solution:
The smallest prime factor will be at least 7. Looking at the modular behavior of multiples of 7, we find that a family of solutions consisting of 7 multiplied by a number satisfying the following expressions simultaneously:
$$3n+2$$
$$4n+1$$
$$5n+1$$
The smallest number of this form is 41 (this is easy to find by noting that $4n+1$ and $5n+1$ together imply $20n+1$), which gives a solution of $7\times41=287$.

To check whether this is the smallest integer satisfying the equations, we note that $287<\sqrt{17}$, so the smallest prime factor of the solution will either be 7, 11, or 13. The requirements for the multipliers of 11 are:
$$3n+1$$
$$4n+1$$
$$5n+2$$
The smallest number satisfying these expressions is 37 (again, easy to find noting that $3n+1$ and $4n+1$ together imply $12n+1$), which gives the solution $11\times37=407>287$.
The requirements for multipliers of 13 are:
$$3n+2$$
$$4n+3$$
$$5n+4$$
The smallest number satisfying these expressions is 59 (the conditions are equivalent to $3n-1$, $4n-1$, and $5n-1$ together, or $60n-1$), giving $13\times59=767>287$, so our answer is in fact 287.

The answer is correct, the reasoning is not: $32\equiv 2 \,(3)\wedge 32\equiv 2\,(5)$ and $32$ does not end on a $7.$

Another idea how to prove it?

 

[fresh_42]

Spoiler: Problem 22

We consider the first map first. Suppose $f(a) = f(b)$. Then $\lbrace a \rbrace =\lbrace b \rbrace$. This implies $a = b$. So, $f$ is injective. If $\vert X \vert = 1$, then $f$ is surjective. Suppose $\vert X \vert \ge 2$. Then we can write $X = \lbrace a, b, \dots \rbrace$. Then $\lbrace a, b \rbrace \in \mathcal{P}(X)$ and $f(x) \neq \lbrace a, b \rbrace$ because $\vert f(x) \vert = 1$ for all $x \in X$. So, $f$ is surjective iff $\vert X \vert = 1$. Lastly, we see $f^{-1}(\emptyset) = \lbrace x \in X : f(x) = \emptyset \rbrace = \emptyset$ because $\vert f(x) \vert = 1$ for all $x \in X$.

Next, we consider the second map. Let $X =\lbrace a ,\dots \rbrace$ and define $A = \lbrace a \rbrace$ and $B = \emptyset$. Then $$g((A,B)) = A \cup B = \lbrace a \rbrace \cup \emptyset = \lbrace a \rbrace = \emptyset \cup \lbrace a \rbrace = B \cup A = g((B,A))$$

and $(A,B) \neq (B,A)$. This shows $g$ is not injective. Let $C \in \mathcal{P}(X)$. Then $g((C,\emptyset)) = C \cup \emptyset = C$. This shows $g$ is surjective. Lastly, observe for arbitrary $A, B \in \mathcal{P}(X)$, if $A \cup B = \emptyset$, then $A \subseteq \emptyset$ and $B \subseteq \emptyset$. This implies $A = \emptyset$ and $B = \emptyset$. So, $g^{-1}(\emptyset) = \lbrace (\emptyset, \emptyset) \rbrace$. []

Almost correct! In case $|X|=1$ we have $\mathcal{P}(X)=\{\emptyset\, , \,\{x\}\}$ but $\emptyset \not\in f(X)$ hence $f$ isn't surjective in that case either: $\emptyset \notin X.$

 

[TeethWhitener]

The answer is correct, the reasoning is not: $32\equiv 2 \,(3)\wedge 32\equiv 2\,(5)$ and $32$ does not end on a $7.$

Another idea how to prove it?

The condition $2\mod5$ means the number ends in a 2 or a 7, and $3\mod4$ means the number has to be odd.

 

[fresh_42]

The condition $2\mod5$ means the number ends in a 2 or a 7, and $3\mod4$ means the number has to be odd.

Sorry, but you wrote

The first and third ($2\mod5$) conditions tell us that it ends in a 7.

and not second and third!

 

[fresh_42]

for #9, I believe that a loop is null homologous iff every holomorphic one - form integrates to zero over it. does that do it? (just throwing out an approach for complex analysts, since a topologist presumably knows that homology is a continuous invariant; or does 0 - homologue have some other meaning?)

Cauchy is correct, but it can be used in either of the two directions, hence it is necessary to at least sketch which proof is meant (a proof where the chain rule is seen would be preferred), rather than saying Cauchy.

 

[TeethWhitener]

Sorry, but you wrote

and not second and third!

Oh, oops…

 

[fresh_42]

Oh, oops…

Here is the proof by the Chinese remainder theorem:There is a solution $x$ since $3,4,5$ are pairwise coprime by the Chinese remainder theorem, and all solutions are congruent modulo $M=3\cdot4\cdot5=60.$ The calculation is
\begin{align*}
7\cdot 3 +(-1)\cdot \dfrac{M}{3}=1 &\Longrightarrow \alpha_1=-20\\
4\cdot 4 +(-1)\cdot \dfrac{M}{4}=1 &\Longrightarrow \alpha_2=-15\\
5\cdot 5 +(-2)\cdot \dfrac{M}{5}=1 &\Longrightarrow \alpha_3=-24
\end{align*}
which results in
$$
x=2\cdot \alpha_1+3\cdot\alpha_2+2\cdot\alpha_3=-133 \equiv 47 \mod M.
$$

 

[ergospherical]

For 30 I observe that $\nabla \cdot F = 2z$, so by theorem of Gauss $\int_A \langle F, n \rangle dS = \int 2z dV - \cancel{123\int_{\mathrm{cover}} dS} + \cancel{123\int_{\mathrm{base}} dS} = \pi R^2 h^2$.

(Directly, one could parameterise $A$ by $\Phi(\theta, z) = (R\cos{\theta}, R\sin{\theta}, z)$ to obtain a surface element $n dS = R(\cos{\theta}, \sin{\theta}, 0)d\theta dz$ and then an integral $\int_A \langle F, n \rangle dS = R^2 \int z dz \int d\theta = \pi R^2 h^2$).

 

[fresh_42]

For 30 I observe that $\nabla \cdot F = 2z$, so by theorem of Gauss $\int_A \langle F, n \rangle dS = \int 2z dV +\cancel{123\int_{\mathrm{cover}} dS} - \cancel{123\int_{\mathrm{base}} dS} = \pi R^2 h^2$.

(Directly, one could parameterise $A$ by $\Phi(\theta, z) = (R\cos{\theta}, R\sin{\theta}, z)$ to obtain a surface element $n dS = R(\cos{\theta}, \sin{\theta}, 0)d\theta dz$ and then an integral $\int_A \langle F, n \rangle dS = R^2 \int z dz \int d\theta = \pi R^2 h^2$).

I guess it will do no harm to elaborate on these two solutions for those who do not "see" it at once.

One possible parameterization is
\begin{align*}
\phi\, : \,[0,2\pi) \times [0,h]&\longrightarrow A\\
(\varphi,z)&\longmapsto (R\cos\varphi ,R\sin\varphi ,z)
\end{align*}
The height of the cylinder is given by $z,$ and for a fixed $z$ we have a circle parallel to the plane $z=0$ described by polar coordinates. $\phi$ is a bijection because every point on $A$ has exactly one pair of parameters $(\phi,z).$

We use this parameterization $\phi$ to calculate the surface integral.
\begin{align*}
\int_A \langle F,n \rangle\,d^2r&=\int_{0}^{2\pi}\int_{0}^{h}\langle F\circ\phi,n \rangle\,\|\partial_\varphi \phi \times \partial_z \phi\| \,dz\,d\varphi \\
&=\int_{0}^{2\pi}\int_{0}^{h}\langle F\circ\phi,\partial_\varphi \phi \times \partial_z \phi \rangle\, \,dz\,d\varphi \\
&=\int_{0}^{2\pi}\int_{0}^{h}\langle \begin{pmatrix}
zR\cos\varphi \\zR\sin\varphi \\123 \end{pmatrix},\begin{pmatrix}
R\cos\varphi \\R\sin\varphi \\0 \end{pmatrix} \rangle\, \,dz\,d\varphi \\
&=\int_{0}^{2\pi}\int_{0}^{h} zR^2\left(\cos^2\varphi +\sin^2\varphi \right)\,dz\,d\varphi \\
&=\int_{0}^{2\pi}\int_{0}^{h} zR^2\,dz\,d\varphi = 2\pi R^2\left[\dfrac{z^2}{2}\right]_{z=0}^{z=h}=h^2\pi R^2
\end{align*}

We could alternatively use Gauß's divergence theorem. This uses closed surfaces, so we have to consider base and cover. Let $C$ be the volume of the cylinder, $D_1$ its base, and $D_2$ its cover. Then $\partial Z=A\cup D_1\cup D_2.$ Note that the two integrals over $D_1$ and $D_2$ cancel each other since the normal vectors $n$ are parallel to the $z$-axis, but pointing into opposite directions, and the third component of $F$ is constant.
\begin{align*}
\int_{D_1} \langle F,n \rangle\,d^2r + \int_{D_2} \langle F,n \rangle \, d^2r &= \int_{D_1}\langle F,\begin{pmatrix}
0\\0\\1 \end{pmatrix} \rangle \,d^2r+ \int_{D_2}\langle F,\begin{pmatrix}
0\\0\\-1 \end{pmatrix} \rangle\,d^2r\\&=
\int_{D_1}123\,d^2r + \int_{D_2}-123\,d^2r \\&=123(\pi R^2-\pi R^2)=0
\end{align*}
Therefore
$$
\int_{\partial Z}\langle F,n \rangle\,d^2r = \int_{A}\langle F,n \rangle\,d^2r+\int_{D_1}\langle F,n \rangle\,d^2r+\int_{D_2}\langle F,n \rangle\,d^2r=\int_{A}\langle F,n \rangle\,d^2r
$$
Now we apply Gauß's divergence theorem
\begin{align*}
\int_{\partial Z}\langle F,n \rangle\,d^2r&=\int_Z\operatorname{div} F\,d^3r\\&=
\int_{0}^{R}\int_{0}^{2\pi}\int_{0}^{h}(\operatorname{div}F)\circ \phi \cdot |\det J_\phi|\,dz\,d\varphi \,d\rho\\
&=\int_{0}^{R}\int_{0}^{2\pi}\int_{0}^{h} 2z\rho \,dz\,d\varphi \,d\rho\\
&=2\cdot \dfrac{R^2}{2}\cdot\dfrac{h^2}{2}\cdot 2\pi = h^2\pi R^2
\end{align*}

 

[fishturtle1]

Spoiler: Problem 30

Definition: Three or more points that lie on the same line are called collinear.

Proof: We write $\mathcal{P} = \lbrace p_1, \dots, p_n \rbrace$. We prove the statement by inducting on $n$.

base case: $n = 2$. Consider the line that passes through the points $p_1$ and $p_2$. There are no other points, so this line contains exactly two elements of $\mathcal{P}$.

inductive step: Proceeding by induction, we suppose that the statement is true for $n-1 \ge 2$. We will show the statement holds for $n$ points. By assumption, $p_1, \dots, p_{n-1}$ are not all collinear. By the inductive hypothesis, we can find a line, say $l$ that contains exactly two of these points. WLOG, suppose these two points are $p_1$ and $p_2$. If $p_n$ is not contained in $l$, then we are done. If $p_n$ is on $l$, then $p_1, p_2,$ and $p_n$ are collinear which contradicts our assumption that $p_1, \dots, p_n$ are not all collinear. []

Let P be a finite set of points in a plane, that are not all collinear.

does this mean no three points in $\mathcal{P}$ are collinear? Or only a specific $p_1, p_2, p_3$?

 

[Infrared]

@fishturtle1 This is fairly famous result, so I feel confident in assuming that @fresh_42 meant that not all of the points lie on the same line. With your interpretation, there would be absolutely nothing to prove (if no three points are collinear, then any line passing through any two of the points would work).

 

[Not anonymous]

28. Consider the circle segment above $A = (-1, 0)$ and $B = (1, 0)$ of $$
x^2 + \left(y + \dfrac{1} {\sqrt{3}}\right)^2 = \dfrac {4}{3}
$$

The point $P := \left(\dfrac{1} {\sqrt{3}}, 1 - \dfrac{1} {\sqrt{3}} \right)$ lies on this segment. Calculate the height $h$ of the circle segment, and $|AP| + |PB|$.

Spoiler: Question 28

Since the given circle's equation can be rewritten as $\left(x-0\right)^2 + \left(y - \dfrac{-1} {\sqrt{3}}\right)^2 = \left(\dfrac {2}{\sqrt{3}}\right)^2$, it must be centered at the point $Q = \left(0, \dfrac {-1}{\sqrt{3}}\right)$ and have the radius $\dfrac {2}{\sqrt{3}}$. Points $A$ and $B$ lie on this circle and therefore the line segment is a chord of this circle. Since the line segment $\overline{AB}$ chord lies on the x-axis $(y = 0)$, the height of the circle segment above $\overline{AB}$ must equal the radius plus the y-coordinate of the center point $Q$, i.e. $h = \dfrac {2}{\sqrt{3}} + \left(\dfrac{-1} {\sqrt{3}}\right) = \dfrac{1} {\sqrt{3}}$.

$$
|AP| = \sqrt{\left(\dfrac{1} {\sqrt{3}} - (-1)\right)^2 + \left(\left(1 - \dfrac{1} {\sqrt{3}}\right) - 0\right)^2} = 2 \sqrt{\dfrac{2}{3}}
$$

$$
|PB| = \sqrt{\left(1 - \dfrac{1} {\sqrt{3}}\right)^2 + \left(0 - \left(1 - \dfrac{1} {\sqrt{3}}\right) \right)^2} = \sqrt{2 \left(1 - \dfrac{1} {\sqrt{3}}\right)^2} = \sqrt{2} - \sqrt{\dfrac{2}{3}}
$$

$$
\Rightarrow |AP| + |PB| = \sqrt{2} + \sqrt{\dfrac{2}{3}}
$$

 

[julian]

Hi @fresh_42. I notice you have given the solutions for December's math challenges. For problem 2 you've written

\begin{align*}
I = \frac{1}{2} \log^2 \frac{a}{a+1} = \log^2 \sqrt{\frac{a}{a+1}}
\end{align*}

The final expression (the RHS) seems wrong because isn't $\log^2 \sqrt{\frac{a}{a+1}} = \dfrac{1}{4} \log^2 \frac{a}{a+1}$?

 

[julian]

Hi, @Fred Wright. I think you got the right answer for problem 2, but you didn't write it down it terms of $a$. If you had it would have been:

\begin{align*}
I = \frac{1}{2} \log^2 \frac{z_0}{z_1} \equiv \frac{1}{2} \log^2 \frac{a}{a+1}
\end{align*}

You skipped writing your answer in terms of $a$ and wrote the answer in terms of $|a|$ and $\phi$ instead. This answer was correct except for a slight typo. The exponent in your expression for $z$ should have been:

\begin{align*}
i \tan^{-1} \left( \frac{\sin \phi}{|a| + \cos \phi} \right)
\end{align*}

Another slight typo you made was writing $I_2 = - Li_2 \left( - \frac{1}{z_0} \right)$. It think $I_2$ should be $+ Li_2 \left( - \frac{1}{z_0} \right)$ instead,

\begin{align*}
I_2 & = \int_0^1 \frac{\log x}{z_0 + x} dx
\nonumber \\
& = boundary \; terms \; - \int_0^1 \frac{\log (z_0 + x)}{x} dx
\nonumber \\
& =boundary \; terms \; - \int_0^1 \frac{\log (1 + \frac{x}{z_0})}{x} dx
\nonumber \\
& = - \int_0^1 \frac{\log (1 + \frac{x}{z_0})}{x} dx
\nonumber \\
& = - \int_0^{- \frac{1}{z_0}} \frac{\log (1 - u)}{u} du
\nonumber \\
& = + Li_2 \left( - \frac{1}{z_0} \right)
\end{align*}

Then

\begin{align*}
I & = I_1 - I_2
\nonumber \\
& = - \left( Li_2 \left( \frac{1}{z_1} \right) + Li_2 \left( - \frac{1}{z_0} \right) \right) .
\end{align*}

 

[fresh_42]

Hi @fresh_42. I notice you have given the solutions for December's math challenges. For problem 2 you've written

\begin{align*}
I = \frac{1}{2} \log^2 \frac{a}{a+1} = \log^2 \sqrt{\frac{a}{a+1}}
\end{align*}

The final expression (the RHS) seems wrong because isn't $\log^2 \sqrt{\frac{a}{a+1}} = \dfrac{1}{4} \log^2 \frac{a}{a+1}$?

Thank you! My bad. I have corrected this. I'm afraid it won't be the last sloppy formula.

 

[julian]

I was just thinking to myself, it is not like @fresh_42 to be sloppery.

 

[fresh_42]

I was just thinking to myself, it is not like @fresh_42 to be sloppery.

Thanks for the flowers. I wrote many of these late at night, and who wants to proofread 500+ pages?

 

[julian]

We are all very grateful! We can learn a lot by reading your solutions!

 

[Not anonymous]

31. Let $\mathcal{P}$ be a finite set of points in a plane, that are not all collinear. Then there is a straight, that contains exactly two points.

Spoiler: Question 31

When $\mathcal{P}$ contains 3 or more points, and not all are collinear, there will exist a polygonal convex hull all of whose vertices belong to and all other points of $mathcal{P}$ are contained within or lie on the edges of this polygon. Let $\{P_1, P_2, ..., P_m\} \subset \mathcal{P}$ be the ordered vertices of this convex hull polygon ($P_1$ can be chosen arbitrarily from the $m$ vertices and the rest of the vertices are named accordingly in order). Let $A \in \mathcal{P} \setminus \{P_1, P_2, ..., P_{m-1}\}$ be the point belonging to $\mathcal{P}$ that is closest to $P_1$ on the line segment $\overline {P_m P_1}$. In the trivial case, $A = P_m$ and in this case the line containing the line segment $\overline {P_m P_1}$ passes through just 2 points of $\mathcal{P}$. Even if $A \neq P_m$, we can find 2 points belonging to $\mathcal{P}$ and lying on or within $\triangle {A P_1 P_2}$ such that the line passing through those 2 points does not contain any other point of $\mathcal{P}$. This is demonstrated by the following figures.

Figure 1: Case 1: Line segment $\overline {P_1 P_2}$ lies in a line that passes through only 2 points from $\mathcal{P}$

Figure 2: Case 2: Line segment $\overline {P_1 P_2}$ contains one or more points from $\mathcal{P}$ other than $P_1, P_2$. $\triangle {A P_1 S_1}$ does not contain any interior point belonging to $\mathcal{P}$ nor does $\overline {A S_1}$ contain points from $\mathcal{P}$ other than $A, S_1$. $\overline {A S_1}$ forms an edge of the polygonal convex hull containing all points of $\mathcal{P}$ except $P_1$. The line passing through this line segment contains no point of $\mathcal{P}$ except $A, S_1$

Figure 3: Case 3: Line segment $\overline {P_1 P_2}$ contains one or more points from $\mathcal{P}$ other than $P_1, P_2$, $\triangle {A P_1 S_1}$ contains one or more interior points belonging to $\mathcal{P}$. Line segment $\overline {T_k S_1}$ forms an edge of the polygonal convex hull containing all points of $\mathcal{P}$ except $P_1$. The line passing through this line segment does not contain any point from $\mathcal{P}$ except $T_k$ and $S_1$

Figure 4: Case 4: Line segment $\overline {P_1 P_2}$ contains one or more points from $\mathcal{P}$ other than $P_1, P_2$. $\triangle {A P_1 S_1}$ does not contain in its interior any point belonging to $\mathcal{P}$, but $\overline {P_1 P_2}$ has some points from $\mathcal{P}$ other than $A, S_1$. $\mathcal{T} \equiv \{T_1, T_2, ..., T_k\} \subset \mathcal{P}$ lie within $\triangle {A P_1 P_2}$ and are vertices of the polygonal convex hull containing all points of $\mathcal{P} \setminus \{P_1, S_1, S_2, ..., S_l\}$. $j \in \{2, ..., l\}$ is the smallest integer such that $\mathcal{T} \cup \{S_j, P_2, P_3, ..., P_m, A\}$ form vertices of a polygonal convex hull (this will contain all points of $\mathcal{P} \setminus \{P_1, S_1, S_2, ..., S_{j-1}\}$). This implies that $S_j$ does not lie on the line passing through $\overline {T_{k-1} T_k}$, since otherwise $T_k$ will not be a vertex of the convex hull. And since $\overline {T_k S_j}$ is an edge of the convex hull, the line passing through it cannot contain any point of $\mathcal{P}$ other than $T_k, S_j$.

Figure 5: Case 5: A special case within case 4 wherein no $S_j \in \{S_1, ..., S_l\}$ meets the condition that both $T_k$ and $S_j$ form vertices of the convex hull of $\mathcal{P} \setminus \{P_1, S_1, S_2, ..., S_{j-1}\}$. In this case, $\overline {T_k P_2}$ will form an edge of the polygonal convex hull of $\mathcal{P} \setminus \{P_1, S_1, S_2, ..., S_j\}$, and the line passing through $\overline {T_k P_2}$ will not pass through any point of $\mathcal{P}$ other than $T_k, P_2$.

 

[Not anonymous]

Sorry, please ignore my previous post (post #90). I think I found a mistake in that solution for question #31. I will attempt to find a correct solution later and make a new post.

 

[fresh_42]

Sorry, please ignore my previous post (post #90). I think I found a mistake in that solution for question #31. I will attempt to find a correct solution later and make a new post.

You do not need an algorithm or any iteration. Consider pairs $(g,P)$ of a straight line in the plane and a point $P\not\in g.$ Then choose a pair such that $\operatorname{dist}(g,P)$ is minimal.

 

[Not anonymous]

You do not need an algorithm or any iteration. Consider pairs $(g,P)$ of a straight line in the plane and a point $P\not\in g.$ Then choose a pair such that $\operatorname{dist}(g,P)$ is minimal.

I didn't expect a reply to my withdrawn incorrect solution. ** thanks for that hint. Below is a solution, hopefully correct this time.

Spoiler: Question 31

Let $\mathcal{L} = \{l_1, l_2, ..., l_m\}$ be the set of all lines that pass through 2 or more points belonging to $\mathcal{P} = \{P_1, P_2, ..., P_n\}$. Suppose $A \in \mathcal{P}, l_i \in \mathcal{L}$ be a point and a line such that $\mathtt{dist}(A, l_i) = \min \limits_{P_j \in \mathcal{P}} \min \limits_{l_k \in \mathcal{P}, P_{j} \notin_{l_k}} \mathtt{dist}(P_j, l_k)$. Such a pair will always exist if not all points of $\mathcal{P}$ are collinear. Without loss of generality, we will assume $l_i = l_1$ for convenience hereafter. By definition, $l_1$ will contain at least two points from $\mathcal{P}$. We will prove that $l_1$ cannot contain more than 2 points from $\mathcal{P}$, thus making it a line passing through exactly 2 points from $\mathcal{P}$.

Let $B, C$ be the two closest points to $A$ among all points from $\mathcal{P}$ lying on $l_1$. With reference to attached figure, $h_{A[BC]} \equiv \mathtt{dist}(A, l_1)$, using the notation $h_{X[YZ]}$ to denote the height of vertex $X$ w.r.t. the base $\bar {YZ}$ in triangle $\Delta {XYZ}$. Note that $BC$ must be the longest edge of $\Delta ABC$ (more precisely, no smaller than the other edges), since otherwise, we could have, for e.g., $h_{B[AC]} \lt h_{A[BC]}$, i.e. distance between $B$ and line passing through $A,C$ is smaller than $\mathtt{dist}(A, l_1)$, a contradiction. Therefore, $\angle{ABC}, \angle{ACB}$ must be acute angles as shown in the figure.

Now suppose there exists yet another point $D \in \mathcal{P}$ that lies on $l_1$. Without loss of generality, we can assume that it lies to the right of point $C$. Let $l_2 \in \mathcal{L}$ denote the line passing through $A, D$. From the figure, we see that $\mathtt{dist}(C, l_2) = h_{C[AD]}$. Using the area computation formulae for triangle $\Delta {AQ_{1}D}$, it follows that $h_{A[BC]} \times \mathtt{len}(Q_{1}D) = h_{C[AD]} \times \mathtt{len}(AD)$. Since $\mathtt{len}(AD) \gt \mathtt{len}(Q_{1}D)$ (as $AD$ is the hypotenuse of $\Delta {AQ_{1}D}$), it follows that $h_{C[AD]} \lt h_{A[BC]}$, i.e. $\mathtt{dist}(C, l_2) < \mathtt{dist}(A, l_1)$. But this contradicts the initial assumption that $\mathtt{dist}(A, l_1)$ is the minimum possible distance between any point in $\mathcal{P}$ and any line in $\mathcal{L}$. Since the contradiction arises only when we assume that there exists a point $D$ as defined above, it must be the case that such as point cannot exist. Hence, $l_1$ must contain only two points from $\mathcal{P}$.

 

[Not anonymous]

Once again I found a mistake in my solution. This time in one of equalities used in the proof. Posting the correction here.

Spoiler: Question 31 - correction to previous post

To show that $h_C[AD] < h_{A[BC]}$ if a point $D$ exists as described in my previous post, I must have used an inequality since I was comparing two different triangles.

The area of $\Delta AQ_{1}D$ is $\dfrac{1}{2} \times h_{A[BC]} \times \mathtt{len}(Q_1D)$. The area of $\Delta ACD$ is $\dfrac{1}{2} \times h_{C[AD]} \times \mathtt{len}(AD)$. From the figure, it can be seen that the area of $\Delta AQ_{1}D$ must be larger than that of $\Delta ACD$. Hence we get:
$$
\dfrac{1}{2} \times h_{A[BC]} \times \mathtt{len}(Q_1D) > \dfrac{1}{2} \times h_{C[AD]} \times \mathtt{len}(AD) \Rightarrow h_{A[BC]} > \dfrac{\mathtt{len}(AD)}{\mathtt{len}(Q_1D)} \times h_{C[AD]}
$$

Since $\mathtt{len}(AD) > \mathtt{len}(Q_1D)$ (as $AD$ is the hypotenuse of $\Delta AQ_1D$), it follows that $h_{A[BC]} > h_{C[AD]}$, i.e. $\mathtt{dist}(A, l_1) > \mathtt{dist}(C, l_2)$, but this contradicts the initial assumption about the minimality of $\mathtt{dist}(A, l_1)$.

The rest of the solution is the same as in the previous post.