Achilles and the Gods Puzzle

[HarryT]

Originally Posted by pdurrant

The right answer, but I'm not convinced that you've properly shown thar it actually is the right answer.

Spoiler:

For instance, if, instead of extending it 100m, would Achilles finish if they extended it by 100m, 200m, 300m, etc,? After all, he'll still be increasing the percentage of the track he's covered all the time.

The reason for it is...

Spoiler:

...that if Achilles is running at a constant speed, and the track is extending at a linear rate (any linear rate), his progress along the track will be some divisor of the arithmetic series:

1 + 1/2 + 1/3 + 1/4 + ...

and that series, as can trivially be shown, sums to infinity:

Group the terms as:

1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8), etc, doubling the number of terms each time. Each group sums to at least 1/2, so we have an infinite number of halves, which sums to infinity.

No matter HOW fast the track stretches linearly, therefore, Achilles will reach the end.

[pdurrant]

Originally Posted by HarryT

The reason for it is...

Spoiler:

...that if Achilles is running at a constant speed, and the track is extending at a linear rate (any linear rate), his progress along the track will be some divisor of the arithmetic series:

1 + 1/2 + 1/3 + 1/4 + ...

and that series, as can trivially be shown, sums to infinity:

Group the terms as:

1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8), etc, doubling the number of terms each time. Each group sums to at least 1/2, so we have an infinite number of halves, which sums to infinity.

No matter HOW fast the track stretches linearly, therefore, Achilles will reach the end.

Yes, spot on.

[omk3]

Spoiler:

Yes he will.
Every time the track stretches, his position changes by an equal percent.
So in the first second, the track is stretched by 100% and becomes 200, so his position is also moved forward by 100%. On the first second he has run 10 meters but is on the 20 meter mark of the 200 meter track.
On the second second, he runs 10 meters more, so he is now on the 30 meter mark. The track stretches by 100 meters, which is 50% of 200, so his position is now on the 45 minute mark of the 300 meter track.
And so on.
The percent of the track he has covered after each second grows (as I found in excel :P) so at one time he will have covered the whole track.
Don't ask me when though

[pdurrant]

Originally Posted by omk3

Spoiler:

Yes he will.
Every time the track stretches, his position changes by an equal percent.
So in the first second, the track is stretched by 100% and becomes 200, so his position is also moved forward by 100%. On the first second he has run 10 meters but is on the 20 meter mark of the 200 meter track.
On the second second, he runs 10 meters more, so he is now on the 30 meter mark. The track stretches by 100 meters, which is 50% of 200, so his position is now on the 45 minute mark of the 300 meter track.
And so on.
The percent of the track he has covered after each second grows (as I found in excel :P) so at one time he will have covered the whole track.
Don't ask me when though

You have the right answer, but you haven't actually shown that it's the right answer.

Spoiler:

Just because the percentage he's travelled always increases, that doesn't necessarily mean that he'll eventually get to the end of the track.
Consider the sequence where he always covers an extra half of the percentage he covered in the previous 10m — he'll cover 10%, 15%, 17.5%, 18.75%, .... but he'll never actually get to 20% of the track, let alone more. You need to show that with the values given in the question he will eventually get 100% of the way along the track.

[jbjb]

A bit late with this (only just saw the original post), but:

Spoiler:

Assuming the track stretches uniformly, the problem is isomorphic to one in which the track stays the same length, but his speed reduces each second. I.e. in the transformed problem, his speed starts at 10, then reduces to 10/2 after one second, 10/3 after the next and so on.

Hence, his distance travelled = 10 + 10/2 + 10/3 + 10/4 .....
which is 10 x (1 + 1/2 + 1/3 + 1/4 ....)

The progression in brackets can easiy be shown to sum to infinity, so (in the transformed domain) there is no limit to how far he can go, given time.

As the problems are isomorphic, the fact that he reaches the end in the transformed problem shows that he will reach the end in the original problem.

/JB

[pdurrant]

Originally Posted by jbjb

A bit late with this (only just saw the original post), but:

Spoiler:

Assuming the track stretches uniformly, the problem is isomorphic to one in which the track stays the same length, but his speed reduces each second. I.e. in the transformed problem, his speed starts at 10, then reduces to 10/2 after one second, 10/3 after the next and so on.

Hence, his distance travelled = 10 + 10/2 + 10/3 + 10/4 .....
which is 10 x (1 + 1/2 + 1/3 + 1/4 ....)

