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} 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!

 

[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} ∑(-1)^n/(x^n*n!)~\text{if}~x>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} ∑(-1)^n/(x^n*n!)~\text{if}~x>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$.)