Challenge Micromass' big September challenge

[micromass]

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

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

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

PREVIOUS UNSOLVED ADVANCED CHALLENGES:
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}<br /> e^{-1/x}~\text{if}~x&gt;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!

 

[fresh_42]

1. Show that it is impossible to find four squares in an arithmetic progression.

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?

 

[micromass]

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?

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

 

[Ygggdrasil]

1. Show that it is impossible to find four squares in an arithmetic progression.

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

 

[member 587159]

High school challenges 2)

I used a calculator to find the partial sums S₀, S₁, S₂, ... and I found the sequence: 1/5, -2/17, 3/37, -4/65, 5/101, ...
So, S_n = (-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 S₀ = 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 S_k+1 = (-1)^(k+1)*(k+2)/(4k^2+16k+17) using S_k =(-1)^k*(k+1)/(4k^2+8k + 5).

S_k+1 = S_k + (-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.

 

[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

 

[member 587159]

Highschool challenges 3b)

Not too sure about this one.

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}<br /> ∑(-1)^n/(x^n*n!)~\text{if}~x&gt;0\\ 0~\text{if}~x\leq 0\end{array}\right.

 

[micromass]

Highschool challenges 3b)

Not too sure about this one.

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}<br /> ∑(-1)^n/(x^n*n!)~\text{if}~x&gt;0\\ 0~\text{if}~x\leq 0\end{array}\right.

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.

 

[Erland]

About Advanced Problem 2:

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.

 

[micromass]

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?

No, sorry.

 

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

 

[mfb]

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.

1. Show that it is impossible to find four squares in an arithmetic progression.

