# FeaturedI Micromass' big October challenge!

Tags:
1. Oct 1, 2016

### micromass

Staff Emeritus
Time for the october challenge! This time a lot of people sent me suggestions for challenges. I wish to thank them a lot! If you think of a good challenge that could be included here, don't hesitate to send me!

Ranking [and previous challenges] here: https://www.physicsforums.com/threads/micromass-big-challenge-ranking.879070/

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. SOLVED BY mfb Thanks to Charles Link I use the notation from the Frenet-Serret frame for curves:
a) Find the trajectory of an object moving in the $x$ direction with velocity $v_0$ at time $t=0$ that experiences a centripetal force (in the $N$ direction) that increases linearly with time (so that acceleration $a=btN$).
b) Does the speed of the object change?

2. Thanks to Erland
Definitions:
The following functions from $\mathbb N^k$ to $\mathbb N$, with $k\ge 0$, are called basic functions:

B1) The zero constant function $Z:\mathbb N^0\to \mathbb N$, given by $$Z()=0$$(so $Z$ is actually the constant $0$).

B2) For all $n\ge 0$ and $i$ such that $1\le i\le n$, the i:th n-ary projection function $P_i^n:\mathbb N^k\to\mathbb N$, given by $$P_i^n(x_1, x_2,\dots, x_n)=x_i,$$ for all $x_1,x_2,\dots,x_n\in \mathbb N$.

B3) The successor function $S:\mathbb N^1\to \mathbb N$, given by $$S(x_1)=x_1+1,$$ for all $x_1\in \mathbb N$.

We obtain new functions from old ones by applying the following operations:

O1) Composition: For all $m,n\ge 0$ and all functions $g:\mathbb N^m\to \mathbb N$ and $h_1,h_2,\dots, h_m:\mathbb N^n\to \mathbb N$, we obtain the function $f:\mathbb N^n\to \mathbb N$, given by
$$f(x_1,x_2,\dots, x_n)=g(h_1(x_1,x_2,\dots,x_n),h_2(x_1,x_2,\dots,x_n),\dots,h_m(x_1,x_2,\dots,x_n)),$$
for all $x_1,x_2,\dots,x_n\in \mathbb N$.

O2) Primitive recursion: For all $n\ge 0$ and all functions $g:\mathbb N^n\to\mathbb N$ and $h:\mathbb N^{n+2}\to\mathbb N$, we obtain the (unique) function $f:\mathbb N^{n+1}\to\mathbb N$ which satisfies the following conditions:

i)
$$f(x_1,x_2,\dots,x_n,0)=g(x_1,x_2,\dots,x_n),$$
for all $x_1,x_2,\dots,x_n\in\mathbb N$,

ii)
$$f(x_1,x_2,\dots,x_n,x_{n+1}+1)=h(x_1,x_2,\dots, x_n, x_{n+1},f(x_1,x_2,\dots,x_n,x_{n+1})),$$
for all $x_1,x_2,\dots,x_n,x_{n+1}\in\mathbb N$.

A function $f:\mathbb N^n\to \mathbb N$, for any $n\ge 0$, is called primitive recursive if it can be obtained from the basic functions B1-B3 by finitely many applications of the operations O1 and O2.

Ackermann's function is the (unique) function $A:\mathbb N^2\to \mathbb N$ which satisfies the following conditions:

a) $A(0,n)=n+1$,
b) $A(m+1,0)=A(m,1)$,
c) $A(m+1,n+1)=A(m,A(m+1,n))$,

for all $m,n\in \mathbb N$.

a) Prove that the factorial function $n!$ is primitive recursive.
b) Prove that the "truncated subtraction" $f(a,b) = \max\{a-b,0\}$ is primitive recursive.
c) Prove that to each primitive recursive function $f:\mathbb N^n\to \mathbb N$, for any $n\ge 0$, there is an $m\in\mathbb N$ such that
$$f(x_1,x_2,\dots,x_n)\le A(m, \max_{1\le i\le n} x_i),$$
for all $x_1,x_2,\dots, x_n\in\mathbb N$.
d) Prove that $A$ is not primitive recursive.

3) 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$.
Find (in ZFC) the number (= cardinality) of all generalized limits.

4) A pirate ship is at the origin of $\mathbb{R}^2$. A merchant vessel is at $(x_0,0)$ with $x_0\neq 0$ as is sailing vertically upwards with constant speed $v$. The pirate vessel is sailing with constant speed $V$ in such a way that at every instant it is always sailing directly towards the merchant vessel.
a) SOLVED BY Charles Link Find the curve in which the pirate vessel moves.
b) SOLVED BY Charles Link For $V>v$, find the total distance traveled by the pirate ship until they capture the merchant vessel.
c) SOLVED BY Chestermiller In the case $v=V$ show that the pirate ship will lag behind the merchant vessel endlessly. Find the asymptotic distance between pirate ship and merchant vessel.

