# Challenge Math Challenge - November 2019

• Featured

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

Gold Member
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.

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

Gold Member
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$$

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

Gold Member
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?

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.

Last edited:

#### Infrared

Gold Member
@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

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

Mentor
2018 Award
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.

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.

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

Mentor
2018 Award
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.

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:

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

Mentor
2018 Award
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.

#### Math_QED

Homework Helper
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.

Last edited:

"Math Challenge - November 2019"