# Basic Math Challenge - July 2018

• Challenge
• Featured
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 travelled 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 travelled (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 lenght 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
Gold Member
2019 Award
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 travelled (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 lenght 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
Gold Member
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.

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 lenght (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 lenght to a portion would end up adding fuel or removing lenght 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
Mentor
(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
Gold Member
2019 Award
I'm not sure what happened to the spoiler tags, but I'll nest your responses in them, for space reasons:

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

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 lenght to a portion would end up adding fuel or removing lenght 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...

Last edited:
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

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
Gold Member
2019 Award
Ok here is a stab at #7, apologies if my writing is hard to follow - trying to describe what I did in a spreadsheet

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.

Math_QED
Homework Helper
2019 Award
Question about 8: What is ##A##? Is it an arbitrary set?

QuantumQuest
Gold Member
Question about 8: What is ##A##? Is it an arbitrary set?
It is just used in the context of explaining what is ##I_A##.

Math_QED
Homework Helper
2019 Award
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
Gold Member
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).

Math_QED
Homework Helper
2019 Award
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.

QuantumQuest
Math_QED
Homework Helper
2019 Award
Here's my solution for 7.

(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

Math_QED
Homework Helper
2019 Award
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?

Last edited:
StoneTemplePython
Gold Member
2019 Award
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?

Last edited:
StoneTemplePython
Gold Member
2019 Award
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?

Math_QED
Homework Helper
2019 Award
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

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.

Last edited:
Math_QED
Homework Helper
2019 Award
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
Gold Member
2019 Award
Yeah, I made a dumb mistake for part 1.

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

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.

Python:
r_prob = 0.25
g_prob = 0.25
b_prob = 0.25
y_prob = 1 - r_prob - g_prob - b_prob

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

Math_QED
Homework Helper
2019 Award
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.

Python:
r_prob = 0.25
g_prob = 0.25
b_prob = 0.25
y_prob = 1 - r_prob - g_prob - b_prob

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

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

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.

Last edited:
StoneTemplePython
Gold Member
2019 Award
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.

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

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

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.

QuantumQuest and StoneTemplePython
StoneTemplePython
Gold Member
2019 Award
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
Homework Helper
My solution for Problem 3
γ=45-α/2
β=135-α/2
According to the Law of sines:
##\overline{AD} = \frac {\overline{CD} \sin(45-α/2)}{\sin(α/2)}## 1
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}##.

#### Attachments

• 2.4 KB Views: 541
Last edited: