2008 iTest Problems/Problem 73

Revision as of 17:40, 21 November 2018 by Rockmanex3 (talk | contribs) (Solution to Problem 73 (credit to official solution) -- tough distance optimization problem)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

As the Kubiks head homeward, away from the beach in the family van, Jerry decides to take a different route away from the beach than the one they took to get there. The route involves lots of twists and turns, prompting Hannah to wonder aloud if Jerry's "shortcut" will save any time at all.

Michael offers up a problem as an analogy to his father's meandering: "Suppose dad drives around, making right-angled turns after $\textit{every}$ mile. What is the farthest he could get us from our starting point after driving us $500$ miles assuming that he makes exactly $300$ right turns?"

"Sounds almost like an energy efficiency problem," notes Hannah only half jokingly. Hannah is always encouraging her children to think along these lines.

Let $d$ be the answer to Michael's problem. Compute $\lfloor d\rfloor$.

Solution

First, we'll show that the farthest distance Jerry can travel with $n$ left turns and $n$ right turns is $n\sqrt{2}$.

Lemma 1: Farthest distance with $n$ left turns and $n$ right turns is $n\sqrt{2}$

Note that all of Jared's turns are perpendicular and occur at every mile. Thus, he travels north or south for $n$ miles and east or west for $n$ miles.

[asy] draw((0,0)--(0,2)--(2,2)--(2,0)--(0,0),dotted); draw((0,0)--(0,1)--(1,1)--(1,2)--(2,2)); draw((0,0)--(2,2)); [/asy]

That means the maximum distance can not be more than the diagonal distance of a square with side lengths $n$. The diagonal case can be achieved by alternating left turns with right turns. An example can be seen when $n = 2$ in the picture above. $\blacktriangleright$


Assume Jerry travels his first mile north. If Jerry takes a turns after every mile and $300$ of these turns are right turns, then he takes $199$ left turns. From the Lemma, after turning left $199$ times and turning right $199$ times, he is $199\sqrt{2}$ miles from the start.


However, Jerry still has $101$ right turns to use. By only using right turns, Jerry can only be at most $\sqrt{2}$ miles from the original spot. If Jerry uses four right turns, then he ends up in the original spot. That means Jerry can use $100$ right turns to end in the original location, resulting in one left-over right turn.


If Jerry ends up being $199\sqrt{2}$ miles from the start after using a right turn, then his final destination is one unit south of the diagonal's endpoint, so Jerry is $\sqrt{199^2 + 198^2} \approx 280.72$ miles from the start. If Jerry ends up being $199\sqrt{2}$ miles from the start after using a left turn, then his final destination is one unit east of the diagonal's endpoint, so Jerry is $\sqrt{200^2 + 199^2} \approx 282.14$ miles from the start.

Thus, the maximum distance from the start is around $282.14$ miles, so $\lfloor d\rfloor = \boxed{282}$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2008 iTest (Problems)
Preceded by:
Problem 72
Followed by:
Problem 74
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100