Basic Math Challenge - August 2018

[fresh_42]

Summer is coming and brings a new basic math challenge! Enjoy! For more advanced problems you can check our other intermediate level math challenge thread!

RULES:

1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
5) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted.

QUESTIONS:

1. Given a non-negative, monotone decreasing sequence $(a_n)_{n \in \mathbb{N}}\subseteq \mathbb{R}\,.$ Prove that $\sum_{n \in \mathbb{N}}a_n$ converges if and only if $\sum_{n \in \mathbb{N}_0}2^na_{2^n}$ converges.

2. (solved by @lpetrich ) Calculate
$$
\sum_{k=0}^\infty \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m!}\cdot \left(\dfrac{(2k)!}{k!}\right)^2 \dfrac{2^{-6k-2}}{(2k-m+1)!}
$$
3. (solved by @nuuskur , @lpetrich ) Show that the product $P=xyz$ of a Pythagorean triple $x^2+y^2=z^2$ is always divisible by $60\,|\,P$. Since this is an easy problem, please make sure you won't forget to name an argument!

4. (solved by @lpetrich, resp. resolved ) Given two vector fields $v,w\, : \,\mathbb{R}^2 \longrightarrow \mathbb{R}^2$ by
$$
v(x,y)=\begin{bmatrix}
y \\ x-y
\end{bmatrix}\; , \;w(x,y)=\begin{bmatrix}
y-x \\ -y
\end{bmatrix}
$$
and two curves in $\mathbb{R}^2$ given as:
$\gamma_1$ is the half circle from $(0,-1)$ to $(0,1)$ with radius $1$ and origin $(0,0)$, run anti-clockwise from bottom to top.
$\gamma_2$ is the straight line segments from (-1,0) correction: $(0,-1)$ to $(1,0)$ and from $(1,0)$ to $(0,1)$, also run through from bottom to top.

• Compute all $4$ path integrals of $v$ and $w$ with both paths $\gamma_1,\gamma_2\,.$
• Determine whether $v$ or $w$ have potentials.

5. (solved by @nuuskur ) Show that $\mathbb{Z}[x]/\langle x^2+2x+4\; , \;5 \rangle \cong \mathbb{Z}_5[4+\sqrt{2}]$ are isomorphic rings.

6. (solved by @lpetrich ) Calculate
$$
\int_0^{\pi} \dfrac{\sin(\varphi)}{3\cos^2(\varphi)+2\cos(\varphi)+3}\,d\varphi
$$
7. (solved by @lpetrich ) Integrate $$\int_1^5 \dfrac{dx}{\sqrt{x^2+3x-4}}$$
8. (solved by @Math_QED ) The random waiting time $X$ on a telephone hotline is characterized by the distribution function $F$ with
$$
F(x) =
\begin{cases}
0 & \text{if } x < 0 \\
a-be^{-\lambda x}1 & \text{if } x \geq 0
\end{cases}
$$
for some parameters $a, b, \lambda \in \mathbb{R}$ with $\lambda > 0\,.$ We further assume that $P(X=0)=0.5$, i.e. there is a $50\,\%$ chance not to wait at all, and $P(X>1[min])=0.25$.

• Determine the parameters with the given information, such that $F$ is actually a distribution function.
  
• Can the distribution be described by a density function? Why? If yes, calculate the density function.

9. (solved by @Danny Sleator ) A princess decided one day to go swimming in the circular lake far from the castle of her father. As soon as she got into the water, suddenly a witch appeared, who wanted to kidnap the girl. The princess swam quickly into the middle of the lake to think of an escape plan. She noticed three things:

• The witch can run four times as fast as I can swim.
• The witch always tries to stay closest to me.
• On land, I'm faster than the witch.

Is there a way for the princess to escape, how? Why doesn't she have a chance to escape?

10. (solved by @Dewgale ) Let $f\, : \,\mathbb{R}^2 \longrightarrow \mathbb{R}$ be defined as $f(x,y)=x(x-1)^2-2y^2\,.$ Determine all critical points of $f$, decide whether there are extrema, and which, and at last consider, whether $f$ has global extrema or not.

 

[lpetrich]

Solution for Question 4:

Spoiler

The path interval of vector $V = \{V_x, V_y\}$ over $X = \{x,y\}$ with parameter $t$ is:
$$ I = \int V \cdot dX = \int V \cdot \frac{dX}{dt} dt $$
The vectors are $u = \{y, x-y\}$ and $v = \{y-x,-y\}$.
The curves of integration are
$$ \gamma_1 = \{\sin t, - \cos t\} \text{ for } t \in [0,\pi] \\
\gamma_2 = \{t,0\} \text{ for } t \in [-1,1] \text{ and } \{1-t,t\} \text{ for } t \in [0,1] $$
The integrals are:

• $(u,\gamma_1)$: $0$
• $(u,\gamma_2)$: $- \frac12$
• $(v,\gamma_1)$: $- \frac{\pi}{2}$
• $(v,\gamma_2)$: $- \frac12$

How much intermediate manipulation should I show?

If a vector field $V$ has potential $P$, then $V = \nabla P = \{\frac{\partial P}{\partial x}, \frac{\partial P}{\partial y} \}$. It is easy to show that this results in the field's curl (asymmetrized gradient) vanishing, or in two dimensions, $\frac{\partial V_x}{\partial y} = \frac{\partial V_y}{\partial x}$. I'm not sure about the converse, that vanishing curl implies a potential. The path integral of $V$ is
$$ \int V \cdot dX = \int \nabla P \cdot dX = P $$
For $u$, we get $1 = 1$, and for $v$, we get $1 = 0$, So $v$ does not have a potential. For $u$, the potential is, from integration of each component,
$$P = xy + F(y) = xy - \frac12 y^2 + G(x) = xy - \frac12 y^2 + P_0 $$

 

[lpetrich]

Solution for Question 6:

Spoiler

Let
$$ I = \int_0^{\pi} \dfrac{\sin(\varphi)}{3\cos^2(\varphi)+2\cos(\varphi)+3}\,d\varphi $$
Change variables from $\varphi$ to $x = \cos\varphi$. The bounds of integration become $x = 1$ and $x = -1$ and the differential $dx = - \sin\varphi \, d\varphi$. With this change of variables, the integral becomes
$$ I = \int_{-1}^1 \dfrac {dx}{3x^2 + 2x + 3} $$
Complete the square in the integrand's denominator:
$$ I = \frac13 \int_{-1}^1 \dfrac {dx}{(x + 1/3)^2 + (8/9)} $$
Change variables again, to $x = -1/3 + (2\sqrt{2}/3) \tan y$ with limits of integration $y = - \arctan(1/\sqrt{2})$ and $y = \arctan(\sqrt{2})$.
$$ I = \frac{1}{2\sqrt{2}} \int_{-\arctan(1/\sqrt{2})}^{\arctan(\sqrt{2})} dy $$
giving
$$ I = \frac{1}{2\sqrt{2}} (\arctan(1/\sqrt{2}) + \arctan(\sqrt{2})) = \frac{\pi}{4\sqrt{2}} $$

 

[lpetrich]

Solution for Question 7:

Spoiler