The progression in brackets can easiy be shown to sum to infinity, so (in the transformed domain) there is no limit to how far he can go, given time.

As the problems are isomorphic, the fact that he reaches the end in the transformed problem shows that he will reach the end in the original problem.

/JB

Yes, the right answer, and an interesting (and correct) way of calculating it. Congratulations!

You might want to search back for some of the previous puzzles. They all have the answers in spoiler tags, so you can still have a go at solving them.

[omk3]

Originally Posted by pdurrant

You have the right answer, but you haven't actually shown that it's the right answer.

Spoiler:

Just because the percentage he's travelled always increases, that doesn't necessarily mean that he'll eventually get to the end of the track.
Consider the sequence where he always covers an extra half of the percentage he covered in the previous 10m — he'll cover 10%, 15%, 17.5%, 18.75%, .... but he'll never actually get to 20% of the track, let alone more. You need to show that with the values given in the question he will eventually get 100% of the way along the track.

Spoiler:

I found in excel (by brute force) that it will take him 12367 seconds to finish the track! The logical reason for this is, I think, that the position of the runner is increased by the same percentage as the track, *plus* 10 meters. So he is slowly but surely moving forward.

[HarryT]

Originally Posted by omk3

Spoiler:

I found in excel (by brute force) that it will take him 12367 seconds to finish the track! The logical reason for this is, I think, that the position of the runner is increased by the same percentage as the track, *plus* 10 meters. So he is slowly but surely moving forward.

Spoiler:

OK, but suppose the track was increasing in length by 1km every 10m. Would he still finish? Can you show that he'll finish no matter what the length increase is?

[pdurrant]

I might be without internet access over the weekend, but I will post my answer to this puzzle on Monday.

Meanwhile, there's a new puzzle that doesn't require and word play or mathematics here: https://www.mobileread.com/forums/showthread.php?t=90822

[clarknova]

Originally Posted by HarryT

Spoiler:

OK, but suppose the track was increasing in length by 1km every 10m. Would he still finish? Can you show that he'll finish no matter what the length increase is?

Spoiler:

Of course he wouldn't finish. You've forgotten that this isn't just a math problem. Achilles would never finish that, as he has a Trojan war to fight and die in.

It's feasible for him to waste 3 and a half hours on this crap for the gods' amusement, but he couldn't spend the millennia eons it would take to finish the race you created above. Even if he wasn't needed for historic wars, people (even Greek Heroes) just don't live long enough to finish that race.

Though perhaps that race could be done as some sort of hellish torture in Hades or Tartarus...

Edit: Millennia doesn't quite describe it. After about 2,315 years of constant running Achilles would only be 35% done, and the track now stretches 488 Astronomical Units. I'm not even sure my computer could finish this race at over 2^24 times the speed of Achilles.

[clarknova]

Originally Posted by clarknova

Spoiler:

Edit: Millennia doesn't quite describe it. After about 2,315 years of constant running Achilles would only be 35% done, and the track now stretches 488 Astronomical Units. I'm not even sure my computer could finish this race at over 2^24 times the speed of Achilles.

Spoiler:

I accidentally left this program running in the background. After running for 126,275.2 (tropical) years poor Achilles is still only 39.44% done with the race, and the track has stretched to 3,984,857,235,456.1km (26637.1 AU). These are just estimates, since the program was never meant to deal with such large numbers, and precision is surely suffering floating point errors with only 64bit floats.

Regardless, I think this really would be an excellent method of torture for Tartarus's damned.

[HarryT]

LOL . Thanks for that.

[pdurrant]

Originally Posted by pdurrant

The gods have heard rumours that Achilles might not be as fast at running as they thought, so they decide to set him a task.

He must run a race on a special 100m racetrack. The special thing about this racetrack is that every time Achilles has run 10m along the race track, the whole track instantly stretches, as if made of rubber, by 100m.

Now Achilles can run indefinitely as a constant 10m/s. He really is a fast runner — good endurance too.

Have the gods set Achilles an impossible task? Can he ever finish the race?

Here's the answer:

Spoiler:

The gods have not set Achilles an impossible task, he can finish the race.

It seems strange as first sight that he could ever finish, as the track grows by 100m every second, while Achilles only runs 10m every second.

The crucial point is that the 100m isn't added just to the end of the track, but is added equally all along the track, including the bits of the track that Achilles has already covered.

