Challenge Are You Ready for the Basic Math Challenge This August?

[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$)
<br /> x\equiv a\pmod{n}\ \&amp;\ y\equiv b\pmod{n} \implies x+y\equiv a+b\pmod{n}.<br />

1. It holds that $x$ or $y$ is a multiple of $3$. Indeed, we have
<br /> (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<br />
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
<br /> x = p^2-q^2\quad y = 2pq\quad z = p^2+q^2,<br />
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)
<br /> 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<br />
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$)
<br /> x\equiv a\pmod{n}\ \&amp;\ y\equiv b\pmod{n} \implies x+y\equiv a+b\pmod{n}.<br />

1. It holds that $x$ or $y$ is a multiple of $3$. Indeed, we have
<br /> (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<br />
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
<br /> x = p^2-q^2\quad y = 2pq\quad z = p^2+q^2,<br />
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)
<br /> 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<br />
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
<br /> [ax+b] + [mx+n] = [(a+m)x + (b+n)]\quad\mbox{and}\quad [ax+b][mx+n] = [(ax+b)(mx+n)] = [ux+v],<br />
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
<br /> \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}).<br />
Firstly $\varphi ([0x +1]) = 1$ so $\varphi$ preserves the multiplicative identity. Furthermore
<br /> \varphi ([ax+b] + [mx+n]) = b+n + (a+m)(4+\sqrt{2}) = \varphi ([ax+b]) + \varphi ([mx+n])<br />
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
<br /> \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}).<br />

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
<br /> Z[x] /\langle g(x), 5\rangle :=Z[x] / (g(x)Z[x] + 5Z[x]) \cong Z_5[x] / g(x)Z_5[x]<br />
-------------------------------------------------------------------------------------------------------------
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
<br /> Z[x] /\langle g(x), 5\rangle :=Z[x] / (g(x)Z[x] + 5Z[x]) \cong Z_5[x] / g(x)Z_5[x]<br />
-------------------------------------------------------------------------------------------------------------
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"... :-)

 

[fresh_42]

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"... :-)

I basically agree on what you wrote, and the age criterion referred to the "usual development" given by school education. But you are right, it is not generally a good one. I would even challenge it from the other side: Just because a problem is given in a group theoretic language, doesn't automatically make it hard, since high schoolers might well be capable to solve it once they've cleared terminological ground. And yes, it is true that some of the intermediate problems are rated by their language rather than their difficulty. Funny enough, some are still unsolved, although an hour of Wikipedia reading would probably be all what is needed to overcome this hurdle.

However, the main concern remains unsolved: how to prevent those who are well trained from immediately solving them? And if not by age, how should we define "basic"? It differs a lot depending on whom you ask.

 

[Freixas]

Spoiler: Comment on Solution to 9

Since her angular velocity is higher than that of the witch she must reach such a point by the intermediate value theorem.

What a great solution! I found I could visualize the answer more easily this way:

The princess can swim a circle with a circumference of .48π in, say, 1 unit of time. The point opposite her, on shore, moves at 2π in the same amount of time, or at 4.1666.. times the princess's speed. The witch's job is now to avoid this moving location, but at best, she can only move at 4 times the princess's speed.

To finish off, you could assume the princess swims in just one direction, clockwise. The witch's maximal distance from the dreaded "opposite" point is just shy of 2π (as seen by the point, which only looks in the clockwise direction). If the witch runs clockwise, she falls behind, which means the forward distance to the witch (as seen by the point) is reduced. If the witch runs counter-clockwise, the distance is clearly reduced. The argument holds at any distance from the point.

 

[Freixas]

However, the main concern remains unsolved: how to prevent those who are well trained from immediately solving them? And if not by age, how should we define "basic"?

Ignoring age, what is "basic"? You can teach a 10-year old or a 40-year old (who skipped school) the same "basic" math concepts. Maybe you approach it from the point of view of math knowledge required (I'm thinking of things like arithmetic, geometry, algebra, calculus, etc.).

To keep it simple, you might just tag the truly beginner problems by describing who you think the problem is targeted to. If you include the word "beginner" somewhere in there, you might you might solve the first problem, too.

I do think the princess problem could be solved using beginning geometry, but it's still not an easy problem. So there's that, too.

 

[fresh_42]

I do think the princess problem could be solved using beginning geometry

All you need formally are the equations circumference equals two $\pi$ times radius and the definition of angular velocity, both very basic concepts.

 

[lpetrich]

In my solution to Question 2, I made a mistake in my statement of the generalized binomial theorem. Here is the correct statement of it:
$$ (1+x)^a = 1 + a x + \frac{a(a-1)}{2!} x^2 + \frac{a(a-1)(a-2)}{3!} x^3 + \dots = \sum_{k=0}^\infty \frac{\Gamma(a+1)}{\Gamma(a+1-k) k!} $$
using the Euler gamma function.

 

[Freixas]

All you need formally are the equations circumference equals two $\pi$ times radius and the definition of angular velocity, both very basic concepts.

The statement of mine that you quoted reflects that we're in agreement. I go along with the claim that, for a member of PhysicsForums, these can assumed to be basic concepts. Not that the assumption is always correct; just that you have to set some baseline.

I said it's not an easy problem based on this line in the original problem statement:

Why doesn't she have a chance to escape?

In fact, she does have a chance, as was nicely proved by Danny Sleator. I figured if you (or whoever wrote this), thought that the princess had no chance, it must, by definition, not be an easy problem. You might want to edit the problem statement, unless it was meant as a deliberate red herring.

 

[StoneTemplePython]

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

I did expect something a little simpler when I saw "Basic Math Challenge"... :-)