Start with
$$ I = \int_1^5 \dfrac{dx}{\sqrt{x^2+3x-4}} $$
The argument of the square root is $(x^2 + 3x - 4) = (x-1)(x+4) = (x+(3/2))^2 - (5/2)^2$. This suggests a change of variables: $x = -(3/2) + (5/2)\cosh y$ with limits of integration $y = \text{arccosh} \,1 = 0$ and $y = \text{arccosh} (13/5)$. The argument of the square root becomes $(5/2)^2 \sinh^2 y$, the differential becomes $(5/2) \sinh y$, and we find
$$ I = \int_0^{\text{arccosh}(13/5)} dy = \text{arccosh} \frac{13}{5} = \log
\left(\frac{13}{5} + \frac{12}{5}\right) = \log 5 $$
using $\text{arccosh} \, x = \log(x + \sqrt{x^2-1})$.

 

[fresh_42]

Solution for Question 4:

Spoiler

The path interval of vector $V = \{V_x, V_y\}$ over $X = \{x,y\}$ with parameter $t$ is:
$$ I = \int V \cdot dX = \int V \cdot \frac{dX}{dt} dt $$
The vectors are $u = \{y, x-y\}$ and $v = \{y-x,-y\}$.
The curves of integration are
$$ \gamma_1 = \{\sin t, - \cos t\} \text{ for } t \in [0,\pi] \\
\gamma_2 = \{t,0\} \text{ for } t \in [-1,1] \text{ and } \{1-t,t\} \text{ for } t \in [0,1] $$
The integrals are:

• $(u,\gamma_1)$: $0$
• $(u,\gamma_2)$: $- \frac12$
• $(v,\gamma_1)$: $- \frac{\pi}{2}$
• $(v,\gamma_2)$: $- \frac12$

How much intermediate manipulation should I show?

If a vector field $V$ has potential $P$, then $V = \nabla P = \{\frac{\partial P}{\partial x}, \frac{\partial P}{\partial y} \}$. It is easy to show that this results in the field's curl (asymmetrized gradient) vanishing, or in two dimensions, $\frac{\partial V_x}{\partial y} = \frac{\partial V_y}{\partial x}$. I'm not sure about the converse, that vanishing curl implies a potential. The path integral of $V$ is
$$ \int V \cdot dX = \int \nabla P \cdot dX = P $$
For $u$, we get $1 = 1$, and for $v$, we get $1 = 0$, So $v$ does not have a potential. For $u$, the potential is, from integration of each component,
$$P = xy + F(y) = xy - \frac12 y^2 + G(x) = xy - \frac12 y^2 + P_0 $$

Your results are correct. It's my fault that I had this typo. The two paths had been meant to start and end at the same points. However, since you haven't worked out the integrals, which I find you should have done for at least one of them for demonstration, we can turn this in an advantage and leave the corrected version for someone else who wants to do it.

The curl argument is correct, too. In the corrected version with two paths for the same connection, there is also an argument by the use of these paths.

So do me a favor and don't add your calculations, so that somebody else can still find the alternative reasoning and give us some explicit calculations.

 

[fresh_42]

Solution for Question 6:

Spoiler

Let
$$ I = \int_0^{\pi} \dfrac{\sin(\varphi)}{3\cos^2(\varphi)+2\cos(\varphi)+3}\,d\varphi $$
Change variables from $\varphi$ to $x = \cos\varphi$. The bounds of integration become $x = 1$ and $x = -1$ and the differential $dx = - \sin\varphi \, d\varphi$. With this change of variables, the integral becomes
$$ I = \int_{-1}^1 \dfrac {dx}{3x^2 + 2x + 3} $$
Complete the square in the integrand's denominator:
$$ I = \frac13 \int_{-1}^1 \dfrac {dx}{(x + 1/3)^2 + (8/9)} $$
Change variables again, to $x = -1/3 + (2\sqrt{2}/3) \tan y$ with limits of integration $y = - \arctan(1/\sqrt{2})$ and $y = \arctan(\sqrt{2})$.
$$ I = \frac{1}{2\sqrt{2}} \int_{-\arctan(1/\sqrt{2})}^{\arctan(\sqrt{2})} dy $$
giving
$$ I = \frac{1}{2\sqrt{2}} (\arctan(1/\sqrt{2}) + \arctan(\sqrt{2})) = \frac{\pi}{4\sqrt{2}} $$

Correct.

Another way to solve this integral is the Weierstraß or tangent half angle substitution.
Here we set $t := \tan\left(\frac{1}{2}\varphi \right)$and get
$$
\sin(\varphi)=\dfrac{2t}{1+t^2}\, , \,\cos(\varphi)=\dfrac{1-t^2}{1+t^2}\, , \,d\varphi = \dfrac{2}{1+t^2}\,dt
$$
which is often a nice way to turn trig functions into polynomials.

 

[fresh_42]

Solution for Question 7:

Spoiler

Start with
$$ I = \int_1^5 \dfrac{dx}{\sqrt{x^2+3x-4}} $$
The argument of the square root is $(x^2 + 3x - 4) = (x-1)(x+4) = (x+(3/2))^2 - (5/2)^2$. This suggests a change of variables: $x = -(3/2) + (5/2)\cosh y$ with limits of integration $y = \text{arccosh} \,1 = 0$ and $y = \text{arccosh} (13/5)$. The argument of the square root becomes $(5/2)^2 \sinh^2 y$, the differential becomes $(5/2) \sinh y$, and we find
$$ I = \int_0^{\text{arccosh}(13/5)} dy = \text{arccosh} \frac{13}{5} = \log
\left(\frac{13}{5} + \frac{12}{5}\right) = \log 5 $$
using $\text{arccosh} \, x = \log(x + \sqrt{x^2-1})$.

Also correct.

Here's another way: In this case we can make use of the Euler Substitution $\sqrt{x^2+3x-4}=(x+4)t$.

In order to solve this integral, we look at the zeros in the denominator which are $x=-4$ and $x=1\,.$ We choose the former and proceed by an Euler substitution: $\sqrt{x^2+3x-4}=\sqrt{(x+4)(x-1)}=(x+4)t\,.$ We then have
$$x=\dfrac{1+4t^2}{1-t^2}\; , \;\sqrt{x^2+3x-4}=\dfrac{5t}{1-t^2}\; , \;dx = \dfrac{10t}{(1-t^2)^2}\,dt$$

 

[lpetrich]

Solution for Question 2: (mistake discovered in one of the sums. Solution removed until it can be corrected)

 

[fresh_42]

Solution for Question 2: (mistake discovered in one of the sums. Solution removed until it can be corrected)

Thanks.

 

[lpetrich]

My would-be solution for Question 2. I'm posting it here for reference in case the original question statement had had a typo in a certain place.

Spoiler

We start with
$$ S = \sum_{k=0}^\infty \sum_{m=0}^k \dfrac{\sqrt{5}^m}{m!}\cdot \left(\dfrac{(2k)!}{k!}\right)^2 \dfrac{2^{-6k-2}}{(2k-m+1)!} $$
The second sum is over 0 to k, and I don't know if that was intended or not. If it was a typo for (2k+1), then my would-be solution will work. Here is that would-be solution:

