# FeaturedChallenge Micromass' big August challenge!

Tags:
1. Aug 12, 2016

### micromass

August is already well underway, so time for some nice challenges! This thread contains both challenges for high schoolers and college freshmen, and for more advanced people. Also some previously unsolved challenges are omitted.

RULES:
• In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
• 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.
• If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
• 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.
1. a) SOLVED BY stevendaryl, disregardthat, mfb Prove there is a unique function $f:\mathbb{R}\rightarrow \mathbb{R}$ such that $f(1) = 2$ and such that for all $x,y\in \mathbb{R}$ holds $f(x+y) = f(x)f(y)$ and such that $f$ is continuous in at least one point.
b) SOLVED BY Erland Prove that uniqueness fails if we drop the continuity condition.

2. SOLVED BY mfb In probability theory, a scale estimator is a function $s$ that takes in $n$ data points and provides an estimate for the variability of the data. The standard deviation is a famous example of a scale estimator. Let $s$ be a scale estimator on $n$ given data points $Y_1$, ..., $Y_n$. We say that the explosion value of $s$ is $x\%$ if we can replace $x\%$ of the data points by arbitrary chosen values in order to make the scale estimate arbitrarily large, while we cannot do the same by replacing less than $x\%$..
As an example, when computing the standard deviation of $n$ data points $Y_1$, ..., $Y_n$, we can replace the $n$th data point by $c$. By taking $c\rightarrow +\infty$, we see clearly that the standard deviation of $Y_1$, ..., $Y_{n-1}$ and $c$ also diverges to $+\infty$. So the standard deviation on $n$ data points explodes already by replacing $1$ data point: the explosion value is $100/n \%$.
Consider the following scale estimator:
$$s(Y_1,...,Y_n) = \text{median}\{|x_i - x_j|~\vert~1\leq i,j\leq n\}$$
Compute the explosion value.

3. SOLVED BY Krylov Notice that the set of $n\times n$-matrices is linearly isomorphic to $\mathbb{R}^{n^2}$. By using this isomorphism, we can talk about distances in the set of $n\times n$-matrices, that is: $M_{n,n}(\mathbb{R})$ is a metric space. Show that the set of all nilpotent matrices (i.e. matrices $N$ such that $N^k = 0$ for some $k\in \mathbb{N}$) is closed in this metric space.

4. SOLVED BY Erland Let $X$ denote the set of all bounded real-valued sequences. Prove that a generalized limit exists for any such sequence. A generalized limit is any function function $L:X\rightarrow \mathbb{R}$ such that
1) $L((x_n + y_n)_n) = L((x_n)_n) + L((y_n)_n)$
2) $L((\alpha x_n)_n) = \alpha L((x_n)_n)$
3) $\liminf_n x_n \leq L((x_n)_n)\leq \limsup_n x_n$
4) If $x_n\geq 0$ for all $n$, then $L((x_n)_n)\geq 0$.
5) If $y_n = x_{n+1}$, then $L((x_n)_n) = L((y_n)_n)$
6) If $x_n\rightarrow x$, then $L((x_n)_n) = x$.

5. SOLVED BY Krylov Let $f:[0,+\infty)\rightarrow [0,+\infty)$ be increasing and satify $f(0)=0$ and $f(x)>0$ for all $x>0$. Let $(X,d)$ be a metric space. Show that if $f''\leq 0$, then $(X,f\circ d)$ also is a metric space.

6. SOLVED BY Krylov, disregardthat Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space. That is: $\Omega$ is a set, $\mathcal{B}$ is a $\sigma$-algebra on $\Omega$, and $\mathbb{P}:\mathcal{B}\rightarrow [0,1]$ satisfies that $\mathbb{P}(\Omega) = 1$ and $\mathbb{P}\left(\bigcup_{k=1}^{+\infty} A_k\right) = \sum_{k=1}^{+\infty} \mathbb{P}(A_k)$ whenever $A_i\cap A_j =\emptyset$ for all $i\neq j$.
This probability space is called nonatomic if $\mathbb{P}(A)>0$ implies that there is a $B\subseteq A$ such that $0<\mathbb{P}(B)<\mathbb{P}(A)$.
Prove that in a nonatomic probability space, for each $\mathbb{P}(A)>0$ and for each $p_1,p_2,...\geq 0$ with $\sum p_k = 1$, then $A$ can be decomposed in a disjoint union $A = \bigcup A_k$ such that $\mathbb{P}(A_n) = p_n\mathbb{P}(A)$.

