Challenge Ready for a Summer Math Challenge?

[fresh_42]

Summer is coming and brings a new basic math challenge! Enjoy! For more advanced problems you can check our other intermediate level math challenge thread!

RULES:
1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
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.
5) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted by @fresh_42

QUESTIONS:

1. (solved by @Mr Davis 97 ) Show that $\arctan \sqrt \frac{1 - x}{1 + x} + \frac{1}{2} \arcsin x = \frac{\pi}{4}$, for all $x \in (-1, 1)$ (by @QuantumQuest)
2. (solved by @mfb ) You want to drive a car around a one way circular track. The car uses a constant amount of diesel per mile driven. There are N diesel canisters mischievously placed around the track. Summing over all gas canisters there is enough fuel to make one full trip /cycle around the track. Your car initially has no gas. Does there always exist a starting position (i.e. at one of the N gas canisters) that you may choose such that you can complete one full trip around the track? (by @StoneTemplePython)
3. (solved by @ehild ) The angle bisector in a given triangle $\bigtriangleup ABC$ of the angle $\alpha = \sphericalangle BAC$ at $A$ intersects the side $\overline{BC}$ at the point $D$. We have the information:
   \begin{align*}
   \overline{BD}\cdot \overline{CD}&= \overline{AD}\,^2 \\
   \sphericalangle ADB &= 45°
   \end{align*}
   a) Determine the inner angles of $\bigtriangleup ABC$.
   b) Determine the precise ratio at which $D$ divides $\overline{BC}$
   (by @fresh_42)
4. (solved by @ehild ) The beam from a lighthouse $3$ miles from a straight coastline turns at the rate of $5$ revolutions per minute. How fast is the point $P$ at which the beam hits the shore moving when that point is $4$ miles from point $A$ on the shore directly opposite the lighthouse? (by @QuantumQuest)
5. (solved by @Mr Davis 97 ) Compute the arc length $\mathcal{L}$ of the cycloid
   $$\gamma\, : \,\mathbb{R} \longrightarrow \mathbb{R}^2\, , \,\gamma(t)=(t-\sin(t),1-\cos(t))$$
   between two neighboring singularities. (by @fresh_42)
6. (solved by @Mr Davis 97 )Let $a$ be an integer and $b$ be also an integer which is formed from $a$ by reversing the order of its digits.
   Show that $a \equiv b \mod 9\,$. (by @QuantumQuest)
7. An urn contains balls, each of which has one of the following colors: red, green, blue and yellow balls. Balls are sampled randomly with replacement. Let r, g, b, and y represent the probabilities of drawing a red, green, blue or yellow.
   
   a) (solved by @Math_QED ) what is the expected number of balls chosen before obtaining the first yellow ball?
   b) (solved by @PeroK ) what is the expected number of different colors of balls obtained before getting the first yellow ball?
   (by @StoneTemplePython)
8. Let $f$ be a differentiable function in $\mathbb{R}$. If $f'$ is invertible and $(f')^{-1}$ is differentiable in $\mathbb{R}$, show that $[I_A (f')^{-1} - f \circ [(f')^{-1} ]]' = (f')^{-1}$ where $I_A$ with $I_A(x) = x$ is the identity function $I_A : A \to A$
   (by @QuantumQuest)
9. (solved by @lpetrich ) At the cash desk of a shopping center five friends (Diana, Ike, Jessica, Stan, Valery) are standing in a row. They are all different in age (26, 27, 30, 33 and 35 years) and would like to buy all different tops (shirt, polo shirt, pullover, sweatshirt and T-shirt) for themselves. The tops are all different colors (blue, yellow, green, red and black) and different sizes (XS, S, M, L and XL).
   
   Find out who is where, how old and what top to buy in which color and size. The positions in the queue can be seen from the cashier, i.e. "front" or "the first person" is right at the cash register. There are no other people in the queue and the cashier is to be ignored.
   
   A. Diana, who wants to buy a top in size XL, stands further ahead than the person who wants to buy a black top.
   B. Jessica stands in front of the person who wants to buy a polo shirt.
   C. The second person in the queue wants to buy a yellow top.
   D. The t-shirt is not red.
   E. Stan wants to buy a sweatshirt. The person standing in front of him is older than the person standing directly behind him.
   F. Ike needs a top in size L.
   G. The last person in the queue is 30 years old.
   H. The oldest person wants to buy the top in the smallest size.
   I. The person standing directly behind Valery wants to buy a red top that is larger than size S.
   J. The youngest person wants to buy a yellow top.
   K. Jessica wants to buy a shirt.
   L. The third person in the queue wants to buy a top in size M.
   M. The polo shirt is red, yellow or green.
   (by @fresh_42)
10. (solved by @lpetrich ) Suppose we have two $\text{ n x n }$ commuting matrices, $\mathbf X$ and $\mathbf Y$.
    
    $\mathbf X$ is special because there exists some positive integer $k$ where $\mathbf X^k = \mathbf I$. On the other hand, $\mathbf Y$ is nilpotent.
    a) Prove that $\mathbf Z := \big(\mathbf X + \mathbf Y\big)$ is nonsingular, and
    b) compute the $\mathbf Z^{-1}$.
    (by @StoneTemplePython)

 

[prakhargupta3301]

Answering to question 2:
No. It isn't.
Here is my logic.
Rate of usage: 1l of diesel per mile.
Let the number of canisters be 'N.'
However, all the canisters spread around the track aren't of equal capacity, as it isn't mentioned otherwise in the question.
Let: The track be of 100 miles. There are 2 canisters overall. One of 1l diesel and other of 99litres of diesel.
It isn't mentioned that the can containing 99litres of diesel WILL be at the starting of 2nd mile (when fuel of 1st can is exhausted). All that is mentioned is that the ∑Fuel spread over the track is 100 litres.
But, the fuel can of 99l diesel might be kept at not a point where 1 litre diesel gets finished, for example, at 5th mile. 3 miles away from the stopped car.

Hence, the answer is no.
(Note: The only possibility of the driver completing the circuit is when the cans of x litres are kept at a distance of x miles from each other. The value of x is variable for every checkpoint or everytime the driver picks up a can. For eg, if a driver picks up a can of 5litres diesel, the next can MUST be kept at 5 miles away.)
Thank you.

 

[StoneTemplePython]

Let: The track be of 100 miles. There are 2 canisters overall. One of 1l diesel and other of 99litres of diesel.
It isn't mentioned that the can containing 99litres of diesel WILL be at the starting of 2nd mile (when fuel of 1st can is exhausted).

I'd suggest carefully re-reading the question. It in fact says

Your car initially has no gas. Does there always exist a starting position (i.e. at one of the N gas canisters) that you may choose such that you can complete one full trip around the track?

 

[Mr Davis 97]

Here is my solution to question 1:

Spoiler