Start with the observation that, mod 2ⁿ, all possible remainders of squares (all quadratic residues) can be expressed as 4^k(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 2ⁿ 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 2ⁿ 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.

 

[micromass]

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

Yes.

 

[Charles Link]

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

 

[fresh_42]

This is what I have for AC 4.

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

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

 

[jbriggs444]

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

 

[micromass]

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

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.

 

[micromass]

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

Fixed it, thanks!

 

[Charles Link]

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.

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.

 

[micromass]

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.

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

 

[mfb]

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.

 

[Erland]

Advanced Problem 3:

The answer in 14.

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.

 

[micromass]

Very nice proof! Anybody interested in more should read the following pdf: http://nzjm.math.auckland.ac.nz/images/6/63/The_Kuratowski_Closure-Complement_Theorem.pdf

 

[ProfuselyQuarky]

For the first high school challenge...

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

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.

 

[jbriggs444]

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.

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?

 

[member 587159]

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.

Nice solution. I didn't even try that one as I'm very bad at probability questions. You seem to be good at those kind of questions (also regarding your other replies in the high school challenge thread), so I'm a bit jaleous ;)

 

[PeroK]

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.

Perhaps it is extraneous information. How about this as an alternative solution:

There must be some process by which the man decides what to tell you. So, assume he mentally tosses a coin to decide whether to tell you about his older or younger child. Let's assume he chooses the older child, who is a boy born on a Tuesday. That doesn't affect the younger child at all, who is a girl or boy with equal probability. So, is the answer not 50%?

Or, look at it this way. After you've calculated 13/27, the man adds "his name is Alfonso and he is going to study maths at university next year". Now, you have to recalculate based on all the new information about him. That doesn't seem quite right. Now you know his name, the probability the other child is a boy changes?

 

[micromass]

"his name is Alfonso and he is going to study maths at university next year".

But would that information change anything? It's quite distinct from the "tuesday" information because the day of the week are 7 distinct possibilities of which one has to occur. The Alfonso information is not like that at all.

 

[mfb]

But would that information change anything? It's quite distinct from the "tuesday" information because the day of the week are 7 distinct possibilities of which one has to occur. The Alfonso information is not like that at all.

You can make a full list of possible names, Alfonso is one of them. Same for everything else. Although their names are clearly not independent.
If you get enough information, the probability approaches 50%, because you then get information about one particular person and the probability that it applies to both becomes negligible.

The main problem with this problem is still the assumption that the father just happens to tell you this information independently of the number of sons born on a Tuesday he has (as long as it is at least 1). It is better to let someone else (e. g. you) ask.

 

[micromass]

You can make a full list of possible names, Alfonso is one of them. Same for everything else. Although their names are clearly not independent.

Right, but that requires a lot of assumptions. With weekdays I know that it's relatively certain that the probability of being born on any weekday is $1/7$. I have no such information on names. So in order to make use of the Alfonso information, we would have to know some kind of probability distribution of the different kind of names. And then we would need to assume that the names were chosen at random too. I really think this is very different from giving the tuesday information.

 

[jbriggs444]

I really think this is very different from giving the tuesday information.

Different in that it makes the problem more complex, yes. But not different in the sense that it still ignores the problem of a self-selected sample.

 

[Thecla]

Regarding the two sons problem -How would the probability change if the man says I have 2 children. One of them is a son born on the 117 th day of the year. What is the other child is also a son?

 

[Thecla]

I am sorry for the above post. What is the probability the other child is also a son?

 

[Incand]

Regarding the two sons problem -How would the probability change if the man says I have 2 children. One of them is a son born on the 117 th day of the year. What is the other child is also a son?

The reasoning should be the same.
If the first child is $M_{117}$ then $P(M_{117},M ) = 365/(365\cdot 2)$
And if the second child is $M_{117}$ then $P(M,M_{117}) = 365/(365\cdot 2)$
Summing up the cases we have $365/730$; However $(M_{117},M_{117})$ are accounted twice so we get $364/729$.

 

[Erland]

Advanced Problem 6:

First, let $s(t)$ be the distance along the circle from Daniel's starting point P to his postion D at time $t\in[0,\frac{\pi a}u[$, where we stipulate that $s(t)\ge 0$ for a counterclockwise path from P to D, and $s(t)\le0$ for a clockwise path.

For every $t\in[0,\frac{\pi a}u[$, $\frac{ds}{dt}=\pm u$ (otherwise, Daniel cannot have the speed $u$ at every moment). By Darboux's Theorem, $\frac{ds}{dt}$ has the Intermediate Value Property. But then, if there are $t_1,t_2\in [0,\frac{\pi a}u[$ with $s(t_1)=u$ and $s(t_2)=-u$, the Intermediate Value Property would give $\frac{ds}{dt}=0$ at some $t$ between $t_1$ and $t_2$, which contradicts $\frac{ds}{dt}=\pm u$. Therefore, we must have either $\frac{ds}{dt}=u$ for all $t\in[0,\frac{\pi a}u[$ or $\frac{ds}{dt}=-u$ for all $t\in[0,\frac{\pi a}u[$.
Assume, without loss of generality, that $\frac{ds}{dt}=u$ for all $t\in[0,\frac{\pi a}u[$ (otherwise, we just redefine the positive direction to be the clockwise one).

We can regard the circle as lying in the complex plane $\mathbb C$ with its centre at the origin and Daniel's starting point P at $a$. Then, Daniel's position at $t\in[0,\frac{\pi a}u[$ is $w(t)=ae^{i\frac uat}$. The lions position at this $t$ is $z(t)=r(t)e^{i\frac uat}$, where $r(t)\ge 0$ (real).

Now, $|\frac{dz}{dt}|=u$, but since

$\frac{dz}{dt}=(\frac{dr}{dt}+i\frac uar)e^{i\frac uat}$, we obtain

$(\frac {dr}{dt})^2+\frac {u^2}{a^2}r^2 =u^2$, which gives

$\frac 1{\sqrt{1-\frac {r^2}{a^2}}}\frac {dr}{dt}=u$,

provided that $t$ is so small so that $r<a$ and $\frac{dr}{dt}>0$ (these certainly hold at $t=0$).

This is a separable differential equation. Solving it gives:

$a\arcsin\frac ra = ut +C$.

Since $r(0)=0$, we can take $C=0$, so

$r=a\sin\frac ua t$.

From this, it follows that $r\to a$ as $t\to \frac\pi2\frac au$. This means that the lion catches Daniel at $t=\frac\pi2\frac au$, and then Daniel has traversed the distance $\frac\pi2 a$ (a quarter of a lap around the circle).

The lion has the same speed as Daniel and has therefore traversed the same distance as him: $\frac\pi2 a$, which is the answer of the problem.

(A further analysis shows that the lion traverses a semicircle with radius $\frac a2$ and centre at $\frac a2i$.)

 

[micromass]

Nice! I should add that this problem came from Gregory's Classical Mechanics.
https://www.amazon.com/dp/0521534097/?tag=pfamazon01-20

 

[mfb]

Nice analysis.

(A further analysis shows that the lion traverses a semicircle with radius $\frac a2$ and centre at $\frac a2i$.)

That property allows a purely geometric proof. The trajectory is unique, so we just have to show that the semi-circle is a solution.
Let O be the origin, D(t) be the position of Daniel, L(t) is the position of the lion, X the point where they meet and M be the point in the middle between X and O. We know the angle MOD is equal to the angle MOL as the lion is always on the line OL. Via the tangent half-angle formula, MOL = 1/2 XML.

MOD(t) is a linear function starting at pi/2 going to 0, therefore XML(t) = 2 MOD(t) is also a linear function starting at pi and going to zero. And that is exactly the condition for a constant speed on the circle, so this trajectory gives a constant lion speed.

Pun not intended[/size]

Edit: fixed angle name.

 

[Erland]

Nice mfb, I did suspect there was a geometric solution...

MOL = 1/2 MXL.

MOD(t) is a linear function starting at pi/2 going to 0, therefore MXL(t) = 2 MOD(t) is also a linear function starting at pi and going to zero.

You mean XML, not MXL, right?

 

[strangerep]

[...] the day of the week are 7 distinct possibilities of which one has to occur..

Huh? I must be missing something.

Perhaps I am stupid enough to think that the fact that one of the sons was born on Tuesday is extraneous information.

The man could have twin boys, born on the same date. Or boys of different ages, both born on a Tuesday. So why is the answer not a simple 50%?

Imho, it's like saying: "I just threw a 6 on a (6-sided) die. Now what is the probability that my next throw will also be a 6?" (The result of the first throw is irrelevant because each throw is an independent event.)

 

[fresh_42]

Nice solution. I didn't even try that one as I'm very bad at probability questions. You seem to be good at those kind of questions (also regarding your other replies in the high school challenge thread), so I'm a bit jaleous ;)

No need. There will always be someone brighter than us. Imagine how obnoxious we would be if we knew everything!
@Erland has beaten me as I was one my way typing in a wrong answer. It's part of the fun to be amazed.
I only regret that I can't memorize all these innovative ideas.

 

[jbriggs444]

Imho, it's like saying: "I just threw a 6 on a (6-sided) die. Now what is the probability that my next throw will also be a 6?" (The result of the first throw is irrelevant because each throw is an independent event.)

Suppse you repeatedly roll two dice until at least one of them comes up six. What is the probability that both are sixes: One in eleven.

You could roll:

1 6: Nope
2 6: Nope
3 6: Nope
4 6: Nope
5 6: Nope
6 6: Yep
6 5: Nope
6 4: Nope
6 3: Nope
6 2: Nope
6 1: Nope

 

[strangerep]

Suppse you repeatedly roll two dice until at least one of them comes up six. What is the probability that both are sixes: One in eleven.

You could roll:

1 6: Nope
2 6: Nope
3 6: Nope
4 6: Nope
5 6: Nope
6 6: Yep
6 5: Nope
6 4: Nope
6 3: Nope
6 2: Nope
6 1: Nope

I don't see how that's not applicable to the current problem. The guy does not keep on conceiving children, discarding daughters until he gets a son, then conceiving more children.

But I guess there's a difference between a guy who already has 2 children, compared to a guy who already has a son and is about to conceive a 2nd child. In the former case, there's initially 4 equal-prob* possibilities for a guy with 2 children:

(a) B B
(b) B G
(c) G B
(d) G G

We're told that possibility (d) is ruled out, leaving only 3 possibilities. Only 1 of those is B+B, so the relevant probability is 1/3.

Or am I still missing something?? (I still don't see the relevance of "Tuesday".)

[*] This assumes the guy is not from a culture that practices female infanticide.

 

[jbriggs444]

Or am I still missing something?? (I still don't see the relevance of "Tuesday".)

The answer has already been given.

Lay out a 14 by 14 grid of possibilities on a piece of paper. First child on the horizontal axis, second child on the vertical axis. Label the rows and columns with the various possibilities -- Monday girl, Friday boy, etc.

Now highlight the column where the first child is a boy born on a Tuesday. Repeat for the column where the second child is a boy born on a Tuesday. How many squares do you have highlighted total? 27.

Now, look at the column where the first child is a Tuesday boy. Of those 14 squares there are 7 where the other child is a girl and 7 where the other child is a boy. One of the "boy" squares is the intersection of the highlighted row and column. Repeat for the row where the second child is a Tuesday boy. Again, there are 7 squares where the other child is a girl and 7 where the other child is a boy. But the intersection has already been counted. So that's 7 girl squares and only 6 boy squares.

7 + 6 = 13 "boy" squares out of a total of 27. 14 "girl" squares out of 27.

A sampling procedure that will make the problem well formed is that you poll people on the street until you find a family with exactly two children, at least one of whom is a boy born on a Tuesday. You then ask whether both children are boys. Out of 196 two-child parents polled, 27 will fit the profile. In 13 of those cases both children will be boys.

 

[strangerep]

Lay out a 14 by 14 grid of possibilities on a piece of paper. [...]

OK. Thanks. I guess I am indeed stoopid.

 

[PeroK]

The answer has already been given.

Lay out a 14 by 14 grid of possibilities on a piece of paper. First child on the horizontal axis, second child on the vertical axis. Label the rows and columns with the various possibilities -- Monday girl, Friday boy, etc.

Now highlight the column where the first child is a boy born on a Tuesday. Repeat for the column where the second child is a boy born on a Tuesday. How many squares do you have highlighted total? 27.

Now, look at the column where the first child is a Tuesday boy. Of those 14 squares there are 7 where the other child is a girl and 7 where the other child is a boy. One of the "boy" squares is the intersection of the highlighted row and column. Repeat for the row where the second child is a Tuesday boy. Again, there are 7 squares where the other child is a girl and 7 where the other child is a boy. But the intersection has already been counted. So that's 7 girl squares and only 6 boy squares.

7 + 6 = 13 "boy" squares out of a total of 27. 14 "girl" squares out of 27.

A sampling procedure that will make the problem well formed is that you poll people on the street until you find a family with exactly two children, at least one of whom is a boy born on a Tuesday. You then ask whether both children are boys. Out of 196 two-child parents polled, 27 will fit the profile. In 13 of those cases both children will be boys.

If you use a sampling procedure based on the direct questions I suggested in post #6, namely:

Qu: How many children do you have?

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

Then, the answer given by @ProfuselyQuarky and @jbriggs444 is, of course, correct.

But, if, instead, you say:

"Tell me something about one of your children"

Then, this changes things, as follows (using the 196 equally likely families above):

The 1 man with two boys both born on a Tuesday is selected.

Only half (6) of the men with two boys (one Tuesday, one other day) are selected, because half of these men tell you about their other child. They say something like "I have a boy born on a Saturday", even though they also have a Tuesday boy.

Likewise only half (7) of the 14 men with a Tuesday boy and a girl are selected - because half of them tell you about the girl.

In this case, only 14 men are selected and, in fact, 7 have two boys and 7 have a boy and a girl.

This is why, in order to produce the problem originally intended, you need direct, specific questions in order select everyone with equal likelihood.

One final point, the issue here is a variation of this issue:

You meet someone and he says: "I have two children, one is son born on Tuesday, his name is Alfonso, he is 17 years old, studies mathematics and his favourite food is ice cream."

Nothing remarkable has happened.

But, if you meet someone and ask (witthout any prior knowledge): "Do you have two children, one is son born on Tuesday, his name is Alfonso, he is 17 years old, studies mathematics and his favourite food is ice cream?"

And, he says "yes", then something very unlikely has happened. This illustrates the probabilistic difference between volunteered information and information obtained through direct questions.

 

[Erland]

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

What do you mean by "the simplest fraction in $\left(\frac{a}{c},\frac{b}{d}\right)$"? $\frac{a+b}{c+d}$ does not contain $\frac ac$ and/or $\frac bd$ in any obvious way.

Aha, you mean the open interval $\left(\frac{a}{c},\frac{b}{d}\right)$!

 

[Charles Link]

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.

It turns out, I misread the problem slightly. The lion does keep his $d \theta /dt$ the same as the man's. I was mistaken in thinking the problem was saying the lion keeps its velocity vector always pointing at the man. The lion thereby uses the same approach of Capt. Kirk in the problem that I previously mentioned.

 

[QuantumQuest]

ADVANCED CHALLENGES: Problem 5

We will utilize AM - GM (Arithmetic Mean - Geometric Mean) inequality. This states that: $(a_{1}a_{2}...a_{n})^{\frac{1}{n}}\leq \frac{a_{1} + a_{2} + \cdots + a_{n}}{n}$. There are many proofs on the net for the weighted and unweighted AM - GM. For instance see Wikipedia: https://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means.

Applying this inequality for $a_{1},a_{2}, ..., a_{n}$ , $b_{1},b_{2},...,b_{n}$ and $a_{1} + b_{1}, a_{2} + b_{2}, ..., a_{n} + b_{n}$ adding them and dividing by the last inequality we have: $\frac{(a_{1}a_{2}...a_{n})^{\frac{1}{n}} + (b_{1}b_{2}...b_{n})^{\frac{1}{n}}}{{[(a_{1} + b_{1})(a_{2} + b_{2})...(a_{n} + b_{n})]}^\frac{1}{n}} =\prod_{i=1}^{n}\{ \frac{a_{i}}{a_{i} + b_{i}}\}^\frac{1}{n} + \prod_{i=1}^{n}\{ \frac{b_{i}}{a_{i} + b_{i}}\}^\frac{1}{n} \leq \frac{1}{n}\sum_{i = 1}^{n}\frac{a_{i}}{a_{i} + b_{i}} + \frac{1}{n}\sum_{i = 1}^{n}\frac{b_{i}}{a_{i} + b_{i}}$. But this last sum of $\sum_{}^{}$ equals to $1$. So, because $\prod_{i=1}^{n}\{ \frac{a_{i}}{a_{i} + b_{i}}\}^\frac{1}{n} + \prod_{i=1}^{n}\{ \frac{b_{i}}{a_{i} + b_{i}}\}^\frac{1}{n}$ is the inequality to be proved if we divide the left side by the right one we're done.

Now, the equality holds if and only if $a_{1} = a_{2} =\cdots= a_{n}$ and $b_{1} = b_{2} =\cdots= b_{n}$.

 

[Erland]

Advanced Problem 9.

$\frac ac < \frac pq$ is equivalent to $pc-aq>0$, or $\begin{vmatrix} p & a \\ q & c\end{vmatrix}>0$, and likewise, $\frac pq < \frac bd$ is equivalent to $\begin{vmatrix} b & p \\ d & q\end{vmatrix}>0$, provided that $q> 0$.

Using that $\begin{vmatrix} b & a \\ d & c\end{vmatrix}= bc-ad=1$, we then see that if $p,q\in\mathbb Z_+$, then $\frac ac < \frac pq < \frac bd$ holds if and only if x=\frac{\begin{vmatrix} p &amp; a \\ q &amp; c\end{vmatrix}}{\begin{vmatrix} b &amp; a \\ d &amp; c\end{vmatrix}}\in\mathbb Z_+ and y=\frac{\begin{vmatrix} b &amp; p \\ d &amp; q\end{vmatrix}}{\begin{vmatrix} b &amp; a \\ d &amp; c\end{vmatrix}}\in\mathbb Z_+ both hold.

By Cramer's rule, these $x$ and $y$ give the solution of the linear system \begin{cases}bx&amp;+&amp;ay&amp;=&amp;p\\dx&amp;+&amp;cy&amp;=&amp;q\end{cases}\tag{*}

(This solution exists and is unique, since $\begin{vmatrix} b & a \\ d & c\end{vmatrix}\neq 0$.)

The problem of finding $p,q\in \mathbb Z_+$, with $q$ minimal, satisfying $\frac ac < \frac pq < \frac bd$ is therefore equivalent to the problem of finding $p,q\in \mathbb Z_+$, with $q$ minimal, such that the system (*) has a solution $(x,y)$ with $x,y\in\mathbb Z_+$.

Since $a\in \mathbb N$ and $b,c,d\in\mathbb Z_+$, we easily find the unique solution of the latter problem if we put $x=y=1$, which gives $q=d+c$ and $p=b+a$. This is then also the unique solution of the former problem.

Thus, the fraction in $]\frac ac, \frac bd[$ with smallest possible (positive) denominator is $\frac{a+b}{c+d}$, Q.E.D.

Remark: As is seen in the proof, we could equally well have stipulated that the numerator should be the smallest possible (positive) one, provided that $a>0$.

 

[parshyaa]

Hii micromass I have a request for you please in next challenge post some more geometry problems just like in earliar challenge you posted donkey and area grazed by him problem.