7. SOLVED BY TeethWhitener Let $p$ be a prime number. Let $r$ and $s$ be natural numbers. We write $r = \sum r_k p^k$ and $s = \sum s_k p^k$ the base $p$ representations of $r$ and $s$. Show
$$\binom{r}{s} = \prod_{k=0}^{+\infty} \binom{r_k}{s_k}~~\text{(mod p)}$$
Note that the above product is a finite product.

8. Take a wire stretched between two posts, and have a large number of birds land on it at random. Take a bucket of yellow paint, and for each bird, paint the interval from it to its closest neighbour. The question is: what proportion of the wire will be painted. More strictly: as the number of birds goes to infinity, what is the limit of the expected value of the proportion of painted wire, assuming a uniform probability distribution of birds on the wire.

9. SOLVED BY Krylov Let $(X,d)$ and $(Y,d')$ be metric spaces with $X$ compact. Let $f:X\rightarrow Y$ and $g:Y\rightarrow X$ be isometries (= distance preserving functions). Prove that $f$ and $g$ are bijections.

PREVIOUS UNSOLVED ADVANCED CHALLENGES:
1. SOLVED BY fresh_42 Let $G$ be a finite group and let $p$ be the smallest prime number which divide $|G|$. Prove that every subgroup $H$ of $G$ such that $p|H| = |G|$ is normal. Use this to find all groups of order $pq$ with $p$ and $q$ (not necessarily distinct) primes.
Hint: consider a homomorphism $G\rightarrow \text{Sym}(G/H)$.

2. In a village of $2016$ people, prove that the probability that exactly $m$ days (ignore leap years) are not a birthday can be approximated by a Poisson distribution.
Hint: Let $p(m,r,n)$ be the probability that putting $r$ balls in $n$ boxes leaves $m$ boxes empty. Show that if we put $\lambda = ne^{r/n}$, then if $n\rightarrow +\infty$ and $r\rightarrow \infty$ in such a way that $\lambda$ remains fixed, prove that $p(m,r,n)- e^{-\lambda}\frac{\lambda^m}{m!}\rightarrow 0$.

CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. SOLVED BY Math_QED Let $a$ be a fixed number in $[0,1]$. Let $x_n = n(1 - a + ae^{1/n})^n - ne^a$. Find $\lim_{n\rightarrow +\infty} x_n$.

2. SOLVED BY Biker Find all places on earth so that can you walk one mile north, one mile west and one mile south then end up back where you started?

3. On a table are $2016$ bells standing in a sequence. At every turn you have to pick $2$ bells, ring them and then exchange their place.
For example, if there were only $4$ bells, they stand initially as $A-B-C-D$. In turn $1$, you pick bells $A$ and $D$, ring them and exchange them to get $D-B-C-A$. In turn $2$, you pick bells $D$ and $B$, ring them and exchange them to get $B-D-C-A$.
The goal of the bell ringer is to take $n$ turns after which the sequence of bells is reversed. For example an easy way to reverse the order in $A-B-C-D$ is first to ring $A$ and $D$ to get $D-B-C-A$ and then to ring $B$ and $C$ to get $D-C-B-A$. We have reversed the bells in $2$ turns.
Show that it is impossible to reverse $2016$ bells in an odd number of turns.

4. SOLVED BY Math_QED Prove that there exists $2016$ consecutive natural numbers, none of which is prime.

5. Find all $10$-digit numbers such that
a) each digit $\{0,1,2,3,4,5,6,7,8,9\}$ is used exactly once
b) the first $n$ digits form a number divisible by $n$ ($n\in \{1,2,3,4,5,6,7,8,9,10\}$).
For example, if my number would be $1234567890$, then $1$ must be divisble by $1$, $12$ must be divisible by $2$, $123$ must be divisible by $3$ and so on.

6. Find all 10-digit numbers where the first digit is how many zeros are in the number, the second digit is how many 1s are in the number etc. until the tenth digit which is how many 9s are in the number.

PREVIOUS CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. Let $p\neq 0$ be a real number. Let $x_1,...,x_n$ be positive real numbers, we define the $p$-mean as
$$M_p(x_1,...,x_n) = \sqrt[p]{\frac{1}{n}\sum_{i=1}^n x_i^p}$$
Note that $M_1(x_1,...,x_n)$ is the usual mean.
Prove that for all $p,q\in \mathbb{R}\cup \{- \infty,+\infty\}$ has that $p\leq q$ implies $M_p(x_1,...,x_n)\leq M_q(x_1,...,x_n)$.