The sums are a sum over k of a sum over m, so I rearrange $S$ so that the k-only terms are outside the m terms:
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} k! k!} \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
The sum over m is rather obviously a binomial-theorem expansion:
$$ \dfrac{(1+\sqrt{5})^{2k+1}}{(2k+1)!} = \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
This gives us
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} (2k+1)! k! k!} (1+\sqrt{5})^{2k+1} =
\sum_{k=0}^\infty \dfrac{(2k)!}{2^{6k+2} (2k+1) k! k!} (1+\sqrt{5})^{2k+1} $$
This can be found with a generalization of the binomial theorem:
$$ (1+x)^a = 1 + a x + \dfrac{a(a-1}{2!} x^2 + \dfrac{a(a-1)(a-2)}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{\Gamma(a+k)}{\Gamma(a) k!} x^k $$
using the Euler gamma function. Take a = -1/2 and reverse the sign of x:
$$ \dfrac{1}{\sqrt{1-x}} = 1 + (1/2) x + \dfrac{1/2 \cdot 3/2}{2!} x^2 + \dfrac {1/2 \cdot 3/2 \cdot 5/2}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} k! k!} x^k $$
Taking the square of x and integrating gives us
$$ \int \dfrac{dx}{\sqrt{1-x^2}} = \arcsin x = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} (2k+1) k! k!} x^{2k+1} $$
To get $S$, we set $x = (1 + \sqrt{5})/4$, giving $x^{2k+1} = (1 + \sqrt{5})^{2k+1}/2^{4k+2}$, and
$$ S = \arcsin \dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \arccos\dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \frac{\pi}{5} = \frac{3}{10} \pi $$

I will prove that $\cos (\pi/5) = (1 + \sqrt{5})/4$. From trigonometric addition identities, it is easy to show that $\cos (5x) = 16 \cos^5 x - 20 \cos^3 x + 5 \cos x$. For $x = \pi/5$ and $\cos (\pi/5) = w$, we find $-1 = 16w^5 - 20w^3 + 5w$. Adding 1 to both sides and factoring gives us $(w+1) ( 4w^2 - 2w - 1)^2 = 0$. The first factor gives a trivial solution, while the second factor gives us $w = (1 \pm \sqrt{5})/4$. One can then find which solution corresponds to $\cos (\pi/5)$ by numerical evaluation. Though not exact, the error bars for this numerical evaluation can easily be made much less than the difference between the solutions. Like with IEEE 754 floating-point numbers, the standard for most hardware floating-point numbers.

 

[fresh_42]

My would-be solution for Question 2. I'm posting it here for reference in case the original question statement had had a typo in a certain place.

Spoiler

We start with
$$ S = \sum_{k=0}^\infty \sum_{m=0}^k \dfrac{\sqrt{5}^m}{m!}\cdot \left(\dfrac{(2k)!}{k!}\right)^2 \dfrac{2^{-6k-2}}{(2k-m+1)!} $$
The second sum is over 0 to k, and I don't know if that was intended or not. If it was a typo for (2k+1), then my would-be solution will work. Here is that would-be solution:

The sums are a sum over k of a sum over m, so I rearrange $S$ so that the k-only terms are outside the m terms:
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} k! k!} \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
The sum over m is rather obviously a binomial-theorem expansion:
$$ \dfrac{(1+\sqrt{5})^{2k+1}}{(2k+1)!} = \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
This gives us
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} (2k+1)! k! k!} (1+\sqrt{5})^{2k+1} =
\sum_{k=0}^\infty \dfrac{(2k)!}{2^{6k+2} (2k+1) k! k!} (1+\sqrt{5})^{2k+1} $$
This can be found with a generalization of the binomial theorem:
$$ (1+x)^a = 1 + a x + \dfrac{a(a-1}{2!} x^2 + \dfrac{a(a-1)(a-2)}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{\Gamma(a+k)}{\Gamma(a) k!} x^k $$
using the Euler gamma function. Take a = -1/2 and reverse the sign of x:
$$ \dfrac{1}{\sqrt{1-x}} = 1 + (1/2) x + \dfrac{1/2 \cdot 3/2}{2!} x^2 + \dfrac {1/2 \cdot 3/2 \cdot 5/2}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} k! k!} x^k $$
Taking the square of x and integrating gives us
$$ \int \dfrac{dx}{\sqrt{1-x^2}} = \arcsin x = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} (2k+1) k! k!} x^{2k+1} $$
To get $S$, we set $x = (1 + \sqrt{5})/4$, giving $x^{2k+1} = (1 + \sqrt{5})^{2k+1}/2^{4k+2}$, and
$$ S = \arcsin \dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \arccos\dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \frac{\pi}{5} = \frac{3}{10} \pi $$

I will prove that $\cos (\pi/5) = (1 + \sqrt{5})/4$. From trigonometric addition identities, it is easy to show that $\cos (5x) = 16 \cos^5 x - 20 \cos^3 x + 5 \cos x$. For $x = \pi/5$ and $\cos (\pi/5) = w$, we find $-1 = 16w^5 - 20w^3 + 5w$. Adding 1 to both sides and factoring gives us $(w+1) ( 4w^2 - 2w - 1)^2 = 0$. The first factor gives a trivial solution, while the second factor gives us $w = (1 \pm \sqrt{5})/4$. One can then find which solution corresponds to $\cos (\pi/5)$ by numerical evaluation. Though not exact, the error bars for this numerical evaluation can easily be made much less than the difference between the solutions. Like with IEEE 754 floating-point numbers, the standard for most hardware floating-point numbers.

Yes, you are right, the upper summation index had been wrong and although you copied the error, your solution is the one of the corrected version. This special problem has been shifted from month to month that I couldn't find the original anymore. I think it was either a copy error of mine or a sloppy Wikipedia entry. Nevertheless, the result is correct and I appreciate your effort for $\operatorname{arccos}\left( \dfrac{1+\sqrt{5}}{4} \right)= \dfrac{\pi}{5}$. Btw., nice work to show the series expansions of $\operatorname{arcsin}$, $\operatorname{arccos}$, resp.

 

[lpetrich]

Solution for Question 3:

Spoiler

Consider Pythagorean triples {x, y, z}, positive integers satisfying $x^2 + y^2 = z^2$. Is their product P = $x y z$ divisible by 60?

From Pythagorean triple - Wikipedia, every Pythagorean triple is given by
$$ x = k \cdot (m^2 - n^2) ,\ y = k \cdot (2mn) ,\ z = k \cdot (m^2 + n^2) $$
where k is a positive integer, and m and n are two coprime integers with one of them even, one of them odd. The article also contains a proof of that theorem.

From this formula, $P = k^3 (2mn (m^4 - n^4))$. Since the divisibility must be true for all $k$, it must be true for $k = 1$, so I use that restriction: $P = 2mn (m^4 - n^4)$.

Since one of m and n must be even, this means that P must be divisible by 2*2 = 4.

For higher primes p, I set the even one of m and n to $2(pa+s)$ and the odd one to $(pb+t)$ where a and b are nonnegative integers and s and t are nonnegative integers that range between 0 and p-1. I then checked on whether P is divisible by p for each value of s and t. That is the case for 3 and 5, but not for any of the other primes that I tested. The highest one I tested was the 100th one, 541, and Mathematica got bogged down there.

So I find that P is always divisible by a number that is at least 4*3*5 = 60. I will now look for an upper limit for the always-divisible number. For that, I use the smallest Pythagorean triple, {3,4,5}. Its product is 60. So 60 is the largest number that divides every Pythagorean-triple product.

 

[fresh_42]

Solution for Question 3:

Consider Pythagorean triples {x, y, z}, positive integers satisfying $x^2 + y^2 = z^2$. Is their product P = $x y z$ divisible by 60?

