The problem was
You are given a set $S$ of $2005$ points (no three collinear) in the 2D plane. For each point $P$ in $S$, you count the number of triangles (formed by points in $S$) within which $P$ lies ($P$ must be strictly inside the triangle).
Show that this number is even, irrespective of the point $P$.
A possible solution
Given a point $P$ form a graph $G$ of the triangles that contain it.
In this graph, two triangles are adjacent if they share a side.
The claim is that each triangle has degree exactly $2001$ in $G$.
To show that, consider a triangle $T = \triangle{ABC}$ which contains $P$ and another point $P'$.
The claim is that exactly one of the triangles $P'AB$, $P'AC$, $P'BC$ contains $P$ (haven't tried proving this rigorously, hence this is only a possible solution)
There are $2001$ such points $P'$ and thus degree of $T$ is $2001$.
Since the degree of each vertex in $G$ is 2001, the number of vertices must be even ($\sum d_i = 2|E| \implies 2001|V| = 2|E| \implies |V|$ is even).
You are given a set $S$ of $2005$ points (no three collinear) in the 2D plane. For each point $P$ in $S$, you count the number of triangles (formed by points in $S$) within which $P$ lies ($P$ must be strictly inside the triangle).
Show that this number is even, irrespective of the point $P$.
A possible solution
Given a point $P$ form a graph $G$ of the triangles that contain it.
In this graph, two triangles are adjacent if they share a side.
The claim is that each triangle has degree exactly $2001$ in $G$.
To show that, consider a triangle $T = \triangle{ABC}$ which contains $P$ and another point $P'$.
The claim is that exactly one of the triangles $P'AB$, $P'AC$, $P'BC$ contains $P$ (haven't tried proving this rigorously, hence this is only a possible solution)
There are $2001$ such points $P'$ and thus degree of $T$ is $2001$.
Since the degree of each vertex in $G$ is 2001, the number of vertices must be even ($\sum d_i = 2|E| \implies 2001|V| = 2|E| \implies |V|$ is even).
No comments:
Post a Comment