2. Take rational numbers $\frac{a}{c}<\frac{b}{d}$ with $a,b,c,d\in \mathbb{N}$.
Prove that if $bc - ad = 1$, then $\frac{a+b}{c+d}$ is the simplest fraction in $\left(\frac{a}{c},\frac{b}{d}\right)$ in the sense of having the smallest denominator.

3. SOLVED BY Pro7 Find
$$\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + 4\sqrt{1 + ...}}}}$$

4. SOLVED BY Biker A donkey is tied with a $50m$ long rope. The rope is tied to the corner of a $20m$ by $10m$ barn. What is the total area that the donkey is capable of grazing?
Here is a sketch:

Last edited: Sep 15, 2016
2. Aug 12, 2016

### Krylov

For advanced problem #3, note that the norm induced by the isomorphism on $M := M_{n,n}(\mathbb{R})$ is the Frobenius-norm $\|\cdot\|_{\text{F}}$. (It does not really matter, we can take any norm we like, since $M$ is finite-dimensional. This fact, however, does not play a role in the sequel.) Furthermore, it holds that the map
$$M \ni A \mapsto A^n \in M \qquad (\ast)$$
is continuous w.r.t. to $\|\cdot\|_{\text{F}}$ since the norm is sub-multiplicative. Indeed,
$$\|(A - B)^n\|_{\text{F}} \le \|A - B\|_{\text{F}}^n \to 0 \qquad \text{as } B \to A \text{ in } M$$
proving continuity. Next, note that the degree for any nilpotent element in $M$ does not exceed $n$. Now, take a sequence $(A_j)_{j \in \mathbb{N}}$ of nilpotent matrices in $M$ that converges to some $A \in M$. By continuity of $(\ast)$ and the fact that $\text{deg}(A_j) \le n$ for all $j \in \mathbb{N}$ it follows that
$$A^n = \lim_{j \to \infty}{A_j^n} = 0$$
so $A$ is nilpotent as well.

3. Aug 12, 2016

### micromass

How would you show that?

4. Aug 12, 2016

### Krylov

You could say that $\sigma(A) = \{0\}$ when $A$ is nilpotent, so the characteristic polynomial of $A$ is $p(\lambda) = \lambda^n$. Then $A^n = 0$ by Cayley-Hamilton.

5. Aug 12, 2016

### Biker

I would give a shot on this.

Challenges for highschool:

I have recently studied limits on my own lets see if it works( Hopefully :c)
1-
So you can simplify it by first taking n as a factor then treat it as sperate
After that you can take the limit to infinity for this:
$(1-a+ae^{1/n})^n - e^a$
as n tends to infinity $e^{1/n}$ to 1 so the whole $(1-a+a)^n$ is 1
we are left with
$1 - e^a$
So the limit of the whole thing is
$(1-e^a) \lim_{n \rightarrow +\infty} n$
If we look at the values of $a$
If $a =0$ then the limit is zero
else
The limit is $-\infty$

Previous challenges highschool:
4. Here is an answer (not sure if this is what you are asking for, If not clarify please. the answer seems easy)
Well if the rope is 50 meters tall, Then lets check at which point the donkey stops.

The furthest point is calculated as following. $x = \sqrt(10^2+ 20^2)$
$x = 10\sqrt(5)$
This means that the donkey can reach any point in the farm so, the total area it will graze is just the area of the barn

6. Aug 12, 2016

### micromass

Sorry, that answer is incorrect. In particular, $1^{+\infty} \neq 1$.

Sorry, I did not post the full question. I'll edit my post now.

7. Aug 12, 2016

### Biker

Oppps, Hmmmm I guess I have to read another topic about that. Thanks for pointing out the reason

Challenges for highschool:
2-
I will just pretend that the earth is a perfect sphere.
If you move close to the south pole, You can mark a circle with a circumference of 1 mile around the earth. Now move 1 mile further to the south and and face the north.
Move one mile north and you are on the circle, Move one mile west and you will come back to the same place (assuming west from your initial location) move 1 mile south and you are back to the same place.

and you can be on the north pole, as the earth is a sphere you will form a triangle that will leads you back to the same place (Disregarding the method I suggested) or you could use the same method but with minor changes at the north pole

Who needs a gps :P

