[Math] Counting lattice ponts

combinatorics

A lattice point is a point with integer coordinates such as $(2,3)$. There are two parts of this problem.

[a] In how many ways can we pick 3 lattice points such that both coordinates of all three points are nonnegative integers less than $4$, and connecting the three points forms a triangle with positive area?

[b] An object in the plane moves from one lattice point to another. At each step, the object may move one unit to the right, one unit to the left, one unit up, or one unit down. If the object starts at $(0,0)$ and takes a 10-step path, how many different points could be the final point?

[a] For the first part here is how I am thinking. Since we are looking for points with nonegative integer less than $4$ then we are considering all integer points within the grid $0\times 0$ and $3\times 3$. There are $16$ points. To form a triangle we need to pick up 3 from 16 in $C(16,3) = 16!/(3! \cdot 13!) = 560$ ways. From here we need to exclude collinear points. Along the diagonals going from top left to bottom right we will have $1[C(3,3)] + 4[C(4,3)] + 1[C(3,3)]$ such points. The same is true for other set of diagonals going from bottom left to top right. So totally $2 \cdot (1 + 4 + 1)$ points need to be excluded for diagonals. Counting along horizontal grid lines we have $4$ ways of choosing 3 collinear points for every line. That makes $4 \cdot 4 = 16$ such points for horizontal lines and another $16$ for vertical grid lines. That brings total number of exclusions to $16 + 16 + 12 = 44$ points. Thus total number of triangles will be $960 – 44 = 916$ points. Am I missing out anything? Why did the problem specifically say – "triangle with positive area"?

[b] Using a grid paper I can see it reaches 4 distinct points. From each of those 4 points the object can reach 8 distinct points $+ 1$ [coming back to $(0,0)$]. Do I have to keep counting this way or is a smart way to solve this problem? Counting gets complicated because the object can move backwards.

Best Answer

Your reasoning for problem A is right, but you made a careless error, changing $560$ into $960$ at the end. The right answer is 516 triangles. The reason for saying positive area is ust to exclude the sets of three colinear points, as you did.

For problem B, take a broader view: After ten steps, you can end up at any even-total-sum point in the diamond whose corners are $(10,0), (0,10), (-10,0), (0,-10)$. This diamond contains 11 (even) points in the long $y=0$ row, 10 points in each of the $y=1$ and $y=-1$ rows, 9 points in $y=2$ and $y=-2$, and so on down to one point at $y=10$ and one at $y=-10$. The total = $$11 + 2\sum_{k=1}^{10}k = 11 + 2\cdot 55 = 121$$ It is significant that this is $11^2$, and in fact that pattern holds: for $n$ steps there are $(n+1)^2$ possible ending points. This is easily shown by induction.

Related Question