6
$\begingroup$

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:

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

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

Here is the answer for practice ones:

1:

enter image description here

2:

enter image description here

3:

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.

$\endgroup$
  • $\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 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.