Let S be the set of {(1,1),(1,−1),(−1,1)}-lattice path which begin at (1,1), do not use the same vertex twice, and never touch either the x-axis or the y-axis. Determine the largest value of n such that every path in S which ends at (n,n) has length at most 50000.
To determine the largest value of n such that every path in S which ends at (n,n) has a length at most 50000, we need to find a pattern based on the number of steps it takes to reach (n, n).
First, let's analyze the given set S. We have three possible moves: moving right (1 step to the right), moving down (1 step downward), and moving diagonally (1 step right and 1 step downward). We also know that we cannot touch the x-axis or the y-axis.
Let's start by drawing the first few lattice paths from (1, 1) to (n, n):
First step: (1, 1) → (2, 1) → (3, 1) → (4, 1) → (5, 1) → ...
Second step: (1, 1) → (1, 2) → (2, 2) → (3, 2) → (4, 2) → ...
Third step: (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) → ...
...
Nth step: (1, 1) → (1, 2) → (1, 3) → ... → (1, n) → (2, n) → (3, n) → ...
From the above paths, we can observe that the number of steps required to reach (n, n) is equal to n - 1. The path consists of moving right n - 1 times, moving down n - 1 times, and moving diagonally n - 1 times.
Therefore, the total number of steps in the path would be 3 * (n - 1).
Now, let's set up the equation:
3 * (n - 1) ≤ 50000
Divide both sides by 3:
n - 1 ≤ 50000/3
n - 1 ≤ 16666.67
Since n is an integer, the largest possible value for n is 16667.
Therefore, the largest value of n such that every path in S which ends at (n, n) has a length at most 50000 is 16667.