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 5 0 0 0 0 .
Details and assumptions
A lattice path is a path in the Cartesian plane between points with integer coordinates.
A step in a lattice path is a single move from one point with integer coordinates to another.
The size of the step from ( x 1 , y 1 ) to ( x 2 , y 2 ) is ( x 2 − x 1 , y 2 − y 1 ) .
The length of a lattice path is the number of steps in the path.
For a set S = { ( x i , y i ) } i = 1 k , an S -lattice path is a lattice path where every step has size which is a member of S .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
It is sufficient to determine the length of the longest { ( 1 , 1 ) , ( 1 , − 1 ) , ( − 1 , 1 ) } -lattice path from ( 1 , 1 ) to ( n , n ) , since all other paths will have length less than or equal to this length. Examining our different steps, we see that taking a step of size ( 1 , 1 ) increases the sum of the coordinates by 2, and taking one of the other steps does not change the sum of the coordinates. Since we are not able to use the same point more than once, after taking a ( 1 , − 1 ) step, we are only able to take a ( 1 , 1 ) step or a ( 1 , − 1 ) step. Thus, any path from ( 1 , 1 ) to ( n , n ) will consist of n − 1 steps of size ( 1 , 1 ) with only one other type of step size between each pair.
For a point ( x , y ) , with x + y = n , at most n consecutive steps of the form ( − 1 , 1 ) or ( 1 , − 1 ) can be taken from this point (from ( 1 , n − 1 ) to ( n − 1 , 0 ) or reverse). However, we cannot arrive at ( 1 , n − 1 ) or ( n − 1 , 1 ) aside from taking a step from ( 2 , n − 2 ) or ( n − 2 , 2 ) respectively. So we can take at most n − 3 steps while keeping the sum of the coordinates equal to n . When we have the sum of our coordinates equal to 2 n , we can take at most n − 2 steps to get to ( n , n ) . This gives us an upper bound of n − 1 + ( 1 + 3 + ⋯ + 2 n − 5 ) + n − 2 = ( n − 1 ) 2 for the length of the path. We see that this length is also attainable by alternatively placing maximal numbers of ( 1 , − 1 ) and ( − 1 , 1 ) between the steps of size ( 1 , 1 ) .
Thus, we must have n − 1 ≤ 5 0 0 0 0 , so n = ⌊ 5 0 0 0 0 ⌋ + 1 = 2 2 4
Problem Loading...
Note Loading...
Set Loading...
first check that from (1,1) to (2,2) the maximum length is 1.
and then from (1,1) to (3,3), we need to go to (2,2) so we only check the maximum length from (2,2) to (3,3) that is 3, so the maximum length from (1,1) to (3,3) is 4.
and then from (1,1) to (4,4) we have the maximum length from (1,1) to (3,3) that is 4, now chek the maximum length from (3,3) to (4,4) it easy to get that is 5. so the maximum length from (1,1) to (4,4) is 9
do it soon...
we assume that the maximum length from (1,1) to (n,n) is ( n − 1 ) 2
by using mathematical induction we will prove it.
for n=2 it easy to check that the maximum length is 1 = ( 2 − 1 ) 2 . since if you move with (1,-1) or (-1,1) you will touch the x − a x i s or y − a x i s
for n=k assume that the maximum length is ( k − 1 ) 2 now we prove for n=k+1 the maximum length is k 2
note that from (1,1) to (k,k) we have the maximum length is ( k − 1 ) 2 now check for from (k,k) to (k+1,k+1) , it's clear that you only can use (1,1) for 1 move and you also only can use (1,-1) and (-1,1) each of them k-1 time. So the maximum length from (k,k) to (k+1,k+1) is 1 + ( k − 1 ) + ( k − 1 ) = 2 k − 1 hence the maximum length from (1,1) to (k+1,k+1) is ( k − 1 ) 2 + 2 k − 1 ) = ( k 2 − 2 k + 1 ) + 2 k − 1 = k 2 so our assumtion proved.
since we want the maximum length is 50.000 we have ( n − 1 ) 2 ≤ 5 0 . 0 0 0 so n ≤ 2 2 4