5) SOLVED BY mfb Consider the recursion relation $S_{n+2} = 2(S_{n+1} - S_n)$ with $S_1 = a$ and $S_2 = b$. Find all $a$ and $b$ such that $S_n = 0$ for infinitely many $n$.

6) SOLVED BY Erland Suppose $X$ and $Y$ are independent random variables distributed according to a uniform distribution on $[0,1]$. Find the distribution of $X^Y$.

7) SOLVED BY TeethWhitener A laser is located $b$ units directly across from position $a$ on an infinite straight wall. An angle $\theta$ is chosen uniformly out of $(-\pi/2,\pi/2)$ and the laser is positioned such that it makes an angle $\theta$ when shining on the wall. Find the expected value and the variance of the random variable $X$ which is the (signed) distance from $a$.

8) SOLVED BY Fightfish 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.

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

10) SOLVED BY Fightfish 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.

1) Show that it is impossible to find four distinct squares as the subsequent elements in an arithmetic progression.
The following sketch may be used (credit will be given for each step, and not just for the entire problem!)
STEP 1:
Assume $\alpha$, $\beta$, $\gamma$ and $\delta$ are four distinct squares that are consecutive elements of an arithmetic progression.
Show that we may assume that they are relatively prime nonnegative integers.
Show that $\text{gcd}(\alpha,\beta) = \text{gcd}(\beta,\gamma) = \text{gcd}(\gamma,\delta) = 1$ and that $\alpha$, $\beta$, $\gamma$, $\delta$ are all odd.
Show that $\text{gcd}(\beta+\alpha, \beta - \alpha) = \text{gcd}(\gamma + \beta,\gamma - \beta) = \text{gcd}(\delta+\gamma,\delta - \gamma) = 2$.

STEP 2:
Define
$$2a = \text{gcd}(\beta+\alpha,\gamma + \beta)$$
$$2b = \text{gcd}(\beta + \alpha, \gamma - \beta)$$
$$2c = \text{gcd}(\beta - \alpha, \gamma + \beta)$$
$$2d = \text{gcd}(\beta-\alpha, \gamma-\beta)$$
Show
$$\beta +\alpha = 2ab,~\beta-\alpha = 2cd$$
$$\gamma + \beta = 2ac,~\gamma-\beta = 2bd$$
$$\delta + \gamma = 2bc,~\delta - \gamma = 2ad$$

STEP 3:
Show that $(a+d)b = (a-d)c$and $(c+d)a = (c-d)b$.
Show that $\text{gcd}(a+d, a-d)$ and $\text{gcd}(c+d,c-d)$ are both either $1$ or $2$.
Show that
$$a+d = mc,~a-d= mb$$
$$c+d = nb,~c-d=na$$
with $m,n\in \{1,2\}$.

2) SOLVED BY TeethWhitener 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)$.
Hint: Use Jensen's inequality with the function $x^{p/q}$.

3) SOLVED BY mfb 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.
Note: an answer that comes from a simulation program will be accepted! Be sure to present both the answer and the program you used.

CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:

1) Let $A,B,C,D$ be complex numbers with length $1$. Prove that if $A+B+C+D=0$, then these four numbers form a rectangle.

2) On an arbitrary triangle, we produce on each side an equilateral triangle. Prove that the centroids of these three triangles forms an equilateral triangle.

3) SOLVED BY Biker Find the total area of the red spot below:

4) SOLVED BY MAGNIBORO A man starts at the origin of $\mathbb{R}^2$. He walks $1$ meter left and $1$ meter up. He walks then $1/2$ of the last distance right. He walks $1/3$ of the last distance down. He walks $1/4$ of the last distance left. Thus the man walks in a spiral. Where does he converge to?

5). SOLVED BY MAGNIBORO Thanks to Erland Ackermann's function is the (unique) function $A:\mathbb N^2\to \mathbb N$ which satisfies the following conditions:

a) $A(0,n)=n+1$,
b) $A(m+1,0)=A(m,1)$,
c) $A(m+1,n+1)=A(m,A(m+1,n))$,

for all $m,n\in \mathbb N$.

a) Find (and prove) a closed form expression for $A(1,n)$.
b) Find (and prove) a closed form expression for $A(2,n)$.
c) Find (and prove) a closed form expression for $A(3,n)$.

6) Thanks to Math_QED Consider the integrals I and J.

