Challenge Math Challenge - November 2019

[fresh_42]

Questions

1. (solved by @tnich ) Show that $\sin\dfrac{\pi}{m} \sin\dfrac{2\pi}{m}\sin\dfrac{3\pi}{m}\cdots \sin\dfrac{(m - 1)\pi}{m} = \dfrac{m}{2^{m - 1}}$ for $m$ = $2, 3, \dots$(@QuantumQuest)

2. (solved by @PeroK ) Show that when a quantity grows or decays exponentially, the rate of increase over a fixed time interval is constant (i.e. it depends only on the time interval and not on the time at which the interval begins). (@QuantumQuest)

3. (solved by @Antarres ) We define the weighted Hölder-mean as
$$
M_w^p :=\left(\sum_{k=1}^n w_kx_k^p\right)^{\frac{1}{p}} , \,M_w^0:=\lim_{p \to 0}M_w^p = \prod_{k=1}^n x_k^{w_k}
$$
for positive, real numbers $x_1,\ldots ,x_n > 0$ and a weight $w=(w_1,\ldots,w_n)$ with $w_1+\ldots +w_n=1\, , \,w_k>0$ and a $p \in \mathbb{R}-\{\,0\,\}.$
Prove $M_w^r \leq M_w^s$ whenever $r<s\,.$
Hint: Use Jensen's theorem for convex functions (see October 2019 / 8a). (@fresh_42)

4. Let $q$ be a rational number such that $\sin(\pi q )$ is rational. Show that $2\sin(\pi q)$ is an integer. (@Infrared)

5. (solved by @Fred Wright and @tnich ) Evaluate $\displaystyle{\int_0^{2\pi}} e^{\cos(\theta)}\cos(\sin(\theta))d\theta.$ (@Infrared)

6. Let $\{X_n\}_{n=1}^\infty$ be a sequence of independent random variables on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$.

(1) Show that $\mathbb{P}\left(\sum_{n=1}^\infty X_n \mathrm{\ converges \ in \ \mathbb{R}} \right) \in \{0,1\}$

(2) If in addition $\mathbb{E}[X_n^2] < \infty, \mathbb{E}[X_n] = 0$ for all $n \geq 1$ and $\sum_{n=1}^\infty \operatorname{Var}(X_n) < \infty$, show that the above probability is $1$.
(@Math_QED)

7. Consider the real $n$-dimensional projective space $\mathbb{R}P^{n+1}$ which is $\left(\mathbb{R}^{n+1}\setminus \{(0,\dots, 0)\}\right)/\sim$ where $\sim$ is the equivalence relation given by
$$(x_1, \dots, x_{n+1}) \sim (y_1, \dots, y_{n+1}) \iff \exists \lambda \neq 0: (x_1, \dots, x_{n+1}) = \lambda(y_1, \dots, y_{n+1})$$
Give $\mathbb{R}P^{n+1}$ the quotient topology. Show that this topological space is Hausdorff and second countable.
(@Math_QED)

8. Let $D$ be a division ring. Consider the matrix ring $R = M_n(D)$ of $n \times n$-matrices with coefficients in $D$. View $R$ as a (left) $R$-module in the natural way. Prove that up to isomorphism, $R$ has a unique simple $R$-submodule.
Hint: Composition series and the Jordan-Hölder theorem. (@Math_QED)

9. (solved by @PeroK ) Show that $\exp(y) \leq 1+y+y^2/2$ for $y < 0$. Since this is elementary, you cannot use any other inequalities without proof.
(@Math_QED)

10. (solved by @PeroK ) If $f$ has the real Fourier representation $$f(x)=\dfrac{a_0}{2}+\sum_{k=1}^\infty (a_k\cos kx + b_k\sin kx)$$ prove
$$
\dfrac{1}{\pi} \int_{-\pi}^{\pi}|f(x)|^2\,dx = \dfrac{a_0^2}{2}+\sum_{k=1}^{\infty}\left(a_k^2+b_k^2\right)
$$
(@fresh_42)

High Schoolers only

11. (solved by @Not anonymous ) A kid throws small balls upwards. It throws each ball when the previous thrown one is at the maximum height of its course. What is the height that balls reach if the kid throws two of them per second?

12. (solved by @etotheipi ) Which rain drops fall faster, small or big ones and why?

13. (solved by @Not anonymous ) A radio station at point $A$ transmits a signal which is received by the receivers $B$ and $C$. A listener located at $B$ is listening to the signal via his receiver and after one second hears the signal via receiver $C$ which has a strong loudspeaker. What is the distance between $B$ and $C$?

14. (solved by @Not anonymous and by @PeroK ) Mr. Smith on a full up flight with 50 passengers on a CRJ 100 had lost his boarding pass. The flight attendant tells him to sit anywhere. All other passengers sit on their booked seats, unless it is already occupied, in which case they randomly choose another seat just like Mr. Smith did. What are the chances that the last passenger gets the seat printed on his boarding pass?

15. (solved by @Not anonymous ) On the first flight day of a little island hopper there was no wind during the return flight. How does the total flight duration from outward and return flight change if, instead, a strong headwind blows on the way to the neighboring island - and on the way back, an equally strong tailwind?

 

[tnich]

Spoiler: Q1

