Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Apologies if the title is unclear, I couldn't think of a good way to express what I want.

Given the usual 2D representation of the complete graph $K_n$ as a regular $n$-gon with each pair of vertices joined, let $U_n$ be the set of the disjoint regions of space delimited by the edges of the graph (so $|U_3|=1, |U_4|=4, |U_5|=11...$). Further, label the nodes of $K_n$ as $p_1, ..., p_n$.

What is the size of the largest subset $S_n \subset U_n$ such that $\forall s \in S_n \exists i, j, k \in K_n$ with $s \subset \triangle ijk$ and $t \not\subset \triangle ijk \forall t \in S_n, t \ne s$? That is, How many points can I place inside drawing of $K_n$ such that each triangle formed by three points on the exterior of $K_n$ contains at most one point?

In case it helps clarify what I'm trying to do, I'm working on a puzzle where letters are encoded by giving three points from a discrete set defining a triangle in which the letter is written. For instance, for $K_4$:

1-------2
|\  A  /|
| \   / |
|  \ /  | 
|   X   |
|  / \  |
| /   \ |
|/  B  \|
3-------4

"A" can be encoded as 123 or 124; B as 234 or 134. No further letters can be unambiguously encoded.

Playing around with pencil and paper, it seems as though $K_n$ can define $n-2$ letters unambiguously, but I haven't investigated far, and I can't immediately come up with a proof.

share|improve this question

1 Answer 1

Let $P\ $ be the number of point that can be placed in $K_n$.

$P \le n-2$

To see this consider three adjacent vertex. Without loss of generality let them be named 1, 2, and 3. Consider the triangle 1-2-3, and notice that it is cut by $n-3$ lines all of which start at vertex 2. (There is $n-1$ lines starting from vertex 2, but two of them are the lines 1-2 and 2-3). Thus the triangle 1-2-3 is divided in $n-2$ smaller triangles. Then notice that the extension of all those small triangles are triangles that have all of their vertices on the perimeter of $K_n$. So all of the space of $K_n$ is divided into $n-2$ triangles. Thus if there is more than $n-2$ points (letter) one of those triangle must contain at least two points (letter).

$P \ge n - 2$

To see this take an edge, say 1-2 and consider all the triangles that have this edge and another vertex on the perimeter of $K_n$. There is $n-2$ of them because there is $n-2$ vertices once we remove the vertices 1 and 2. Now each of those triangle contain smaller triangles when $n \ge 5$. For each big triangle place a point in the smaller triangle that is closest to the third vertex (i.e. the vertex that is not 1 or 2). In this way you can place $n-2$ points. It should be clear that each of the smaller triangle that contain a point is not contained in any of the other big triangle because all the big triangles here share the edge 1-2 and a different vertex. Since we know that the formula works for $n \le 4$ we are done.

Thus $P = n - 2$

Note that the proof that $P \ge n - 2$ only shows that there is a one to one map between the points and the big triangle constructed. The proof does not show that each possible big triangle (including those that don't have the edge 1-2) unambiguously determines a point (letter).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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