# FeaturedChallenge Micromass' big September challenge!

Tags:
1. Sep 1, 2016

### micromass

September, schools restart, summer ends, but a new challenge is here:

RULES:
1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
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.

1. Show that it is impossible to find four distinct squares as the subsequent elements in an arithmetic progression.

2. SOLVED BY Strants Show that the $n$ roots of a real/complex polynomial of degree $n$ depend continuously on the coefficients.

3. SOLVED BY Erland On a subset $A$ of $\mathbb{R}$ we can apply the operations of complementation $\mathbb{R}\setminus A$ and of closure $\overline{A}$. By doing this repeatedly one can form for example $\overline{\mathbb{R}\setminus(\mathbb{R}\setminus A)}$. How many different sets can I maximally generate from $A$ in this manner?

4. SOLVED BY fresh_42 Find the sum of
$$\frac{1}{\binom{4}{3}} - \frac{1}{\binom{6}{3}} + \frac{1}{\binom{8}{3}} - \frac{1}{\binom{10}{3}} + ...$$

5. SOLVED BY QuantumQuest Let $a_k,b_k$ be positive real numbers for $1\leq k\leq n$. Show
$$\left(\prod_{k=1}^n a_k\right)^{1/n}+\left(\prod_{k=1}^n b_k\right)^{1/n} \leq \left(\prod_{k=1}^n (a_k+b_k)\right)^{1/n}$$
When does equality hold?

6. SOLVED BY Erland The luckless Daniel (D) is thrown into a circular arena of radius $a$ containing a lion L. Initially, the lion is at the centre O of the arena while Daniel is at the perimeter. Daniel's strategy is to run with his maximum speed $u$ around the perimater. The lion's strategy is to run with speed $u$ in such a way that it remains on the (moving) radius OD. What distance did the lion cover before he caught Daniel?

7. Let $X$ denote the set of all bounded real-valued sequences. As was shown in last challenge, 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$.
Show that:
a) SOLVED BY Erland There is more than one generalized limit.
b) SOLVED BY Erland For a given bounded real sequence $(x_n)_n$, we have that every generalized limit $L$ assigns the same value $l$ to this sequence if and only if
$$\lim_{p\rightarrow +\infty}\frac{x_n + ... + x_{n+p-1}}{p} = l$$
uniformly in $n$.
In other words if and only if
$$\forall\varepsilon>0:~\exists p_0:~\forall p>p_0:~\forall n:~\left|\frac{x_n + ... +x_{n+p-1}}{p} - L\right|<\varepsilon$$
c) SOLVED BY Erland Find an example of a sequence that does not satisfy the condition in (b) but for which $\frac{1}{n}\sum_{i=1}^n x_i$ does converge.
d) SOLVED BY Erland Show that we can find a generalized limit $L$ such that $L((x_n)_n) = \lim_{n\rightarrow +\infty} \frac{1}{n}\sum_{i=1}^n x_i$ if the limit exists.

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

9. SOLVED BY Erland 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.

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

CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. SOLVED BY ProfuselyQuarky You meet a man on the street and he says, “I have two children and one is a son born on a Tuesday.” What is the probability that the other child is also a son?

2. SOLVED BY Math_QED Find and prove a simple formula for the sum
$$\frac{1^3}{1^4 + 4} - \frac{3^3}{3^4 +4} + \frac{5^3}{5^4 + 4} - ... + \frac{(-1)^n (2n + 1)^3}{(2n+1)^4 + 4}$$

3. SOLVED BY Biker Consider the function
$$f(x)=\left\{\begin{array}{l} e^{-1/x}~\text{if}~x>0\\ 0~\text{if}~x\leq 0\end{array}\right.$$
a) Show that $f$ is infinitely many times differentiable on $\mathbb{R}$.
b) Find the Taylor series of $f$ around the point $0$.

4. Show that for $0<\lambda<1$ and $\alpha,\beta\geq 0$ holds
$$\alpha^\lambda \beta^{1-\lambda}\leq \lambda \alpha+(1-\lambda)\beta$$

PREVIOUS CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. 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.

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

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

