2
$\begingroup$

I recently met a rather hard problem:

A lattice point is a ordered pair where both $x$ and $y$ of $(x, y)$ are both integers. A triangle is forms by of the lattice points $(1, 1)$, $(9, 1)$, and $(9, n)$. For what integer value of $n>0$ are there exactly 560 lattice points strictly in the interior of the triangle?

My first approach was trying to set an equation using Shoelace and Pick's. I found the area via Shoelace formula in terms of $n$ and then all I needed to do was to set this equal to Pick's theorem. However, I found it extremely hard to count the # of lattice points on the "lines" of the triangle, so that I didn't get very far.

I then tried another approach. I begin by drawing a diagram: enter image description here

Since the triangle is a right triangle, I can add a congruent triangle to make a rectangle, with the right angle at $(1, n)$. Since both triangles are congruent, then the entire rectangle has $560\cdot 2=1120$ lattice points in the interior. There are 7 possible $x$ coordinates I labeled in the diagram that can serve as valid $x$ coordinated for interior lattice points, so thus, there are $\frac{1120}{7}=160$ possible $y$ coordinates for the interior lattice points.

I have highlighted in red the 3 invalid $y$ coordinates that cannot serve as a $y$ coordinate for an interior lattice point. Thus, we can see that $n-3$(3 for the 3 invalid $y$ coordinates)$=160$. This means that $n=163$. However, this is wrong.

What am I doing wrong? What hole is there in my logic?

Furthermore, could I solve for $n$ using my first method(Shoelace=Pick's and solve)?

Is there any other way to solve this if I can't solve it this way?

Thanks!

Max0815

$\endgroup$
1
$\begingroup$

Your error is that the lattice points on the diagonal from $(1,1)$ to $(9,n)$ (excluding the endpoints) are interior points of the rectangle, but are not counted in the $2\times560$ points.

The main takeaway is that you will have to deal with that pesky diagonal one way or another. The triangle being right-angled with coordinate-parallel sides allows both approaches: The shoelace/Pick approach is more general, the second is easier, especially if you don't know about the Pick formula.

I'll give some hints for the first approach:

1) From the 3 sides of the triangle, 2 should be trivial by now, you did them for the second approach!

2) That leads to the diagonal, which represents a displacement of $(8,n-1)$, or if you look at the linear function on which that diagonal lies, it is $y=\frac{n-1}8(x-1)+1$

3) Any lattice point in the interior of that diagonal is characerized by 2 conditions:

a) $2\le x \le 8$, and

b)$\frac{n-1}8(x-1)$ must be an integer.

4) So the key question becomes: For which/how many $x'=x-1$ satisfying $1 \le x' \le 7$ is $\frac{n-1}8x'$ an integer?

5) The answer depends of course on the value of $\frac{n-1}8$. If that is already an integer (so $8|(n-1)$), every $1 \le x' \le 7$ works. OTOH, if $n-1$ is odd, then $x'$ would have to be divisible by $8$, which it can't be in that range.

6) Can you find the remaining cases? Can you find the respective number of solution $x'$? If you can't, try $n-1=2,4,6$ maybe you see something!

7) The previous parts of the problem should all be 'simple' formulas of $n$. If you can solve 6), you have several cases now for the part of the number of lattice points on the diagonal. Solve them each, then check if the solution (if one exists) matches the condition (that means if you use the formula that applies when $8|(n-1)$ and get a solution $n=165$, then it can't be correct, as $8$ does not divide $164$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you also help me on my second approach? $\endgroup$ – Max0815 Mar 22 '19 at 1:37
  • $\begingroup$ The help is basically the same. As I wrote, the error you made is that you did not account for the lattice points on the $(1,1)-(9,n)$ diagonal. I tried to jumpstart that calculation with my answer. If you have the result, you can use it for either approach. $\endgroup$ – Ingix Mar 22 '19 at 10:32
  • $\begingroup$ Ok. Got it. Thank you. $\endgroup$ – Max0815 Mar 23 '19 at 21:41
0
$\begingroup$

enter image description here

Since the triangle is a right triangle, I can add a congruent triangle to make a rectangle, with the right angle at $(1, n)$. Since both triangles are congruent, then the entire rectangle has $560\cdot 2=1120$ lattice points in the interior. There are 7 possible $x$ coordinates I labeled in the diagram that can serve as valid $x$ coordinated for interior lattice points, so thus, there are $\frac{1120}{7}=160$ possible $y$ coordinates for the interior lattice points.

I have highlighted in red the 3 invalid $y$ coordinates that cannot serve as a $y$ coordinate for an interior lattice point. However, when $y=0$, this line has lattice points that will not ever be in the triangle bound by $(9, n)$, and the other two points in the problem, so only the top and middles lines highlighted in red serve as invalid. Thus, we can see that $n-2=160$. This means that $n=\boxed{162}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.