8. Aug 12, 2016

### Math_QED

You might want to add to 4 of the high school problem: "without giving an example", otherwise I can give you a gap larger than 2016 numbers between 2 prime numbers with no other prime numbers in.

Last edited: Aug 12, 2016
9. Aug 12, 2016

### Erland

In Advanced Problem 1b, you mean the continuity condition, right?

10. Aug 12, 2016

### micromass

Yes, sorry.

11. Aug 12, 2016

### Number Nine

I'm tired now, so I haven't had as much time as I'd like to think this through, but: For (2), Let $n$ be the number of observations. Note that

1) The explosion value for the median is .5 (as $n \rightarrow \infty$)
2) There are $N = {n \choose 2}$ pairs of the form $|x_i - x_j|$
3) Altering $k$ elements alters $C_k = k(n-1)$ pairs ($k$ choices for the changed element, and any one of the other observations for the other element).

So, we need to set
\begin{align*} C_k = k(n-1) = \frac{n!}{4(n-2)!} = \frac{N}{2} \end{align*}
which gives
\begin{align*} k = \frac{n!}{4(n-1)!} = \frac{n}{4} \end{align*}

which gives an explosion value of .25 as $n \rightarrow \infty$

12. Aug 12, 2016

### micromass

That is incorrect. Consider the following three data points: $0$, $1$, $2$. Then we have only three values of the form $|x_i - x_j|$, namely,
$$|0 - 0| = |1-1| = |2-2| = 0$$
$$|1 - 2| = |2-1| = |0-1| = |1 - 0| = 1$$
$$|2 - 0| = |0-2| = 2$$
Thus the estimate is $s = \text{med}\{0,1,2\} = 1$.

13. Aug 12, 2016

### Biker

Donkey's challenge
I have got a solution of 7539.8822 Using some approximations. The real value is a bit 20ish meter less than that

Last edited: Aug 12, 2016
14. Aug 12, 2016

### micromass

Only exact solutions count, no approximations!

15. Aug 12, 2016

### Biker

Okay, I figured out the whole solution and solved my approximation problem.

First lets see the picture below, This is how I interpreted it.

Okay so as we see here we have 3 section.
1) The big circle :p
2) the 2 small circles
3) Intersection
What you need to find out is that intersection (there is an approximation way 20m less than what expected) but we will find it with a another way without leaving a bit.
so first we have to find theta 1 and theta 4
Using this formula
$C^2 = A^2 + B^2 + 2 A B cos \theta$
The numbers denote the length of each side of the triangle.
To find theta 1 you have to subtract the angle of the triangle of the barn from the acquired angle from the previous equation
You will find that theta 1 is equal to 35.138
Same thing applies to theta 4 and it is equal to 21.304
Now You could get theta 7 and theta 8 by subtracting theta 1 and theta 4 from 90

So as you have the angle use it to find the area that theta 7 and theta 8 are facing.
$\frac{\theta_7}{360} \pi 30^2$
$\frac{\theta_8}{360} \pi 40^2$
So what we are missing is the area of the big triangle - the triangle in the barn
You can get the area using this formula
#p# is half of the circumference
$area = \sqrt{p(p-a)(p-b)(p-c)} ~ - ( 0.5 * 10 * 20 )$

By adding these areas together you have found the area of the intersection and the two circles( 1/4 of the shape)

for the other 3/4 it is easy, you just have to find the area of $\frac{3}{4} \pi 50^2$

Sum all that and you have that the damn donkey will eat $7512.210951 m^2$ worth of grass.

16. Aug 12, 2016

### Krylov

Here is my attempt for advanced problem #9. Both $f$ and $g$ are injective since they are isometries. It remains to show that they are also surjective. For this we note that $h : = g \circ f : X \to X$ is an isometry. Since $X$ is compact, it follows that $h$ is surjective.

