Micromass' big August challenge

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

Ranking here: https://www.physicsforums.com/threads/micromass-big-challenge-ranking.879070/

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.

ADVANCED CHALLENGES:
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:

 

[S.G. Janssens]

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.

 

[micromass]

Next, note that the degree for any nilpotent element in $M$ does not exceed $n$.

How would you show that?

 

[S.G. Janssens]

How would you show that?

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.

 

[Biker]

I would give a shot on this.

Challenges for high school:

I have recently studied limits on my own let's 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 high school:
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 let's 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

 

[micromass]

I would give a shot on this.

Challenges for high school:

I have recently studied limits on my own let's 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$

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

Previous challenges high school:
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 let's 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

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

 

[Biker]

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

Challenges for high school:
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

 

[member 587159]

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.

 

[Erland]

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

 

[micromass]

Yes, sorry.

 

[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 anyone 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$

 

[micromass]

2) There are $N = {n \choose 2}$ pairs of the form $|x_i - x_j|$

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

 

[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

 

[micromass]

Only exact solutions count, no approximations!

 

[Biker]

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

First let's 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.

 

[S.G. Janssens]

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.

 

[Number Nine]

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

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.

 

[micromass]

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.

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

 

[member 587159]

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.

 

[micromass]

That's right!

 

[Biker]

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.

I searched about the topic and saw that it must be related to derivatives and L'hopital rule (not hospital :D, he wouldn't like to be called hopsital) but it is some of the stuff I haven't 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

 

[member 587159]

That's right!

Here's my working:

Page 1: https://4.bp.blogspot.com/-tyPPHqnx...JA5dY9W2mBu1t8wCLcB/s1600/20160813_132613.jpg
Page 2: https://4.bp.blogspot.com/-dQHlJFzP...DXsXj0dYtcAHN3QCLcB/s1600/20160813_132617.jpg
Calculation of the derivative: https://4.bp.blogspot.com/-i5-5D4Ru...gq4NnKU5Ahe_2kwCLcB/s1600/20160813_132624.jpg

 

[mfb]

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 Y_i: Imagine Y_i=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.

 

[S.G. Janssens]

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

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

 

[micromass]

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 Y_i: Imagine Y_i=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.

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.

 

[micromass]

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

Yes, I think it needs to be somewhat more rigorous than what you wrote, although you do have the right idea.

 

[BiGyElLoWhAt]

For advanced #8, do the birds never leave, and can the birds occupy the same space? I'm assuming they are point-like as well.

 

[micromass]

For advanced #8, do the birds never leave, and can the birds occupy the same space? I'm assuming they are point-like as well.

The birds never leave. The birds are point-like, so they can in principle occupy the same space, but this has probability 0 anyway.

 

[Biker]

Hmmm,

There could be a proof using some simple arithmetic laws..

Well once you reach the reversed sequence and as we agreed it is $\frac{n}{2}$ if $n$ is even.
No matter how destructive you are to this pattern you only have two choices.
Either an odd number of destructive moves
or an even number of destructive moves

Now in order to get back to your reversed sequence you have to trace back what you did. (doing what you have done in reversed)
So if there is an odd number of destructive moves, there is an odd number of rebuilding moves
Total moves = odd + odd = Even
So if there is an even number of destructive moves, there is an even number of rebuilding moves
Total moves = Even + Even = EvenSo as a whole, it is minimal moves + destructive and rebuilding moves.
Every move from the start = Even + Even = Even

Which is technically still a simple proof.

 

[fresh_42]

L'hopital rule (not hospital :D, he wouldn't like to be called hopsital)

But then you should write de L'Hôpital.

 

[S.G. Janssens]

For advanced challenge #5, I would proceed as follows. Define $\rho : X \times X \to \mathbb{R}$ by $\rho := f \circ d$. Then:

1. Clearly $\rho(x, y) \ge 0$ for all $x,y \in X$.
2. If $\rho(x,y) = 0$ then $f(d(x,y)) = 0$ so $d(x,y) = 0$ and $x = y$ since $d$ is a metric.
3. Conversely, $\rho(x,x) = f(d(x,x)) = f(0) = 0$ for all $x \in X$.
4. Symmetry of $\rho$ is immediate from symmetry of $d$.

The triangle inequality remains. Let $x, y, z \in X$ be arbitrary. Then
$$
\rho(x,y) = f(d(x,y)) \le f(d(x,z) + d(z,y))
$$
since $f$ is increasing and $d$ satisfies the triangle inequality. We are therefore done if we can show that $f$ is subadditive, which we do now. Because $f'' \le 0$ we see that $f$ is concave. For arbitrary $s,t \ge 0$ we have
$$
f(s + t) = \frac{s}{s + t}f(s + t) + \frac{t}{s + t}f(s + t) \qquad (\ast)
$$
For the first term on the right, we have (writing $\mu := \tfrac{s}{s +t} \in [0,1]$),
$$
\mu f(s + t) = \mu f(s + t) + (1 - \mu)f(0) \le f(\mu(s + t) + (1 - \mu)0) = f(\mu(s + t))
$$
where it was used that $f$ is concave with $f(0) = 0$. The second term on the right of $(\ast)$ is estimated likewise. Therefore $(\ast)$ implies that
$$
f(s + t) \le f(s) + f(t)
$$
which is subadditivity.

 