First, we focus on simplifying the expression $\displaystyle \arctan \sqrt \frac{1 - x}{1 + x}$. Let $x = \cos 2 t$. Then $\displaystyle \arctan \sqrt \frac{1 - \cos 2t}{1 + \cos 2t} = \arctan \sqrt \frac{2 \sin^2 t}{2 \cos^2 t} = \arctan |\tan t |$. Since $x \in (-1,1)$, we know $t \in (0, \pi /2)$, so $\tan t > 0$ and we can drop the absolute value. So ultimately, we have that $\displaystyle \arctan \sqrt \frac{1 - x}{1 + x} = t = \frac{1}{2} \arccos x$. Now, $\displaystyle \frac{1}{2} \arcsin x + \frac{1}{2} \arccos x = \frac{1}{2} (\arcsin x + \arccos x)$. But by the cofunction identities $\sin (\pi / 2 - \theta) = \cos \theta \implies \sin (\pi / 2 - \arccos x ) = x \implies \pi / 2 - \arccos x = \arcsin x \implies \arcsin x + \arccos x = \pi / 2$ as long as $x \in (-1, 1)$.
So we have our final answer, $\displaystyle \frac{1}{2} \cdot \frac{\pi}{2} = \frac{\pi}{4}$.

 

[Mr Davis 97]

Here is my solution to question 5:

Spoiler

Every singularity occurs at $t = 2 \pi n$ where $n \in \mathbb{Z}$. We will compute the arc length from $0$ to $2 \pi$. From multivariable calculus, we know that when a curve is defined parametrically the arc length along the curve as $t$ varies from $a$ to $b$ is $\displaystyle \int_a^b \sqrt{\left( \frac{dx}{dt}\right)^2 + \left( \frac{dy}{dt} \right)^2} ~ dt$. Substituting the information we have on hand results in the following integral: $\displaystyle \int_0^{2 \pi} \sqrt{(1-\cos t)^2 + ( \sin t)^2} ~ dt = \int_0^{2 \pi} \sqrt{2 - 2 \cos t} ~ dt = \sqrt{2} \int_0^{2 \pi} \sqrt{1 - \cos t} ~ dt$. By symmetry of the integrand, we have the equivalent integral $\displaystyle 2 \sqrt{2} \int_0^{\pi} \sqrt{1 - \cos t} ~ dt$. Note that $\displaystyle 2 \sin^2 (\frac{t}{2}) = 1 - \cos t$, so we merely have to evaluate $\displaystyle 4 \int_0^{\pi} \sin \frac{t}{2} ~ dt$, which is equal to $\displaystyle 4 \left[- 2\cos \frac{t}{2} \right]_0^{\pi} = -8 [0 - 1] = 8$.

 

[Mr Davis 97]

Here is my solution to question 6:

Spoiler

Suppose that $a$ is a k-digit integer. So $a =a_{k-1}a_{k-2} \dots a_2 a_1 a_0 = a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0$. Therefore $b = a_{0}a_{1} \dots a_{k-3} a_{k-2} a_{k-1} = a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1}$. We'll start by computing $a$ mod 9. First, we'll focus on each summand of $a$. Let $n \in [0, k-1]$. Then $\displaystyle a_n 10^n \equiv a_n (1+9)^n \equiv a_n \sum_{i=0}^{n} \dbinom{n}{i} (1)^{n-i}(9)^i \equiv a_n (1 + n 9 + \cdots + n 9^{n-1} + 9^n) \equiv a_n \bmod{9}$. Hence $a \equiv a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0 \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \bmod{9}$. Therefore, $b \equiv a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1} \equiv a_0 + a_1 + \cdots a_{k-3} + a_{k-2} + a_{k-1} \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \equiv a \bmod{9}$

 

[lpetrich]

I have a solution for question 9, but its derivation is very lengthy, with several multiple partial solutions. I was unable to think of a way of avoiding that multiplicity -- it reached 9 at one point.

 

[fresh_42]

I have a solution for question 9, but its derivation is very lengthy, with several multiple partial solutions. I was unable to think of a way of avoiding that multiplicity -- it reached 9 at one point.

There is a golden way to solve it, but it is certainly not easy to see from the start. But once you have the solution, couldn't you reconstruct from there, which way avoids the large number of cases?

 

[lpetrich]

I will try 9:

Spoiler

The solution's rows will be from first to last in line, and the solution's columns will be name, age, top, color, size

Using rules C, G, J, and L gives
Name, Age, Top, Color, Size
--, --, --, --, --
--, 26, --, Yellow, --
--, --, --, --, M
--, --, --, --, --
--, 30, --, --, --

For H, there are two possibilities:
Name, Age, Top, Color, Size
--, 35, --, --, XS
--, 26, --, Yellow, --
--, --, --, --, M
--, --, --, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, --, --, --, --
--, 26, --, Yellow, --
--, --, --, --, M
--, 35, --, --, XS
--, 30, --, --, --

Rule E splits them further:
Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, --
--, 27, --, --, M
--, 33, --, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, --
--, 33, --, --, M
--, 27, --, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 35, --, --, XS
--, 26, --, Yellow, --
--, 33, --, --, M
Stan, 27, Sweatshirt, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 33, --, --, --
Stan, 26, Sweatshirt, Yellow, --
--, 27, --, --, M
--, 35, --, --, XS
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 27, --, --, --
--, 26, --, Yellow, --
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
--, 30, --, --, --

Rules A and F give:
Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, S
--, 27, --, --, M
Diana, 33, --, --, XL
Ike, 30, --, Black, L

Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, S
--, 33, --, --, M
Diana, 27, --, --, XL
Ike, 30, --, Black, L

Name, Age, Top, Color, Size
--, 35, --, --, XS
Diana, 26, --, Yellow, XL
--, 33, --, --, M
Stan, 27, Sweatshirt, --, S
Ike, 30, --, --, L

Name, Age, Top, Color, Size
Diana, 33, --, --, XL
Stan, 26, Sweatshirt, Yellow, S
--, 27, --, --, M
--, 35, --, --, XS
Ike, 30, --, --, L

Name, Age, Top, Color, Size
Diana, 27, --, --, XL
Ike, 26, --, Yellow, L
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
--, 30, --, --, S

Name, Age, Top, Color, Size
Diana, 27, --, --, XL
--, 26, --, Yellow, S
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
Ike, 30, --, --, L

Name, Age, Top, Color, Size
Ike, 27, --, --, L
Diana, 26, --, Yellow, XL
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
--, 30, --, --, S

Name, Age, Top, Color, Size
--, 27, --, --, S
Diana, 26, --, Yellow, XL
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
Ike, 30, --, --, L

Rules B, I, and K trim them down:
Name, Age, Top, Color, Size
Diana, 33, --, --, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, --, M
Valery, 35, Polo Shirt, --, XS
Ike, 30, --, Red, L

