# Polygon Construction for Specified Number of Interior and Boundary Lattice Points

Construct a simple polygon on a grid of equal-distanced points such that:

1. all the polygon's vertices are grid points,
2. there are exactly $$i~(\geq 0)$$ lattice points in the interior, and
3. there are exactly $$b~(\geq 3)$$ lattice points on the boundary.

As a practice, construct it for:

• $$i = 5$$ and $$b = 12$$
• $$i = 0$$ and $$b = 10$$
• $$i = 9$$ and $$b = 3$$

As for examples:

• On the left side, it's a polygon with $$5$$ interior points and $$16$$ boundary points.
• On the right side, it's a polygon with $$9$$ interior points and $$10$$ boundary points.

This puzzle was submitted (but not accepted) for The 31st International Olympiad in Informatics (IOI 2019).

• What do you want us to answer, exactly? – Jay Jun 8 at 10:16
• How to construct such polygon, for all $i$ and $b$. – athin Jun 8 at 10:17
• Isn't this more math than informatics? I thought IOI was a computing olympiad. – greenturtle3141 Jun 8 at 15:25
• @greenturtle3141 sometimes it has ad-hoc and constructive problems where logic and creativity are needed. It may also cover numerous math problems like game theory. IMHO the difference with math olympiad is algorithm/construction vs rigorous (mathematical) proof. – athin Jun 8 at 21:28

Here is the answer for practice ones:

1:

2:

3:

To construct b=3;

You just need to make a bigger triangle for all i's.

As show below for i=9.

The general idea is actually the same as above, if you want to increase b

you just need to visit extra points for the triangle while controlling your i value.

for example, if you want b=5 and i=9;

or for example, if you want b=20 and i=9;

So you should

decide your $$i$$ first as a triangle b=3, then increase b as much as you want on the grid to control the value of b.

so you can create polygons with every $$i\geq0$$ and $$b\geq3$$ values with the method above.

• Yep, this will work! Of course there are a lot of other ways (which may be easier -- or harder -- than your construction). Anyway, congrats! – athin Jun 8 at 22:51