So, in the 1st second, Achilles runs 10m, which is 10% of the track. The track then increases to 200m, but because the extra length is added equally, Achilles is still 10% of the way along the track.

In the 2nd second, Achilles runs another 10m, which is 5% of the longer track, taking him to 15% overall. The track then increases to 300m, but Achilles is still 15% of the way along, now 45m along the track, despite having only run 20m.

In the 3rd second, Achilles runs another 10m, which is 3 1/3% of the longer track, taking him to 18 1/3% overall. The track then increases to 400m, but Achilles is still 18 1/3% of the way along, now 73 1/3m along the track, despite having only run 30m.

This continues. Every second Achilles runs a smaller and smaller percentage of the track, but the percentage he covers always increases.

The question is, does the percentage ever reach 100%? It might not. If he covered, in each second, 10%, 5%, 2.5%, 1.25%, 0.625%, 0.3125%, etc. he'd never get past 20% of the way along the track!

It's sometimes easier to look at fractions rather than percentages. With the conditions in this problem, every second from the start of the race, Achilles covers

1/10, 1/20, 1/30, 1/40, 1/50, 1/60, 1/70, 1/80, 1/90, ...

So to find out if Achilles finishes the race, we need to know if the sum of all those fractions ever reaches 1.

Consider the following sequence of fractions:

1/10, 1/20, 1/40, 1/40, 1/80, 1/80, 1/80, 1/80, 1/160, ...

Each of these fractions is less than or equal to the corresponding fraction in the sequence we're interested in. But this sequence clearly (!) reaches and exceeds one — just look at it like this:

1/10 + 1/20 + (1/40 + 1/40) + (1/80 + 1/80+ 1/80 + 1/80) + (1/160 + ...

each of the bracked terms adds up to 1/20, and we obviously have more than twenty such bracketed terms, so this sequence, when added all together, is more than 1.

So the sequence of fractions we're interested in, since every fraction in it is greater than or equal to the corresponding term in the sequence that does exceed 1, also adds up to more than 1 — which corresponds to 100% of the track length.

So we know that Achilles will eventually reach the end of the track. It will take him some time though. Other answers in this thread give the results of numerical calculations to work out roughly how long it will take him.

[jbjb]

Originally Posted by pdurrant

Here's the answer:

Spoiler:

It's sometimes easier to look at fractions rather than percentages. With the conditions in this problem, every second from the start of the race, Achilles covers

1/10, 1/20, 1/30, 1/40, 1/50, 1/60, 1/70, 1/80, etc.

So to find out if Achilles finishes the race, we need to know if the sum of all those fractions ever reaches 1.

Consider the following sequence of fractions:

1/10, 1/20, 1/20, 1/40, 1/40, 1/40, 1/40, 1/80, 1/80, 1/80, ....

Each of these fractions is less than or equal to the corresponding fraction in the sequence we're interested in.

Spoiler:

I don't think that explanation of the diverging sum is quite right. For example, if you take the third item in each sequence, the entry from the second sequence is not actually less than or equal to that from the first.

Perhaps a better way would be to group them as:
1/10, 1/20, (1/30 + 1/40), (1/50 + 1/60 + 1/70 + 1/80) ... etc.

In general, the nth group of terms (where n starts at 1 for (1/30+1/40)) will (for all n > 0) be a sum of 2^n fractions, the least of which will be 1/(20*(2^n)). Thus the sum of each group must be at least (2^n)/(20*(2^n)), or 1/20. A sum of an infinite sequence of groups, each of which has a sum of at least 1/20 will itself be infinite.

Cheers,
John

[pdurrant]

Originally Posted by jbjb

Spoiler:

I don't think that explanation of the diverging sum is quite right. For example, if you take the third item in each sequence, the entry from the second sequence is not actually less than or equal to that from the first.

Perhaps a better way would be to group them as:
1/10, 1/20, (1/30 + 1/40), (1/50 + 1/60 + 1/70 + 1/80) ... etc.

In general, the nth group of terms (where n starts at 1 for (1/30+1/40)) will (for all n > 0) be a sum of 2^n fractions, the least of which will be 1/(20*(2^n)). Thus the sum of each group must be at least (2^n)/(20*(2^n)), or 1/20. A sum of an infinite sequence of groups, each of which has a sum of at least 1/20 will itself be infinite.

Cheers,
John

You're entirely correct. I'll change it so it's correct. That's what I get for writing and posting without double-checking. (I usually write the answer to a text file one day, and then re-read and post it the next.)