Let S be the set of {(1,1), (1,−1), (−1,1), (1,0), (0,1)}-lattice paths which begin at (1,1), do not use the same vertex twice, and never touch either the x-axis or the y-axis. Let Sx,y be the set of paths in S which end at (x,y).For how many ordered pairs (x,y) subject to 1≤x,y≤31, is |Sx,y| a multiple of 3?
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 (x1,y1) to (x2,y2) is (x2−x1,y2−y1).
The length of a lattice path is the number of steps in the path.
For a set S={(xi,yi)}ki=1, an S-lattice path is a lattice path where every step has size which is a member of S.
To solve this problem, we need to count the number of lattice paths that satisfy the given conditions and whose endpoints have a certain property.
Let's start by understanding the problem constraints:
- The lattice paths must be in the set S, which consists of five possible steps: {(1,1), (1,-1), (-1,1), (1,0), (0,1)}.
- The paths must begin at the point (1,1) and cannot touch the x-axis or y-axis.
- We need to count the number of lattice paths that end at each point (x,y) where 1≤x,y≤31.
- We are interested in finding the number of ordered pairs (x,y) for which the number of lattice paths ending at (x,y) is a multiple of 3.
To solve this problem, we can use a dynamic programming approach. We will build a table to store the number of lattice paths ending at each point (x,y). We will start with the base cases and iteratively fill in the table using the recurrence relation.
Here are the steps to solve this problem:
Step 1: Initialize a 2D table with dimensions 31x31. Set all entries to 0.
Step 2: Set the base cases:
- Set table[1][1] = 1, since the starting point is (1,1).
Step 3: Iterate through each point (x,y) from (1,1) to (31,31):
- Check if the point (x,y) is reachable from any of the previous points using one of the steps from set S.
- If reachable, compute the number of lattice paths ending at point (x,y) by summing up the number of lattice paths ending at the previous points that can reach (x,y) using one of the steps in set S.
- Update the table entry table[x][y] with the computed value.
Step 4: Count the number of points (x,y) where the table entry table[x][y] is a multiple of 3.
Step 5: Return the count obtained in Step 4, which represents the number of ordered pairs (x,y) satisfying the given conditions.
By following these steps, you can solve the problem and determine the number of ordered pairs (x,y) for which the number of lattice paths ending at (x,y) is a multiple of 3.