Straight line problem : Find the number of points which lies between the figure : $(0,0) , (0,21); (20,0)$

Question

Problem:

Find the number of points which lies inside the triangle : $(0,0) , (0,21); (20,0) $

Approach :

Let us take point $A = (0,0)$, $B = (0,21)$, and $C = (20,0)$.

Since the figure formed by joining these points $ABC$ is a triangle where:

Point $A$ lies on origin; $B$ lies on $y$-axis and $C$ lies on $x$-axis. I am unable to find the condition to find the number of points which lies in this triangle.

Please help in this context.. thanks...

Answer 1

Hint

Take the equations: $$ \begin{align} 0 \le x & \le 20 \\ 0 \le y &\le 21 \\ \dfrac{x}{20} + \dfrac{y}{21} &\le 1 \\ x, \ y \in \left\{0,\ 1,\ 2,\ 3,\ \cdots \right\} \end{align} $$

Answer 2

If a point $(x,y)$ is on the origin side of line $BC$, the point satisfies this inequality: $$\begin{align} y \le& 21 - \frac{21}{20}x\\ y \le& 21 - x -\frac{x}{20} \end{align}$$

And the maximum integer $y$ that satisfies this inequality is dependent on $x$, and is given by $\left\lfloor21 - x -\frac{x}{20}\right\rfloor$. For integer $x$, this is equivalent to $21-x-\left\lceil\frac{x}{20}\right\rceil$. The last ceiling is $0$ for $x=0$ and $1$ for $x\in \{1,2,3,\ldots,19\}$.

So if you were to count all integer coordinates inside the triangle, you should sum the maximum integer $y$ over $x\in \{1,2,3,\ldots,19\}$.

$$\begin{align} S=\sum_{x=1}^{19}{\sum_{y=1}^{\left\lfloor21 - x -\frac{x}{20}\right\rfloor}1} =&\sum_{x=1}^{19}\left\lfloor21 - x -\frac{x}{20}\right\rfloor\\ =& \sum_{x=1}^{19}\left(21-x-\left\lceil\frac{x}{20}\right\rceil\right)\\ =& \sum_{x=1}^{19}\left(21-x-1\right)\\ =& \sum_{x=1}^{19}\left(20-x\right)\\ \end{align}$$

This should not be too difficult. If you also want the point on the boundary, you can do so similarly.

Answer 3

Let $P$ a lattice polygon, $A$ it's area, $I$ the number of the interior lattice points, $B$ number the lattice points on the boundary of $P$. Then $$A=I+B/2-1.$$ This is known as Pick's theorem. From here we conclude $211=I+B/2$. Obviously there are $42$ points on both axis and no lattice point on the line segment from $(0,21)$ to $(20,0)$: It's slope is $-21/20$, assuming a lattice point on the segment, one could reduce $-21/20$. So $B/2=21\Rightarrow I=190\Rightarrow I+B=232$.

Michael