what about the gas canisters problem in our last basic challenge? It was problem 2:

https://www.physicsforums.com/threads/basic-math-challenge-july-2018.950689/

= = = =
I think it garnered a lot of interest as it is understandable to most everyone. There were a lot of attempts at it. @mfb solved it in perhaps the most constructive way (post number 48) - - - however his discussions of global minimum, etc. could be off-putting for some I suppose.

A simpler approach is to solve it inductively in 3 lines -- though I'll show it in 5 lines via iteration. sketch:

Spoiler

1.) total fuel supply exactly matches the total fuel required by track length so either we have the special case where all intervals exactly have the amount of gas required to complete the interval (in which case the problem is done) or there must be at least one interval that has more fuel than distance traveled. For Basic thread people can reason this out -- say it's obvious with a couple sentences explaining-- I thought this insight was, essentially, had in post 26. A tighter approach would be to show this with some inequalities but I wouldn't insist on it necessarily for Basic.

2.) For the $n= 2$ canisters case, start at the one that has a surplus -- i.e. the canister that has more fuel than the distance from it to the next canister. (Again if everything is zero balance, we can choose any starting spot and we're done.). We now know a viable starting position exists for all $n=2$ canister cases.

3.) For the 3 canisters case (and again if everything is zero balance we're done, so assume it's not) use bunching: We know there is at least one canister with a surplus and so we can bunch/fuse it with the canister sequentially after it. Because there's a fuel surplus in between the two there's no danger in running out of gas in that interval -- so we can just consider total distance and total fuel change in the 'bunched' setup. But now we have a 2 canister case where we've already showed that a viable starting point exists. Hence we know a viable starting position exists for all $n=3$ canister cases.

4.) For the 4 canisters case (and again if everything is zero balance we're done, so assume it's not) use bunching: Consider the canister with the surplus and bunch/fuse it with the canister sequentially after it. We've now reduced the problem to the 3 canister case which we've already solved in the affirmative... so we now know that a viable starting position must exist for all $n=4$ canister cases.

5.) and so on...

- - -
so yes there must always be some way of driving over the track without running out of fuel in the $n$ canister case.

edit:
I'm not sure if it's helpful, but you can also view this in terms of an $n=1$ gas canisters on the track must be trivially true / by definition you pick that can start at the single gas canister and have just enough gas to make the lap. You could then view, if you like, the $n=2$ case as a case where you select the canister with surplus and via bunching have now reduced the problem to the $n=1$ case. Doing the recurrence at the $n=2$ case something helps with people's intuition, other times I think they want to directly solve the $n=2$ case and set it as the base case.

- - - -

Ignoring age, what is "basic"? You can teach a 10-year old or a 40-year old (who skipped school) the same "basic" math concepts...

I do think the princess problem could be solved using beginning geometry, but it's still not an easy problem. So there's that, too.

The only technique needed for the above gas canisters problem is familiarity with induction (or iteration), and to play around with the problem for a bit. In this sense the problem is Basic as induction is perhaps the most basic proof technique -- but the emphasis is on Basic Math Challenge -- i.e. people need to play around with the problem for a while because it is a challenge.

 

[fresh_42]

unless it was meant as a deliberate red herring.

It was. One lesson to learn is not to have prejudices anywhere: Rely on your argument, not on what's written, it might be wrong.

 

[archaic]

What's the difference between $\mathbb{N}$ and $\mathbb{N}_0$ ? Wikipedia says it's the same. (reference to the first question)

 

[fresh_42]

What's the difference between $\mathbb{N}$ and $\mathbb{N}_0$ ? Wikipedia says it's the same. (reference to the first question)

I used the distinction $\mathbb{N}=\{\,1,2,3,\ldots \,\}\, , \,\mathbb{N}_0=\{\,0,1,2,3,\ldots \,\}$.
It's unnecessary to discuss whether zero is a natural number or not. Both have pros and cons.

 

[lpetrich]

I used the distinction $\mathbb{N}=\{\,1,2,3,\ldots \,\}\, , \,\mathbb{N}_0=\{\,0,1,2,3,\ldots \,\}$.
It's unnecessary to discuss whether zero is a natural number or not. Both have pros and cons.