Rules D and M:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, --, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, --, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, --, Red, L

Rule A:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, --, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, Black, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, --, Red, L

The remaining shirt type and color complete the solution:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, Blue, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, Black, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, Pullover, Red, L

 

[fresh_42]

I will try 9:
The remaining shirt type and color complete the solution:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, Blue, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, Black, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, Pullover, Red, L

Forgive me that I didn't check the way (mine is of course slightly different), but the result is correct!

 

[fresh_42]

Here is my solution to question 5:

Spoiler

Every singularity occurs at $t = 2 \pi n$ where $n \in \mathbb{Z}$. We will compute the arc length from $0$ to $2 \pi$. From multivariable calculus, we know that when a curve is defined parametrically the arc length along the curve as $t$ varies from $a$ to $b$ is $\displaystyle \int_a^b \sqrt{\left( \frac{dx}{dt}\right)^2 + \left( \frac{dy}{dt} \right)^2} ~ dt$. Substituting the information we have on hand results in the following integral: $\displaystyle \int_0^{2 \pi} \sqrt{(1-\cos t)^2 + ( \sin t)^2} ~ dt = \int_0^{2 \pi} \sqrt{2 - 2 \cos t} ~ dt = \sqrt{2} \int_0^{2 \pi} \sqrt{1 - \cos t} ~ dt$. By symmetry of the integrand, we have the equivalent integral $\displaystyle 2 \sqrt{2} \int_0^{\pi} \sqrt{1 - \cos t} ~ dt$. Note that $\displaystyle 2 \sin^2 (\frac{t}{2}) = 1 - \cos t$, so we merely have to evaluate $\displaystyle 4 \int_0^{\pi} \sin \frac{t}{2} ~ dt$, which is equal to $\displaystyle 4 \left[- 2\cos \frac{t}{2} \right]_0^{\pi} = -8 [0 - 1] = 8$.

Yes, that's correct. The symmetry argument could be replaced by changing $t \mapsto \frac{1}{2}t$ earlier, but this doesn't make a difference. Well done!

 

[QuantumQuest]

Here is my solution to question 1:

Well done @Mr Davis 97.

 

[QuantumQuest]

Here is my solution to question 6:

Your solution is correct up to the point you express $b$ in the last line. Could you write $b$ in a more clear way and how you reach the expression that is to be proved?

 

[lpetrich]

Solution for question 10:

Spoiler

I start with noting that if a matrix $A$ is invertible, then its inverse $A^{-1}$ satisfies $A A^{-1} = A^{-1} A = I$.

The matrix $X$ has an inverse: $X^{k-1}$. It is easy to verify that: $X^{k-1} X = X X^{k-1} = X^k = I$

The matrix $Y$ is nilpotent: $Y^p = 0$ for some positive integer p.

From $X$ and $Y$ commuting, it can be shown that any power of $X$ will also commute with any power $Y$. I will show that for the inverse of $X$ with $Y$ itself. Take $X Y = Y X$ and multiply both sides by $X^{-1}$. Then, $X^{-1} X Y X^{-1} = X^{-1} Y X X^{-1}$ or $Y X^{-1} = X^{-1} Y$.

We wish to find $Z = X + Y$. Simplify it by setting $Y = X U$, where $U = X^{-1} Y$. This gives us $Z = X (I + U)$. Take a power of $U$: $U^m = X^{-m} Y^m$. This means that $U^p = 0$, and that $U$ is also nilpotent. It can also be shown that all powers of $U$ commute with all powers of $X$.

It is easiest to do Part (b) first. Set up $W = 1 - U + U^2 - U^3 + U^4 - ... +(-U)^{p-1}$. Multiply it by $I+U$:
$$ W(1+U) = (1+U)W = 1 + U - U - U^2 + ... + (-1)^{p-1} U^p = I $$
The answer:
$$ Z^{-1} = X^{-1} W $$
By construction,
$$Z^{-1} Z = X^{-1} W X (I + U) = W (I + U) = I ,\\ Z Z^{-1} = X (I + U) X^{-1} W = (I + U) W = I$$
Turning to Part (a), the successful construction of an inverse for Z means that Z is nonsingular.

 

[StoneTemplePython]

This works, and is a variant of the standard answer.
- - - -
A tiny bit of cleanup (i.e. consistent use of $\mathbf I$ not $1$) would help readability, e.g. here:

It is easiest to do Part (b) first. Set up $W = 1 - U + U^2 - U^3 + U^4 - ... +(-U)^{p-1}$. Multiply it by $I+U$:
$$ W(1+U) = (1+U)W = 1 + U - U - U^2 + ... + (-1)^{p-1} U^p = I $$

- - - -
directly showing the inverse of $\mathbf Z$, well, shows it is invertible.

However, it may be worth noting that $p(1) \neq 0$ for the characteristic polynomial of a nilpotent matrix, but this is exactly what is given by $\det\big(-\mathbf X^{-1}\mathbf Y - \mathbf I \big)$ hence we know

$\det\big( \mathbf Z\big) = \det\big(\mathbf X + \mathbf Y\big) = \det\big(\mathbf Y + \mathbf X\big) = \det\big(-\mathbf X\big) \det\big(-\mathbf X^{-1}\mathbf Y - \mathbf I \big) \neq 0$

 

[Pro7]

I have got the solution to question 3 as follows
angles are A=60, B=105 , C=15 (all in degrees)
BD/CD = tan(15) ...(15 also is in degrees)
I am having a hard time uploading the proof as I've done it in a note book and I am not quite sure how to write mathematical statements here.(I am well aware of the rules)
I have the scanned images of the notebook answers, can someone tell how to upload here?

 

[fresh_42]

I have got the solution to question 3 as follows
angles are A=60, B=105 , C=15 (all in degrees)
BD/CD = tan(15) ...(15 also is in degrees)
I am having a hard time uploading the proof as I've done it in a note book and I am not quite sure how to write mathematical statements here.(I am well aware of the rules)
I have the scanned images of the notebook answers, can someone tell how to upload here?

Uploads are only second best solution, if not third as they cannot be accessed (on the bottom right of this edit window is the functionality for it, or use the image icon next to the smiley). Under Info you will find this https://www.physicsforums.com/help/latexhelp/ which includes the basis to write LaTeX. It's really not very difficult and in case you want to post more frequently on PF or you will have to write science articles elsewhere, it's worth learning it. Here are two other helpful pages:
http://detexify.kirelabs.org/symbols.html
https://www.sharelatex.com/learn/Spacing_in_math_mode

For the ratio, the precise value was asked for, i.e. a real number (root expressions are allowed), not the tangent of an angle.

 

[archaic]