Good luck and thanks for playing!

Last edited: Sep 18, 2016
2. Sep 1, 2016

### Staff: Mentor

Under which conditions? I mean $a_n = n \cdot d^2$ has a lot of squares.
And may I give the hint on previous HS1 that we have a leap year?

Last edited: Sep 1, 2016
3. Sep 1, 2016

### micromass

The squares have to be the subsequent elements in an arithmetic progression. So $a$, $a+d$, $a+2d$ and $a+3d$ are all squares.

4. Sep 1, 2016

### Ygggdrasil

Here, you must mean four perfect squares, or else the statement is trivially false.

5. Sep 1, 2016

### Math_QED

High school challenges 2)

I used a calculator to find the partial sums S0, S1, S2, ... and I found the sequence: 1/5, -2/17, 3/37, -4/65, 5/101, ...
So, Sn = (-1)^n*(n+1)/(4(n+1)^2+1) = (-1)^n*(n+1)/(4n^2+8n + 5)

Now, let's proof this using mathematical induction:

We can say that the equality holds for n = 0, since S0 = 1/5 = (-1)^0*1/5
Now, suppose the equality holds for n = k, then it must hold for n = k +1.

So, in particular, we have to proof that Sk+1 = (-1)^(k+1)*(k+2)/(4k^2+16k+17) using Sk =(-1)^k*(k+1)/(4k^2+8k + 5).

Sk+1 = Sk + (-1)^(k+1)*[2(k+1)+1]^3/([2(k+1)+1]^4+4)
= (-1)^k(k+1)/(4k^2+8k+5) + (-1)^(k+1)(2k+3)^3/((2k+3)^4+4)

And here I saw that I would have to use a lot of trivial algebra..., so instead I used wolframalpha.com (http://www.wolframalpha.com/input/?i=((-1)^(k+1)*(2k+3)^3/((2k+3)^4+4))+((-1)^k(k+1)/(4k^2+8k+5))) and I found that this expression is equal to (-1)^(k+1)*(k+2)/(4k^2+16k+17). And this is exactly what we wanted to show. So QED.

6. Sep 1, 2016

### PeroK

For number 1 on the high school challenges, there are some debatable issues, which (in my view) are removed by asking direct questions of the man:

Qu: How many children do you have?
Ans: 2

Qu: Do you have a son born on a Tuesday?
Ans: yes

7. Sep 1, 2016

### Math_QED

Highschool challenges 3b)

It is well known that e^x = ∑x^n/n!
Substituting -1/x yields: e^(-1/x) = ∑ (-1/x)^n/n! = ∑ (-1)^n/(x^n*n!) for x > 0