$I = \int\limits_0^{\frac{\pi}{2}}\frac{\sin x\cos x}{x+1}dx$
$J = \int\limits_0^{\pi}\frac{\cos x}{(x+2)^{2}}dx$

What is I in function of J?

7) Compute the integral $\int \sqrt{\tan(x)}dx$ (the final answer must be written with elementary functions only).

8) Thanks to mfb Find all bases $b>6$ where $5654$ is a prime power.

9) SOLVED BY MAGNIBORO Thanks to Math_QED Let $I_n = \int\limits_0^1 x^n\sqrt{1-x}dx$

Show that $I_n = \frac{2n}{2n+3}I_{n-1} \quad \forall n \in \mathbb{N}\backslash\{0\}$

10) Thanks to Math_QED Calculate:

$\int\limits_{-1}^1\frac{1}{(e^x+1)(x^2 +1)}dx$

11) Thanks to Math_QED Calculate:

$\int \frac{\sqrt[6]{\frac{x}{x-3}} - \sqrt[4]{\frac{x}{x-3}}}{x^2 -3x}dx$

12). Thanks to Math_QED Prove that every matrix $A \in M_{n,n}(\mathbb{R})$ can be written as the sum of a symmetric and an antisymmetrix matrix.

PREVIOUS CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:

1) Show that for $0<\lambda<1$ and $\alpha,\beta\geq 0$ holds
$$\alpha^\lambda \beta^{1-\lambda}\leq \lambda \alpha+(1-\lambda)\beta$$
Hint: Fix all but one of the variables and use derivatives.

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

### Staff: Mentor

With problems that long, some clearer separation between the problems would help.

As far as I can see, we have some ambiguity concerning the initial direction of N. Let it point in the y-direction, and introduce a complex coordinate, the real part is x and the imaginary part is y. The acceleration is then given by $\dot v(t) = i b t \frac{v(t)}{|v(t)|}$. Use the ansatz $v(t)=v_0e^{iwt^2}$. Then $\dot v(t) = 2iv_0wt e^{iwt^2}$. Plugging this into the differential equation leads to $2iv_0^2wt e^{iwt^2} = i b t v_0e^{iwt^2}$. Simplification shows that $2v_0w = b$. Therefore, $$v(t)=v_0 \exp(\frac{ibt^2}{2v_0})$$
As we can see, the speed does not change.

Splitting it into components again, $v_x = v_0 \cos(\frac{bt^2}{2v_0})$ and $v_y = v_0 \sin(\frac{bt^2}{2v_0})$. To check the method from above we can calculate the derivatives of those:
$a_x = - bt \sin(\frac{bt^2}{2v_0})$ and $a_y = bt \cos(\frac{bt^2}{2v_0})$. The magnitude is "bt" as expected and it is always orthogonal to the velocity as well.

To find the position as function of time, we have to integrate cos(x2) which does not have a solution in closed form, but of course it is possible finding the position using the Fresnel integral. There might be a function for the path (but not the position as function of time) that avoids this issue, I don't know.

There is the trivial case of a=b=0 where all elements are zero. Apart from that:
Consider an arbitrary series that has a zero at some point: Sc = 0, Sc+1 = d for some d. Then Sc+2 = 2d, Sc+3 = 2d, Sc+4 = 0 and Sc+5 = -4d. As we can see, if a series has 0 at some point we get some pseudo-repetition with Sc+4 = -4Sc+0. The series is also unique in its backward evolution: If we know Sc=0 then Sc-4=0 with the same argument. A series has either zeros everywhere, zeros exactly every 4th step, or no zeros. That allows a classification of all series which have infinitely many zeros:

a=0 and b arbitrary
b=0 and a arbitrary
a=b
2a=b

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

### Fightfish

Problem 10