Solution for question six :
We have $a = a_0a_1...a_n$ and $b = a_na_{n-1}...a_0$ (would work for any order though), we could rewrite them as $a = (a_n * 10^0) + (a_{n-1} * 10^1) + ... + (a_0 * 10^n)$ and $b = (a_0 * 10^0) + (a_1 * 10^1) + ... + (a_n * 10^n)$ and we know that $10^n \equiv 1 [9]$ thus $a \equiv b [9]$

 

[QuantumQuest]

Solution for question six :

What you write is correct but it is not a full solution.

 

[archaic]

What you write is correct but it is not a full solution.

Alright let me edit a little.

Solution for question six :
We have $a = a_0a_1...a_n$ and $b = a_na_{n-1}...a_0$ (would work for any order though), we could rewrite them as :
$a = (a_n * 10^0) + (a_{n-1} * 10^1) + ... + (a_0 * 10^n)$ and $b = (a_0 * 10^0) + (a_1 * 10^1) + ... + (a_n * 10^n)$ and we know that $10^n \equiv 1 [9]$ which gives us $a \equiv a_n + a_{n-1} + ... + a_0 [9]$ and also $b \equiv a_0 + a_1 + ... + a_n [9]$
Moreover, addition is commutative $=> a \equiv b [9]$

 

[archaic]

What you write is correct but it is not a full solution.

Mr Davis had already solved it I think,

Here is my solution to question 6:

Spoiler

Suppose that $a$ is a k-digit integer. So $a =a_{k-1}a_{k-2} \dots a_2 a_1 a_0 = a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0$. Therefore $b = a_{0}a_{1} \dots a_{k-3} a_{k-2} a_{k-1} = a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1}$. We'll start by computing $a$ mod 9. First, we'll focus on each summand of $a$. Let $n \in [0, k-1]$. Then $\displaystyle a_n 10^n \equiv a_n (1+9)^n \equiv a_n \sum_{i=0}^{n} \dbinom{n}{i} (1)^{n-i}(9)^i \equiv a_n (1 + n 9 + \cdots + n 9^{n-1} + 9^n) \equiv a_n \bmod{9}$. Hence $a \equiv a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0 \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \bmod{9}$. Therefore, $b \equiv a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1} \equiv a_0 + a_1 + \cdots a_{k-3} + a_{k-2} + a_{k-1} \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \equiv a \bmod{9}$

 

[Thugles]

For question 2: Yes.

Let's divide the track in 360 equal parts (360 degrees)
Summing all diesel canisters, the car is able to complete at least one full cycle, which means each canister contains an amount of fuel that is enough for the car to run a mininum distance of L = 360/n (n being the number of diesel canisters). For instance: if n = 2, then each canister is enough for the car to run through half the track (L = 360/2 = 180) and so on.

Therefore, for the car not be able to complete the track, each canister must be positioned at a distance X > L from each other. Summing all these distances, we have nX, which is also the total length of the track. Therefore:

X > L
nX > nL
nX > n*(360/n)
nX > 360

Which is impossible, since the track has 360 degrees only.

(English is not my main language, and I apologize for any mistakes. I read that question several times, but I still may have committed an intepretation mistake; so sorry in advance!)

Edit: forgot to add one explanation.

 

[StoneTemplePython]

Let's divide the track in 360 equal parts (360 degrees)
Summing all diesel canisters, the car is able to complete at least one full cycle, which means each canister contains an amount of fuel that is enough for the car to run a mininum distance of L = 360/n (n being the number of diesel canisters). For instance: if n = 2, then each canister is enough for the car to run through half the track (L = 360/2 = 180) and so on.

I like the gist of this but I didn't follow:

Therefore, for the car not be able to complete the track, each canister must be positioned at a distance X > L from each other. Summing all these distances, we have nX, which is also the total length of the track.

It is not that each cannister must be $\gt L$ it is merely that problems can occur if there is even one of those cases-- for any selected sample path, if you hit one of those 'extra long' gaps and don't have enough gas in the tank at the time you encounter it, then you fail.

- - - -
Note: there are some additional challenges in using a discretization argument like this -- what if a car is at the beginning, middle or end of an interval? One could run out of gas in the beginning of an interval with the car at the end of that same interval... If you divide the track into $K$ partitions and select large $K \gt \gt 360$ you can of course get better and better approximations and eventually an arbitrarily good approximation. (For purposes of this problem we may envision the cars as dots /points on this track). I don't think this needs belaboring for Basic challenge, but I will say that strictly speaking this approach does introduce additional technical challenges -- I know of a couple of much simpler solutions that don't require any notion of limits.

You may find it instructive to focus on the 2 cars case a bit more.

 

[QuantumQuest]

Alright let me edit a little.

Solution for question six :

Mr Davis had already solved it I think,

After you express $a$ and $b$ as a sum of products there is a more rigorous way in order to show that $a \equiv b\mod9$. Obviously, I can't tell what it is but as a hint it utilizes polynomials and a known property of modulus.

For @Mr Davis 97 solution see my post #13. Again the same hint I gave you above holds true.

 

[mfb]

@Thugles: The canisters don't have to have the same amount of fuel and the same distance between them.
They also don't have to be at integer degrees.

Spoiler

Once the problem is solved, it can be interesting to consider what changes if we allow an infinite number of fuel depots. It won't help finding a solution to the finite case, however.

 

[Thugles]

I like the gist of this but I didn't follow:
It is not that each cannister must be $\gt L$ it is merely that problems can occur if there is even one of those cases-- for any selected sample path, if you hit one of those 'extra long' gaps and don't have enough gas in the tank at the time you encounter it, then you fail.

I see the mistake now!

The clarification from @mfb is something I really didn't considerate. I'm having trouble my initial logic, so I'll try a different approach:

Considering U = units of distance and F = units of fuel. Since the total amount of fuel is always enough for the car to complete one cycle, we can assume that the amount of units traveled is the same amount of units of fuel used, which means that, for the complete circuit, $X = U$ (from starting point A to final point A): $U_{a,a} = F_{a,a}$

(I'm not sure if it's necessary to add but that basically means that we can find a relation of U = kF, where k is a real constant. We are assuming k = 1 for simplification purposes)

Since the car starts without gas, it necessarily has to pick the starting point at one of the canisters.

Assuming N = 2, we have two canisters A and B. Assuming A to be the starting point. The car will fail only if the amount of units traveled (from A to B) is greater than the amount of fuel he has available on that interval, which means $U_{a,b} > F_{a,b}$. Having in mind that $U_{a,a} = U_{a,b} + U_{b,a}$ and $F_{a,a} = F_{a,b} + F_{b,a}$, and we know that the whole circle must wield $U_{a,a} = F_{a,a}$: if the route AB makes the car run out of fuel before reaching canister B, then route BA makes the car arrive in canister A with more than enough fuel: $U_{b,a} < F_{b,a}$ to compensate. Therefore the car could simply start from point B.

