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 in the lengths of such paths.
First, let's analyze the structure of the lattice paths in S. Each path corresponds to a sequence of "right" (R) and "up" (U) moves. Since the path cannot touch the x-axis or the y-axis, the number of R moves and the number of U moves must be equal.
Let's consider the number of R moves in a path. Since the path starts at (1,1) and ends at (n,n), the number of R moves will be n-1. Therefore, the number of U moves will also be n-1.
Now, let's calculate the length of a path in terms of the number of R moves (or U moves) it contains. Since each move corresponds to a unit distance, the length of the path will be the sum of the absolute values of the coordinates. For example, the length of the path (1,1), (1,-1), (-1,1) is |1| + |1| + |1| + |-1| + |-1| + |1| = 6.
For a path with t R moves (or U moves), the number of U moves (or R moves) will also be t. Therefore, the length of the path can be calculated as:
Length = |1| + |1| + ... + |1| + |-1| + |-1| + ... + |-1|
= t + 1 + t + 1 + ... + t + 1
= 2t(n - 1)
Now, we need to find the largest value of n such that every path in S, which ends at (n,n), has a length at most 50000. Let L represent the length of a path.
In our case, L = 2t(n - 1) = 50000.
Since we are looking for a positive integer value of n, we can start with n = 1 and increment it until we find the largest value that satisfies the equation.
For n = 1,
L = 2t(1 - 1) = 2t * 0 = 0
Since the length is 0, it does not satisfy the condition.
Next, for n = 2,
L = 2t(2 - 1) = 2t
We can solve 2t = 50000 to find the largest value of t that satisfies the equation.
Dividing both sides by 2 gives us t = 50000/2 = 25000.
Therefore, for n = 2 and t = 25000, the largest value of n for which every path in S, ending at (n,n), has a length at most 50000 is n = 2.
Hence, the largest value of n is 2.