From Pythagorean triple - Wikipedia, every Pythagorean triple is given by
$$ x = k \cdot (m^2 - n^2) ,\ y = k \cdot (2mn) ,\ z = k \cdot (m^2 + n^2) $$
where k is a positive integer, and m and n are two coprime integers with one of them even, one of them odd. The article also contains a proof of that theorem.

From this formula, $P = k^3 (2mn (m^4 - n^4))$. Since the divisibility must be true for all $k$, it must be true for $k = 1$, so I use that restriction: $P = 2mn (m^4 - n^4)$.

Since one of m and n must be even, this means that P must be divisible by 2*2 = 4.

Why can you (still) assume this? In the original Wiki version a factor $2$ could have been shifted into $k$, but as you set $k=1$ you need a different argument.

For higher primes p, I set the even one of m and n to $2(pa+s)$ and the odd one to $(pb+t)$ ...

Ehm, what?
Did you mean: "Let $m=2(pa+s)$ be even and $n=pb+t$ odd."?

... where a and b are nonnegative integers and s and t are nonnegative integers that range between 0 and p-1. I then checked on whether P is divisible by p for each value of s and t.

Where?

That is the case for 3 and 5, but not for any of the other primes that I tested. The highest one I tested was the 100th one, 541, and Mathematica got bogged down there.

So I find that P is always divisible by a number that is at least 4*3*5 = 60. I will now look for an upper limit for the always-divisible number. For that, I use the smallest Pythagorean triple, {3,4,5}. Its product is 60. So 60 is the largest number that divides every Pythagorean-triple product.

The proof as it stands has flaws, and as I mentioned, that this is an easy question, even without the Wikipedia theorem, all used properties should be explicitly mentioned. You don't need to test any primes, only $2^2,3,5$ are stated.

 

[lpetrich]

I will try Question 3 again.

Spoiler

Statement of the problem. A Pythagorean triplet is a triplet of positive integers $(x,y,z)$ that satisfies the Pythagorean equation $x^2 + y^2 = z^2$. Consider the product of the members of a Pythagorean triplet $P = x y z$. What is their greatest common denominator D?

Upper limit. An upper limit on D comes from the smallest possible value of P. The smallest Pythagorean triplet is (3,4,5), and its P value = 60. Thus, D must evenly divide 60.

Divisor-product theorem. This theorem greatly simplifies the proof, since it is much easier to find some relatively-prime divisors of D than D itself. In particular, we need only check 4, 3, and 5, because they are relatively prime, and because their product is the upper limit on D found earlier.

The theorem: for positive integers a, b, x, and for a and b being relatively prime, if $a | x$ and $b | x$ then $ab | x$ (the | means "evenly divides"). Proof: The first divisibility, $a | x$, implies $x = ay$ for some positive-integer y. The second divisibility involves dividing by b, and since a is not divisible by b, y must be: $y = bz$ for some positive-integer z. Thus, $x = a(bz) = (ab)z$ thus proving the theorem.

In the next parts, I use modular arithmetic, and that is justified by $a | x$ being equivalent to $x \mod a = 0$. I use modular arithmetic because of its greater compactness of notation: 1 mod 2 instead of (2n+1).

Divisor 4. I start out with the prime factor, and I do modulo 2. The triplet members are either 0 or 1, and the squares of them are likewise either 0 or 1. There are only four possible combinations that satisfy the Pythagorean equation:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 mod 2

Thus, a Pythagorean triplet contains either three even numbers or one even number and two odd numbers. For all even numbers, one can divide out 2: $x = 2x', y = 2y', z = 2z'$. This process can be repeated until at least one triplet member is odd. Thus, (all even) = (2 to some power) * (one even, two odd). That means that we only have to do the case of one even, two odd, since its results will also hold for the all-even case.

Looking for further constraints, I multiply the modulus by 2, and do modulo 4. The even one is either 0 or 2, and the odd ones either 1 or 3. The even one's square is always 0, and the odd ones' squares are always 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 4

The remaining one would give 1 + 1 = 0 mod 4. That means that of (x,y,z), z is always odd and x and y are one even, one odd.

Looking even further, I multiply the modulus by 2 again, and do modulo 8. The even one is 0, 2, 4, or 6, and its squares are 0 or 4. The odd ones are 1, 3, 5, 7, and 9, and their squares are all 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 8

The remaining ones would give 4 + 1 = 1, 1 + 4 = 1 mod 8. The even one is thus 0 or 4 mod 8, meaning that the even one is always divisible by 4. So one of x and y is divisible by 4 and the other one is odd. Also, z is odd.

This means that product P is always divisible by 4.

Divisor 3. I do modulo 3 here. The triplet members are 0, 1, or 2, and their squares are 0, 1, or 1. The only possible combinations are:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 mod 3

So (1) all three of x, y, and z are divisible by 3, or (2) one of x and y is divisible by 3 and the other one is not. Also, z is not divisible by 3.

This means that product P is always divisible by 3.

Divisor 5. I do modulo 5 here. The triplet members are 0, 1, 2, 3, or 4, and their squares are 0, 1, 4, 4, or 1. The only possible combinations are:

0 + 0 = 0, 1 + 4 = 0, 4 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1, 4 + 0 = 4, 0 + 4 = 4 mod 5

Thus, either one of x, y, and z, or else all three of them, are divisible by 5.

This means that product P is always divisible by 5.

Combined Divisor. Using the divisor-product theoream gives $4 \cdot 3 \cdot 5 = 60$, the maximum value found earlier for D, the GCD of the P's. Thus, D = 60, the result that we wanted to prove.

 

[fresh_42]

I will try Question 3 again.

Statement of the problem. A Pythagorean triplet is a triplet of positive integers $(x,y,z)$ that satisfies the Pythagorean equation $x^2 + y^2 = z^2$. Consider the product of the members of a Pythagorean triplet $P = x y z$. What is their greatest common denominator D?

Upper limit. An upper limit on D comes from the smallest possible value of P. The smallest Pythagorean triplet is (3,4,5), and its P value = 60. Thus, D must evenly divide 60.

Divisor-product theorem. This theorem greatly simplifies the proof, since it is much easier to find some relatively-prime divisors of D than D itself. In particular, we need only check 4, 3, and 5, because they are relatively prime, and because their product is the upper limit on D found earlier.

The theorem: for positive integers a, b, x, and for a and b being relatively prime, if $a | x$ and $b | x$ then $ab | x$ (the | means "evenly divides"). Proof: The first divisibility, $a | x$, implies $x = ay$ for some positive-integer y. The second divisibility involves dividing by b, and since a is not divisible by b, y must be:

This is true but not as obvious as you suggest. You used a property which prime numbers have, but you only have coprime numbers. Since we're all used to integers, this indeed appears obvious. However, in general, i.e. for other rings, this cannot be concluded in this way. E.g. it looks as if you implicitly used the unique factorization theorem, which in arbitrary rings isn't available. Maybe you had another proof in mind, but as you didn't write it, I cannot know.

$y = bz$ for some positive-integer z. Thus, $x = a(bz) = (ab)z$ thus proving the theorem.

In the next parts, I use modular arithmetic, and that is justified by $a | x$ being equivalent to $x \mod a = 0$. I use modular arithmetic because of its greater compactness of notation: 1 mod 2 instead of (2n+1).