This always applies, no matter how many canisters we have. We know it's possible to divide all the fuel available and also divide all the length of the track in the same number of partitions. No matter how many canisters we have, there is always a possible starting point. If there is a portion of the track between two canisters (1 and 2) that would make the car run out of fuel before reaching the second canister, it will be compensated by another portion of the track where the car will reach the second canister with more fuel than necessary (that "extra" amount is exactly how much the car lacked in the first situation).

(I had some trouble taking these out of my head; I apologize if it got too confusing)

 

[StoneTemplePython]

Since the car starts without gas, it necessarily has to pick the starting point at one of the canisters.

Assuming N = 2, we have two canisters A and B. Assuming A to be the starting point. The car will fail only if the amount of units traveled (from A to B) is greater than the amount of fuel he has available on that interval, which means $U_{a,b} > F_{a,b}$. But we know that the whole circle must wield $U_{a,a} = F_{a,a}$: if the route AB makes the car run out of fuel before reaching canister B, then route BA makes the car arrive in canister A with more than enough fuel: $U_{b,a} < F_{b,a}$ to compensate. Therefore the car could simply start from point B.

I like this quite a bit.

This always applies, no matter how many canisters we have. We know it's possible to divide all the fuel available and also divide all the length of the track in the same number of partitions. No matter how many canisters we have, there is always a possible starting point. If there is a portion of the track between two canisters (1 and 2) that would make the car run out of fuel before reaching the second canister, it will be compensated by another portion of the track where the car will reach the second canister with more fuel than necessary (that "extra" amount is exactly how much the car lacked in the first situation).

I'm not quite buying this argument. Yes, if things are not uniform, (at least) one canister must have an "extra amount". But how do we know that you can always get this "extra amount" without first running out of gas, merely by choosing a 'good' starting position?

(I had some trouble taking these out of my head; I apologize if it got too confusing)

I think your intuition is good here. The fact that you have the $N=2$ case locked down and you're having trouble translating thoughts to paper for the general case would strongly hint at trying to formalize the $N > 2$ case, perhaps in terms of a smaller subproblem that you've already solved...

 

[QuantumQuest]

Regarding problem $6$: Although a more rigorous argument, using polynomials and the property of modulus that if $a \equiv b\mod m$ then it also holds that $f(a) \equiv f(b)(\mod m)$ where $f(x)$ is a polynomial with integer coefficients, can be used in order to conclude to what is asked in the question, I think that @Mr Davis 97 can get the solution credit as it becomes evident from his solution that finally $a \equiv b\mod 9$. Also, @archaic's solution is along the same lines and can be regarded as correct but it came after Mr Davis 97's solution.

 

[Thugles]

I think your intuition is good here. The fact that you have the $N=2$ case locked down and you're having trouble translating thoughts to paper for the general case would strongly hint at trying to formalize the $N > 2$ case, perhaps in terms of a smaller subproblem that you've already solved...

(Consider a "portion" as being a section of track between two canisters)

We already know it's possible to divide both the total amount of fuel (F) and the total length (U) in the same number of partitions. Therefore, $U = F$.

If we number all the canisters (from 1 to n) in their respective positions, we have, for the general case:

$U = U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n}$
$F = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n}$

(I thought about writing the second one as $F = F_{1} + F_{2} + F_{3} + ... + F_{n}$; instead, intepret $F_{a,b}$ simply as the amount of fuel in canister a)

Since $U = F$, we have $U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n} = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n} = C$ (with C being a real constant)

Therefore, no matter how many "low fuel canisters" or "really lenghty portions" we have; they will be balanced by canisters with more fuel and shorter lenghts. If that didn't happen, the relation wouldn't remain constant.

(But I'm afraid I'm just saying that that the amount of fuel is almost enough, instead of answering the question...?)

I'm not quite buying this argument. Yes, if things are not uniform, (at least) one canister must have an "extra amount". But how do we know that you can always get this "extra amount" without first running out of gas, merely by choosing a 'good' starting position?

I think I can see the "informal" solution but I'm sure sure if I can express that in a mathematical way
To me, since U = F, distributing the fuel is the same thing as distributing the circle. It's impossible to distribute circle in a way that it's impossible to make the cycle; taking away from one portion means compensating it somewhere else, and we are always going to have a starting point.

The "perfect" way of having the car run the cycle is by distributing the cannisters symmetrically with the same amount of fuel in each of them (therefore the car arrives at each canister exactly when he's about to run out of fuel), which means any canister is a valid starting point. If I want the car to fail, I need to either remove a bit of fuel in one canister and add in on the another one or move one of the canisters a little bit towards either direction, in order to create one particular portion of track that is bigger than the car can reach.

But, due to the symmetry of the arrangement and the circle, removing fuel or adding length to a portion would end up adding fuel or removing length to another portion. There will always be at least one spot where the amount of fuel required to reach the next canister is greater than the amount of units I need to run, giving me "extra" fuel to compensate the places where I was supposed to dail.

(Thanks for all the clarifying replies. Now I realize I underestimated that question quite a bit! Last try for today, I promise)

 

[mfb]

(But I'm afraid I'm just saying that that the amount of fuel is almost enough, instead of answering the question...?)

So far you only demonstrated that your overall fuel balance will work out - but that was given already.

In general, there will be only one starting point where you can complete the circle. Given the positions and fuel amounts, how can you find this point?

 

[StoneTemplePython]

I'm not sure what happened to the spoiler tags, but I'll nest your responses in them, for space reasons:

Spoiler

(Consider a "portion" as being a section of track between two canisters)

We already know it's possible to divide both the total amount of fuel (F) and the total length (U) in the same number of partitions. Therefore, $U = F$.

If we number all the canisters (from 1 to n) in their respective positions, we have, for the general case:

$U = U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n}$
$F = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n}$

(I thought about writing the second one as $F = F_{1} + F_{2} + F_{3} + ... + F_{n}$; instead, intepret $F_{a,b}$ simply as the amount of fuel in canister a)

Since $U = F$, we have $U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n} = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n} = C$ (with C being a real constant)

Therefore, no matter how many "low fuel canisters" or "really lenghty portions" we have; they will be balanced by canisters with more fuel and shorter lenghts. If that didn't happen, the relation wouldn't remain constant.

(But I'm afraid I'm just saying that that the amount of fuel is almost enough, instead of answering the question...?)

So if you were allowed to choose the sequencing then the above equations would work. However the problem is that I mischievously get to choose the sequencing of the gas canisters. You don't get to permute them / choose their ordering in general. You can only choose where you start in the cycle (i.e. a cyclic property).

Spoiler

I think I can see the "informal" solution but I'm sure sure if I can express that in a mathematical way
To me, since U = F, distributing the fuel is the same thing as distributing the circle. It's impossible to distribute circle in a way that it's impossible to make the cycle; taking away from one portion means compensating it somewhere else, and we are always going to have a starting point.