One could use $\mathbb{N}_1$ instead of $\mathbb{N}$ to indicate its starting number, as with $\mathbb{N}_0$.

 

[Chris Miller]

Most involve terminologies that prevent my understanding the problem. Question 9 was fun though. Something to think about. I'd advise the princess to swim in the smallest possible circle in the center of her pond, forcing the witch to sprint the pond's circumference in order to maintain minimal distance. Even if she's a Kenyan marathoner, she should drop dead in a few hours. Failing this, I'd advise she swim away from the witch in the direction that is perpendicular to the tangent of the point the witch is on, which will be a curve if the witch is moving along the circumference. In other words, to maintain maximum distance from the witch at all times.

 

[mfb]

One could use $\mathbb{N}_1$ instead of $\mathbb{N}$ to indicate its starting number, as with $\mathbb{N}_0$.

I have seen $\mathbb{N}^+$ for natural numbers starting at 1.

 

[member 587159]

My solution for (8):

Spoiler

(a) Since $F$ is a distribution function, it must satisfy $F \to 1$ whenever $x \to \infty$. Hence, $a=1$.

Since $X$ denotes waiting time, and it isn't physically possible to wait a negative time, we have $\mathbb{P}\{X < 0\} = \mathbb{P}( \emptyset) = 0$. It follows that $F(0) = \mathbb{P}\{X \leq 0\} = \mathbb{P}\{X < 0\} + \mathbb{P}\{X = 0\} = 1/2$, so $a -b = 1-b = 1/2$ and $b = 1/2$.

On the other hand, $1 - F(1) = 1 - \mathbb{P}\{X \leq 1\} = \mathbb{P}\{X > 1\} = 1/4$. It follows that $3/4 = F(1) = 1-1/2e^{- \lambda}$. This can be solved for $\lambda$ with the help of logarithms.

(b) The distribution can be described by a density function, because the distribution function is differentiable everywhere except possibly not at $0$. Hence, we can define the density function $f$ by

$f(x) = \begin{cases} 0 \quad x = 0 \\ b \lambda e^{- \lambda x} \quad x \neq 0\end{cases}$

Here, I used a basic result in probability theory: if a distribution function is differentiable everywhere, except at an (at most) countable set of points, the distribution is absolutely continuous, and the density is given by the derivative on the points where the function is differentiable and 0 elsewhere.

 

[fresh_42]

My solution for (8):
(a) Since $F$ is a distribution function, it must satisfy $F \to 1$ whenever $x \to \infty$. Hence, $a=1$.

Since $X$ denotes waiting time, and it isn't physically possible to wait a negative time, we have $\mathbb{P}\{X < 0\} = \mathbb{P}( \emptyset) = 0$. It follows that $F(0) = \mathbb{P}\{X \leq 0\} = \mathbb{P}\{X < 0\} + \mathbb{P}\{X = 0\} = 1/2$, so $a -b = 1-b = 1/2$ and $b = 1/2$.

On the other hand, $1 - F(1) = 1 - \mathbb{P}\{X \leq 1\} = \mathbb{P}\{X > 1\} = 1/4$. It follows that $3/4 = F(1) = 1-1/2e^{- \lambda}$. This can be solved for $\lambda$ with the help of logarithms.

So?

(b) The distribution can be described by a density function, because the distribution function is differentiable everywhere except possibly not at $0$. Hence, we can define the density function $f$ by

$f(x) = \begin{cases} 0 \quad x = 0 \\ b \lambda e^{- \lambda x} \quad x \neq 0\end{cases}$

Here, I used a basic result in probability theory: if a distribution function is differentiable everywhere, except at an (at most) countable set of points, the distribution is absolutely continuous, and the density is given by the derivative on the points where the function is differentiable and 0 elsewhere.

Could you give a quotation of this "basic result"?
But anyway, this is the "Basic" challenge, so we do not talk about measure theory and integrability means Riemann, not Lebesgue. However, as you pointed out the critical point $x=0$ it is a correct answer, however, in basic math terms there is no density function because of the discontinuity at $x=0\,.$

Summary:

Basic: Because the distribution function isn't continuous (at $x=0$) and thus not differentiable, it cannot result from a density function.
(acceptable answer in this case)

Advanced mathematics: The discontinuity at $x=0$ isn't a satisfactory hurdle for not to speak of a density function, which becomes obvious if we draw the graph. To overcome such obstacles is the main reason why probability theory nowadays is based on measure theory and Lebesgue integration, rather than combinatorics and Riemann integrability. So in case you encounter $\sigma-$algebras somewhere, this is the reason: make sets measurable (=volume) in a meaningful way, although they might contain a few problematic points. It means: Make the best out of the misery, as long as we still can get a well-defined theory. It's like having a ball minus a point or a two-dimensional slice, in which case the ball has still the volume $\frac{4}{3}\pi r^3\,.$ That's the basic idea behind measure theory and the related $\sigma-$algebras, so don't be scared.