Divisor 4. I start out with the prime factor, and I do modulo 2. The triplet members are either 0 or 1, and the squares of them are likewise either 0 or 1. There are only four possible combinations that satisfy the Pythagorean equation:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 mod 2

Thus, a Pythagorean triplet contains either three even numbers or one even number and two odd numbers. For all even numbers, one can divide out 2: $x = 2x', y = 2y', z = 2z'$. This process can be repeated until at least one triplet member is odd. Thus, (all even) = (2 to some power) * (one even, two odd). That means that we only have to do the case of one even, two odd, since its results will also hold for the all-even case.

Looking for further constraints, I multiply the modulus by 2, and do modulo 4. The even one is either 0 or 2, and the odd ones either 1 or 3.

Why? $3$ is odd and $2\cdot 3 = 6 = 2 \,\operatorname{mod}4\,.$ If you had squared it first, then $(2n+1)^2=1\,\operatorname{mod}4$ but you haven't. Squaring first does the job, because odd numbers squared have a remainder one modulo four, which also excludes the case $1+1=0 \,(2)$ since even numbers squared are divisible by four and $1+1\neq 0\,(4)\,.$

The even one's square is always 0,...

I can't follow you anymore. If you multiply by $2$, which you did, your equation becomes $2x^2+2y^2=2z^2$ which isn't Pythagorean anymore. So how can you still reason with squares? The same argument applies to the next step. Maybe I don't see what you meant, but that's the price you pay if you put a distance between your arguments and your equation by modulo.

... and the odd ones' squares are always 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 4

The remaining one would give 1 + 1 = 0 mod 4. That means that of (x,y,z), z is always odd and x and y are one even, one odd.

From here on I have difficulties to follow you. Up to now you have (with the corrections above) w.l.o.g. $x=2u\; , \;y=2v+1\; , \;z=2w+1$ and $y^2=z^2=1\,\operatorname{mod}(2),(4)$.

Looking even further, I multiply the modulus by 2 again, and do modulo 8.

Now what exactly do you multiply by two? The remainders so far, then you have no squares anymore. The entire equation $x^2+y^2=z^2$, then you have no squares anymore. The single numbers $x,y,z$, then you made them divisible by four.

The even one is 0, 2, 4, or 6, and its squares are 0 or 4. The odd ones are 1, 3, 5, 7, and 9, and their squares are all 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 8

The remaining ones would give 4 + 1 = 1, 1 + 4 = 1 mod 8. The even one is thus 0 or 4 mod 8, meaning that the even one is always divisible by 4. So one of x and y is divisible by 4 and the other one is odd. Also, z is odd.

This means that product P is always divisible by 4.

Divisor 3. I do modulo 3 here. The triplet members are 0, 1, or 2, and their squares are 0, 1, or 1. The only possible combinations are:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 mod 3

So (1) all three of x, y, and z are divisible by 3, or (2) one of x and y is divisible by 3 and the other one is not. Also, z is not divisible by 3.

This means that product P is always divisible by 3.

Divisor 5. I do modulo 5 here. The triplet members are 0, 1, 2, 3, or 4, and their squares are 0, 1, 4, 4, or 1. The only possible combinations are:

0 + 0 = 0, 1 + 4 = 0, 4 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1, 4 + 0 = 4, 0 + 4 = 4 mod 5

Thus, either one of x, y, and z, or else all three of them, are divisible by 5.

This means that product P is always divisible by 5.

Combined Divisor. Using the divisor-product theoream gives $4 \cdot 3 \cdot 5 = 60$, the maximum value found earlier for D, the GCD of the P's. Thus, D = 60, the result that we wanted to prove.

The cases $3$ and $5$ are correct. The case $4$ is sloppy at least, or I don't see it. This is by the way the only case, the representation $x=u^2-v^2\, , \,y=u^2+v^2\, , \,z=2uv$ does a good job, since only $2\,|\,uv(u-v)(u+v)(u^2+v^2)$ will be left to show.

Maybe, I'm too stupid to follow your arguments, but $0+1=1$ is simply to few information to actually see anything.

 

[nuuskur]

I'll try question 3, looks like something that can be given the ol' modular arithmetic treatment.

Spoiler: Problem 3

Let positive integers $x,y,z$ satisfy $x^2+y^2 = z^2$. We will show $60\mid xyz$.
To this end it suffices to show $k\mid xyz$ where $k=3,4,5$. It then stands that the least common multiple (which is $60$) divides the product.

The following is implied by (a.k.a addition in $Z_n$)
$$x\equiv a\pmod{n}\ \&\ y\equiv b\pmod{n} \implies x+y\equiv a+b\pmod{n}.$$

1. It holds that $x$ or $y$ is a multiple of $3$. Indeed, we have
$$(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2+2k)+1\quad\mbox{and}\quad (3k+2)^2 = 9k^2 + 12k +4 = 3(3k^2 + 4k +1) +1$$
Assuming neither is a multiple of $3$ would mean $z^2\equiv 2\pmod{3}$ which contradicts the above.

2. At least one factor is divisible by $4$. We can parametrise
$$x = p^2-q^2\quad y = 2pq\quad z = p^2+q^2,$$
with $(p,q)=1$. If $p$ or $q$ is even, we're done. Suppose they are both odd. The square of an odd number is of the form $4m+1$ yielding $p^2-q^2 \equiv 0\pmod{4}$.3. At least one factor is divisible by $5$. Possible squares modulo $5$ are $0,1,4$. If none of the factors is a multiple of $5$ then the possibilities for $x^2+y^2-z^2\pmod{5}$ include (up to commutativity)
$$1+1-1 =1\quad 1+1-4 = 3\quad 1+4-1 = 4\quad 1+4-4 =1\quad 4+4-1 = 2\quad 4+4-4 = 4\quad$$
none of which is $0$, contradicting the initial equality.

 

[nuuskur]

For question $5$ I don't understand the construction. I'd recognise something like $R[x] / \langle m(x) \rangle$ where the quotient is taken w.r.t the ideal generated by $m$. But what is $Z[x] / \langle m(x), n \rangle$? What is the meaning of the parameter $n$? What sort of ideal is that?

Ah it's a constant polynomial!

 

[fresh_42]

For question $5$ I don't understand the construction. I'd recognise something like $R[x] / \langle m(x) \rangle$ where the quotient is taken w.r.t the ideal generated by $m$. But what is $Z[x] / \langle m(x), n \rangle$? What is the meaning of the second parameter? What sort of ideal is that?

$\langle a,b \rangle \subseteq R$ means the ideal generated by $a$ and $b$, so (since $R$ is Abelian here): $\langle a,b \rangle =Ra+Rb\,.$ It's simply not a principal ideal, but one generated by two elements. For a non Abelian ring it would be $\langle a,b \rangle =RaR+RbR\,.$

 

[fresh_42]

I'll try question 3, looks like something that can be given the ol' modular arithmetic treatment.

Spoiler: Problem 3

Let positive integers $x,y,z$ satisfy $x^2+y^2 = z^2$. We will show $60\mid xyz$.
To this end it suffices to show $k\mid xyz$ where $k=3,4,5$. It then stands that the least common multiple (which is $60$) divides the product.

The following is implied by (a.k.a addition in $Z_n$)
$$x\equiv a\pmod{n}\ \&\ y\equiv b\pmod{n} \implies x+y\equiv a+b\pmod{n}.$$

