Challenge Math Challenge - December 2021

Click For Summary
This month's math challenges will adopt a new format, presenting one problem daily throughout December. The first problem involves proving that a group with 3129 elements is solvable, which has been discussed in relation to Sylow theorems and group order. Participants have expressed appreciation for the challenges and the learning opportunities they provide, despite some topics being advanced. The discussion highlights the importance of understanding group properties, particularly the implications of subgroup normality and structure. Overall, the community looks forward to future challenges after this creative break.
  • #61
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.
 
Physics news on Phys.org
  • #62
fishturtle1 said:
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*}
 
  • Wow
Likes fishturtle1
  • #63
Here's an exact answer to 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
 
  • Like
Likes TeethWhitener and fresh_42
  • #64
Quick go at 27.

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*}

 
Last edited:
  • #65
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.
 
Last edited:
  • #66
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 )
$$
 
  • #67
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).
 
  • #68
ergospherical said:
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\}##
 
  • #69
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##. []
 
  • #70
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?)
 
  • #71
The missing rest of the month is added now.
 
  • #72
TeethWhitener said:
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?
 
  • #73
fishturtle1 said:
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.##
 
Last edited:
  • Like
Likes fishturtle1
  • #74
fresh_42 said:
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.
 
  • #75
TeethWhitener said:
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!
 
  • #76
mathwonk said:
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.
 
  • #77
fresh_42 said:
Sorry, but you wrote

and not second and third!
Oh, oops…
 
  • #78
TeethWhitener said:
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.
$$
 
  • #79
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##).
 
  • #80
ergospherical said:
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*}
 
Last edited:
  • Like
Likes ergospherical
  • #81
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. []
fresh_42 said:
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##?
 
  • #82
@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).
 
  • Informative
Likes fishturtle1
  • #83
fresh_42 said:
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|##.

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}}
$$
 
  • #84
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}##?
 
Last edited:
  • #85
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*}
 
Last edited:
  • #86
julian said:
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.
 
  • #87
I was just thinking to myself, it is not like @fresh_42 to be sloppery.
 
  • #88
julian said:
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?
 
  • #89
We are all very grateful! We can learn a lot by reading your solutions!
 
  • #90
fresh_42 said:
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.

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.

geogebra-export4.png



Figure 1:
Case 1: Line segment ##\overline {P_1 P_2}## lies in a line that passes through only 2 points from ##\mathcal{P}##
geogebra-export5.png

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##
geogebra-export1.png


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##
geogebra-export6.png


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##.
geogebra-export3.png


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

Attachments

  • geogebra-export4.png
    geogebra-export4.png
    7.9 KB · Views: 175
  • geogebra-export2.png
    geogebra-export2.png
    11.4 KB · Views: 141
  • geogebra-export3.png
    geogebra-export3.png
    12.3 KB · Views: 143

Similar threads

  • · Replies 33 ·
2
Replies
33
Views
9K
  • · Replies 61 ·
3
Replies
61
Views
11K
  • · Replies 42 ·
2
Replies
42
Views
10K
  • · Replies 114 ·
4
Replies
114
Views
11K
  • · Replies 60 ·
3
Replies
60
Views
12K
  • · Replies 175 ·
6
Replies
175
Views
26K
  • · Replies 86 ·
3
Replies
86
Views
13K
  • · Replies 28 ·
Replies
28
Views
7K
  • · Replies 61 ·
3
Replies
61
Views
13K
  • · Replies 100 ·
4
Replies
100
Views
11K