Project Euler 761 - Runner and Swimmer

Official link: https://projecteuler.net/problem=761

Thought Process

My first 90% problem, and I understand why. This is the longest I ever worked on a problem, and by far the hardest. Also this is my longest post by a lot so enjoy!

I decided to try this one because I watched the Numberphile video on this problem and it seemed fun and possible, I highly recommend watching the video first as it will fill in some gaps that I leave.

Case 1: The circle

This is the easiest to prove. 

Below is a little geogebra diagram I made to help me visualize the problem. Note that this strategy works because if the runner decides to turn back on their chosen path (WLOG they run to the right) then the swimmer just starts moving forward on the line that connects the swimmer, center, and the runner and the swimmer will have increased their lead.

Case 2: The square

This was significantly harder

Attempt 1: The same strategy as circle

Who would've thought this wouldn't work? Either way it was helpful in coming up with better strategies. Below I detail the same case as the circle but with a square and I had some fun learning how to use geogebra so it highlights where the swimmer can "escape" just press "reset" and then "find exit areas"

Either way, here is the proof that this method is wrong

Attempt 2: Using optimal swimmers path

Seeing as the above is wrong, there is likely a different, but still quite similar, strategy going on.

It was tempting to think maybe with an inner square the swimmer could position itself on a corner and then dash to the corner, but the runner can actually just stay still in the center, and just move left and right forcing the swimmer back to the center for their own sake, so I'm going to continue with the assumption that the swimmer and runner will stay in the center.

Given that we know that a dash is optimal (A curved line would make no sense as it is unoptimized) we need to figure out where the swimmer will dash from.

The first step is to find the optimal angle of incidence the path of the swimmers dash creates with the edge of the pool

Now we know the angle at which the swimmer wants to dash towards the edge of the lake! 

Note that this also shows that our previous analysis of the best angle for our case 1 is wrong, I leave it there to show my process.

Now let's continue adopting the strategy that the runner will follow the swimmer all the time and imagine the swimmer is on the edge of a square of side length 2/v. As the runner run's to the right, the swimmer will begin swimming to the left while slowly increasing it's y co-ordinate, then as the runner reaches the corner (1, -1), the swimmer will essentially reach (-1/v, 1/v) the swimmer can dash to the line x = -1 at the angle stated above and beat the runner if v~5.9.

Let's think about what the runner can do after he reaches the point (1, -1)

Options 2 and 3 improve the swimmers position, so it is clear that once the runner has committed to an option they must follow through.

Attempt 3: Stay put strategy

Now we know that the runner must commit to a direction, if they go too early the swimmer can force the runner to go the long way around the square, hence logically the runner should stay put at (0, -1) until the swimmer reaches a point (0, h) such that they are indifferent between the long way and a direct dash to y = 1.

Again a little geogebra applet to help me visualize the problem

Now we need to find this h

Case 3: The hexagon

Finally, we have arrived at the actual problem.

First thing to note is that our optimal angle calculation actually works for every shape (including the circle) so we can re-use it

Attempt 1: The same strategy as the square

Once again setting up a geogebra to aid in visualizing

After sorting out all the correct lengths we need to find h

Attempt 2: The solution

Given that the previous case is wrong, I guessed that the answer could be the case where the runner positions themselves on a corner, thankfully for the last time, we repeat the same process again. Another geogebra to help visualize the problem.

Finally, the problem is solved! Although it is quite short of proof, as I exclude all other start points, and my justifications for other cases are not as sound proof as I would like, however I am still very happy with how I worked through this problem! 

I actually found this stackexchange post where someone details how to solve this problem for ANY shape, and has a generalization for all regular n-gons, but in the spirit of Project Euler and this website, I wanted to actually do it myself and understand the problem.

Here is the pdf explaining the general solution: https://drive.google.com/file/d/0ByRo3goCgoh7OFJCQ2RiUzEycVE/view?resourcekey=0-rnfXNmyCFU8vMZKuH2cwdQ huge props to stewbasic who is the author!

Interactive Code

Input an integer (n)

Code will output the maximal speed of the runner given an n-gonal lake