1. It holds that $x$ or $y$ is a multiple of $3$. Indeed, we have
$$(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2+2k)+1\quad\mbox{and}\quad (3k+2)^2 = 9k^2 + 12k +4 = 3(3k^2 + 4k +1) +1$$
Assuming neither is a multiple of $3$ would mean $z^2\equiv 2\pmod{3}$ which contradicts the above.

2. At least one factor is divisible by $4$. We can parametrise
$$x = p^2-q^2\quad y = 2pq\quad z = p^2+q^2,$$
with $(p,q)=1$. If $p$ or $q$ is even, we're done. Suppose they are both odd. The square of an odd number is of the form $4m+1$ yielding $p^2-q^2 \equiv 0\pmod{4}$.3. At least one factor is divisible by $5$. Possible squares modulo $5$ are $0,1,4$. If none of the factors is a multiple of $5$ then the possibilities for $x^2+y^2-z^2\pmod{5}$ include (up to commutativity)
$$1+1-1 =1\quad 1+1-4 = 3\quad 1+4-1 = 4\quad 1+4-4 =1\quad 4+4-1 = 2\quad 4+4-4 = 4\quad$$
none of which is $0$, contradicting the initial equality.

Well written as on the points. However, I would have liked to read, that for $4\,|\,xyz$ you used the fact that $2$ is prime.

 

[nuuskur]

Spoiler: Problem 5

It holds that $Z[x] / \langle p\rangle \cong Z_p[x]$. This is due to the first isomorphism theorem for rings. Indeed, the mapping $Z[x]\to Z_p[x],\quad \sum _{n} c_n x^n \mapsto \sum _{n} [c_n] x^n$ is a surjective ring homomorphism annihilated by $\langle p\rangle$.

So, we're left to show $Z_5[x] / \langle x^2+2x+4 \rangle \cong Z_5[4+\sqrt{2}]$. Computing modulo $x^2+2x+4$ we get 25? cosets of the form $[ax + b] , a,b\in Z_5$. Addition and multiplication work modulo 5 as follows
$$[ax+b] + [mx+n] = [(a+m)x + (b+n)]\quad\mbox{and}\quad [ax+b][mx+n] = [(ax+b)(mx+n)] = [ux+v],$$
where for multiplication one performs long division to determine the coset of the product.

On the other side we got $Z_5[4+\sqrt{2}] = \{a+b(4+\sqrt{2}) \mid a,b\in Z_5\}$. Also 25 elements, so this leads to a rather natural looking bijection
$$\varphi : Z_5[x] / \langle x^2+2x+4 \rangle \to Z_5[4+\sqrt{2}],\quad [ax + b] \mapsto b + a(4+\sqrt{2}).$$
Firstly $\varphi ([0x +1]) = 1$ so $\varphi$ preserves the multiplicative identity. Furthermore
$$\varphi ([ax+b] + [mx+n]) = b+n + (a+m)(4+\sqrt{2}) = \varphi ([ax+b]) + \varphi ([mx+n])$$
Compatibility with multiplication is not so obvious or downright false. To be continued...

 

[fresh_42]

Spoiler: Problem 5

It holds that $Z[x] / \langle p\rangle \cong Z_p[x]$. This is due to the first isomorphism theorem for rings. Indeed, the mapping $Z[x]\to Z_p[x],\quad \sum _{n} c_n x^n \mapsto \sum _{n} [c_n] x^n$ is a surjective ring homomorphism annihilated by $\langle p\rangle$.

So, we're left to show $Z_5[x] / \langle x^2+2x+4 \rangle \cong Z_5[4+\sqrt{2}]$.

Spoiler: Problem 5

No. You have shown $\mathbb{Z}_5[x] \cong \mathbb{Z}[x]/5\mathbb{Z}[x]$, but the argument, why this passes to the quotients $\mathbb{Z}_5[x]/\langle m(x) \rangle \cong \mathbb{Z}[x]/(5\mathbb{Z}[x]+m(x)\mathbb{Z}[x])$ with $m(x):=x^2+2x+4$ is missing.

I think you should at least note that $\xi := 4+\sqrt{2} \notin \mathbb{Z}_5$ because this is important here, and that $\overline{m}(x):=x^2+2x+4 \in \mathbb{Z}_5[x]$ is the minimal polynomial of $\xi$. As stated before, not everybody is firm in ring theory.

Computing modulo $x^2+2x+4$ we get 25? cosets of the form $[ax + b] , a,b\in Z_5$

On the other side we got $Z_5[4+\sqrt{2}] = \{a+b(4+\sqrt{2}) \mid a,b\in Z_5\}$. Also 25 elements, so this leads to a rather natural looking bijection
$$\varphi : Z_5[x] / \langle x^2+2x+4 \rangle \to Z_5[4+\sqrt{2}],\quad [ax + b] \mapsto b + a(4+\sqrt{2}).$$

to be continued, I have to power off

 

[nuuskur]

@fresh_42, you're right the handwavy argument for the initial isomorphism for quotients doesn't quite work.

uh oh, can't edit my last post. At any rate I dusted off some of my ring theory..
it's still a bit handwavy (I omit routine checks), but I did break down the more interesting points

Spoiler: Problem 5, take 2

Will often make use of the so called first isomorphism theorem for rings (FITR). Namely the following part.
Given rings $R,Q$ and a surjective homomorphism of rings $\varphi : R\to Q$. It holds that $R/\mbox{ker}\varphi \cong Q$.

Denote $x^2+2x+4 =: g(x)$.
First, we'll show $Z[x] / \langle g(x) , p \rangle \cong Z_p[x] / \langle g(x) \rangle$.
Given ring $R$ and two ideals $I,J\trianglelefteq R$ it holds that $I+J$ is also an ideal and (more importantly) $R / (I+J) \cong (R/I) / [J]$ , where $[J] := \{a + I \mid a\in J\}\trianglelefteq R/I$ is an ideal. Define $\varphi:R \to (R/I) / [J],\quad r \mapsto (r+I) + [J]$, which is a surjective homomorphism of rings. Its kernel is $I+J$. Now apply FITR.
With that we have
$$Z[x] /\langle g(x), 5\rangle :=Z[x] / (g(x)Z[x] + 5Z[x]) \cong Z_5[x] / g(x)Z_5[x]$$
-------------------------------------------------------------------------------------------------------------
Given field $F$ and its subfield $K$, it holds that if $\beta\in F$ is algebraic over $K$ (i.e there is a polynomial in $K[x]$ whose root is $\beta$) with minimal polynomial $m(x)$ (if there is one such polynomial, we can certainly pick a minimal one), then $K[x] / \langle m(x) \rangle \cong K[\beta]$.
Indeed, define $\varphi :K[x]\to K[\beta],\quad f\mapsto f(\beta)$. Technically, there is a potential well-definedness issue here i.e $f(\beta) = \sum _n c_n \beta ^n \overset{?}\in K[\beta]$, but the powers of $\beta$ span the $K$-vector space $K[\beta]$, so that's ok. The degree of minimal polynomial determines the dimension of the vector space.

The mapping $\varphi$ is a surjective homomorphism of rings. We need to show its kernel is precisely $\langle m(x)\rangle$, where $\langle m(x)\rangle \subseteq \mbox{ker}\varphi$ is clear. Conversly, suppose $\varphi (f) = 0$ i.e $f(\beta) = 0$. Since $m$ is a minimal polynomial of $\beta$ it holds that $m\mid f$ thus $f\in \langle m(x)\rangle$. Now apply FITR.