(The short proof of this latter fact can be found in, for example, Vol. 2 of Garling's A Course in Mathematical Analysis, see Thm. 15.4.11 there. It amounts to assuming to the contrary that $h$ is not surjective, so there exists $x \in X \setminus h(X)$. Then $\delta := d(x, h(X)) > 0$ as $h(X)$ is closed. The sequence $(h^{(n)}(x))_{n \in \mathbb{N}}$ of iterations of $x$ does not have a convergent subsequence, its terms being at least $\delta$ apart. This contradicts sequential compactness of $X$.)

In any case, surjectivity of $h$ implies surjectivity of $g$. This in turn yields sequential compactness (hence compactness) of $Y$. (Indeed, let $(y_n)_n$ be a sequence in $Y$. Then the sequence $(g(y_n))_n$ in $X$ has a subsequence $(g(y_{n(m)}))_m$ converging to some limit $x \in X$. Since $g$ is surjective, there exists $y \in Y$ such that $x = g(y)$. Therefore,
$$d'(y_{n(m)},y) = d(g(y_{n(m)}), g(y)) = d(g(y_{n(m)}), x) \to 0 \quad \text{as } m \to \infty$$
proving that the subsequence $(y_{n(m)})_m$ converges to $y$ in $Y$. Hence $Y$ is sequentially compact.)

Redefining $h := f \circ g : Y \to Y$ we find an isometry of the compact space $Y$ and as before this implies that $h$ is surjective, proving that $f$ is surjective as well.

17. Aug 12, 2016

### Number Nine

Just for clarification, wouldn't that be $s = \text{med}\{0,0,0,1,1,1,1,2,2\} = 1$? Which in this case evaluates identically, but may not in general. The curly brackets suggest set notation, which I guess would ignore multiplicities, though I'm not sure if that's what you meant. Otherwise:

For some reason, I assumed that we weren't double counting $|x_i - x_j|$ and $|x_j - x_i|$, or counting the $j=i$ case. If the median is taken over the entire distance matrix (and not the lower triangular part, as I assumed), then there are $N=n^2$ elements, $2k(n-1)$ of which are affected by manipulating $k$ elements (since the diagonal elements are not). We then need to manipulate
\begin{align*} k = \frac{n^2}{4(n-1)} \end{align*}
in order to explode the median, which gives
\begin{align*} k/n = \frac{n^2}{4(n-1)} = \frac{n}{4(n-1)} \end{align*}
which is $0.25$ in the limit, unless I missed something obvious again. That the answer is the same as in the lower triangular part makes sense, since both the lower and upper triangular parts behave identically by symmetry, and the diagonal becomes irrelevant in the limit.

18. Aug 13, 2016

### micromass

Right, the curly brackets indicate set notation, so you should ignore multiplicities.

19. Aug 13, 2016

### Math_QED

For the high school challenge, is the answer of 1: 1/2*e^a*(1-a)*a? To achieve this answer, I used l'Hospital's rule but I'm not sure whether this is allowed for sequences. I will post my working if the answer would be correct.

20. Aug 13, 2016

### micromass

That's right!

21. Aug 13, 2016

### Biker

I searched about the topic and saw that it must be related to derivatives and L'hopital rule (not hospital :D, he wouldnt like to be called hopsital) but it is some of the stuff I havent studied yet...
I wish I could have solved it :C

Highschool Challenges:
3
This is a simple proof, not a lot of mathematics
It turns out that the example you used is just the minimal number of ways you could do to reverse a sequence.
Now think of all the possibilities one could do to rearrange it, The minimal number of ways is x/2 if x is even
delay any additional moves to the end like this
Some additional moves -- ) minimal moves - -- ) end
minimal moves --- ) some additional moves --- ) end
So you have a reversed sequence then you can do the additional moves.
Suppose you have
6 5 4 3 2 1
This is a reversed sequence
Any additional move would require a even number of moves to bring it to the reversed sequence again
for example
6 5 4 2 3 1
6 2 4 5 3 1
6 2 4 3 5 1
6 5 4 3 2 1

So 2016/2 = 1008 (minimal moves)
any additional move would increase this by an even number.

Hope this is sufficient, I could maybe reform the proof in a more mathematical way

22. Aug 13, 2016

### Math_QED

23. Aug 13, 2016

### Staff: Mentor

Explosion value problem (advanced #2):

Based on post #12, the median runs over the set of distinct absolute differences only? Then the explosion value is 1/n for some realizations of Yi: Imagine Yi=1 for all i from 0 to n, clearly s=0. Now pick any element and set it to arbitrarily large values: we get the median of 0 and some large value, assuming we define the median to be the average if the set has an even number of elements this average gets arbitrarily large.

24. Aug 13, 2016

### Krylov

There is no need to look sad, you are doing a very good job.

25. Aug 13, 2016

### micromass

The idea is that your construction must work for all realizations of $Y_i$, not just special cases. Sure for some realizations of $Y_i$, you don't need much to make $s$ explode. But it must work for all realizations.