Let $x_{n}$ denote the value of the $n$-th digit of the number. One immediate constraint that follows is that $\sum x_{n} = 10$ since $x_{n}$ represents the number of times the digit $n$ appears in the number. Suppose that $x_{0} = \alpha$, where $\alpha$ is obviously non-zero. Then there are $(9-\alpha)$ nonzero elements (one of which is $x_\alpha$ which must sum up to $(10-\alpha)$. It is thus clear that all of these nonzero elements must be unity except for one that has the value $2$. Thus, we have $x_{2} = 1$, which forces $x_{1} = 2$ and $x_{\alpha} = 1$. There can be no other non-zero elements, and so it must be the case that $9 - \alpha = 3$.
Hence, $\{x_{0} = 6, x_{1} = 2, x_{2} = 1, x_{6} = 1 \}$ with the rest being zero is the only solution.

4. Oct 1, 2016

### Fightfish

Problem 8

Not sure how much detail you want here - but the answer seems to follow directly from the theorems pertaining to permutations/transpositions. In particular, that any particular permutation is of definite parity: if a permutation can be represented as an odd (even) number of transpositions, then it cannot be decomposed into an even (odd) number of transpositions. Here, we see that one possible decomposition involves $(1\,\,2016)(2\,\,2015) \cdots (1008\,\,1009)$, which is an even number of transpositions. Thus, by that theorem, there does not exist any other decomposition that contains an odd number of transpositions.

5. Oct 1, 2016

### Stella.Physics

for UNSOLVED ADVANCED CHALLENGES #3. When you say proportion of the wire painted, you mean for an individual bird or for the sum?
do the birds occupy space on the wire or are they dimensionless?

6. Oct 1, 2016

### micromass

Staff Emeritus
The total sum of the painted pieces.

They are pointlike.

7. Oct 1, 2016

### Stella.Physics

before writing down my calculations is the proportion $\frac{2(n-1)}{n}$ ?

8. Oct 1, 2016

### micromass

Staff Emeritus
I'm not saying anything without solution. But I have no idea what $n$ is. I don't expect a dependence on a number $n$.

9. Oct 1, 2016

### Stella.Physics

sorry my bad, n is the number of birds :P

10. Oct 1, 2016

### micromass

Staff Emeritus
Read the problem carefully. The number of birds should not enter into the solution.

11. Oct 1, 2016

### Stella.Physics

So there are 2 problems the first with random distribution and the second with a uniform distribution.
So the question to the first problem is: about the proportion that is painted, is this about the whole painted area from the first to the last bird or should I take into account the areas that would be double painted?

12. Oct 1, 2016

### micromass

Staff Emeritus
No, there is one problem. The birds have uniform distribution, and you are supposed to find the asymptotic proportion of the painted wire.

13. Oct 1, 2016

### Stella.Physics

OK, now it's clear thank you. What about the double painted areas, can the proportion value be over 1? Meaning taking double painted areas into account.

14. Oct 1, 2016

### micromass

Staff Emeritus
Double painted = painted. So proportion cannot be bigger than 1.

15. Oct 1, 2016

### Stella.Physics

OK so this is what I have done so far, in simple thinking

n is the number of the birds
L is the length of the wire
P is the painted area
z is the distance between 2 birds In a homogeneous distribution
and z/2 is the distance from the end of the wire to the birds sitting at both ends of the distribution.

So P=(n-1)z
L = P+ 2 $\frac{z}{2}$ = (n-1)z+z=zn ⇒ z= $\frac{L}{n}$

so the proportion is $\frac{P}{L}$ = $\frac{(n-1)z}{zn}$ = $\frac{n-1}{n}$ = 1 - $\frac{1}{n}$

so of course if the number of birds goes to infinity the proportion becomes 1.

How come and the number of birds cannot affect the final painted proportion like you say?

16. Oct 1, 2016

### micromass

Staff Emeritus
That is not the correct answer.

17. Oct 1, 2016

### Staff: Mentor

Read the problem statement more carefully. A piece of wire is painted only if it is the connection to the closest neighbor for any bird.

18. Oct 2, 2016

### Stella.Physics

The distribution is uniform meaning that each bird is the closest neighbor to the previous one and next one, as they are equally spaced. Except from the two birds sitting on the edges. And we want to know what part of the wire is painted, not the distance of yellow paint, so I left out the areas that where painted 2 times since they are between two neighbor birds.
So I think I've used this kind of thinking in my image.
This one has been puzzling me since last night :P

A second thought was that the first bird will sit on the middle (L/2) of the wire and then the others on the quarters (L/4) and so on....so I could use a Taylor series, but then the part "a large number of birds land on it at random" would be ruined :P

19. Oct 2, 2016

### micromass

Staff Emeritus
That is not what uniform distribution means

20. Oct 2, 2016

### aheight

#5: (Derivation: just put the small piece in lower left corner in upper top corner, then half of the center red piece on the top to get a square 10x10. Then the area of the red is equal to 100 - the circle area and the small piece in lower left which is equal to the area in the bracket below. Use quadratic formula to find $(x_0,y_0)$.

red=$\left(100-25\pi\right)-\biggr[1/2(x_0 y_0)+\int_{x_0}^{5} \left(5+\sqrt{25-(x-5)^2}\right)dx\biggr]$
where the point $(x_0,y_0)$ is the solution to the simultaneous equations $y=1/2x$ and $y=5+\sqrt{25-(x-5)^2}$.

Last edited: Oct 2, 2016