[stevendaryl]

1. a) 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) Prove that uniqueness fails if we drop the continuity condition.

Spoiler

So we have $f(1) = 2$ and $f(x+y) = f(x) f(y)$. I'm going to switch over to a new function $g(x) = log_2(f(x))$. Then in terms of $g$, we have:

$g(1) = 1$
$g(x+y) = g(x) + g(y)$

We can easily prove by induction that for any $n$,

$g(n x) = n g(x)$

and (equivalently)

$g(\frac{x}{m}) = \frac{1}{m} g(x)$

Together, these imply that for any rational number $r$,

$g(r) = r g(1) = r$

If that's true for rational numbers, then by continuity, it is true for any number. So we have:

$g(x) = x$

So
$f(x) = 2^x$

---
Proving that it is not unique if you drop continuity is a lot harder. My gut feeling is that no finite number of applications of the rules could possibly determine the value of $g(\pi)$ (for example). So it's consistent to have $g(\pi)$ equal to anything you like, $5$, for example. But actually showing that you can set $g(\pi) = 5$ and still satisfy the rules $g(1) = 1$, $g(x+y) = g(x) + g(y)$ seems difficult. I'm thinking that maybe transfinite recursion or using Zorn's lemma or something might be needed. I will come back to this, but I want to establish the first part.

 

[fresh_42]

Spoiler

"["Spolier"]"text"["/Spolier"]"

 

[micromass]

Spoiler

So we have $f(1) = 2$ and $f(x+y) = f(x) f(y)$. I'm going to switch over to a new function $g(x) = log_2(f(x))$. Then in terms of $g$, we have:

$g(1) = 1$
$g(x+y) = g(x) + g(y)$

We can easily prove by induction that for any $n$,

$g(n x) = n g(x)$

and (equivalently)

$g(\frac{x}{m}) = \frac{1}{m} g(x)$

Together, these imply that for any rational number $r$,

$g(r) = r g(1) = r$

If that's true for rational numbers, then by continuity, it is true for any number. So we have:

$g(x) = x$

So
$f(x) = 2^x$

---
Proving that it is not unique if you drop continuity is a lot harder. My gut feeling is that no finite number of applications of the rules could possibly determine the value of $g(\pi)$ (for example). So it's consistent to have $g(\pi)$ equal to anything you like, $5$, for example. But actually showing that you can set $g(\pi) = 5$ and still satisfy the rules $g(1) = 1$, $g(x+y) = g(x) + g(y)$ seems difficult. I'm thinking that maybe transfinite recursion or using Zorn's lemma or something might be needed. I will come back to this, but I want to establish the first part.

But it is not given that $f$ is continuous. It is only given that $f$ is continuous in one point.

 

[stevendaryl]

But it is not given that $f$ is continuous. It is only given that $f$ is continuous in one point.

Ah! My mistake. So if it is continuous at a point $x$, that means that as $y \rightarrow x$, $f(y) \rightarrow f(x)$. In terms of the function $g(x) = log_2(f(x))$, I showed that $g(x) = x$ for all rational values of $x$. For any point $x$, there is a sequence of rationals $r_1, r_2, ...$ converging to $x$. So if $g(x)$ is continuous at $x$, then it must be that $g(r_1), g(r_2), ...$ converges to $g(x)$. Since $g(r) = r$ for a rational, that means that $r_1, r_2, ...$ converges to $g(x)$, which means that $g(x) = x$.

Now, let $\alpha$ be an arbitrary positive real number. Let $r_1 , r_2 , ...$ be a sequence of rationals that converges to $\frac{x}{\alpha}$. That means $r_1 \alpha, r_2 \alpha, ...$ converges to $x$. Then if $g(x)$ is continuous at $x$, then $g(r_1 \alpha), g(r_2 \alpha) ...$ converges to $g(x)$, which is $x$. But it's also the case (proved in the previous post) that $g(r \alpha) = r g(\alpha)$ when $r$ is rational. So we have:
$r_1 g(\alpha), r_2 g(\alpha), ...$ converges to $x$. That means that $r_1, r_2, ...$ converges to $\frac{x}{g(\alpha)}$. We already said that it converged to $\frac{x}{\alpha}$. It can't converge to both unless $g(\alpha) = \alpha$. So we have $g(\alpha) = \alpha$ for all positive $\alpha$.

For negative $\alpha$, just note that $\alpha -\alpha = 0$. Since $0$ is rational, $g(0) = 0$. So $g(\alpha + -\alpha) = g(\alpha) + g(-\alpha) = 0$. So $g(\alpha) = - g(-\alpha)$. This allows us to extend $g$ to all values of $\alpha$, positive or negative.

The only missing point is that you only said that $f(x)$ is continuous at some point, not that $g(x)$ is continuous. So what I really need to do is worry about the case where $f(x)$ is continuous, but $g(x)$ is not, which would mean $x \leq 0$. I'll put off worrying about this.