So, we have,
$$f(x)=\left\{\begin{array}{l} ∑(-1)^n/(x^n*n!)~\text{if}~x>0\\ 0~\text{if}~x\leq 0\end{array}\right.$$

8. Sep 1, 2016

### micromass

A Taylor series can't have negative powers of $x$. What you have computed is a Laurent series, and then only of the positive part.

9. Sep 1, 2016

### Erland

I once asked this very question at Usenet, and got an answer, so I know how to prove it. Is it still OK for me give a proof here?

Anyway, I think you should specify exactly what you mean by "the ... roots ... depend continuously on the coefficients". Continuously according to which topological spaces?

There might be some alternatives for this, but the proof I received probably can be adjusted to fit any of them.

10. Sep 1, 2016

### micromass

No, sorry.

11. Sep 1, 2016

### Erland

About Advanced Problem 3: It would of course depend upon $A$: If $A=\varnothing$ or $A=\mathbb R$, then the answer is $2$: $\varnothing$ and $\mathbb R$. If $A$ is a closed or open bounded interval, then the answer is $4$: $A$ itself, its interior or closure, and the complements of these two sets.

But I suppose you mean the maximum taken over all possible subsets $A$ of $\mathbb R$...?

12. Sep 1, 2016

### Staff: Mentor

I worked a bit on problem 1, and while many individual primes work well, I'm missing some generalization, or the approach does not work at all. I thought I share my work so far, feel free to use it or show me how pointless it was.
All variables in this post are non-negative integers.
Start with the observation that, mod 2n, all possible remainders of squares (all quadratic residues) can be expressed as 4k(8m+1). This is a well-known result but you can also find it at Wikipedia.
In particular, mod 4, the only possible remainders are 0 and 1.

Assume we have such a progression, consisting of the four numbers X, X+Q, X+2Q and X+3Q. Their remainders mod 2n also form an arithmetric progression, possibly wrapping over (e. g. 10, 13, 0, 3 if we consider them mod 16). If Q is not divisible by 4, then (at least) one remainder mod 4 has to be 2 or 3, which is impossible. Therefore, Q has to be divisible by 4.

Consider the case that X is even. As X is a perfect square, it is also divisible by 4, which means all four numbers are. We can divide all numbers by 4 to find a smaller arithmetric progression with four squares. We can continue that until the sequence starts with an odd number. If there is such a progression, there is also one with odd X, consider only this case.

As all four numbers are odd, their remainders mod 2n are also odd. Therefore they all can be written as (8m+1). It also implies Q is a multiple of 8. That's as far as powers of 2 go within that framework.

The same argument as with divisibility by 4 can also be made with 3: the only quadratic residues are 0 and 1 (does not follow from previous things, but it is trivial to check), the only "arithmetic progressions" in there are "always 0" and "always 1". Therefore Q has to be divisible by 3 as well. If X is divisible by 3, then both X and X+Q are divisible by 9, and we can divide the whole progression by 9 until the four numbers have a remainder of 1 mod 3.

mod 5: residues 0, 1, 4, no non-trivial progression possible, Q has to be divisible by 5, it is sufficient to consider X not divisible by 5.
mod 7: 0, 1, 2, 4, Q has to be divisible by 7, ...
mod 11: 0, 1, 3, 4, 5, 9, Q has to be divisible by 11, ...
mod 13: 0, 1, 3, 4, 9, 10, 12, Q has to be divisible by 13, ...
mod 17: 0, 1, 2, 4, 8, 9, 13, 15, 16, here there are progressions possible (15,16,0,1 and 13,15,0,2 and 9,13,0,4,8) so the argument does not work.

13. Sep 1, 2016

### micromass

Yes.

14. Sep 1, 2016

#6 with the lion is interesting and I think also not real difficult, but I previously worked a very similar problem so that I am ineligible for that one. ... editing... A little effort in trying to re-work the problem proved unsuccessful, and then I recalled completely the original similar problem, and there are distinct differences that make @micromass version much more difficult. $\\$ The original problem was that Capt. Kirk was trapped in the middle of a circular lake by a Romulin who was on shore and could run 4x as fast as Capt. Kirk could swim. The question was, could Capt. Kirk get out of the lake safely? $\\$ The solution I worked out was that Capt. Kirk used a more intelligent approach then the lion, and as long as he could, (until his radial location was $r=(1/4)R$), he swam in such a manner (and not directly away from the Romulin), so as to keep the $d \theta /dt$ the same. That way, the Romulin was as far away as possible at the $r=(1/4)R$ point. He therefore needed to go $(3/4)R$ before the Romulin went $\pi R$ and since $\pi >3$ he successfully got out. The path inside of $r=(1/4)R$ as I recall, (I solved this a few years ago) was a simple one. (I believe it was semi-circle, but it wasn't even necessary to solve for the precise path.) $\\$ In any case, the lion uses a much less intelligent and mathematically more difficult approach of running directly at the man. I do plan on trying to solve this one, but it appears to be quite difficult...

Last edited: Sep 1, 2016
15. Sep 1, 2016

### Staff: Mentor

This is what I have for AC 4.

Let $S$ denote the sum and $a_k = \binom{2k}{3}^{-1} - \binom{2k+2}{3}^{-1}$ so $S = a_2 + a_4 + a_6 + \dots$

Then we get

$a_k = \frac{3! \; (2k-3)!}{(2k)!} - \frac{3! \; (2k-1)!}{(2k+2)!} \\ = \frac{6}{2k} \Big{(} \frac{1}{(2k-1)(2k-2)} - \frac{1}{(2k+2)(2k+1)} \Big{)} \\ = \frac{6}{2k} \cdot \frac{(4k^2+6k+2)-(4k^2-6k+2)}{(2k-2)(2k-1)(2k+1)(2k+2)} \\ = \frac{36}{(2k-2)(2k+2)(2k+1)(2k-1)} \\ =\frac{9}{(k^2-1)(4k^2-1)} \\ = \frac{-12}{4k^2-1} + \frac{3}{k^2-1} \\ = \frac{6}{2k+1} - \frac{6}{2k-1} - \frac{3}{2} \cdot \frac{1}{k+1} + \frac{3}{2} \cdot \frac{1}{k-1} \\$

With $k=2n \; (n \geq 1)$ we have

$S= \sum_{n=1}^{\infty}a_n = \sum_{n=1}^{\infty}\Big{(} \Big{(} \frac{6}{4n+1} - \frac{6}{4n-1}\Big{)} - \Big{(} \frac{3}{2} \cdot \frac{1}{2n+1} - \frac{3}{2} \cdot \frac{1}{2n-1}\Big{)}\Big{)} \\ \overset{(*)}= 6 \cdot (\frac{\pi}{4} - 1) - \frac{3}{2} \cdot (- \frac{1}{2\cdot 1 - 1}) = \frac{1}{2} (3\pi - 9) ≈ 0.212388980_4$

where I used for (*) Leibniz' (1682) formula for $\frac{\pi}{4}$ as also used in a previous challenge and the telescope property for the latter (and hopefully avoided typos).

Last edited: Sep 1, 2016
16. Sep 2, 2016

### jbriggs444

For problem 1, one assumes that you wish to disallow the trivial arithmetic progression: 0, 0, 0, 0 ...

17. Sep 2, 2016

### micromass

I don't know if the lion's plan is less intelligent. After all the mean difference is that in your scenario, the prey starts in the middle. While in my scenario, he starts at the edge. So it's a it different.

18. Sep 2, 2016

### micromass

Fixed it, thanks!

19. Sep 2, 2016

If you try working the Capt. Kirk problem, (and a urge the readers to do this with a constant $d \theta/dt$ until he gets to the $r=(1/4)R$ point), I think they will find it to be quite simple. Meanwhile, the lion problem turns out to be a much more difficult differential equation containing both the coordinates of the man and the coordinates of the lion. I don't know whether I will be able to obtain a solution.

20. Sep 2, 2016

### micromass

Assuming you have the correct equation, it does have a nice closed form solution.
If you do solve it, feel free to post its solution. It doesn't matter that you've seen a similar problem before, as long as this one is new (which it apparently is).

21. Sep 2, 2016

### Staff: Mentor

The lion's strategy is optimal, assuming Daniel can instantly change his direction. If the lion would choose any other path, Daniel could take advantage of it by choosing a direction that goes away from the lion.

22. Sep 2, 2016

### Erland

Let's change the notation a little:

For $B\subseteq \mathbb R$, let $B^c$ be the complement of $B$ w.r.t. $\mathbb R$, let $B^*$ be the closure of $B$, and let $B^o$ the interior of $B$.

We know that:

i. $B^{cc}=B$
ii. $B^{**}=B^*$
iii. $B^{oo}=B^o$
iv. $B^{c*}=B^{oc}$
v. $B^{co}=B^{*c}$
vi. $B^o\subseteq B\subseteq B^*$

It follows from vi and ii that $B^{*o*o}\subseteq B^{***o}=B^{*o}$, and from iii and vi it follows that $B^{*o}=B^{*ooo}\subseteq B^{*o*o}$. Thus:

vii. $B^{*o*o}=B^{*o}$.

In a similar manner, it follows also that:

viii. $B^{o*o*}=B^{o*}$.

Now, given $A\subseteq \mathbb R$, consider the following 14 subsets of $\mathbb R$:

1a. $A$. 1b. $A^c$.
2a. $A^*$. 2b. $A^{*c}$.
3a. $A^o$. 3b. $A^{oc}$.
4a. $A^{*o}$. 4b. $A^{*oc}$.
5a. $A^{o*}$. 5b. $A^{o*c}$.
6a. $A^{*o*}$. 6b. $A^{*o*c}$.
7a. $A^{o*o}$. 7b. $A^{o*oc}$.

Since, by i and v, $B^o=B^{cco}=B^{c*c}$ for all $B\subseteq \mathbb R$, it follows that all these 14 sets can be generated from $A$ by finitely many applications of $^c$ and $^*$.

If we apply $^c$ to any of the sets in the a-column, we get the corresponding set in the b-column (1a becomes 1b, 2a becomes 2b, etc.), and, by i, we get the sets in the a-column by applying $^c$ to the corresponding sets in the b-column. Thus, application of $^c$ to any of these 14 sets gives us back one of these sets.

We must prove that the same holds for application of $^*$ to any of these sets.

1a becomes 2a
1b becomes 3b, by iv
2a becomes 2a, by ii
2b becomes 4b, by iv
3a becomes 5a
3b becomes 3b, by iv and iii
4a becomes 6a
4b becomes 4b, by iv and iii
5a becomes 5a, by ii
5b becomes 7b, by iv
6a becomes 6a, by ii
6b becomes 4b, by iv and vii
7a becomes 5a, by viii
7b becomes 7b, by iv and iii

Thus, application of $^*$ to any of these 14 sets gives us back one of these sets.

We have proved that these 14 sets, and only those, can be generated from A by finitely many applications of $^c$ and $^*$.

It remains to prove that these 14 sets are mutually distinct for at least one set $A\subseteq\mathbb R$. To do this we choose

$A=\{-1\}\cup(\,]0,1[\,\cap \,\mathbb Q)\,\cup\,]1,2[\,\cup\,]2,\infty[$ .

Then, our 7 a-sets (1a-7a) are:

1a. $\{-1\}\cup(\,]0,1[\,\cap \,\mathbb Q)\,\cup\,]1,2[\,\cup\,]2,\infty[$
2a. $\{-1\}\cup[0,\infty[$
3a. $]1,2[\,\cup\,]2,\infty[$
4a. $]0,\infty[$
5a. $[1,\infty[$
6a. $[0,\infty[$
7a. $]1,\infty[$

These 7 sets are mutually distinct. It follows that the 7 b-sets (1b-7b) are also mutually distinct, since they are the complements of the a-sets. Also, no a-set can be equal to any b-set, because all the a-sets contain (i.e.) 3, while no b-set does. Hence, all these 14 sets are mutually distict.

We have proved that the maximal number of sets which can be generated from a subset $A\subseteq \mathbb R$ by finitely many applications of $^c$ and $^*$ is 14.

23. Sep 2, 2016

### micromass

24. Sep 2, 2016

### ProfuselyQuarky

For the first high school challenge....
The man has two children and one of them is a boy. The gender of the man’s son, however, is entirely independent from the gender of his sibling. Hence, the man can have either two boys, an older boy and a younger girl, or a younger girl with an older boy.

Boy, Boy
Boy, Girl
Girl, Boy

Without considering the Tuesday factor, there’s about a 33% chance of the man having two boys.

We are already given that the man has one son born on Tuesday. The boy’s sibling has the chance of being male or female as well as being born on any day of the week. That gives $14$ possibilities.

On top of that, we are not told whether the initial son is the eldest or the youngest. The second child might be either, so that, in turn, gives us $28$ possibilities rather than $14$. 14/28 is 50%. However, the instance of both children being born on Tuesday while both being male is accounted for twice. Thus, rather than having $28$ possibilities, there are really only $27$. $13$ of those $27$ scenarios consider the second child as a boy. Therefore, the probability that the man has a second son is 13/27, which is about 48%.

I was stupid enough at first to think that the fact that one of the son's was born on Tuesday was extraneous information, and on the surface it really sounds that way. Thank you for this riddle, micro, it occupied dead time.

25. Sep 2, 2016

### jbriggs444

What have you assumed about the probability that a random man encountered on the street will volunteer precisely the specified information? That is, can you firm up the sampling procedure?