$$\sin\frac{\pi}{m} \sin\frac{2\pi}{m}\sin\frac{3\pi}{m}\cdots \sin\frac{(m - 1)\pi}{m}\\
=\prod_{k=1}^{m-1}\sin\frac{k\pi}{m}\\
=\prod_{k=1}^{m-1}\frac{exp\big(\frac{ik\pi}{m}\big)-exp\big(\frac{-ik\pi}{m}\big)}{2i}\\
=\prod_{k=1}^{m-1}\frac {exp\big(\frac{ik\pi}{m}\big)}{2i}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {exp\big(\sum_{k=1}^{m-1}\frac{ik\pi}{m}\big)}{(2i)^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {exp\big(\frac{i(m-1)\pi}{2}\big)}{(2i)^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {i^{m-1}}{(2i)^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {1}{2^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)$$
When multiplied out
$$\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)
=1 + \sum_{n=1}^{m-1}P_n$$
where $P_n$ is the sum of all products $\prod_{j=1}^n \big[-exp\big(\frac{-i2k_j\pi}{m}\big)\big]$ in which the values of $k_j$ are all distinct. Note that these products only include terms for $k$ from $1$ to $m-1$; none of them include $-exp\big(\frac{-i0\pi}{m}\big)=-1$. The rest is a proof by induction on $n$ to show that $P_n=1$ for $n$ from $1$ to $m-1$ and therefore $1 + \sum_{n=1}^{m-1}P_n=m$.
For $n=1$
$$P_1 = \sum_{j=1}^{m-1}-exp\big(\frac{-i2k\pi}{m}\big)\\
= 1+ \sum_{j=0}^{m-1}-exp\big(\frac{-i2k\pi}{m}\big)\\
=1$$
The last step follows from the symmetry of summing complex numbers evenly spaced on a circle about the origin.
Due to symmetry $P_{n+1} - exp\big(\frac{-i0\pi}{m}\big) P_n$ is also also equal to zero. Now given the induction hypotheses that $P_n=1$,
$$P_{n+1} =1$$

 

[PeroK]

Spoiler: Q9

I'll assume that $e > 1$, by whatever definition we are using, hence $e^{-y} < 1$ for $y > 0$, and $1 - e^{-y} > 0$ for $y > 0$. Then:

$-1 + y + e^{-y} > 0$ for $y > 0$

Just check the value at $y=0$ and differentiate.

Then, by the same process:

$1-y+ \frac 1 2 y^2 -e^{-y} > 0$ for $y > 0$

Which is equivalent to the stated inequality.

 

[PeroK]

Spoiler: Q2

Assume a quantity changes exponentially over time:

$Q(t) = Q_0 \exp(at)$, where $a \ne 0$

Then:

$Q(t + \Delta t) - Q(t) = Q(t)[\exp(a \Delta t )- 1]$

And, the rate of increase or decrease:

$\frac{Q(t + \Delta t) - Q(t)}{Q(t)}$

Depends only on $\Delta t$.

Seemed a bit easy if I've interpreted that correctly.

 

[PeroK]

Spoiler: Q1

$$\sin\frac{\pi}{m} \sin\frac{2\pi}{m}\sin\frac{3\pi}{m}\cdots \sin\frac{(m - 1)\pi}{m}\\
=\prod_{k=1}^{m-1}\sin\frac{k\pi}{m}\\
=\prod_{k=1}^{m-1}\frac{exp\big(\frac{ik\pi}{m}\big)-exp\big(\frac{-ik\pi}{m}\big)}{2i}\\
=\prod_{k=1}^{m-1}\frac {exp\big(\frac{ik\pi}{m}\big)}{2i}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {exp\big(\sum_{k=1}^{m-1}\frac{ik\pi}{m}\big)}{(2i)^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {exp\big(\frac{i(m-1)\pi}{2}\big)}{(2i)^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {i^{m-1}}{(2i)^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)\\
=\frac {1}{2^{m-1}}\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)$$
When multiplied out
$$\prod_{k=1}^{m-1}1-exp\big(\frac{-i2k\pi}{m}\big)
=1 + \sum_{n=1}^{m-1}P_n$$
where $P_n$ is the sum of all products $\prod_{j=1}^n \big[-exp\big(\frac{-i2k_j\pi}{m}\big)\big]$ in which the values of $k_j$ are all distinct. Note that these products only include terms for $k$ from $1$ to $m-1$; none of them include $-exp\big(\frac{-i0\pi}{m}\big)=-1$. The rest is a proof by induction on $n$ to show that $P_n=1$ for $n$ from $1$ to $m-1$ and therefore $1 + \sum_{n=1}^{m-1}P_n=m$.
For $n=1$
$$P_1 = \sum_{j=1}^{m-1}-exp\big(\frac{-i2k\pi}{m}\big)\\
= 1+ \sum_{j=0}^{m-1}-exp\big(\frac{-i2k\pi}{m}\big)\\
=1$$
The last step follows from the symmetry of summing complex numbers evenly spaced on a circle about the origin.
Due to symmetry $P_{n+1} - exp\big(\frac{-i0\pi}{m}\big) P_n$ is also also equal to zero. Now given the induction hypotheses that $P_n=1$,
$$P_{n+1} =1$$

Spoiler

The last equality comes more easily directly from looking at the mth roots of unity:

$(1+ z + \dots + z^{m-1}) = \Pi (z - \exp(i2\pi k/m))$

And setting $z =1$ and reindexing the roots to go clockwise.

 

[tnich]

Spoiler

The last equality comes more easily directly from looking at the mth roots of unity:

$(1+ z + \dots + z^{m-1}) = \Pi (z - \exp(i2\pi k/m))$

And setting $z =1$ and reindexing the roots to go clockwise.

Yes, I woke up thinking of that this morning. I do like the symmetry argument, though.

 

[PeroK]

Spoiler: Q10

First, we have:

$2(\sin kx \cos mx)= \sin(k +m)x + \sin(k-m)x$

If $k \ne m$, the product is an odd function, hence the integral is zero. And also when $k = m$.

Also, the integral of $\sin kx$ and $\cos kx$ vanish over the interval.

And, the integral of $\cos^2 x$ and $\sin^2 x$ over the interval equal $\pi$. To see this, note for example that:

$2\cos^2 kx = \cos 2kx + 1$

This implies that the integral over the interval vanishes for all cross terms ($a_0, \cos kx, \sin mx$ are mutually orthogonal functions).

This leaves only the square terms in these functions:

$\int_{-\pi}^{\pi} |f(x)|^2 dx = 2\pi(a_0^2/4) + \pi \sum (a_k^2 + b_k^2)$

 

[fresh_42]

Spoiler: Q10

First, we have:

$2(\sin kx \cos mx)= \sin(k +m)x + \sin(k-m)x$

If $k \ne m$, the product is an odd function, hence the integral is zero. And also when $k = m$.

Also, the integral of $\sin kx$ and $\cos kx$ vanish over the interval.

And, the integral of $\cos^2 x$ and $\sin^2 x$ over the interval equal $\pi$. To see this, note for example that:

$2\cos^2 kx = \cos 2kx + 1$

This implies that the integral over the interval vanishes for all cross terms ($a_0, \cos kx, \sin mx$ are mutually orthogonal functions).

This leaves only the square terms in these functions:

$\int_{-\pi}^{\pi} |f(x)|^2 dx = 2\pi(a_0^2/4) + \pi \sum (a_k^2 + b_k^2)$

Yes.

The identity is called Parseval Equation. An alternative proof can be given by using Euler's identity, in case anyone will give it a try.

 

[StoneTemplePython]

Spoiler: Q9

I'll assume that $e > 1$, by whatever definition we are using, hence $e^{-y} < 1$ for $y > 0$, and $1 - e^{-y} > 0$ for $y > 0$. Then:

$-1 + y + e^{-y} > 0$ for $y > 0$

Just check the value at $y=0$ and differentiate.

Then, by the same process:

$1-y+ \frac 1 2 y^2 -e^{-y} > 0$ for $y > 0$

Which is equivalent to the stated inequality.

since the exponential function applied to the left half of the real line is intimately tied in with probability, and coin tossing in particular, I'll offer a simple probabilistic proof of this analytic result. I tried not to skip steps so it isn't particularly short, but my sense is a lot of the below stuff comes up semi-regularly in the probability forum.

The proof as of now is incomplete because it relies on Bonferonni's Inequalities, which is a refinement of inclusion-exclusion. I plan on dropping in a reasonably nice proof of Bonferonni in the near future to complete this.

Spoiler: Q9 probabilistic proof

The only machinery needed is (1) knowledge of simple probability spaces (i.e. with finitely many points in the sample space) and (2) basic knowledge of limits of sequences.

Bonferonni Inequalities to be dropped in a bit later.

consider Bernouli Trials / iid coin tosses, where each toss has probability of success (heads) given by $0 \lt p \lt 1$. We toss the coin $n$ times. The exact values of p and n may be chosen later.

letting $A_k$ denote the event of a heads on the $k$th toss, the probability of at least one heads in n tosses is given by

$Pr\Big(\text{at least one success}\Big) = Pr\Big(A_1 \cup A_2 \cup ... \cup A_n\Big)$

applying Bonferonni inequlities (a black box at this stage, I know) gives

$E\Big[e_1\big(\mathbf z\big)\Big] - E\Big[e_2\big(\mathbf z\big)\Big]$
$= \Big\{\sum_{k=1}^n Pr\Big(A_k\Big)\Big\} - \sum_{k=1}^n \sum_{j\gt k} Pr\big(A_k \cap A_j\big)$
$\leq Pr\Big(A_1 \cup A_2 \cup ... \cup A_n\Big)$
$\leq \sum_{k=1}^n Pr\Big(A_k\Big)$
$= E\Big[e_1\big(\mathbf z\big)\Big]$

where
$\mathbf z := \begin{bmatrix} \mathbb I_{A_1} \\ \mathbb I_{A_2}\\ \vdots \\ \mathbb I_{A_n} \end{bmatrix}$

note: this vector of indicator random variables and the associated elementary symmetric polynomials aren't needed here but I find them a lot easier to follow notationally so I put them in for optional clarity.

now consider the complementary event of no heads in n tosses, which is given by
$1 - Pr\Big(\text{at least one success}\Big) = 1 - Pr\Big(A_1 \cup A_2 \cup ... \cup A_n\Big) = Pr\Big(A_1^C \cap A_2^C \cap ... \cap A_n^C\Big)$

Taking our above bonferonni inequality, negating it and adding one, we can then say
$1 - \sum_{k=1}^n Pr\Big(A_k\Big)$
$\leq 1- Pr\Big(A_1 \cup A_2 \cup ... \cup A_n\Big)$
$=Pr\Big(A_1^C \cap A_2^C \cap ... \cap A_n^C\Big)$
$\leq 1-\Big\{\sum_{k=1}^n Pr\Big(A_k\Big)\Big\} + \sum_{k=1}^n \sum_{j\gt k} Pr\big(A_k \cap A_j\big)$

now we specialize to the fact that our coin tossing has iid trials and input that information into the above inequalties, getting
$1 - n \cdot p$
$\leq Pr\Big(A_1^C \cap A_2^C \cap ... \cap A_n^C\Big)$
$= \Big(1 -p\Big)^n$
$= \Big(1 +(-p)\Big)^n$
$\leq 1-n\cdot p + \binom{n}{2}\cdot p^2$
$= 1-n\cdot p + \frac{n(n-1)}{2}\cdot p^2$
$\leq 1-n\cdot p + \frac{n^2}{2}\cdot p^2$

now for any $x \in (-\infty, 0)$, we may select $p:= \frac{- x}{n} = \frac{\vert x \vert }{n} \in (0,1)$ for all sufficiently large $n$, giving us

$1 - n \cdot \frac{- x}{n}$
$= 1 + x$
$\leq \Big(1 +(-\frac{-x}{n}\Big)^n$
$\leq \Big(1 +\frac{x}{n}\Big)^n$
$\leq 1 - n \cdot \frac{- x}{n} + \frac{n^2}{2}\cdot \big(\frac{- x}{n}\big)^2$
$\leq 1 + x + \frac{1}{2}\cdot x^2$

so we have the pointwise bound that we wanted, and can now treat it as an analytic problem, pass limits and get
$1 + x$
$\leq \lim_{n\to \infty} \Big(1 +\frac{x}{n}\Big)^n$
$= e^x$
$\leq 1 + x + \frac{1}{2} x^2$
again for all $x \in (-\infty, 0)$

- - - -
the one major weakness with this approach is we have
$0 \lt b_n = \Big(1 +\frac{x}{n}\Big)^n = \Big(1 -\frac{\vert x\vert}{n}\Big)^n \lt \Big(1 -\frac{\vert x\vert}{n+1}\Big)^{n+1} =b_{n+1}$
again for sufficiently large n, aka all $n \gt \vert x\vert$
(the strictness of the inequality holds, by e.g. taking (n+1)th roots of each side and applying $\text{GM} \leq \text{AM}$)

so we have a monotone increasing sequence that is bounded above, etc. which tells us that the lower bound
$1 +x \lt b_{n+1} \lt L = e^x$
is strict.

But the weakness is that since we are passing limits it is not clear that the upper bound of
$b_{n+1} \lt L = e^x \leq 1 + x + \frac{1}{2} x^2$
is strict. So in general if we want sharpness, passing limits isn't particularly desirable when constructing an inequality. That said, I still quite like the underlying interpretation here.

 

[member 587159]

Spoiler: Q9

I'll assume that $e > 1$, by whatever definition we are using, hence $e^{-y} < 1$ for $y > 0$, and $1 - e^{-y} > 0$ for $y > 0$. Then:

$-1 + y + e^{-y} > 0$ for $y > 0$

Just check the value at $y=0$ and differentiate.

Then, by the same process:

$1-y+ \frac 1 2 y^2 -e^{-y} > 0$ for $y > 0$

Which is equivalent to the stated inequality.

The idea is certainly correct, but it might benefit less advanced readers if you flesh out the details of the following sentence:

"Just check the value at $y=0$ and differentiate."

 

[PeroK]

The idea is certainly correct, but it might benefit less advanced readers if you flesh out the details of the following sentence:

"Just check the value at $y=0$ and differentiate."

The key is that:

If $f(0) = 0$ and $f'(x) > 0$ for $x > 0$ then $f(x) > 0$ for $x> 0$.

To see this, assume not and apply the mean value theorem.

 

[member 587159]

The key is that:

If $f(0) = 0$ and $f'(x) > 0$ for $x > 0$ then $f(x) > 0$ for $x> 0$.

To see this, assume not and apply the mean value theorem.

Fair enough. Good job. There is no need for a proof by contradiction though.

By the mean value theorem, there is $\xi > 0$ such that $f(x)-f(0) = (x-0)f'(\xi) \implies f(x) > 0$

 

[etotheipi]

Spoiler: Problem 12

The force of viscous drag given by Stokes law is F = 6\pi\eta r v, and at terminal velocity this equals weight. Assuming the drop is spherical, $$v = \frac{mg}{6\pi\eta r} = \frac{\frac{4}{3} \pi r^{3} \rho g}{6\pi\eta r} = \frac{2 \rho g r^{2}}{9\eta}$$ which implies that v \propto r^{2}, so a larger drop will fall faster.

 

[Fred Wright]

Q5

Spoiler: Q5

$$\int_0^{2\pi}e^{cos(\theta)}cos(sin(\theta))d\theta=\int_0^{2\pi}\frac {1}{2}[e^{cos(\theta)+isin(\theta) }+e^{cos(\theta)-isin(\theta) }]d\theta$$The integral formula for the modified Bessel function of the first kind:$$\int_0^{2\pi}e^{xcos(\theta)+ysin(\theta) } d\theta=2\pi I_0(\sqrt {x^2 + y^2})$$$x=1$ and $y=i$ therefore:
$$\int_0^{2\pi}\frac {1}{2}[e^{cos(\theta)+isin(\theta) }+e^{cos(\theta)-isin(\theta) }]d\theta=\pi I_0(\sqrt {1 + i^2} ) + \pi I_0(\sqrt {1 +(-i)^2} )= 2\pi I_0(0)$$ The expansion for $I_0$ :$$I_0(x)=\sum_{m=0}^{\infty}\frac {1}{m!\Gamma (m+1)}(\frac {x}{2})^{2m}$$With $x=0$ only the first term in the expansion survives and$$I_0(0)= \frac {1}{0!\Gamma(1)}=\frac {1}{0!0!}=1$$Thus$$\int_0^{2\pi}e^{cos(\theta)}cos(sin(\theta))d\theta=2\pi$$

 

[Infrared]

@Fred Wright This looks right!

The question can be done without using special functions, so I'll still accept other solutions.

 

[tnich]

Spoiler: Q5

$$\int_0^{2\pi}e^{\cos\theta}\cos(\sin\theta) d\theta\\
=\int_0^{2\pi}\frac {e^{\cos\theta+i\sin\theta}+e^{\cos\theta-i\sin\theta}} 2 d\theta\\
=\int_0^{2\pi}\frac {e^{e^{i\theta}}}2d\theta+\int_0^{2\pi}\frac {e^{e^{-i\theta}}} 2d\theta$$
Letting $\phi = -\theta$ in the second integral gives
$$\int_0^{2\pi}\frac {e^{e^{i\theta}}}2d\theta-\int_0^{-2\pi}\frac {e^{e^{i\phi}}} 2d\phi\\
=\int_0^{2\pi}\frac {e^{e^{i\theta}}}2d\theta+\int_{-2\pi}^0\frac {e^{e^{i\phi}}} 2d\phi\\
=\int_0^{2\pi}\frac {e^{e^{i\theta}}}2d\theta+\int_0^{2\pi}\frac {e^{e^{i\phi}}} 2d\phi\\
=\int_0^{2\pi}e^{e^{i\theta}}d\theta$$
Letting $z=e^{i\theta}$ we can convert to a contour integral on the unit circle,
$$\oint \frac {e^z}{iz}dz$$
The residue of $\frac {e^z}i$ at $z=0$ is $-i$, so the value of the contour integral is $2\pi i (-i)=2\pi$.

 

[Infrared]

@tnich Nice, this was my intended solution. You can save a few steps by noting that the integrand in your third line is the real part of $e^{e^{i\theta}}$, so that you don't have to do the following change of variables.

 

[Not anonymous]

15. On the first flight day of a little island hopper there was no wind during the return flight. How does the total flight duration from outward and return flight change if, instead, a strong headwind blows on the way to the neighboring island - and on the way back, an equally strong tailwind?

Spoiler: Q15

Answer: Compared to the situation where there were no winds, the duration will be longer when there are equally strong headwinds and tailwinds during the outward and return flights.

I assume that the "original" speed of the airplane, i.e. the speed had there been no wind, is the same during onward and return flights and that the pilots do not change the plane's speed to negate the effect of headwind and tailwind. Let $v$ be the original speed. Let $x$ be the increase/decrease in speed caused by tailwind/headwind. Let $d$ be the distance between the 2 islands.

Total duration of flights when there were no winds = $t_1 = \frac {2d} {v}$
Total duration of flights when there is headwind of speed $x$ during one flight and tailwind of same speed during the other flight = $t_2 = \frac {d} {(v-x)} + \frac {d} {(v+x)} = \frac {2dv} {v^2 - x^2}$

$$ t_2 - t_1 = 2d \times \frac {x^2} {v (v^2 - x^2)}$$

The above time difference value must be a positive value since $d$, $v$ and $x$ are positive and since $x$ must be less than $v$ (otherwise the plane would be moving backward and will not be able to reach the destination), the denominator is also positive. That means $t_2 \gt t_1$

 

[Not anonymous]

11. A kid throws small balls upwards. It throws each ball when the previous thrown one is at the maximum height of its course. What is the height that balls reach if the kid throws two of them per second?

Spoiler: Q11

I assume that the kid throws every ball with the same speed. Without that assumption, there would be innumerable valid solution - the kid could alternate between 2 speeds for the throw for odd and even numbered throws and achieve a rate of 2 balls per seconds. But with the same speed assumption, every ball must be reaching its maximum height 0.5 seconds after its throw.

Gravitational acceleration $g = 9.8 \ m / s^2$. When ball reaches maximum height, its speed becomes 0. If initial speed of ball is $s$ and speed becomes 0 after 0.5 seconds due to deceleration $g$, $0 = s - 0.5 \times g \Rightarrow s = 4.9 \ m /s$

Maximum height reached by ball $D$ = Distance traveled by ball in 0.5 seconds from the time of throw. Using the equation for distance as a function of velocity $v$ and time $t$, and knowing that velocity of the ball $t$ seconds after its throw is $v = (s - g t)$ we get

$$
D = \int_0^{0.5} v \, dt = \int_0^{0.5} (s - gt) \, dt =\left. st - \frac {gt^2} {2} \right|_0^{0.5} =
0.5 s - \frac {9.8 \times {0.5}^2} {2} = 1.225 \ m
$$

So answer is 1.225 meters

 

[tnich]

Spoiler: Q4

I can't prove this one, but I can give a counter-example. For $q=\frac 1 6$, $\sin \pi q=\frac 1 2$ and both are rational, but $2q=\frac 1 3$, which is not an integer. What am I missing?

 

[Infrared]

@tnich Ack, sorry! The conclusion should be that $2\sin(\pi q)$ is an integer.

 

[fresh_42]

@tnich Ack, sorry! The conclusion should be that $2\sin(\pi q)$ is an integer.

Corrected.

 

[Not anonymous]

13. A radio station at point A transmits a signal which is received by the receivers B and C. A listener located at B is listening to the signal via his receiver and after one second hears the signal via receiver C which has a strong loudspeaker. What is the distance between B and C?

Spoiler: Q13

Answer: The distance between B and C would be approximately equal to the distance traveled by sound in air in 1 second, i.e. around 340 m.

To prove this, let us denote by $d_1$, $d_2$ and $d_3$ the distances between A & B, A & C, and B & C respectively. Let $T_0$ be the time instant at which radio signal was emitted from A, $T_1$ be the time instant at which it was received at A and $T_2$ be the instant at which the retransmitted (as sound) signal from C is heard at B. Let $v_l$ and $v_s$ be the speed of radio waves (which is same as speed of light) and speed of sound respectively. I assume that the signal is emitted at sound from C instantaneously on receiving the signal from A, i.e. there is no time lag between signal reception and sound emission at C. It is given that $T_2 - T_1 = 1$

$$
T_1 = T_0 + \frac {d_1} {v_l} \\

T_2 = T_0 + \frac {d_2} {v_l} + \frac {d_3} {v_s} \\

T_2 - T_1 = 1 \Rightarrow \frac {d_2} {v_l} + \frac {d_3} {v_s} - \frac {d_1} {v_l} = 1 \\
\Rightarrow d_3 = v_s + v_s \frac {d_1 - d_2} {v_l}
$$

By triangle inequality, $d_2 \le d_1 + d_3 \Rightarrow 0 \le d_2 \le d_1 + d_3$ (lower bound is 0 as d_2 is a length)

If $d_2 = 0$, substituting in the earlier equation gives $d_3 = v_s + v_s \frac {d_1} {v_l}$, but this is also case where points A and C coincide, so distance between B & C = distance between B & A $\Rightarrow d_3 = v_s + v_s \frac {d_3} {v_l} \Rightarrow d_3 = \frac {v_s} {1 - \frac {v_s} {v_l}}$

If on the other hand, $d_2 = d_1 + d_3$, the earlier equation becomes
$$
d_3 = v_s + v_s \frac {- d_3} {v_l} \Rightarrow d_3 = \frac {v_s} {1 + \frac {v_s} {v_l}}
$$

Therefore $d_3 \in (\frac {v_s} {1 + \frac {v_s} {v_l}}, \frac {v_s} {1 - \frac {v_s} {v_l}})$

Since speed of sound is very small compared to speed of radio waves $\frac {v_s} {v_l} \approx 0 \Rightarrow$ denominators of both lower and upper bounds are almost equal to 1, so the value $d_3 \approx v_s \approx 340 \ m$

 

[Fred Wright]

Yet another way to solve problem 5

Spoiler: Prob. 5

$$I(\theta)=\int_0^{2\pi}e^{cos(\theta )}cos(sin(\theta ))d\theta =\int_0^{2\pi}\frac {1}{2}(e^{cos(\theta) + isin(\theta)} + e^{cos(\theta) - isin(\theta)})d\theta
\\ =\int_0^{2\pi}d\theta \sum_{m=0}^{\infty}[\frac {(cos(\theta)+ isin(\theta))^m +(cos(\theta)- isin(\theta))^m}{2m!}]$$ I observe that$$cos(m\theta)=\frac {(e^{i\theta} )^m + (e^{-i\theta} )^m}{2}
\\ = \frac{(cos(\theta)+ isin(\theta))^m +(cos(\theta)- isin(\theta))^m}{2}$$therefor,$$I(\theta)=\int_0^{2\pi} \sum_{m=0}^{\infty}\frac{cos(m\theta)}{m!}d\theta
\\ = \int_0^{2\pi}d\theta (1 + \frac{cos(\theta)}{1!} + \frac{cos(2\theta)}{2!} + ...)$$ Integration of $cos(m\theta)$, with m an integer greater than 0, over a period of $2\pi$, yields zero, so only the first term survives in the expansion and thus$$I(\theta)=2\pi$$

 

[Infrared]

$$I(\theta)=\int_0^{2\pi} \sum_{m=0}^{\infty}cos(m\theta) d\theta
\\$$

Unfortunately, the sum under your integral sign doesn't converge (for any $\theta$). I think you lost your factorial term.

 

[Fred Wright]

Unfortunately, the sum under your integral sign doesn't converge (for any $\theta$). I think you lost your factorial term.

The sum should have been$$I(\theta)=\int_0^{2\pi} \sum_{m=0}^{\infty}\frac{cos(m\theta)}{m!}d\theta$$I was to hasty with typing latex. I think that sum converges.

 

[StoneTemplePython]

The proof as of now is incomplete because it relies on Bonferonni's Inequalities, which is a refinement of inclusion-exclusion. I plan on dropping in a reasonably nice proof of Bonferonni in the near future to complete this.

It is too late, I know, but it belatedly occurs to me that I should have just ditched this Bonferonni stuff and instead mimicked the proof for the Bernouli Inequality.

Spoiler: Q9, again

for $a \in (-1,0)$

claim:
$\big(1-\vert a \vert\big)^n \leq 1 - n\vert a \vert + \binom{n}{2}a^2$
for natural number $n \geq 2$

Base Case:
$n=2$
$\big(1-\vert a \vert\big)^2 = 1-2\vert a \vert + \vert a \vert^2 \leq 1 - 2\vert a \vert + \binom{2}{2}a^2$
(i.e. met with equality)

Inductive Case:
suppose holds for $n-1$, need to show this implies it holds for n
$\big(1 + a \big)^n$
$\big(1-\vert a \vert\big)^n$
$=\big(1-\vert a \vert\big) \cdot \big(1-\vert a \vert\big)^{n-1}$
$\leq \big(1-\vert a \vert\big)\big(1 - (n-1)\vert a \vert + \binom{n-1}{2}\vert a\vert ^2\big)$ (inductive hypothesis, note $\big(1-\vert a \vert\big)\gt 0$)
$= \big(1 - (n-1)\vert a \vert + \binom{n-1}{2}a^2\big) + \big(-\vert a \vert + (n-1) \vert a \vert^2 -\binom{n-1}{2}\vert a\vert^3\big)$
$= 1 - n\vert a \vert + \big\{\binom{n-1}{2}a^2 + (n-1) a^2\big\} -\binom{n-1}{2}\vert a\vert^3$
$= 1 - n\vert a \vert + \big\{\frac{(n-1)(n-2)}{2}a^2 + \frac{2n-2}{2} a^2\big\} -\binom{n-1}{2}\vert a\vert^3$
$= 1 - n\vert a \vert + \big\{\frac{n^2-3n + 2}{2}a^2 + \frac{2n-2}{2} a^2\big\} -\binom{n-1}{2}\vert a\vert^3$
$= 1 - n\vert a \vert + \big\{\frac{n^2-n}{2}a^2 \big\} -\binom{n-1}{2}\vert a\vert^3$
$= 1 - n\vert a \vert + \binom{n}{2}a^2 -\binom{n-1}{2}\vert a\vert^3$
$\leq 1 - n\vert a \vert + \binom{n}{2}a^2$
$= 1 + n\cdot a + \binom{n}{2}a^2$

now for any
$x \in (-\infty, 0)$
we can select
$a:= \frac{x}{n}$
for all large enough $n$ (i.e. $n \gt \vert x \vert$ )

giving
$\big(1 + \frac{x}{n} \big)^n$
$=\big(1 + a \big)^n$
$\leq 1 + n\cdot a + \binom{n}{2}a^2$
$= 1 + n\cdot \frac{x}{n} + \binom{n}{2}\frac{x^2}{n^2}$
$\leq 1 + x + \frac{n^2}{2}\frac{x^2}{n^2}$
$= 1 + x + \frac{x^2}{2}$

now passing limits gives the result, i.e.

$e^{x} = \lim_{n\to \infty} \big(1 + \frac{x}{n} \big)^n \leq 1 + x + \frac{x^2}{2}$
for $x \in (-\infty, 0)$

 

[QuantumQuest]

Spoiler: Q11

I assume that the kid throws every ball with the same speed. Without that assumption, there would be innumerable valid solution - the kid could alternate between 2 speeds for the throw for odd and even numbered throws and achieve a rate of 2 balls per seconds. But with the same speed assumption, every ball must be reaching its maximum height 0.5 seconds after its throw.

Gravitational acceleration $g = 9.8 \ m / s^2$. When ball reaches maximum height, its speed becomes 0. If initial speed of ball is $s$ and speed becomes 0 after 0.5 seconds due to deceleration $g$, $0 = s - 0.5 \times g \Rightarrow s = 4.9 \ m /s$

Maximum height reached by ball $D$ = Distance traveled by ball in 0.5 seconds from the time of throw. Using the equation for distance as a function of velocity $v$ and time $t$, and knowing that velocity of the ball $t$ seconds after its throw is $v = (s - g t)$ we get

$$
D = \int_0^{0.5} v \, dt = \int_0^{0.5} (s - gt) \, dt =\left. st - \frac {gt^2} {2} \right|_0^{0.5} =
0.5 s - \frac {9.8 \times {0.5}^2} {2} = 1.225 \ m
$$

So answer is 1.225 meters

Well done. Just one comment: letter $s$ is usually for distance, so I think that it's best to denote initial velocity as $\upsilon_0$ just to avoid potential looking back and forth from readers.

 

[QuantumQuest]

13. A radio station at point A transmits a signal which is received by the receivers B and C. A listener located at B is listening to the signal via his receiver and after one second hears the signal via receiver C which has a strong loudspeaker. What is the distance between B and C?

Spoiler: Q13

Answer: The distance between B and C would be approximately equal to the distance traveled by sound in air in 1 second, i.e. around 340 m.

To prove this, let us denote by $d_1$, $d_2$ and $d_3$ the distances between A & B, A & C, and B & C respectively. Let $T_0$ be the time instant at which radio signal was emitted from A, $T_1$ be the time instant at which it was received at A and $T_2$ be the instant at which the retransmitted (as sound) signal from C is heard at B. Let $v_l$ and $v_s$ be the speed of radio waves (which is same as speed of light) and speed of sound respectively. I assume that the signal is emitted at sound from C instantaneously on receiving the signal from A, i.e. there is no time lag between signal reception and sound emission at C. It is given that $T_2 - T_1 = 1$

$$
T_1 = T_0 + \frac {d_1} {v_l} \\

T_2 = T_0 + \frac {d_2} {v_l} + \frac {d_3} {v_s} \\

T_2 - T_1 = 1 \Rightarrow \frac {d_2} {v_l} + \frac {d_3} {v_s} - \frac {d_1} {v_l} = 1 \\
\Rightarrow d_3 = v_s + v_s \frac {d_1 - d_2} {v_l}
$$

By triangle inequality, $d_2 \le d_1 + d_3 \Rightarrow 0 \le d_2 \le d_1 + d_3$ (lower bound is 0 as d_2 is a length)

If $d_2 = 0$, substituting in the earlier equation gives $d_3 = v_s + v_s \frac {d_1} {v_l}$, but this is also case where points A and C coincide, so distance between B & C = distance between B & A $\Rightarrow d_3 = v_s + v_s \frac {d_3} {v_l} \Rightarrow d_3 = \frac {v_s} {1 - \frac {v_s} {v_l}}$

If on the other hand, $d_2 = d_1 + d_3$, the earlier equation becomes
$$
d_3 = v_s + v_s \frac {- d_3} {v_l} \Rightarrow d_3 = \frac {v_s} {1 + \frac {v_s} {v_l}}
$$

Therefore $d_3 \in (\frac {v_s} {1 + \frac {v_s} {v_l}}, \frac {v_s} {1 - \frac {v_s} {v_l}})$

Since speed of sound is very small compared to speed of radio waves $\frac {v_s} {v_l} \approx 0 \Rightarrow$ denominators of both lower and upper bounds are almost equal to 1, so the value $d_3 \approx v_s \approx 340 \ m$

Well done. I want to point out here that what is asked from the potential solver of the question is, essentially, to recognize that he / she has to use the speed of sound in order to find the distance asked. So, an answer along these lines:

Because radio waves have speed $\approx 300,000 \frac{km}{sec}$, the signal is received almost simultaneously by $B$ and $C$ although they are at different distances from $A$. But sound travels from $C$ to $B$ at $\approx 330 \frac{m}{sec}$ ($0^o C$) or $\approx 340 \frac{m}{sec}$ ($20^o C$). So, taking the second speed (as more general), distance from $B$ to $C$ is $BC \approx 340 \times 1 \enspace m = 340 \enspace m$

would be sufficient.

 

[Infrared]

@Fred Wright Looks good now, but in order to interchange the sum and integral at the end, you should establish uniform convergence (or else use some other criterion). Fortunately this is easy in this case (e.g. use Weierstrass M-test)

 

[Antarres]

Spoiler: Q3

Consider the function $f(x) = x^{s/r}$ where $s>r$ are non-zero real numbers. We analyze the convexity. Taking the second derivative we find:
$$f''(x) = \frac{s}{r}\left(\frac{s}{r} - 1\right)x^{\frac{s}{r} - 2} = \frac{s(s-r)}{r^2}x^{\frac{s}{r}-2}$$
Since the power function is strictly positive for $x>0$, we find that $f(x)$ is convex for $s>0$ and concave for $s<0$. We will then use the Jensen's inequality for this function, and weights as they're defined in the exercise.
Case 1: $s>0$
$$\left(\sum_{k=1}^n \omega_k x^r_k\right)^{\frac{s}{r}} \leq \sum_{k=1}^n \omega_k (x^r_k)^{\frac{s}{r}} =\sum_{k=1}^n \omega_k x^s_k$$
Taking the $\frac{1}{s}$ - th power of both sides, we obtain the inequality as required.
Case 2: $s<0$
If $s>r$ then $r<0$, as well. Using case 1, we find($-s<-r$):
$$\left(\sum_{k=1}^n \omega_k x^{-r}_k\right)^{\frac{1}{-r}} \geq \left(\sum_{k=1}^n \omega_k x^{-s}_k\right)^{\frac{1}{-s}}$$
The inequality sign will reverse when we raise to the power of -1, so we get:
$$\left(\sum_{k=1}^n \omega_k x^{-r}_k\right)^{\frac{1}{r}} \leq \left(\sum_{k=1}^n \omega_k x^{-s}_k\right)^{\frac{1}{s}}$$
But now without loss of generality we can apply the same inequality to the set of numbers $y_k = \frac{1}{x_k}$, which gives us the desired inequality. Since sets $x_k$ and $y_k$ both satisfy the same constraints(that they are positive), this substitution gives equivalent inequality to the one above.

This completes the proof.

 

[fresh_42]

Spoiler: Q3

Consider the function $f(x) = x^{s/r}$ where $s>r$ are non-zero real numbers. We analyze the convexity. Taking the second derivative we find:
$$f''(x) = \frac{s}{r}\left(\frac{s}{r} - 1\right)x^{\frac{s}{r} - 2} = \frac{s(s-r)}{r^2}x^{\frac{s}{r}-2}$$
Since the power function is strictly positive for $x>0$, we find that $f(x)$ is convex for $s>0$ and concave for $s<0$. We will then use the Jensen's inequality for this function, and weights as they're defined in the exercise.
Case 1: $s>0$
$$\left(\sum_{k=1}^n \omega_k x^r_k\right)^{\frac{s}{r}} \leq \sum_{k=1}^n \omega_k (x^r_k)^{\frac{s}{r}} =\sum_{k=1}^n \omega_k x^s_k$$
Taking the $\frac{1}{s}$ - th power of both sides, we obtain the inequality as required.
Case 2: $s<0$
If $s>r$ then $r<0$, as well. Using case 1, we find($-s<-r$):
$$\left(\sum_{k=1}^n \omega_k x^{-r}_k\right)^{\frac{1}{-r}} \geq \left(\sum_{k=1}^n \omega_k x^{-s}_k\right)^{\frac{1}{-s}}$$
The inequality sign will reverse when we raise to the power of -1, so we get:
$$\left(\sum_{k=1}^n \omega_k x^{-r}_k\right)^{\frac{1}{r}} \leq \left(\sum_{k=1}^n \omega_k x^{-s}_k\right)^{\frac{1}{s}}$$
But now without loss of generality we can apply the same inequality to the set of numbers $y_k = \frac{1}{x_k}$, which gives us the desired inequality. Since sets $x_k$ and $y_k$ both satisfy the same constraints(that they are positive), this substitution gives equivalent inequality to the one above.

This completes the proof.

What about the cases $r<0<s$ and $r\cdot s = 0$?

 

[Antarres]

What about the cases $r<0<s$ and $r\cdot s = 0$?

Case $r<0<s$ is covered in case 1, since the negative value of $r$ doesn't change the procedure based on Jensen's inequality, in this case(convexity analysis is the same, and nowhere in the inequality derivation is negative power taken that would reverse the sign of inequality).
As for $r \cdot s = 0$, thank you for reminding me, I'll add it here.

Spoiler: Q3 - addendum

Case 3: $r = 0$, $s>0$.
We look at the definition of the mean for $r=0$, we find:
$$\prod_{k=1}^n x_k^{\omega_k} = \exp\left({\ln{\prod_{k=1}^n x_k^{\omega_k}}}\right)= \exp\left(\sum_{k=1}^n \omega_k \ln{x_k}\right)$$
By Jensen inequality for logarithm function which is concave on the the whole domain, we know that:
$$\sum_{k=1}^n \omega_k \ln{x_k} \leq \ln{\left(\sum_{k=1}^n \omega_k x_k \right)}$$
Combining the last two equations we find(exponential function is strictly raising so it doesn't change the inequality):
$$\prod_{k=1}^n x_k^{\omega_k} \leq \sum_{k=1}^n \omega_k x_k$$
Now we use the same trick as in case 2. We make a substitution that gives us equivalent inequality: $x_k \rightarrow y_k = x_k^s$. Taking $\tfrac{1}{s}$ - th power of both sides of this inequality(which doesn't reverse inequality sign since $s>0$ so this power function is strictly raising on positive reals), we find the desired inequality:
$$\prod_{k=1}^n x_k^{\omega_k} \leq \left(\sum_{k=1}^n \omega_k x_k^s\right)^{\frac{1}{s}}$$

Case 4: $s=0$, $r<0$
Looking at case 3 for $-r>s=0$ we find the inequality:
$$\prod_{k=1}^n x_k^{\omega_k} \leq \left(\sum_{k=1}^n \omega_k x_k^{-r}\right)^{\frac{1}{-r}}$$
Now raising to the power of -1 reverses the sign of inequality, and then the equivalent substitution $x_k \rightarrow x_k^{-1}$ obtains the desired inequality(the product gets simply raised to the power of 1 in total by these two transformations, while the inequality reverses sign, and the right side changes to the desired form).

 

[Not anonymous]

14. Mr. Smith on a full up flight with 50 passengers on a CRJ 100 had lost his boarding pass. The flight attendant tells him to sit anywhere. All other passengers sit on their booked seats, unless it is already occupied, in which case they randomly choose another seat just like Mr. Smith did. What are the chances that the last passenger gets the seat printed on his boarding pass?

Should we assume that Mr. Smith is equally likely to be the 1st, 2nd, 3rd, .., 50th passenger to board the flight, so the probability of his being the $i^{th}$ passenger to board the flight is 1/50? If so, here is an attempt to solve the problem. There could be a much more intuitive and simpler way to solve the problem but this is the best approach I could get to.

Spoiler: Q14

Let $P_i$ be the probability of last boarding passenger getting the seat printed on his/her boarding pass when Smith is the $i^{th}$ passenger to board the flight.

$P_{50} = 1$ because if Smith is the last passenger to board, just one seat would be left and it should be the one originally allotted to him since all other passengers have already occupied their original seats.

$P_{49} = 1/2$ because 2 seats are free when Smith boards and the probability of his choosing his allotted seat, and so not displacing the last and 50th passenger, is 1/2

Notice that if Smith is the $i^{th}$ passenger to board and i < 50, the last passenger gets his/her original seat either if Smith picks his (Smith's) own original seat (the "no displaced passenger" case) or if Smith picks the seat of the $j^{th}$ passenger $j \in {i, (i+1)..., 49}$ and the chain of displacements caused does not involve someone between $i^{th}$ and $50^{th}$ passengers occupying the last passenger's seat. If Smith is the 40th passenger to board and randomly chooses the seat of say the 46th passenger, then passengers 41 to 45 (as per order of boarding) occupy their original seats, 46th passenger has to pick a seat randomly and so the chain of displacements starts at 46 and in this case the (conditional) probability of the last passenger getting his/her original seat is the same as it would have been if instead Smith was the 46th passenger to board.

$P_{48} =$ Probability of Smith picking his original seat + (Probability of Smith picking the seat of 49th passenger x Probability that 49th passenger does not choose 50th passenger's seat) = $1/3 + 1/3 \times 1/2 = 1/2$

$P_{47} =$ Probability of Smith picking his original seat + (Probability of Smith picking 48th passenger's seat x $P_{48}$) + (Probability of Smith picking 49th passenger's seat x $P_{49}$) = $1/4 + 1/4 \times 1/2 + 1/4 \times 1/2 = 1/2$

It is now easy to show that $P_{46}, P_{45}, .., P_{2}, P_{1}$ are all equal to 1/2.

Now, the final unconditional probability of last passenger getting his/her originally allotted seat is $1/50 \times P_{1} + 1/50 \times P_{2} + .. + 1/50 \times P_{49} + 1/50 \times P_{50} = 49/50 \times 1/2 + 1/50 \times 1 = 51/100 = 0.51$

 

[fresh_42]

Should we assume that Mr. Smith is equally likely to be the 1st, 2nd, 3rd, .., 50th passenger to board the flight, so the probability of his being the $i^{th}$ passenger to board the flight is 1/50? If so, here is an attempt to solve the problem. There could be a much more intuitive and simpler way to solve the problem but this is the best approach I could get to.

Spoiler: Q14

Let $P_i$ be the probability of last boarding passenger getting the seat printed on his/her boarding pass when Smith is the $i^{th}$ passenger to board the flight.

$P_{50} = 1$ because if Smith is the last passenger to board, just one seat would be left and it should be the one originally allotted to him since all other passengers have already occupied their original seats.

$P_{49} = 1/2$ because 2 seats are free when Smith boards and the probability of his choosing his allotted seat, and so not displacing the last and 50th passenger, is 1/2

Notice that if Smith is the $i^{th}$ passenger to board and i < 50, the last passenger gets his/her original seat either if Smith picks his (Smith's) own original seat (the "no displaced passenger" case) or if Smith picks the seat of the $j^{th}$ passenger $j \in {i, (i+1)..., 49}$ and the chain of displacements caused does not involve someone between $i^{th}$ and $50^{th}$ passengers occupying the last passenger's seat. If Smith is the 40th passenger to board and randomly chooses the seat of say the 46th passenger, then passengers 41 to 45 (as per order of boarding) occupy their original seats, 46th passenger has to pick a seat randomly and so the chain of displacements starts at 46 and in this case the (conditional) probability of the last passenger getting his/her original seat is the same as it would have been if instead Smith was the 46th passenger to board.

$P_{48} =$ Probability of Smith picking his original seat + (Probability of Smith picking the seat of 49th passenger x Probability that 49th passenger does not choose 50th passenger's seat) = $1/3 + 1/3 \times 1/2 = 1/2$

$P_{47} =$ Probability of Smith picking his original seat + (Probability of Smith picking 48th passenger's seat x $P_{48}$) + (Probability of Smith picking 49th passenger's seat x $P_{49}$) = $1/4 + 1/4 \times 1/2 + 1/4 \times 1/2 = 1/2$

It is now easy to show that $P_{46}, P_{45}, .., P_{2}, P_{1}$ are all equal to 1/2.

Now, the final unconditional probability of last passenger getting his/her originally allotted seat is $1/50 \times P_{1} + 1/50 \times P_{2} + .. + 1/50 \times P_{49} + 1/50 \times P_{50} = 49/50 \times 1/2 + 1/50 \times 1 = 51/100 = 0.51$

Close, but no. You used Bayes' theorem but didn't formalize it, so I have difficulties to pin down the error. My guess is, that e.g. if Mr. Smith boards first, then there aren't 50 choices left, only 49. It can be solved without Bayes, or better with far fewer cases.

 

[Not anonymous]

Close, but no. You used Bayes' theorem but didn't formalize it, so I have difficulties to pin down the error. My guess is, that e.g. if Mr. Smith boards first, then there aren't 50 choices left, only 49. It can be solved without Bayes, or better with far fewer cases.

Thanks fresh_42, for reviewing my answer! I am not as strong on intuitive thinking as other people on this forum and will need to think a lot more to find a simpler approach that doesn't use Bayes' theorem. Since you mentioned that my previous answer was close, I make one more attempt at solving the problem and along the same lines as before. Smith will definitely have the choice of 50 seats if he is the 1st passenger to board, so I guess it should be assumed that Smith is NOT the last passenger to board, either because it is a trivial case and there is no choice to be made, or because the wording of the question says "printed on his boarding pass", so the last passenger has a pass and therefore is not Mr. Smith. If that assumption is made, only the final step in my earlier solution, and the probability of Smith being the $i^{th}$ passenger change. The probability of Smith being the $i^{th}$ passenger would be $1/49$ where $i \in {1, 2, .., 49}$. The final step therefore becomes:

Spoiler: Q14

Final unconditional probability of last passenger getting his/her originally allotted seat is $\sum_{i=1}^{49} 1/49 \times P_{i} = 49 \times 1/49 \times 1/2 = 1/2 = 0.5$

Note that $P_{50} = 1$ is still used in deriving $P_{49}, .., P_{1}$ and is a valid value because it represents the situation where the NONE of the passengers before the 50th passenger have occupied a seat that is different from what was originally allotted to them.

When I get some free time, I will continue pondering over this problem in the hope of finding a simpler, more elegant way to solve the problem. It requires more creative thinking and that doesn't come naturally to all

 

[fresh_42]

Thanks fresh_42, for reviewing my answer! I am not as strong on intuitive thinking as other people on this forum and will need to think a lot more to find a simpler approach that doesn't use Bayes' theorem.

Well, probabilities isn't my favorite subject either. I tend to count wrongly. The solution I have also uses more words than formulas, so yours is not bad, and 0.5 is the correct answer.

 

[member 587159]

Well, probabilities isn't my favorite subject either. I tend to count wrongly. The solution I have also uses more words than formulas, so yours is not bad, and 0.5 is the correct answer.

Yes, this is also what I hate about probability. The analytical side of the subject is nice though.

 

[Antarres]

Spoiler: Q7

Based on the equivalence relation given in the exercise, we find that this $n$-dimensional projective space is quotient space of $\mathbb{R}^{n+1}$ where points on every ray that is given by a $(n+1)$-dimensional vector from the origin are equivalent. Therefore, every equivalence class is one ray in $\mathbb{R}^{n+1}$, and quotient map with respect to which we define the topology, maps every point in $\mathbb{R}^{n+1}$ onto it's equivalence class. It is trivial to see that this map is surjective. We will use this map to induce quotient topology on the projective space. 'Geometrically', this space will then be given by a certain set of points on $S^n$, the $n$-dimensional hypersphere of unit radius with the center at the origin. Each point on the hypersphere will be mapped with inverse quotient map into a ray that is defined by the vector in $\mathbb{R}^{n+1}$. We notice that the points which are connected by the diameter of the hypersphere are also identified, that is, rays of opposite directions are also identified. So, bearing this in mind, we will define geometrical representation of $\mathbb{R}P^n$ in $\mathbb{R}^{n+1}$ with the following convention(it will make the treatment more palpable, at least to me):
1. We take $(0, 0, \dots , 0, 1)$ to be the north pole of $S^n$(All points/vectors we are mentioning are $\mathbb{R}^{n+1}$ coordinates notation).
2. Then $\mathbb{R}P^n$ is represented by a set of points on $S^n$ with positive coordinate $0 < x_{n+1} \leq 1$(northern hemisphere), and points $x_{n+1} = 0$ on $S^n$(equator), for which $x_1>0$, and points $x_{n+1}=0 , x_1 = 0$ for which $x_2>0$, etc. inductively, up until the point $(0, 0, \dots , 0, 1, 0)$.
Three-dimensional analog of this would be north hemisphere of a 3-dimensional sphere with equator circle given by points defined by $\phi \in [0,\pi)$, where $\phi$ is the azimuthal angle on the equator with $\phi=0$ defined to be measured counterclockwise from the point $(x =1 , y = 0, z=0)$.
We will call this geometrical representation of $\mathbb{R}P^n$, $S$, and it is homeomorphic to $\mathbb{R}P^n$.

The quotient topology is then induced in a standard way. Open sets in $R\mathbb{P}^n$ are sets who's inverse images under quotient map are open in $\mathbb{R}^{n+1}$. Let's take $P$ to be the set of all $n$-dimensional hyperplanes in $\mathbb{R}^{n+1}$ that intersect $S^n$. Their intersections will be $(n-1)$-dimensional spheres on the surface of this hypersphere. These $(n-1)$-dimensional spheres are contained in $S$, or they're intersecting $S$ or they're disjunct from $S$. We will consider the first two cases, since the third one isn't interesting to us.

In the first case, if we name interiors of those $(n-1)$-dimensional spheres, $U_i$, we find that inverse image of $U_i$ is the space bounded by a circular conical surface in $\mathbb{R}^{n+1}$, whose axis direction is given by the direction of the vector perpendicular to the hyperplane that generated the boundary of $U_i$ by intersecting with $S$. This set is obviously open in $\mathbb{R}^{n+1}$, so it should be open in the quotient topology.

In the second case, the $(n-1)$-dimensional hypersphere is intersecting $S$ and the intersection is an $(n-1)$ dimensional 'arc', with ends at the equator(If it's end is on the open-ended part of the equator, the arc is open-ended on that side, while if it's on the part of the equator that is included in $S$, then that end of the arc is closed(not in the sense of topology but in the sense that it includes the point from the equator)). The equator of $S^n$(or of $S$) is mapped by inverse quotient map into a hyperplane passing through the origin, which is open in $\mathbb{R}^{n+1}$, hence the equator of $S$ is open in quotient topology. However, the interior bounded by the arc and the equator, which we may call $W_i$ is mapped with inverse quotient map into space that is bounded on one side by part of a conical surface that is the image of the arc the same way as in case 1, and the hyperplane that is the image of the equator.
Also, it can be that the arc is actually half of the 'great circle' of $S$, in which case it is mapped into a hyperplane in $\mathbb{R}^{n+1}$ so in that case the inverse image of $W_i$ is the space between two intersecting hyperplanes passing through the origin(the direction of 'between' is given by any vector whose end is mapped into $W_i$). So this set in the second case is also open in $\mathbb{R}^{n+1}$, and therefore should be open in the quotient topology. So the union of $W_i$ and the part of the equator that is the boundary of $W_i$, which we can call $V_i$ is open in $\mathbb{R}^{n+1}$. We assert that the sets $U_i$ and $V_i$ consist the basis of quotient topology.
We need to check the two conditions for the basis:
1. For every $x \in S$ we have a basis element that contains it.
If we take an arbitrary $x \in S$, then the vector given by coordinates of $x$ in $\mathbb{R}^{n+1}$ defines the hyperplane that is perpendicular to it. We choose this hyperplane to intersect $S^n$ at the half the length of this vector, and obtain one of the two intersections mentioned above. Then such an intersection with $S$ defines a basis element $U_i$ or $V_i$ that contains $x$. The notion of length of this vector is not needed for this claim, since the point of intersection of the chosen hyperplane with the ray is defined with all the coordinates of $x$ halved.
2. If $x$ belongs to the intersection of two basis elements $B_1$ and $B_2$, then there exists a basis element $B_3 \subset B_1 \cap B_2$ containing $x$.
Take two basis elements containing a chosen point $x$ in $S$, such that they are not subsets of one another(in which case the condition follows trivially). Every basis element can be defined by the hyperplane that generated it, to which there corresponds a unique point in $S$ whose inverse image is a ray perpendicular to this hyperplane. Choose a hyperplane corresponding to $x$, such that it is tangent to the boundary of $B_1$. Name the basis element generated by it $B'_1$. Choose another hyperplane corresponding to $x$ such that it is tangent to the boundary of $B_2$. Name the basis element generated by it $B'_2$. Then both $B'_1$ and $B'_2$ contain $x$, and either $B'_1 \subseteq B'2$ or $B'_2 \subseteq B'_1$, since they are generated by two parallel hyperplanes. Without loss of generality, choose the first option(proving the condition in the second option is the same). Since the boundary of $B'_2$ is tangent to the boundary of $B_2$, it may intersect the boundary $B_1$. But then since $B'_1 \subseteq B'_2$, it cannot have a non-empty intersection with $B_2$. Since it's boundary tangents the boundary of $B_1$, it's interior is then contained in $B_1 \cap B_2$. Therefore $B'_1$ is the sought for basis element, by construction. In the second case it would be $B'_2$.

This has proven that our collection of sets $U_i$ and $V_i$ is a basis, and therefore, the quotient topology is generated by it.

To prove that $\mathbb{R}P^n$ is Hausdorff, we need to show that two points $x_1$ and $x_2$ of $S$ may have disjunct neighbourhoods.
Choose two points $x_1$ and $x_2$ and hyperplanes corresponding to them in such a way, that those hyperplanes intersect outside $S$, and generate basis elements belonging to the collection $U_i$. Then those two basis elements $U_1$ and $U_2$ are disjunct trivially.
To prove that $\mathbb{R}P^n$ is second-countable, we may parametrize every basis element with the radius of the $(n-1)$-dimensional sphere that is it's boundary. Then we can choose for the basis of the quotient topology those basis elements that have rational radii. Such a basis is countable, so $\mathbb{R}P^n$ is second-countable.

I might have overcomplicated the solution, but I hope it is correct. I've only recently started improving in topology, so this was a nice exercise.

 

[member 587159]

Spoiler: Q7

Based on the equivalence relation given in the exercise, we find that this $n$-dimensional projective space is quotient space of $\mathbb{R}^{n+1}$ where points on every ray that is given by a $(n+1)$-dimensional vector from the origin are equivalent. Therefore, every equivalence class is one ray in $\mathbb{R}^{n+1}$, and quotient map with respect to which we define the topology, maps every point in $\mathbb{R}^{n+1}$ onto it's equivalence class. It is trivial to see that this map is surjective. We will use this map to induce quotient topology on the projective space. 'Geometrically', this space will then be given by a certain set of points on $S^n$, the $n$-dimensional hypersphere of unit radius with the center at the origin. Each point on the hypersphere will be mapped with inverse quotient map into a ray that is defined by the vector in $\mathbb{R}^{n+1}$. We notice that the points which are connected by the diameter of the hypersphere are also identified, that is, rays of opposite directions are also identified. So, bearing this in mind, we will define geometrical representation of $\mathbb{R}P^n$ in $\mathbb{R}^{n+1}$ with the following convention(it will make the treatment more palpable, at least to me):
1. We take $(0, 0, \dots , 0, 1)$ to be the north pole of $S^n$(All points/vectors we are mentioning are $\mathbb{R}^{n+1}$ coordinates notation).
2. Then $\mathbb{R}P^n$ is represented by a set of points on $S^n$ with positive coordinate $0 < x_{n+1} \leq 1$(northern hemisphere), and points $x_{n+1} = 0$ on $S^n$(equator), for which $x_1>0$, and points $x_{n+1}=0 , x_1 = 0$ for which $x_2>0$, etc. inductively, up until the point $(0, 0, \dots , 0, 1, 0)$.
Three-dimensional analog of this would be north hemisphere of a 3-dimensional sphere with equator circle given by points defined by $\phi \in [0,\pi)$, where $\phi$ is the azimuthal angle on the equator with $\phi=0$ defined to be measured counterclockwise from the point $(x =1 , y = 0, z=0)$.
We will call this geometrical representation of $\mathbb{R}P^n$, $S$, and it is homeomorphic to $\mathbb{R}P^n$.

The quotient topology is then induced in a standard way. Open sets in $R\mathbb{P}^n$ are sets who's inverse images under quotient map are open in $\mathbb{R}^{n+1}$. Let's take $P$ to be the set of all $n$-dimensional hyperplanes in $\mathbb{R}^{n+1}$ that intersect $S^n$. Their intersections will be $(n-1)$-dimensional spheres on the surface of this hypersphere. These $(n-1)$-dimensional spheres are contained in $S$, or they're intersecting $S$ or they're disjunct from $S$. We will consider the first two cases, since the third one isn't interesting to us.

In the first case, if we name interiors of those $(n-1)$-dimensional spheres, $U_i$, we find that inverse image of $U_i$ is the space bounded by a circular conical surface in $\mathbb{R}^{n+1}$, whose axis direction is given by the direction of the vector perpendicular to the hyperplane that generated the boundary of $U_i$ by intersecting with $S$. This set is obviously open in $\mathbb{R}^{n+1}$, so it should be open in the quotient topology.

In the second case, the $(n-1)$-dimensional hypersphere is intersecting $S$ and the intersection is an $(n-1)$ dimensional 'arc', with ends at the equator(If it's end is on the open-ended part of the equator, the arc is open-ended on that side, while if it's on the part of the equator that is included in $S$, then that end of the arc is closed(not in the sense of topology but in the sense that it includes the point from the equator)). The equator of $S^n$(or of $S$) is mapped by inverse quotient map into a hyperplane passing through the origin, which is open in $\mathbb{R}^{n+1}$, hence the equator of $S$ is open in quotient topology. However, the interior bounded by the arc and the equator, which we may call $W_i$ is mapped with inverse quotient map into space that is bounded on one side by part of a conical surface that is the image of the arc the same way as in case 1, and the hyperplane that is the image of the equator.
Also, it can be that the arc is actually half of the 'great circle' of $S$, in which case it is mapped into a hyperplane in $\mathbb{R}^{n+1}$ so in that case the inverse image of $W_i$ is the space between two intersecting hyperplanes passing through the origin(the direction of 'between' is given by any vector whose end is mapped into $W_i$). So this set in the second case is also open in $\mathbb{R}^{n+1}$, and therefore should be open in the quotient topology. So the union of $W_i$ and the part of the equator that is the boundary of $W_i$, which we can call $V_i$ is open in $\mathbb{R}^{n+1}$. We assert that the sets $U_i$ and $V_i$ consist the basis of quotient topology.
We need to check the two conditions for the basis:
1. For every $x \in S$ we have a basis element that contains it.
If we take an arbitrary $x \in S$, then the vector given by coordinates of $x$ in $\mathbb{R}^{n+1}$ defines the hyperplane that is perpendicular to it. We choose this hyperplane to intersect $S^n$ at the half the length of this vector, and obtain one of the two intersections mentioned above. Then such an intersection with $S$ defines a basis element $U_i$ or $V_i$ that contains $x$. The notion of length of this vector is not needed for this claim, since the point of intersection of the chosen hyperplane with the ray is defined with all the coordinates of $x$ halved.
2. If $x$ belongs to the intersection of two basis elements $B_1$ and $B_2$, then there exists a basis element $B_3 \subset B_1 \cap B_2$ containing $x$.
Take two basis elements containing a chosen point $x$ in $S$, such that they are not subsets of one another(in which case the condition follows trivially). Every basis element can be defined by the hyperplane that generated it, to which there corresponds a unique point in $S$ whose inverse image is a ray perpendicular to this hyperplane. Choose a hyperplane corresponding to $x$, such that it is tangent to the boundary of $B_1$. Name the basis element generated by it $B'_1$. Choose another hyperplane corresponding to $x$ such that it is tangent to the boundary of $B_2$. Name the basis element generated by it $B'_2$. Then both $B'_1$ and $B'_2$ contain $x$, and either $B'_1 \subseteq B'2$ or $B'_2 \subseteq B'_1$, since they are generated by two parallel hyperplanes. Without loss of generality, choose the first option(proving the condition in the second option is the same). Since the boundary of $B'_2$ is tangent to the boundary of $B_2$, it may intersect the boundary $B_1$. But then since $B'_1 \subseteq B'_2$, it cannot have a non-empty intersection with $B_2$. Since it's boundary tangents the boundary of $B_1$, it's interior is then contained in $B_1 \cap B_2$. Therefore $B'_1$ is the sought for basis element, by construction. In the second case it would be $B'_2$.

This has proven that our collection of sets $U_i$ and $V_i$ is a basis, and therefore, the quotient topology is generated by it.

To prove that $\mathbb{R}P^n$ is Hausdorff, we need to show that two points $x_1$ and $x_2$ of $S$ may have disjunct neighbourhoods.
Choose two points $x_1$ and $x_2$ and hyperplanes corresponding to them in such a way, that those hyperplanes intersect outside $S$, and generate basis elements belonging to the collection $U_i$. Then those two basis elements $U_1$ and $U_2$ are disjunct trivially.
To prove that $\mathbb{R}P^n$ is second-countable, we may parametrize every basis element with the radius of the $(n-1)$-dimensional sphere that is it's boundary. Then we can choose for the basis of the quotient topology those basis elements that have rational radii. Such a basis is countable, so $\mathbb{R}P^n$ is second-countable.

I might have overcomplicated the solution, but I hope it is correct. I've only recently started improving in topology, so this was a nice exercise.

Thanks for the answer! Looking at the projective space as a sphere with antipodal points identified is good intuition. My answer does not use this though but I looked up other answers and this is definitely a way to approach the problem.

For starters, it needs a proof that this construct $S$ is homeomorphic to my definition of the projective space.

To be quite explicit, describe the sphere with antipodal points identified somewhat more carefully (I guess you will need an equivalence relation for this), the topology you place on it and exhibit an explicit homeomorphism between your construct $S$ and the projective space.

 

[PeroK]

Thanks fresh_42, for reviewing my answer! I am not as strong on intuitive thinking as other people on this forum and will need to think a lot more to find a simpler approach that doesn't use Bayes' theorem. Since you mentioned that my previous answer was close, I make one more attempt at solving the problem and along the same lines as before. Smith will definitely have the choice of 50 seats if he is the 1st passenger to board, so I guess it should be assumed that Smith is NOT the last passenger to board, either because it is a trivial case and there is no choice to be made, or because the wording of the question says "printed on his boarding pass", so the last passenger has a pass and therefore is not Mr. Smith. If that assumption is made, only the final step in my earlier solution, and the probability of Smith being the $i^{th}$ passenger change. The probability of Smith being the $i^{th}$ passenger would be $1/49$ where $i \in {1, 2, .., 49}$. The final step therefore becomes:

Spoiler: Q14

Final unconditional probability of last passenger getting his/her originally allotted seat is $\sum_{i=1}^{49} 1/49 \times P_{i} = 49 \times 1/49 \times 1/2 = 1/2 = 0.5$

Note that $P_{50} = 1$ is still used in deriving $P_{49}, .., P_{1}$ and is a valid value because it represents the situation where the NONE of the passengers before the 50th passenger have occupied a seat that is different from what was originally allotted to them.

When I get some free time, I will continue pondering over this problem in the hope of finding a simpler, more elegant way to solve the problem. It requires more creative thinking and that doesn't come naturally to all

If it's not too late:

Spoiler

For a plane with any number of seats. Let's call Mr Smith's seat $S$ and the last to board's seat $X$.

When Mr Smith enters the plane, some seats are taken. But not $S$ or $X$. If Mr Smith sits elsewhere, then one and only one of seats $S$ or $X$ is left for the last passenger. To see this, imagine Mr Smith sits in seat $Y$. There are no problems until passenger $Y$ boards. If he/she sits in another seat $Z$, then there are no problems until passenger $Z$ boards. Sooner or later one of these displaced passengers sits in seat $S$ or $X$ and then there are no problems until $X$ boards.

As $S$ and $X$ are equally likely to be the one taken, the probability is equal that $X$ has his seat or Mr Smith's left.

If Mr Smith sits in his seat, $S$, then $X$ gets his correct seat. But, if Mr Smith sits in seat $X$, then $X$ gets Mr Smith's seat. As these happen with equal likelihood (whenever Mr Smith boards), again $X$ gets his seat or Mr Smith's with equal probability in these cases.

This assumes, as above, that Mr Smith is not the last passenger.

 

[PeroK]

14. (solved by @Not anonymous and by @PeroK ) Mr. Smith on a full up flight with 50 passengers on a CRJ 100 had lost his boarding pass. The flight attendant tells him to sit anywhere. All other passengers sit on their booked seats, unless it is already occupied, in which case they randomly choose another seat just like Mr. Smith did. What are the chances that the last passenger gets the seat printed on his boarding pass?

I have a generalisation of this for any passenger. Assume Mr Smith boards first. Suppose there are $N$ seats on the flight and consider the $K$th last to board and the set of $K + 1$ seats that are Mr Smith's seat and the $K$ seats of the last $K$ passengers to board. Note that the $K$th last to board gets their seat as long as one of the other $K$ seats in that list gets occupied before their seat. The probability they get their seat is, therefore, $K/(K+1)$.

To see this, Mr Smith is equally likely to sit in anyone of these $K +1$ seats. If he does, then the remaining passengers gets their correct seats until possibly the $K$th last. If Mr Smith picks another seat, then the passenger whose seat he has taken is again equally likely to sit in anyone of those $K + 1$ seats. And, if he/she sits in another seat, then the same applies to the next displaced person etc.

In any case, when the $K$th last passenger boards, there is a probability of only $1/(K+1)$ that their seat is occupied.

And, even if Mr Smith does not board first then the same probabilities apply to all passengers who board after Mr Smith. I.e. everyone before Mr Smith gets their seat with probability $1$; and, everyone after Mr Smith gets their seat with probability $K/(K+1)$, if they are the $K$th last to board.

 

[fresh_42]

If it's not too late:

Spoiler

For a plane with any number of seats. Let's call Mr Smith's seat $S$ and the last to board's seat $X$.

When Mr Smith enters the plane, some seats are taken. But not $S$ or $X$. If Mr Smith sits elsewhere, then one and only one of seats $S$ or $X$ is left for the last passenger. To see this, imagine Mr Smith sits in seat $Y$. There are no problems until passenger $Y$ boards. If he/she sits in another seat $Z$, then there are no problems until passenger $Z$ boards. Sooner or later one of these displaced passengers sits in seat $S$ or $X$ and then there are no problems until $X$ boards.

As $S$ and $X$ are equally likely to be the one taken, the probability is equal that $X$ has his seat or Mr Smith's left.

If Mr Smith sits in his seat, $S$, then $X$ gets his correct seat. But, if Mr Smith sits in seat $X$, then $X$ gets Mr Smith's seat. As these happen with equal likelihood (whenever Mr Smith boards), again $X$ gets his seat or Mr Smith's with equal probability in these cases.

This assumes, as above, that Mr Smith is not the last passenger.

It's never too late for a second solution, or in this case, a third since the solutions have been published.