Since $4+\sqrt{2} =: \beta\notin Z_5$ (there can be no linear polynomial in $Z_5[x]$ with root $\beta$) and $g(\beta) =0$, $g$ is a minimal polynomial of $\beta$, thus the isomorphism $Z_5[x] / \langle g(x)\rangle \cong Z_5[\beta]$.

 

[ISamson]

@fresh_42 @Greg Bernhardt . I (for my young age) find that these problems are very alien,difficult to me, as I am only in year 8 :) . However, I would really enjoy to take part in a similar challenge, but much easier, like a high school level, however still challenging and interesting for such age. I would propose some type of advanced logic problem, or something with patterns and numbers.
If such possibility is real, I am in. What do you think?

 

[pbuk]

Problem 9 only needs high school maths.

Spoiler: Problem 9

If the distance from the centre of the pond to the edge is $r$, half the distance around the pond is given by $\pi r$ where the constant $\pi$ is a bit more than 3.1.

This, plus an understanding of similar triangles (if you stretch a triangle without changing its shape until one side is 4x longer than it started, all the sides are 4x longer than they started).

 

[nuuskur]

I initially thought P9 to be triangle-solvable, but she doesn't have to swim in a straight line, does she? I haven't looked at the problem in depth, perhaps a winning strategy with involving only straight lines exists for the girl.

 

[Dewgale]

Spoiler: Problem 10 Solution

Let us assume that x and y are independent variables. Given the function
$$ f(x,y) = x(x-1)^2 - 2y^2 $$
the critical points are given by setting the gradient of the function equal to zero. The gradient is given by
$$ \nabla f(x,y) = (x-1)(3x-1)\hat{x} + 4y \hat{y} $$
Setting each component equal to zero, it is clear that $y = 0$ and $x = 1/3, \, 1$. This therefore gives two critical points: $C_1 = (1/3, 0)$ and $C_2 = (1,0)$.

The second derivative of the function with respect to $y$ is given by
$$ f_{yy}(x,y) = -4 $$
The second derivative of the function with respect to $x$ is given by
$$ f_{xx}(x,y) = 6x - 4 $$
We can immediately see that $f_{xx}(1,0) = 2$ and $f_{xx}(1/3,0) = -2$ - both non-zero. However, the concavity of $C_1$ is the same in $x$ and $y$: it is a maximum. The concavities differ at $C_2$, so it is a saddle point, not an extremum.

Finally, to determine if it is a global extremum, we can simply determine that the value of the function at $C_1$ is $f(1/3,0)= 4/27$, and show that $f(\infty,0) = \infty$: clearly, $C_1$ is not a global maximum, and no other extrema exist. Therefore, there are no global extrema.

 

[Danny Sleator]

Spoiler: Solution to problem 9 (Princess)

The princess can escape as follows. Assume WLOG that the radius of the pond is $1$. The princess goes to a point that is $r=.24$ from the center of the pond. Then she swims clockwise at radius $r$ at her maximum velocity until she is opposite the witch. (Since her angular velocity is higher than that of the witch she must reach such a point by the intermediate value theorem.)

Now the princess's distance to the closest point to her, $X$, at the edge of the pond is $.76$. Meanwhile the witch's distance to $X$ (going round the pond) is $\pi > 4 * .76$. Therefore the princess can escape simply by swimming to $X$. voila'

Note that this solution does not use the 2nd assumption $--$ namely that the witch stays as close as possible to the princess. The solution works for any witch strategy. Also, the solution works as long as the ratio of witch velocity over princess velocity is $< \pi +1$. If the ratio is $\pi+1$ or higher, is it impossible for the princess to escape?

 

[fresh_42]

@fresh_42, you're right the handwavy argument for the initial isomorphism for quotients doesn't quite work.

uh oh, can't edit my last post. At any rate I dusted off some of my ring theory..
it's still a bit handwavy (I omit routine checks), but I did break down the more interesting points

Spoiler: Problem 5, take 2

Will often make use of the so called first isomorphism theorem for rings (FITR). Namely the following part.
Given rings $R,Q$ and a surjective homomorphism of rings $\varphi : R\to Q$. It holds that $R/\mbox{ker}\varphi \cong Q$.

Denote $x^2+2x+4 =: g(x)$.
First, we'll show $Z[x] / \langle g(x) , p \rangle \cong Z_p[x] / \langle g(x) \rangle$.
Given ring $R$ and two ideals $I,J\trianglelefteq R$ it holds that $I+J$ is also an ideal and (more importantly) $R / (I+J) \cong (R/I) / [J]$ , where $[J] := \{a + I \mid a\in J\}\trianglelefteq R/I$ is an ideal. Define $\varphi:R \to (R/I) / [J],\quad r \mapsto (r+I) + [J]$, which is a surjective homomorphism of rings. Its kernel is $I+J$. Now apply FITR.
With that we have
$$Z[x] /\langle g(x), 5\rangle :=Z[x] / (g(x)Z[x] + 5Z[x]) \cong Z_5[x] / g(x)Z_5[x]$$
-------------------------------------------------------------------------------------------------------------
Given field $F$ and its subfield $K$, it holds that if $\beta\in F$ is algebraic over $K$ (i.e there is a polynomial in $K[x]$ whose root is $\beta$) with minimal polynomial $m(x)$ (if there is one such polynomial, we can certainly pick a minimal one), then $K[x] / \langle m(x) \rangle \cong K[\beta]$.
Indeed, define $\varphi :K[x]\to K[\beta],\quad f\mapsto f(\beta)$. Technically, there is a potential well-definedness issue here i.e $f(\beta) = \sum _n c_n \beta ^n \overset{?}\in K[\beta]$, but the powers of $\beta$ span the $K$-vector space $K[\beta]$, so that's ok. The degree of minimal polynomial determines the dimension of the vector space.

The mapping $\varphi$ is a surjective homomorphism of rings. We need to show its kernel is precisely $\langle m(x)\rangle$, where $\langle m(x)\rangle \subseteq \mbox{ker}\varphi$ is clear. Conversly, suppose $\varphi (f) = 0$ i.e $f(\beta) = 0$. Since $m$ is a minimal polynomial of $\beta$ it holds that $m\mid f$ thus $f\in \langle m(x)\rangle$. Now apply FITR.

Since $4+\sqrt{2} =: \beta\notin Z_5$ (there can be no linear polynomial in $Z_5[x]$ with root $\beta$) and $g(\beta) =0$, $g$ is a minimal polynomial of $\beta$, thus the isomorphism $Z_5[x] / \langle g(x)\rangle \cong Z_5[\beta]$.

I think a simple statement to use the second isomorphism theorem would have done it. (You used the first repeatedly, so why not the second?)
$$
\mathbb{Z}[x]/ \langle g(x)\; , \;5\rangle \cong (\mathbb{Z}[x]/5\mathbb{Z}[x])/(\langle g(x)\; , \;5 \rangle /5\mathbb{Z}[x]) \cong \mathbb{Z}_5[x]/\langle \overline{g}(x)\rangle
$$
where $\overline{g}(x)\in \mathbb{Z}_5[x]$ is $g(x)$ with reduced coefficients.

Now it remains to show that your isomorphism is one, although I used the opposite direction $\psi(\beta)=x$ but this is probably the same amount of work.