The "perfect" way of having the car run the cycle is by distributing the cannisters symmetrically with the same amount of fuel in each of them (therefore the car arrives at each canister exactly when he's about to run out of fuel), which means any canister is a valid starting point. If I want the car to fail, I need to either remove a bit of fuel in one canister and add in on the another one or move one of the canisters a little bit towards either direction, in order to create one particular portion of track that is bigger than the car can reach.

But, due to the symmetry of the arrangement and the circle, removing fuel or adding length to a portion would end up adding fuel or removing length to another portion. There will always be at least one spot where the amount of fuel required to reach the next canister is greater than the amount of units I need to run, giving me "extra" fuel to compensate the places where I was supposed to dail.

(Thanks for all the clarifying replies. Now I realize I underestimated that question quite a bit! Last try for today, I promise)

Since this is a Basic thread, the argument needs to be fairly tight though perhaps not completely airtight. What I'm strongly hinting at is:

you solved it explicitly for the $N = 2$ case and have identified some interesting structural features for general $N$. Why not try to solve it explicitly for $N=3$ and perhaps explicitly for $N=4$. What kinds of patterns can you find here? There's no shame in solving multiple base cases. Then with a pinch of insight you can put it all together in a seamless inductive proof. (I trust you're somewhat familiar with induction in math, or recursion in programming... this is a very nice exercise for it. If you're not, or don't want to go this way, mfb is hinting at another approach)

(Thanks for all the clarifying replies. Now I realize I underestimated that question quite a bit! Last try for today, I promise)

It's ok to submit another one -- as long as you seem to be making incremental progress / putting in a real effort it's fine by me.

In general, there will be only one starting point where you can complete the circle. Given the positions and fuel amounts, how can you find this point?

@Thugles --this seems to hint at the other solution I'm aware of -- a very slick thought experiment that shows how to quickly find the 'right' starting position which gives you existence for free.
- - - -
There certainly may be even more approaches though these are the 2 mains ones I'm aware of.

As a reminder: if different people solve the same problem in significantly different ways, then they both get credit. It's worth exploring different approaches for interesting problems.

edit:
There's also a real nice way to set this one up for a contradiction. So that's 3 distinct solution approaches that I'm aware of...

 

[BWV]

Ok here is a stab at #7, apologies if my writing is hard to follow - trying to describe what I did in a spreadsheet

Spoiler: Spoiler

An urn contains balls, each of which has one of the following colors: red, green, blue and yellow balls. Balls are sampled randomly with replacement. Let r, g, b, and y represent the probabilities of drawing a red, green, blue or yellow.

a) what is the expected number of balls chosen before obtaining the first yellow ball?
b) what is the expected number of different colors of balls obtained before getting the first yellow ball? The probability of drawing a yellow ball is ¼ and the distribution of the number of trials before the first yellow ball is drawn follows a geometric distribution

a) The expectation of a geometric distribution is 1/p. p=1/4 so the expectation is 4 balls (the distribution is skewed so the median is significantly less: 2.4 balls)

b) The probability of a the first success at draw n follows a geometric distribution with p= ¼.

At each draw before the first success there are ( combinations of picking k balls with $\binom n k$ with k<=n

There is a ¼ probability that k=0 (a success in the first trial)

Let s=turn when first yellow ball is drawn and 0<n<s a prior (non-yellow) draw for s>1

Let M = a k x n matrix (each column is a draw and each row is $\binom n k$,
, the number of combinations of balls of different colors drawn, with 0 if k<n)

Then S = normalizing M, dividing each column vector entry by the sum of that column vector, so that the sum of each column vector =1

Let v= a nx1 (column) vector with each entry representing the probability mass function corresponding to the geometric distribution with p=1/4 and k=n+1 (k=trial of first yellow ball is drawn)

Then multiply Mv , which gives the probability for 1,2,3 different colors of balls for n (every outcome except a yellow ball on the first draw) Mv ≈ (0.502,0.269,0.224)

Let P = (0.25 0.75(Mv)) ≈ (0.25,0.377,0.202,0.168), the probabilities corresponding to 0,1,2,3 different colored balls drawn

The expectation is the dot product of (0,1,2,3) and P, which ≈1.26 expected different colored balls drawn before the first yellow one

 

[StoneTemplePython]

Ok here is a stab at #7, apologies if my writing is hard to follow - trying to describe what I did in a spreadsheet

Spoiler: Spoiler

An urn contains balls, each of which has one of the following colors: red, green, blue and yellow balls. Balls are sampled randomly with replacement. Let r, g, b, and y represent the probabilities of drawing a red, green, blue or yellow.

a) what is the expected number of balls chosen before obtaining the first yellow ball?
b) what is the expected number of different colors of balls obtained before getting the first yellow ball?The probability of drawing a yellow ball is ¼ and the distribution of the number of trials before the first yellow ball is drawn follows a geometric distribution

a) The expectation of a geometric distribution is 1/p. p=1/4 so the expectation is 4 balls (the distribution is skewed so the median is significantly less: 2.4 balls)

b) The probability of a the first success at draw n follows a geometric distribution with p= ¼.

