5
$\begingroup$

$3n$ points are drawn on a flat piece of paper, such that no $3$ points lie on a straight line. Is it always possible to connect triples of points with straight lines, such that you form $n$ triangles and no two triangles intersect or touch each other?

$\endgroup$
3
  • $\begingroup$ Trivially no if all 3n points are on a line. Probably you mean that no three points are on a single line? $\endgroup$
    – Bubbler
    Dec 8, 2021 at 11:59
  • $\begingroup$ @Bubbler yes i agree, having 9 points in a 3x3 grid , its not possible to connect pairs of points to form N triangles. Plus I fail to understand what the OP means by pairs points while referring to 3 sets of points. $\endgroup$ Dec 8, 2021 at 12:07
  • $\begingroup$ ah sorry, forgot about collinear points. Will update. $\endgroup$ Dec 8, 2021 at 12:15

1 Answer 1

9
$\begingroup$

Is it possible?

Yes it is always possible.

Why?

Order your points by x-coordinate (and by y for those with equal x - if any).
Take three points at a time from the ordered list to form each triangle.
The first triangle obviously won't intersect any other.
For each subsequent triple, its points are entirely to the right of all triangles created so far (or at least as far right and above - for the equal x case), so edges between them are guaranteed to not intersect existing triangles.

$\endgroup$
1
  • $\begingroup$ I think you could also rot13(ebgngr gur cynar (ol rcfvyba) fb gung ab gjb cbvagf unir gur fnzr l-inyhr) to make the rest of the argument a little slicker $\endgroup$ Dec 8, 2021 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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