5
$\begingroup$

A time traveler is collecting treasures.

He is using a space-time ship to transport between 5 different place-rooms. Each place has 1 precious treasure from the ancient times in each of 5 time zones.

Rules

  • His space-time ship can only visit a particular space-time room once
  • If he is in space-time room xy, he can freely travel to space-time room xa OR by. Example : from room 12 he can go to rooms 11,13,15,14,22,52,32 and 42.
  • He gets treasure if he visits rooms in order from newer time to older time. Example : If he visits 41 -> 51 -> 52, he will get 3 treasures, because 41 is newer than 52. If he visits 52 -> 51 -> 41, he will only get 2 treasures, because 52 is older than 41 (in the same place column).
  • So if he start from time-space room 44, he lost treasures at rooms 33,22, and 11 (But not at room 55), because places-rooms 33,22,11 is newer than place-room 44, and place-room 55 is older than place-room 44.

What is the maximum number of treasures he can get?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Suspending disbelief that the treasure wouldn't just disappear from his hands. $\endgroup$ – boboquack Oct 9 '17 at 8:06
  • 4
    $\begingroup$ I don't understand the treasure-collection rules. In the 52-51-41 sequence, I can understand if he visits 52 first, takes the treasure, then later finds nothing at 41. But 52 and 51 are different places - why doesn't he get a treasure each for 52 and 51 regardless of order? $\endgroup$ – Lawrence Oct 9 '17 at 14:33
  • 1
    $\begingroup$ Is the third row supposed to say "because 52 is older than 41? $\endgroup$ – DqwertyC Oct 9 '17 at 14:43
  • 1
    $\begingroup$ @JamalSenjaya So why is the reason given for only 2 treasures in the 52-51-41 case "because 52 is older than 51"? $\endgroup$ – Lawrence Oct 10 '17 at 15:03
  • 1
    $\begingroup$ @Lawrence Agreed, should be 41. (Forgive my deleted reply) $\endgroup$ – LeppyR64 Oct 10 '17 at 15:11
2
$\begingroup$

The best I found (by creating a brute force program) is

23 treasures

There are many combinations of this that will work. One of which is

11, 51, 53, 23, 22, 24, 34, 33, 32, 35, 45, 43, 44, 54, 14, 15, 55, 25, 21, 31, 41, 42, 52, 12, 13

Other combinations include:

I found 164,551 that should work assuming my program is written correctly (and assuming not all rooms must be visited), so I'm not even going to begin to try to put them all here or manually test all of them.

$\endgroup$
2
$\begingroup$

My understanding of the third rule is that once a room is visited in an older time, treasure can't be obtained in a newer time. With this in time, the best solution I've found is:

23 treasure

Following this path:

enter image description here
Room 53 is crossed out because its treasure is destroyed by entering room 14.

There may be a way to get at least one more, but it's impossible to get all the treasure, because:

You can never move to a room in the same time (with the current numbering), so at least one of the places must be accessed at in row 2 before it is accessed in row 1, meaning that at least that treasure isn't available.

$\endgroup$
1
$\begingroup$

The maximum number is

23. It's pretty easy to find an example of a solution with 23 moves, and others have already shown those.

It's impossible to get any more than that, because

there will always be at least one square left over at the beginning of the journey, and at least another one at the end.

To show why this is, consider the possible moves. First, let's call two squares connected, if it's possible to move between them. Then,

you must always pick a square that is the topmost unvisited one in its column in order to not destroy a treasure.

Taking this into account,

Regardless of which of the top row squares you choose as your starting point, the next one will destroy a treasure: there are no connections between any of the squares in the top row, and neither is any of the top row squares connected to the square just below it. This means that for the second square, you have to pick one that is not the topmost unvisited square in its column, and at least one treasure will be destroyed.

Similarly,

If we managed to get all the remaining squares, the next-to-last square would need to be the square just above the final one, or another square in the bottom row. Again, no matter which bottom row square we choose as the final one, no such connection exists.

Therefore, it is impossible to improve on this result.

