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).

  • $\begingroup$ What do you want us to answer, exactly? $\endgroup$
    – Jay
    Jun 8, 2019 at 10:16
  • $\begingroup$ How to construct such polygon, for all $i$ and $b$. $\endgroup$
    – athin
    Jun 8, 2019 at 10:17
  • $\begingroup$ Isn't this more math than informatics? I thought IOI was a computing olympiad. $\endgroup$ Jun 8, 2019 at 15:25
  • $\begingroup$ @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. $\endgroup$
    – athin
    Jun 8, 2019 at 21:28

1 Answer 1


Here is the answer for practice ones:


enter image description here


enter image description here


To construct b=3;

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

As show below for i=9.

enter image description here

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;

enter image description here

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

enter image description here

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.

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

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.