Rescuing Princess Peach: Shortest Path Problem

(I did this work for my university purpose! adopted as an article to share with you all. An experimental post ! ) 

We try to solve an exciting real-world geometry problem. This article presents two solutions, one intuitive and the second mathematical.


Food for thought
 — The shortest distance between two points in a plane is a straight line. This is a well-known theorem proved using lengthy calculus and geometry. Here is the link to the proof. With this in hand, we are ready to dive into our story.

Mario is close to saving Princess Peach from King Koopa. Here is a top view of the current scenario. Mario is at point S, and Princess Peach is at point T.

Image for post

The red boundary is an opaque wall, through which Mario can not see. We are interested to find a curve C, which is the shortest path from S to T. There is no straight line joining S to T without being obstructed by the opaque wall.

Intuitive idea

Let us take inspiration from nature to solve this problem. If we tie one end of an elastic string at S and another end at T, what should be the final configuration of the string? If the string is tight, it should be bent at V going from S to V and V to T forming two straight lines.

Hmm… Intuitively looks like SV+VT should be the shortest path from S to T. Since elastic string would try to minimize its elastic potential energy.

Proving our idea

Theorem 1 — The shortest path has to be composed of straight lines.

Proof (Contradiction): Let us assume there is a curve C which is the shortest path from S to T.

Image for post

Prove by contradiction for Theorem 1

len(SP)<len(C1) and len(PT)<len(C2)

Hence, len(SP)+len(PT)<len(C) — Which contradicts our assumption

Theorem 2 — The shortest path between S to T is composed of exactly two straight lines. (This proof is left to the readers as an exercise for fun! Hint: We need to contradict that there could be the shortest path composed of three line segments. Let me know if you require proof.)

Theorem 3 — The shortest path is SV+VT

Image for post

Figure to prove Theorem 3

We try to prove that any general path SP+PT will have a longer length than SV+ST.

Construction- Since point V obstructs view from S to T, angle(SVT) is reflex [By angle SVT, we mean angle(SVR) +angle(RVT) >180 degree]. We choose a point R such that angle(RVT)=90 degrees, and we also join SR. This means the angle(RVS) has to be greater than 90 degrees.

Proof- Since angle(RVS)>90 degrees, angle(RVS) has to be the largest angle of the triangle(SRV). This implies, RS>SV

By the triangle inequality, SP+PR>RS. Which means SP+PR>SV — — — (1)

In triangle VRT, RT is the hypotenuse. Hence, RT>VT — — — — (2)

Adding (1) and (2), we obtain SP+PR+RT>SV+VT

Hence, SP+PT>SV+VT

This proves that Mario should take the path SV + VT to reach Princess Peach the fastest!

Published by Mayank

Heyy, I am your friend Mayank. Loves talking about photography, tech, politics, and combinatorics. Hit me up if you got a puzzle xD

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website with WordPress.com
Get started
%d bloggers like this: