Mixing
N cars travelling the greatest distance
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Considering $n$ cars, each can travel 100km with a full tank of fuel.They are travelling along a road. They must all return to the starting point, with one car travelling the furtherest to deliver a letter. What is the maximum distance between the letterbox and the starting point?
I consider this question as this:
assume the maximum distance is $X$.
As $n=1,X=50$
$n=2,X=75$
Note for $n=2$:both car drive 25km, then car 1 give 25km of fuel to car 2, car 2 keep driving 50 and back, car 1 give 25km of fuel to car 2 and they both drive back.
...
As $nrightarrow infty, Xrightarrow infty$ since one car can just give fuel to every other car after $0.0000000001m$.
But how can one generalise this in terms of $n$ and $X$?
Any help appreciated.
combinatorics algebra-precalculus
asked Aug 6 at 1:01
abc...
1,190524
add a comment |Â
up vote
1
down vote
favorite
Considering $n$ cars, each can travel 100km with a full tank of fuel.They are travelling along a road. They must all return to the starting point, with one car travelling the furtherest to deliver a letter. What is the maximum distance between the letterbox and the starting point?
I consider this question as this:
assume the maximum distance is $X$.
As $n=1,X=50$
$n=2,X=75$
Note for $n=2$:both car drive 25km, then car 1 give 25km of fuel to car 2, car 2 keep driving 50 and back, car 1 give 25km of fuel to car 2 and they both drive back.
...
As $nrightarrow infty, Xrightarrow infty$ since one car can just give fuel to every other car after $0.0000000001m$.
But how can one generalise this in terms of $n$ and $X$?
Any help appreciated.
combinatorics algebra-precalculus
asked Aug 6 at 1:01
abc...
1,190524
Can the cars refuel at the starting point? It sounds like no.
– Ross Millikan
Aug 6 at 2:04
@RossMillikan no they can't.
– abc...
Aug 6 at 2:15
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Considering $n$ cars, each can travel 100km with a full tank of fuel.They are travelling along a road. They must all return to the starting point, with one car travelling the furtherest to deliver a letter. What is the maximum distance between the letterbox and the starting point?
I consider this question as this:
assume the maximum distance is $X$.
As $n=1,X=50$
$n=2,X=75$
Note for $n=2$:both car drive 25km, then car 1 give 25km of fuel to car 2, car 2 keep driving 50 and back, car 1 give 25km of fuel to car 2 and they both drive back.
...
As $nrightarrow infty, Xrightarrow infty$ since one car can just give fuel to every other car after $0.0000000001m$.
But how can one generalise this in terms of $n$ and $X$?
Any help appreciated.
combinatorics algebra-precalculus
asked Aug 6 at 1:01
abc...
1,190524
Considering $n$ cars, each can travel 100km with a full tank of fuel.They are travelling along a road. They must all return to the starting point, with one car travelling the furtherest to deliver a letter. What is the maximum distance between the letterbox and the starting point?
I consider this question as this:
assume the maximum distance is $X$.
As $n=1,X=50$
$n=2,X=75$
Note for $n=2$:both car drive 25km, then car 1 give 25km of fuel to car 2, car 2 keep driving 50 and back, car 1 give 25km of fuel to car 2 and they both drive back.
...
As $nrightarrow infty, Xrightarrow infty$ since one car can just give fuel to every other car after $0.0000000001m$.
But how can one generalise this in terms of $n$ and $X$?
Any help appreciated.
combinatorics algebra-precalculus
asked Aug 6 at 1:01
abc...
1,190524
edited Aug 6 at 1:46
asked Aug 6 at 1:01
abc...
1,190524
asked Aug 6 at 1:01
abc...
1,190524
asked Aug 6 at 1:01
abc...
1,190524
1,190524
Can the cars refuel at the starting point? It sounds like no.
– Ross Millikan
Aug 6 at 2:04
@RossMillikan no they can't.
– abc...
Aug 6 at 2:15
add a comment |Â
Can the cars refuel at the starting point? It sounds like no.
– Ross Millikan
Aug 6 at 2:04
@RossMillikan no they can't.
– abc...
Aug 6 at 2:15
Can the cars refuel at the starting point? It sounds like no.
– Ross Millikan
Aug 6 at 2:04
Can the cars refuel at the starting point? It sounds like no.
– Ross Millikan
Aug 6 at 2:04
@RossMillikan no they can't.
– abc...
Aug 6 at 2:15
@RossMillikan no they can't.
– abc...
Aug 6 at 2:15
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Your solution for $n=2$ is good and points the way to the general solution. We assume the cars cannot refuel at the starting point. Clearly the last leg is made by one car alone, starting with with a full tank and making a $100$ km round trip, so the leg is $50$ km. As you say, two cars setting off with full tanks can go $25$ km and transfer fuel to one to do the final stage, then get home. Now if we have three cars, we want them to drive a distance $d$, fill two cars that do the $75$ km thing, then return home. We have three cars making the round trip of $d$ plus the $200$ km for the last two stages. We have $6d+200=300, d=frac 1006$, using $300$ of fuel. Add a fourth car to the mix and they make eight round trips of $d'$ plus the $300$ of fuel for the last three stages, so $8d'+300=400, d'=frac 1008$
Car number $k$ adds $frac 1002k$ to the distance covered, so the total distance for $n$ cars is $sum_i=1^nfrac 50i$, which is $50$ times the $n^th$ Harmonic number, or about $50(ln n+gamma)$
We need to convince ourselves that it is more efficient to just add one to the fleet at each stage than have (say) three cars go together to refuel the last one and have nine go together to refuel those three. The intuitive approach is to note that fuel far from the start of the road is precious so we want as few cars as possible driving out there.
answered Aug 6 at 2:44
Ross Millikan
276k21187352
add a comment |Â
up vote
1
down vote
For convenience of notation, we can scale the problem by a factor of $largefrac1100$ so that a car can go a distance of at most $1$ on a full tank. At the end, we can multiply by $100$ to undo the initial scaling.
With the scaled version, let $f(n)$ be the maximum achievable distance, given $n$ cars.
Partial result:
$$;f(n) ge sum_k=1^n frac12k$$
Proof:
Proceed by induction on $n$.
Clearly we have $f(1)=largefrac12$, so the claim holds for the base case, $n=1$.
Suppose the claim holds for some positive integer $n$.
Consider the case of $n+1$ cars.
At a distance $largefrac12(n+1)$ from the starting point, let car $n+1$ refuel all the other cars to full capacity, and wait for their return.
By the inductive hypothesis, one of the cars $1,...,n$ can achieve a distance of $f(n)$ from the point where car $n+1$ waits, with the all cars returning to that point.
On their return, car $n+1$ has exactly enough fuel to get all $n+1$ cars back to the starting point.
Thus, we have
$$
f(n+1)
ge
frac12(n+1)+f(n)
ge
frac12(n+1)+sum_k=1^n frac12k
=
sum_k=1^n+1frac12k
$$
which completes the induction.
Undoing the initial scaling, it follows that for $n$ cars, a distance
$$X=50sum_k=1^n frac1k$$
is achievable. I don't know whether or not it's the maximum possible value of $X$.
answered Aug 6 at 3:21
quasi
33.4k22359
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Your solution for $n=2$ is good and points the way to the general solution. We assume the cars cannot refuel at the starting point. Clearly the last leg is made by one car alone, starting with with a full tank and making a $100$ km round trip, so the leg is $50$ km. As you say, two cars setting off with full tanks can go $25$ km and transfer fuel to one to do the final stage, then get home. Now if we have three cars, we want them to drive a distance $d$, fill two cars that do the $75$ km thing, then return home. We have three cars making the round trip of $d$ plus the $200$ km for the last two stages. We have $6d+200=300, d=frac 1006$, using $300$ of fuel. Add a fourth car to the mix and they make eight round trips of $d'$ plus the $300$ of fuel for the last three stages, so $8d'+300=400, d'=frac 1008$
Car number $k$ adds $frac 1002k$ to the distance covered, so the total distance for $n$ cars is $sum_i=1^nfrac 50i$, which is $50$ times the $n^th$ Harmonic number, or about $50(ln n+gamma)$
We need to convince ourselves that it is more efficient to just add one to the fleet at each stage than have (say) three cars go together to refuel the last one and have nine go together to refuel those three. The intuitive approach is to note that fuel far from the start of the road is precious so we want as few cars as possible driving out there.
answered Aug 6 at 2:44
Ross Millikan
276k21187352
add a comment |Â
up vote
1
down vote
accepted
Your solution for $n=2$ is good and points the way to the general solution. We assume the cars cannot refuel at the starting point. Clearly the last leg is made by one car alone, starting with with a full tank and making a $100$ km round trip, so the leg is $50$ km. As you say, two cars setting off with full tanks can go $25$ km and transfer fuel to one to do the final stage, then get home. Now if we have three cars, we want them to drive a distance $d$, fill two cars that do the $75$ km thing, then return home. We have three cars making the round trip of $d$ plus the $200$ km for the last two stages. We have $6d+200=300, d=frac 1006$, using $300$ of fuel. Add a fourth car to the mix and they make eight round trips of $d'$ plus the $300$ of fuel for the last three stages, so $8d'+300=400, d'=frac 1008$
Car number $k$ adds $frac 1002k$ to the distance covered, so the total distance for $n$ cars is $sum_i=1^nfrac 50i$, which is $50$ times the $n^th$ Harmonic number, or about $50(ln n+gamma)$
We need to convince ourselves that it is more efficient to just add one to the fleet at each stage than have (say) three cars go together to refuel the last one and have nine go together to refuel those three. The intuitive approach is to note that fuel far from the start of the road is precious so we want as few cars as possible driving out there.
answered Aug 6 at 2:44
Ross Millikan
276k21187352
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Your solution for $n=2$ is good and points the way to the general solution. We assume the cars cannot refuel at the starting point. Clearly the last leg is made by one car alone, starting with with a full tank and making a $100$ km round trip, so the leg is $50$ km. As you say, two cars setting off with full tanks can go $25$ km and transfer fuel to one to do the final stage, then get home. Now if we have three cars, we want them to drive a distance $d$, fill two cars that do the $75$ km thing, then return home. We have three cars making the round trip of $d$ plus the $200$ km for the last two stages. We have $6d+200=300, d=frac 1006$, using $300$ of fuel. Add a fourth car to the mix and they make eight round trips of $d'$ plus the $300$ of fuel for the last three stages, so $8d'+300=400, d'=frac 1008$
Car number $k$ adds $frac 1002k$ to the distance covered, so the total distance for $n$ cars is $sum_i=1^nfrac 50i$, which is $50$ times the $n^th$ Harmonic number, or about $50(ln n+gamma)$
We need to convince ourselves that it is more efficient to just add one to the fleet at each stage than have (say) three cars go together to refuel the last one and have nine go together to refuel those three. The intuitive approach is to note that fuel far from the start of the road is precious so we want as few cars as possible driving out there.
answered Aug 6 at 2:44
Ross Millikan
276k21187352
Your solution for $n=2$ is good and points the way to the general solution. We assume the cars cannot refuel at the starting point. Clearly the last leg is made by one car alone, starting with with a full tank and making a $100$ km round trip, so the leg is $50$ km. As you say, two cars setting off with full tanks can go $25$ km and transfer fuel to one to do the final stage, then get home. Now if we have three cars, we want them to drive a distance $d$, fill two cars that do the $75$ km thing, then return home. We have three cars making the round trip of $d$ plus the $200$ km for the last two stages. We have $6d+200=300, d=frac 1006$, using $300$ of fuel. Add a fourth car to the mix and they make eight round trips of $d'$ plus the $300$ of fuel for the last three stages, so $8d'+300=400, d'=frac 1008$
Car number $k$ adds $frac 1002k$ to the distance covered, so the total distance for $n$ cars is $sum_i=1^nfrac 50i$, which is $50$ times the $n^th$ Harmonic number, or about $50(ln n+gamma)$
We need to convince ourselves that it is more efficient to just add one to the fleet at each stage than have (say) three cars go together to refuel the last one and have nine go together to refuel those three. The intuitive approach is to note that fuel far from the start of the road is precious so we want as few cars as possible driving out there.
answered Aug 6 at 2:44
Ross Millikan
276k21187352
answered Aug 6 at 2:44
Ross Millikan
276k21187352
answered Aug 6 at 2:44
Ross Millikan
276k21187352
answered Aug 6 at 2:44
Ross Millikan
276k21187352
276k21187352
add a comment |Â
add a comment |Â
up vote
1
down vote
For convenience of notation, we can scale the problem by a factor of $largefrac1100$ so that a car can go a distance of at most $1$ on a full tank. At the end, we can multiply by $100$ to undo the initial scaling.
With the scaled version, let $f(n)$ be the maximum achievable distance, given $n$ cars.
Partial result:
$$;f(n) ge sum_k=1^n frac12k$$
Proof:
Proceed by induction on $n$.
Clearly we have $f(1)=largefrac12$, so the claim holds for the base case, $n=1$.
Suppose the claim holds for some positive integer $n$.
Consider the case of $n+1$ cars.
At a distance $largefrac12(n+1)$ from the starting point, let car $n+1$ refuel all the other cars to full capacity, and wait for their return.
By the inductive hypothesis, one of the cars $1,...,n$ can achieve a distance of $f(n)$ from the point where car $n+1$ waits, with the all cars returning to that point.
On their return, car $n+1$ has exactly enough fuel to get all $n+1$ cars back to the starting point.
Thus, we have
$$
f(n+1)
ge
frac12(n+1)+f(n)
ge
frac12(n+1)+sum_k=1^n frac12k
=
sum_k=1^n+1frac12k
$$
which completes the induction.
Undoing the initial scaling, it follows that for $n$ cars, a distance
$$X=50sum_k=1^n frac1k$$
is achievable. I don't know whether or not it's the maximum possible value of $X$.
answered Aug 6 at 3:21
quasi
33.4k22359
add a comment |Â
up vote
1
down vote
For convenience of notation, we can scale the problem by a factor of $largefrac1100$ so that a car can go a distance of at most $1$ on a full tank. At the end, we can multiply by $100$ to undo the initial scaling.
With the scaled version, let $f(n)$ be the maximum achievable distance, given $n$ cars.
Partial result:
$$;f(n) ge sum_k=1^n frac12k$$
Proof:
Proceed by induction on $n$.
Clearly we have $f(1)=largefrac12$, so the claim holds for the base case, $n=1$.
Suppose the claim holds for some positive integer $n$.
Consider the case of $n+1$ cars.
At a distance $largefrac12(n+1)$ from the starting point, let car $n+1$ refuel all the other cars to full capacity, and wait for their return.
By the inductive hypothesis, one of the cars $1,...,n$ can achieve a distance of $f(n)$ from the point where car $n+1$ waits, with the all cars returning to that point.
On their return, car $n+1$ has exactly enough fuel to get all $n+1$ cars back to the starting point.
Thus, we have
$$
f(n+1)
ge
frac12(n+1)+f(n)
ge
frac12(n+1)+sum_k=1^n frac12k
=
sum_k=1^n+1frac12k
$$
which completes the induction.
Undoing the initial scaling, it follows that for $n$ cars, a distance
$$X=50sum_k=1^n frac1k$$
is achievable. I don't know whether or not it's the maximum possible value of $X$.
answered Aug 6 at 3:21
quasi
33.4k22359
add a comment |Â
up vote
1
down vote
up vote
1
down vote
For convenience of notation, we can scale the problem by a factor of $largefrac1100$ so that a car can go a distance of at most $1$ on a full tank. At the end, we can multiply by $100$ to undo the initial scaling.
With the scaled version, let $f(n)$ be the maximum achievable distance, given $n$ cars.
Partial result:
$$;f(n) ge sum_k=1^n frac12k$$
Proof:
Proceed by induction on $n$.
Clearly we have $f(1)=largefrac12$, so the claim holds for the base case, $n=1$.
Suppose the claim holds for some positive integer $n$.
Consider the case of $n+1$ cars.
At a distance $largefrac12(n+1)$ from the starting point, let car $n+1$ refuel all the other cars to full capacity, and wait for their return.
By the inductive hypothesis, one of the cars $1,...,n$ can achieve a distance of $f(n)$ from the point where car $n+1$ waits, with the all cars returning to that point.
On their return, car $n+1$ has exactly enough fuel to get all $n+1$ cars back to the starting point.
Thus, we have
$$
f(n+1)
ge
frac12(n+1)+f(n)
ge
frac12(n+1)+sum_k=1^n frac12k
=
sum_k=1^n+1frac12k
$$
which completes the induction.
Undoing the initial scaling, it follows that for $n$ cars, a distance
$$X=50sum_k=1^n frac1k$$
is achievable. I don't know whether or not it's the maximum possible value of $X$.
answered Aug 6 at 3:21
quasi
33.4k22359
For convenience of notation, we can scale the problem by a factor of $largefrac1100$ so that a car can go a distance of at most $1$ on a full tank. At the end, we can multiply by $100$ to undo the initial scaling.
With the scaled version, let $f(n)$ be the maximum achievable distance, given $n$ cars.
Partial result:
$$;f(n) ge sum_k=1^n frac12k$$
Proof:
Proceed by induction on $n$.
Clearly we have $f(1)=largefrac12$, so the claim holds for the base case, $n=1$.
Suppose the claim holds for some positive integer $n$.
Consider the case of $n+1$ cars.
At a distance $largefrac12(n+1)$ from the starting point, let car $n+1$ refuel all the other cars to full capacity, and wait for their return.
By the inductive hypothesis, one of the cars $1,...,n$ can achieve a distance of $f(n)$ from the point where car $n+1$ waits, with the all cars returning to that point.
On their return, car $n+1$ has exactly enough fuel to get all $n+1$ cars back to the starting point.
Thus, we have
$$
f(n+1)
ge
frac12(n+1)+f(n)
ge
frac12(n+1)+sum_k=1^n frac12k
=
sum_k=1^n+1frac12k
$$
which completes the induction.
Undoing the initial scaling, it follows that for $n$ cars, a distance
$$X=50sum_k=1^n frac1k$$
is achievable. I don't know whether or not it's the maximum possible value of $X$.
answered Aug 6 at 3:21
quasi
33.4k22359
edited Aug 6 at 3:40
answered Aug 6 at 3:21
quasi
33.4k22359
answered Aug 6 at 3:21
quasi
33.4k22359
answered Aug 6 at 3:21
quasi
33.4k22359
33.4k22359
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873489%2fn-cars-travelling-the-greatest-distance%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Can the cars refuel at the starting point? It sounds like no.
– Ross Millikan
Aug 6 at 2:04
@RossMillikan no they can't.
– abc...
Aug 6 at 2:15