For all who don't know the theorems @nuuskur has used, e.g. $f(\beta)=0 \Longrightarrow g(x)\,|\,f(x)$, one can also simply calculate it.

Take $\psi\, : \,\mathbb{Z}_5[\beta] \longrightarrow \mathbb{Z}_5[x]/\langle x^2+2x+4 \rangle$ with $\psi(\beta)=x$ and show (surjectivity is given by construction)
a) (homomorphy) $\psi[(u\beta+v)(p\beta+q)]=\psi(u\beta+v)\psi(p\beta+q)$
b) (injectivity) $px+q = (ux+v)(x^2+2x+4) \Longrightarrow 5\,|\,px+q$

I mentioned this in case you were asking why this is a basic problem: it can be done step by step. And personally I think, this should be done step by step once or twice in order to understand what those theorems really mean.

 

[nuuskur]

Funny story with the isomorphism theorems. I avoided the 2nd theorem on purpose back when I was taking ring theory. I made it a challenge to myself to prove stuff without since it often felt kind of cheap. Whatever that means, it's a perfectly fine theorem and the implications are as good as any other.

 

[fresh_42]

@fresh_42 @Greg Bernhardt . I (for my young age) find that these problems are very alien,difficult to me, as I am only in year 8 :) . However, I would really enjoy to take part in a similar challenge, but much easier, like a high school level, however still challenging and interesting for such age. I would propose some type of advanced logic problem, or something with patterns and numbers.
If such possibility is real, I am in. What do you think?

We'd be pleased to offer such a challenge, but now comes the problem with it: How can we prevent all those undergraduates to solve them immediately? We have taken the "badge" criterion to give all others a head start, but how can we know, whether someone is really at school, yet?

 

[fresh_42]

Spoiler: Problem 10 Solution

Let us assume that x and y are independent variables. Given the function
$$ f(x,y) = x(x-1)^2 - 2y^2 $$
the critical points are given by setting the gradient of the function equal to zero. The gradient is given by
$$ \nabla f(x,y) = (x-1)(3x-1)\hat{x} + 4y \hat{y} $$
Setting each component equal to zero, it is clear that $y = 0$ and $x = 1/3, \, 1$. This therefore gives two critical points: $C_1 = (1/3, 0)$ and $C_2 = (1,0)$.

The second derivative of the function with respect to $y$ is given by
$$ f_{yy}(x,y) = -4 $$
The second derivative of the function with respect to $x$ is given by
$$ f_{xx}(x,y) = 6x - 4 $$
We can immediately see that $f_{xx}(1,0) = 2$ and $f_{xx}(1/3,0) = -2$ - both non-zero. However, the concavity of $C_1$ is the same in $x$ and $y$: it is a maximum. The concavities differ at $C_2$, so it is a saddle point, not an extremum.

Finally, to determine if it is a global extremum, we can simply determine that the value of the function at $C_1$ is $f(1/3,0)= 4/27$, and show that $f(\infty,0) = \infty$: clearly, $C_1$ is not a global maximum, and no other extrema exist. Therefore, there are no global extrema.

Correct. Just a remark:
A short defnition $C_1=(\frac{1}{3},0)\; , \;C_2=(1,0)$ would have been nice. The more as you used them in the opposite order, i.e. discussed $(1,0)$ first and $(\frac{1}{3},0)$ second before switching to $C_i\,.$

 

[fresh_42]

Spoiler: Solution to problem 9 (Princess)

The princess can escape as follows. Assume WLOG that the radius of the pond is $1$. The princess goes to a point that is $r=.24$ from the center of the pond. Then she swims clockwise at radius $r$ at her maximum velocity until she is opposite the witch. (Since her angular velocity is higher than that of the witch she must reach such a point by the intermediate value theorem.)

Now the princess's distance to the closest point to her, $X$, at the edge of the pond is $.76$. Meanwhile the witch's distance to $X$ (going round the pond) is $\pi > 4 * .76$. Therefore the princess can escape simply by swimming to $X$. voila'

Note that this solution does not use the 2nd assumption $--$ namely that the witch stays as close as possible to the princess. The solution works for any witch strategy. Also, the solution works as long as the ratio of witch velocity over princess velocity is $< \pi +1$. If the ratio is $\pi+1$ or higher, is it impossible for the princess to escape?

Correct.

And for all of you who have to deal with first year's physics practica here is the calculation:

We have to determine what the maximal radius of the girl's circle is (being still faster), and whether this will be sufficient to reach the shore in time. We must have with the radius $R$ of the lake
$$
\omega_P > \omega_W \,\, \Longleftrightarrow \,\, \frac{v_P}{R_P}>\frac{v_W}{R} = \frac{4v_P}{R} \,\, \Longleftrightarrow \,\,R_P < \frac{1}{4}R
$$
So we have to show that for the remaining time
\begin{align*}
T_W&=\dfrac{\text{ half circle }}{\text{ speed }}=\dfrac{\pi R}{v_W}\\
&>\dfrac{3R}{v_W} = \dfrac{\frac{3}{4}R}{\frac{1}{4}v_W}\\
&=\dfrac{R-\frac{1}{4}R}{v_P}=\dfrac{\text{ remaining distance }}{v_P}\\
&=\dfrac{R-R_P}{v_P}=T_P
\end{align*}

 

[ISamson]

We'd be pleased to offer such a challenge, but now comes the problem with it: How can we prevent all those undergraduates to solve them immediately? We have taken the "badge" criterion to give all others a head start, but how can we know, whether someone is really at school, yet?

You are correct and I share your opinion. However, I believe that it would be the interest of the younger students to challenge themselves mathematically and develop themselves. Even if other people solve them first, students can still discuss the question, solution, answer and always have a go anyway.

 

[fresh_42]

You are correct and I share your opinion. However, I believe that it would be the interest of the younger students to challenge themselves mathematically and develop themselves. Even if other people solve them first, students can still discuss the question, solution, answer and always have a go anyway.

Don't underestimate the competition aspect: "Me first!" or - sorry to say this - the temptation to brag. Maybe we could appeal at the honesty of our members and create a thread for ... what: under 18, 16, 15? What do you think? A thread about useful techniques come to mind, e.g. the partial fraction decomposition or long division. But if you look at the current thread, problems 3 and 9 only use high school math, problems 6 and 7 are integration methods with a learning effect as you can see by my comments to the solutions, and the others are basically easy, only the language might be a bit un-schoolish.

My logic puzzle in July had been meant to fit into this category - it was the first being solved.

 

[Freixas]

Maybe we could appeal at the honesty of our members and create a thread for ... what: under 18, 16, 15?

Interesting assumption about age. I started composing classical music in my 60's. I'm always miffed about music contests that have age limits. The assumption is that age equates to experience level.

Most of the problems listed here look like gobbledygook to me. The princess one is about the only one I might have tackled (OK, I'm lazy). When I was in high school I was considered one of the top students in my math class. In college, I took advanced math classes and got A's. Forty years have elapsed and all that is gone (use it or lose it). Looking over the solutions for the Pythagorean triples problem, I realize that when I was doing this stuff, there were a bunch of tools (theorems, tricks for solving equations, etc.) that I could put to bear on a problem, much as your solvers did. Gone, all gone. Well, I still remember some basics (really basic) or can look up things like the formula for the circumference of a circle.

I'm not saying you should write problems for me, just noting that age might not be the right qualifier to use. I did expect something a little simpler when I saw "Basic Math Challenge"... :-)