$\endgroup$
  • 1
    $\begingroup$ I think this proof is incomplete - there does not seem to be any prohibition on a path that starts by destroying one treasure (but not visiting that room), and then visiting the room with the destroyed treasure immediately before the final room on the bottom row... something that could perhaps help with constructing a 24 room solution if one is possible, or which needs to be considered by a proof of impossibility. $\endgroup$ – Steve Oct 10 '17 at 13:37
  • $\begingroup$ For example, consider a path which starts 51 -> 11 -> 12 ... (destroying the treasure in 45), and ends ... -> 42 -> 45 -> 55 (visiting the room with the destroyed treasure only to make a path between the last 2 rooms with a treasure intact). $\endgroup$ – Steve Oct 10 '17 at 13:59
  • $\begingroup$ ah yes, that does indeed sound like a possibility. $\endgroup$ – Bass Oct 10 '17 at 15:45
  • $\begingroup$ I think it is a possibility, but there may only be one way to make it work. I've tried it several times, to no avail (yet) $\endgroup$ – DqwertyC Oct 10 '17 at 15:58
1
$\begingroup$

Others have already given and founds plenty of examples where the path length is

23

Bass's answer gave the initial outline of the proof of maximality, but missed a crucial point:

A solution of length 24 may be possible if we visit the room where the treasure was destroyed as the penultimate step.

For example, a path that starts 51 -> 11 -> 12 -> ... could hypothetically finish with ... -> 42 -> 45 -> 55. If the remaining rooms could be arranged to complete the path, this would

leave only the treasure in room 45 destroyed, and allow recovering all 24 remaining treasures.

Unfortunately, before finding an elegant proof, I resorted to a brute force search program which chooses one of the top row as the treasure to be destroyed by the first 2 moves, and then

sets this as the room to be visited 24th, and the treasure below it as either first or second.

All other decisions by the brute force search are restricted to the up to 5 "available" rooms which still contain treasure and will not cause other treasure to be destroyed (and which link to the adjacent rooms in the sequence according to the rules).

The result was that

plenty of paths of length 24 were found according to the restrictions, but none of them allowed travel to the final non-visited room.

I'd noticed before switching to a brute-force solution that:

once the "to be destroyed" room is chosen, it forces the choice of rooms at each end, for example, when choosing room 45 to be destroyed, room 51 must be visited either first or second. If it is chosen as the first, then 51 -> 53 -> ... is a dead end, with no valid third room, so 51 -> 11 -> 12 -> is forced, and the first genuine choice is between rooms 32 and 22.
Similarly, 45 is connected to 42 and 55 on the bottom row, so these must be in positions 23 and 25 in some order. ... -> 55 -> 45 -> 42 does not have any valid predecessor to 55 (other than taking a room "out of order" and destroying another treasure), so a solution collecting 24 treasures with treasure 45 destroyed must end ... -> 42 -> 45 -> 55.

In fact more choices are "forced", so if treasure 45 is chosen to be destroyed near the start then one of the following is forced:

51 -> 11 -> 12 -> [32/22] -> ... ... -> [31/33] 34 -> 44 -> 42 -> 45 -> 55
53 -> 51 -> 11 -> [14/12] -> ... ... -> [31/33] 34 -> 44 -> 42 -> 45 -> 55

As the brute-force search worked forwards, it instead found that

when it reached room 45 on the 24th turn, it was always via the sequence ... -> 55 -> 15 -> 45 or ... -> 52 -> 55 -> 45, with room 42 having been visited earlier in the sequence.

In addition, the not visited room was always

one of the two rooms on the bottom row which are neither reachable from the room in which the treasure was destroyed, nor in the same "place" as it. i.e. 13 and 21 if room 45 was chosen.

There is probably a much more elegant proof than this brute-force solution, but I'll leave that for someone else to find, however one hint I notice that can probably be exploited in a more elegant proof is that

the grid appears to have a carefully constructed symmetry... the first digits shift one column to the left from one row to the next, and the second digits shift two columns to the left.

In particular this should mean that

the choice of which treasure on the top row is destroyed will be arbitrary, as any solution that destroys one treasure can be converted to one that destroys a different treasure simply by relabelling the rooms.

$\endgroup$

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.