At each draw before the first success there are ( combinations of picking k balls with $\binom n k$ with k<=n

There is a ¼ probability that k=0 (a success in the first trial)

Let s=turn when first yellow ball is drawn and 0<n<s a prior (non-yellow) draw for s>1

Let M = a k x n matrix (each column is a draw and each row is $\binom n k$,
, the number of combinations of balls of different colors drawn, with 0 if k<n)

Then S = normalizing M, dividing each column vector entry by the sum of that column vector, so that the sum of each column vector =1

Let v= a nx1 (column) vector with each entry representing the probability mass function corresponding to the geometric distribution with p=1/4 and k=n+1 (k=trial of first yellow ball is drawn)

Then multiply Mv , which gives the probability for 1,2,3 different colors of balls for n (every outcome except a yellow ball on the first draw) Mv ≈ (0.502,0.269,0.224)

Let P = (0.25 0.75(Mv)) ≈ (0.25,0.377,0.202,0.168), the probabilities corresponding to 0,1,2,3 different colored balls drawn

The expectation is the dot product of (0,1,2,3) and P, which ≈1.26 expected different colored balls drawn before the first yellow one

Sorry. A correct answer only uses symbols like "r, g, b, y" (and perhaps 1, since these are probabilities and sum to one). Note the problem does not say there are only 4 balls in the urn or that odds of drawing a ball are uniform. It says every ball has one color and there are 4 distinct colors in total and the probability of drawing a given ball color is given by $r$ for red, $g$ for green, $b$ for blue and $y$ for yellow.

 

[member 587159]

Question about 8: What is $A$? Is it an arbitrary set?

 

[QuantumQuest]

Question about 8: What is $A$? Is it an arbitrary set?

It is just used in the context of explaining what is $I_A$.

 

[member 587159]

It is just used in the context of explaining what is $I_A$.

It is in the problem statement though. I think you have to replace it by $\mathbb{R}.$

 

[QuantumQuest]

We are in the context of $\mathbb{R}$ regarding $f$ but during the solution you can introduce $I_A$ as it is (i.e. in a more generalized fashion).

 

[member 587159]

We are in the context of $\mathbb{R}$ regarding $f$ but during the solution you can introduce $I_A$ as it is (i.e. in a more generalized fashion).

I guess you can do that, but formally the other functions should be restricted to $A$ too if this is a proper subset of $\mathbb{R}$. But it doesn't matter, I understood the question now.

 

[member 587159]

Here's my solution for 7.

Spoiler

(a) Let $X$ be the variable that indicates "the amount of balls chosen before getting yellow". Then $X$ has a geometric distribution with parameter $p = r+g+b = 1-y$, if we consider pulling a non-yellow ball as a failure, and it is well known that $\mathbb{E}[X] = \frac{1}{r+g+b}$.

(b) Let $Y$ be the variable that indicates "the amount of different colors chosen before getting yellow". Then $Y$ can attain the values $0,1,2,3$.

DISCLAIMER: I assume in this answer that all the quantities $p,g,r,y$ are non-zero. Otherwise, I would divide by zero and some of the series won't converge.

Then:

$\mathbb{P}\{Y = 0\} = y$

Write $R_k$ for the event "pulling red balls the first $k$ pulls", and define $B_k$ and $G_k$ similarly. Define $Y_l$ as the event "pulling a yellow ball the $l^{th}$ try".

Then,

$\mathbb{P}\{Y=1\} = \mathbb{P}(\bigcup_{k=1}^\infty (R_k \cap Y_{k+1})) + \mathbb{P}(\bigcup_{k=1}^\infty (B_k \cap Y_{k+1})) + \mathbb{P}(\bigcup_{k=1}^\infty (G_k \cap Y_{k+1}))$

$= \sum_{k=1}^\infty \mathbb{P}(R_k \cap Y_{k+1}) + \sum_{k=1}^\infty \mathbb{P}(B_k \cap Y_{k+1}) + \sum_{k=1}^\infty \mathbb{P}(G_k \cap Y_{k+1})$

$= y\sum_{k=1}^\infty r^k + y\sum_{k=1}^\infty b^k + y\sum_{k=1}^\infty g^k$

$= y(\frac{r}{1-r} + \frac{b}{1-b} + \frac{g}{1-g})$

In the same way,

$\mathbb{P}\{Y=2\} = y(\frac{r+g}{1-(r+g)} + \frac{r+b}{1-(r+b)} + \frac{b+g}{1-(b+g)})$
$\mathbb{P}\{Y=3\} = y\frac{(r+g+b)}{1-(r+g+b)} =r+g+b$

so we obtain:

$\mathbb{E}[Y] = y(\frac{r}{1-r} + \frac{b}{1-b} + \frac{g}{1-g} + 2(\frac{r+g}{1-(r+g)} + \frac{r+b}{1-(r+b)} + \frac{b+g}{1-(b+g)})) + 3(r+g+b)$

and now I hope I'm not asked to simplify this :P

 

[member 587159]

I have a question about question 2. It says it is a one way ride. Do you get to choose the direction you are going?

Otherwise the answer seems that it is not possible, since it already fails for $N=2$.

Also, do all the cans contain the same amount of fuel?

 

[StoneTemplePython]

Here's my solution for 7.

I'll take a look at this tomorrow. From where I sit, this formally should be deleted because helpers aren't supposed to put in solutions until the 16th of the month. There is ambiguity on time zones for that rule, though I think we observe GMT (as in Greg Mean Time.)
- - - -

edit: despite being impressed with myself on "GMT", I'm taking a look at the solution now.
- - - -
edit2:
The solution stated is wrong. Your assumption that they are non-zero probabilities is fine by me.

I'll throw a couple bones your way:

For part 1 -- your answer is actually how I first answered the problem, but is wrong. Why?

For part 2 -- there is a very simple solution here that looks a lot nicer than your final formula. You are correct that the possible number of different colors seen before yellow is in $\{0,1,2,3\}$. You may want to look at your formula on simple qualitative grounds.

For example what expected value of Y does it give in the uniform case?

 

[StoneTemplePython]

I have a question about question 2. It says it is a one way ride. Do you get to choose the direction you are going?

Otherwise the answer seems that it is not possible, since it already fails for $N=2$.

Also, do all the cans contain the same amount of fuel?

You may want to re-read the problem and prior comments in the thread on this problem... gas cans don't have uniform amounts of fuel in general .

You choose starting point but not direction. (The track is said to be "one way" meaning a pre defined direction. For fun I'll insist that the cars must go clockwise.)

Why do you think this fails for N=2?

 

[member 587159]

I'll take a look at this tomorrow. From where I sit, this formally should be deleted because helpers aren't supposed to put in solutions until the 16th of the month. There is ambiguity on time zones for that rule, though I think we observe GMT (as in Greg Mean Time.)
- - - -

edit: despite being impressed with myself on "GMT", I'm taking a look at the solution now.
- - - -
edit2:
The solution stated is wrong. Your assumption that they are non-zero probabilities is fine by me.

I'll throw a couple bones your way:

For part 1 -- your answer is actually how I first answered the problem, but is wrong. Why?

For part 2 -- there is a very simple solution here that looks a lot nicer than your final formula. You are correct that the possible number of different colors seen before yellow is in $\{0,1,2,3\}$. You may want to look at your formula on simple qualitative grounds.

For example what expected value of Y does it give in the uniform case?

Yeah, I made a dumb mistake for part 1.

Succes should be pulling yellow, so the expected value should be

Spoiler

1/p = 1/y

I will look at 2 later today, but is the formula correct as it stands? If not, I'm curious to see where I made a mistake.

 

[member 587159]

You may want to re-read the problem and prior comments in the thread on this problem... gas cans don't have uniform amounts of fuel in general .

You choose starting point but not direction. (The track is said to be "one way" meaning a pre defined direction. For fun I'll insist that the cars must go clockwise.)

Why do you think this fails for N=2?

I was wrong and you are right. It doesn't fail for $N =2$.

 

[StoneTemplePython]

Yeah, I made a dumb mistake for part 1.

Succes should be pulling yellow, so the expected value should be

Spoiler

1/p = 1/y

I will look at 2 later today, but is the formula correct as it stands? If not, I'm curious to see where I made a mistake.

Part 1 is still not right but getting warmer. (I correct what I said earlier -- your current answer is what I initially thought of as the answer but a closer read of the question indicates otherwise)

Part 2 is wrong -- unless there is some mass cancellation I'm not seeing and a major transcription error in the below.

r_prob = 0.25
g_prob = 0.25
b_prob = 0.25
y_prob = 1 - r_prob - g_prob - b_probdef ev(r, g, b, y):
    part1 = r/(1-r) + b/(1-b) + g/(1-g)
    part2 = (r+g)/(1-(r+g)) + (r+b)/(1-(r+b)) + (b+g)/(1-(b+g))
    part3 = (r+g+b)
    return (part1 + 2*part2)*y + 3*(r+g+b)

 
print(ev(r_prob, g_prob, b_prob, y_prob))
# prints expected value of 4 which is impossible

compare against

$\mathbb{E}[Y] = y(\frac{r}{1-r} + \frac{b}{1-b} + \frac{g}{1-g} + 2(\frac{r+g}{1-(r+g)} + \frac{r+b}{1-(r+b)} + \frac{b+g}{1-(b+g)})) + 3(r+g+b)$

 

[member 587159]

Part 1 is still not right but getting warmer. (I correct what I said earlier -- your current answer is what I initially thought of as the answer but a closer read of the question indicates otherwise)

Part 2 is wrong -- unless there is some mass cancellation I'm not seeing and a major transcription error in the below.

r_prob = 0.25
g_prob = 0.25
b_prob = 0.25
y_prob = 1 - r_prob - g_prob - b_probdef ev(r, g, b, y):
    part1 = r/(1-r) + b/(1-b) + g/(1-g)
    part2 = (r+g)/(1-(r+g)) + (r+b)/(1-(r+b)) + (b+g)/(1-(b+g))
    part3 = (r+g+b)
    return (part1 + 2*part2)*y + 3*(r+g+b)

 
print(ev(r_prob, g_prob, b_prob, y_prob))
# prints expected value of 4 which is impossible

compare against

$\mathbb{E}[Y] = y(\frac{r}{1-r} + \frac{b}{1-b} + \frac{g}{1-g} + 2(\frac{r+g}{1-(r+g)} + \frac{r+b}{1-(r+b)} + \frac{b+g}{1-(b+g)})) + 3(r+g+b)$

EDIT:

I was confused by a different use of the geometric distribution. This is what happens when we become too lazy to calculate expectations :). I hope it is correct this time.

Spoiler

Corresponding to the probability function $\mathbb{P}\{X = k\} = q^kp = (1-y)^k y$, we have

$\mathbb{E}[X] = \frac{q}{p} = \frac{1-y}{y} = \frac{r+g+b}{y}$

so this is the answer.

For (2), I discovered that my calculation for $\mathbb{P}\{Y=2\}, \mathbb{P}\{Y=3\}$ is wrong. I couldn't split up it in sums since the events aren't disjoint. Trying to correct that now.

 

[StoneTemplePython]

EDIT:

I was confused by a different use of the geometric distribution. This is what happens when we become too lazy to calculate expectations :). I hope it is correct this time.

Spoiler

Corresponding to the probability function $\mathbb{P}\{X = k\} = q^kp = (1-y)^k y$, we have

$\mathbb{E}[X] = \frac{q}{p} = \frac{1-y}{y} = \frac{r+g+b}{y}$

so this is the answer.

Correct. It can also be interpreted as a classic 0 vs 1 indexing error. What you (and I) originally did was count total draws, but the question wants to count total failures -- hence it is the prior answer minus one, i.e. $\frac{1}{p} - 1 = \frac{1-p}{p} = \frac{q}{p}$

 

[mfb]

Solution for 2, the one I gave a hint towards already:

Spoiler

Consider a modified problem where negative fill values for the tank are allowed. Start at an arbitrary place with 0 fuel, keep track of your fuel. You get a function that decreases with a constant slope (your fuel consumption) most of the time and does a finite number of discrete jumps upwards at the fuel talks. After the full length you are at zero again (or higher if we have excess fuel). If you keep the position of the fuel tank as part of the previous segment then every segment has a minimum and you can find a global minimum. Start at this global minimum and your tank will always have fuel.

I mentioned the infinite case already, so let's have a look at this. Let's say the length of the track is 1. Put $2^{-n}$ fuel at position $2^{-n}$ for n=1 to infinity. The total fuel is 1. If you don't start at a fuel tank then you cannot drive. If you start at a fuel tank you have just enough fuel to reach the next fuel tank - until you get to 1/2 at place 1/2, which brings you to position 1 (or equivalently: 0) exactly - but there is no fuel tank there, you cannot continue. This is a purely mathematical result, obviously.

 

[StoneTemplePython]

Solution for 2, the one I gave a hint towards already:

Consider a modified problem where negative fill values for the tank are allowed. Start at an arbitrary place with 0 fuel, keep track of your fuel. You get a function that decreases with a constant slope (your fuel consumption) most of the time and does a finite number of discrete jumps upwards at the fuel talks. After the full length you are at zero again (or higher if we have excess fuel). If you keep the position of the fuel tank as part of the previous segment then every segment has a minimum and you can find a global minimum. Start at this global minimum and your tank will always have fuel.

As a slightly more physical take: you could ask that your friend gets in the car the 'day' before and starts with a full tank at a canister and logs consumption vs amounts available at each canister. Reading these logs in line with the above would give you 'an inside tip' afterward and ensure you choose the a starting spot guaranteed to succeed.

- - - - -

A few other thoughts:
1.) There's at least two other ways to prove the existence of a 'good' starting spot -- via induction and a contradiction involving 'pigeons'...
2.) Any discussion of infinite dimensional cases forces structural issues not in the problem -- the other two techniques aren't designed for it, and the existence of a global minimum partial sum (not merely a greatest lower bound) becomes troublesome. In any case, it's really outside the scope.
3.) This question, with $n$ canisters, under a slightly different guise, has been asked of many maths students interviewing with Cambridge (undergrad I think). It's a nice problem though kind of rough to have thrown at you on the spot.

 

[ehild]

My solution for Problem 3

Spoiler: problem3

γ=45-α/2
β=135-α/2
According to the Law of sines:
$\overline{AD} = \frac {\overline{CD} \sin(45-α/2)}{\sin(α/2)}$ 1
$\overline{AD}= \frac {\overline{BD}\sin(135-α/2)}{\sin(α/2)}$ 2
multiplying eqs1 and eqs2 and using that $\overline{AD}^2=\overline{BD} \overline{CD}$,
$\sin(45°-α/2)\sin(135°-α/2)=\sin^2(α/2)$
The solution is α/2=30°: α=60, β=105°, γ=15°.
Dividing eq 1 with eq 2
$\frac{\overline{BD}}{\overline{CD}} = \frac {\sin(45°-α/2)}{\sin(135°-α/2)} =\frac{\sin(15°) }{\sin(105°)} = \tan(15°)$
Using the half angle formula :$\tan^2(x/2) =\frac {1-\cos(x)}{1+\cos(x)}$ . With x=30°, $\tan(15°)=2-\sqrt{3}$.