14
$\begingroup$

The ship of Theseus consists of n parts. The first part needs to be replaced every day, the second part every second day, the third part every three days and so on.

Theseus is concerned that replacing all parts on the same day may cause the ship to lose its identity, and become something different than the ship of Theseus. But he has a strategy to avoid this situation: whenever all parts are scheduled for replacement on the same day, before starting to replace the old parts, he adds a new part to his ship, which only needs to be replaced in $n + 1$ days.

The ship originally consisted of only one part and today Theseus has announced that he's added the 100th part to it.

How old is the ship of Theseus?

$\endgroup$
  • 6
    $\begingroup$ It's not really related to the puzzle itself, but I don't think Theseus has actually solved his problem. How does adding a new part (that wasn't part of the original ship) help preserve its identity? $\endgroup$ – KSmarts Mar 26 '15 at 16:17
  • 7
    $\begingroup$ @KSmarts "Now Theseus has two problems" $\endgroup$ – Michael Mar 26 '15 at 19:02
  • 3
    $\begingroup$ @KSmarts: If you accept Theseus's implicit premise (i.e., "the ship retains its identity if there is always at least one part intact"), then it should retain its identity. You add the new piece, and that piece is now part of the ship; that piece will remain intact for the remainder of the day while the others are replaced, so at no point does the ship lose its identity. $\endgroup$ – wchargin Mar 27 '15 at 4:06
11
$\begingroup$

First parts

Starting from the first day, Theseus has a single-part ship: this means that this part can only work for a day before being replaced, so Theseus should replace the first part on the second day. Given that replacing the first and only part will let the ship "lose its identity", then before replacing the first part, Theseus adds a second part: so the second part of his ship is added on the second day, before removing the first one.

On the second day, the first part has got to be changed again, but the second part has still got one day. On the third day the parts will be changed together, meaning that Theseus will have to add a third part.

Adding the nth part

When will Theseus have to change all the $n$ parts together again? It is easy to understand that Theseus will have to change all the parts when the number of days becomes equal to $lcm(1, 2, 3, ..., n-1, n) + 1$, which is the least common multiple of the duration of each part plus one, because the first day the only existing part doesn't have to be changed.

We can write a table representing the day when Theseus has to change all the $n$ parts together based on $n$:

n       day

1       2
2       3
3       7
4       13
5       61
6       61
7       421
8       841
9       2521
10      2521
...     ...
60      9690712164777231700912801
61      591133442051411133755680801

We can clearly see that this number becomes dramatically large when dealing with these amounts of parts.


Solution

When Theseus adds the $100$th part, this means that he already changed all the parts together $99$ times (adding a new part every time), and that it has come the day to change all the parts together again. So the age $A$ of the ship can be obtained solving the following equation:

$A = 1 + \sum \limits_{i=1}^{99} lcm(1, 2, ..., i) \simeq 2.149 \times 10^{41}$

The ship is $214959977860203405582463952869483994880562$ days old.

Which is around $588.93$ billions of billions of billions of billions of years, WOW!

Program

I created a small Python 2.7 script to calculate the number of days, here it is:

from fractions import gcd

def lcm(a, b):
    return (a/(gcd(a, b))*b)

age = 1 
for i in xrange(1, 100):
    age += reduce(lcm, range(1, i+1))

print "Theseus' ship is", age, "days old!"
$\endgroup$
  • $\begingroup$ This is correct. Excellent. $\endgroup$ – GOTO 0 Mar 26 '15 at 15:10
  • $\begingroup$ Just curious: How many years is that? $\endgroup$ – Mark Mar 26 '15 at 15:56
  • 3
    $\begingroup$ @Mark Around $588.93$ millions of millions of millions of millions of millions of millions of years. $\endgroup$ – Marco Bonelli Mar 26 '15 at 16:08
  • 8
    $\begingroup$ @Mark $5.885*10^{38}$ years, for those of us who prefer scientific notation to "millions of ...". $\endgroup$ – Tim S. Mar 26 '15 at 18:21
6
$\begingroup$

Very old indeed - Theseus is effectively immortal, and his ship is almost certainly space-faring, as the number of days is rather more than the current age of the universe, and probably more than the expected life of most suns.

The actual answer is more than $32\times 27\times 35\times 97\#$, where $97\#$ (97 primorial) is the product of all primes up to $97$.

This number is the least common multiple of all the numbers up to $100$. However there are some extra multiples in there too, so the actual age is larger than this, although it is less than $100!$ (100 factorial).

By way of concrete example, when Theseus added the 22nd part, the ship was approximately 2 million years old.

$\endgroup$
  • 1
    $\begingroup$ This is roughly what I was just writing in my answer, so I'll upvote you and leave mine unfinished. :) $\endgroup$ – Ian MacDonald Mar 26 '15 at 14:51
5
$\begingroup$

The ship is

214959977860203405582463952869483994880561

days old.

Explanation:

If the nth part is added today, the (n+1)th part will be added after lcm(1…n) days. Thus the 100th part gets added on day number $\sum_{i=1}^{99} \mathrm{lcm}(1,\ldots i)$.

$\endgroup$
  • 2
    $\begingroup$ You didn't consider the first day $\endgroup$ – Marco Bonelli Mar 26 '15 at 15:09
  • 3
    $\begingroup$ @Marco - the age on the first day would be zero days old, though. $\endgroup$ – Joffan Mar 26 '15 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.