Largest number of sides and diagonals

Question

I have asked to solve the following: For given an integer number $n\ge3$, find the largest positive number $k_n$ for which: for every convex $n-$polygon (with $n$ sides), we can find $k_n$ segments, each segment is a side or a diagonal of this $n-$polygon, such that for any two segments, they always has a common point.

For example: $n=3$: Triangle $ABC$ we can choose the set $\{AB,BC,CA\}$ that is $k_3=3$.

$n=4$: Quadrilateral $ABCD$ then we can choose $\{AB,BC,AC,BD\}$ that is $k_4=4$.

I have no idea to solve this? Could anyone help me?

Answer 1

ArsenBerk provided an algorithm that shows choosing $n$ such segments is possible, but not that choosing more is impossible. Here is a proof of that.

Suppose that for some convex $n$-gon, $n+1$ segments have been chosen meeting the conditions. We will obtain a contradiction.

By pigeonhole principle, there exists a vertex which is the endpoint of at least two chosen segments. Label that vertex $A_0$, and all the others, in clockwise direction, starting and ending with its neighbours, as $A_1, A_2, \dots, A_{n-1}$. Let the first of these which is connected to $A_0$ (here and henceforth, "connected" means "connected by a chosen segment") be $A_r$ and the last one be $A_{n-s}$, with $1\leq r < n-s \leq n-1$. The maximum number of chosen segments with $A_0$ as endpoint is then $(n-s)-(r-1) = n-s-r+1$.

Any chosen segments not having $A_0$ as an endpoint must be of the form $A_iA_j$ with $1\leq i < j \leq n-1$. If $i > r$, then $A_0A_r \cap A_iA_j = \emptyset$ (because they are non-adjacent sides in the convex quadrilateral $A_0A_rA_iA_j$), so we must have $i \leq r$. Similarly, if $j < n-s$, $A_iA_j \cap A_{n-s}A_0 = \emptyset$, therefore $j \geq n-s$.

Let us relabel the points $A_j$, for which $j \geq n-s$ (there are $s$ of those) as $B_1, B_2, \dots, B_s$, keeping the same clockwise-is-ascending order: $A_{n-s}$ is now $B_1$, and so on. A useful visualization could be that we are painting these points blue; if we also imagine $A_1, \dots, A_r$ as red, then we have shown that all chosen segments not attached to $A_0$ must connect a red point with a blue point.

---

Lemmma: In the convex polygon $A_1A_2\dots A_rB_1B_2\dots B_s$, with $r,s \geq 1$, the maximum number of chosen segments of the type $A_iB_j$ so that any two have a point in common, is $r+s-1$.

Proof: By induction. If $r+s = 2$, there is altogether only one segment, so that is the maximum that can be chosen. Assume the claim is true for every such polygon with $r+s = t-1$ for some $t > 2$. We prove it for $r+s = t$.

If $r = 1$, then every chosen segment connects the same red point with one of $s = t-1$ blue points, which makes at most $t-1$ segments. Similarly for the case $s = 1$.

Now suppose $r,s > 1$, and at least $t$ segments have been chosen. Consider the vertices $A_1$ and $B_1$. If both of these are endpoints of more than one chosen segment, then each must be connected to at least one other point. Let $A_1$ be connected to $B_j$ ($j > 1$) and $B_1$ be connected to $A_i$ ($i > 1$). But then $A_1A_iB_1B_j$ is a convex quadrilateral with two non-adjacent sides chosen, a contradiction. So at least one of $A_1$ or $B_1$ is an endpoint of at most one chosen segment. If we remove it, in the resulting (still convex) $t-1$-gon we have lost at most one chosen segment, so at least $t-1$ chosen segments remain, contradicting the inductive hypothesis. Therefore at most $t-1= r+s-1$ segments can be chosen.

---

Going back to the original polygon, it has at most $n-s-r+1$ chosen segments attached to $A_0$, and from the lemma, at most $r+s-1$ segments not attached to $A_0$, or in total at most $n$ chosen segments.

Answer 2

I think $k_n = n$. My reasoning is that we can choose the segments systematically in order to see this result:

First, let's choose a point from the $n$-gon $A_1A_2...A_n$. Without loss of generality, we can assume it is regular and choose $A_1$ by using the symmetry. Then every segment that has an end point $A_1$ is included to our count (because $A_1$ will be the common vertex) so there are $(n-1)$ such segments. Now, for the sides $A_1A_2$ and $A_1A_n$, the diagonal $A_2A_n$ also intersects all of other $(n-1)$ segments. And this the maximum we can get because except that diagonal, we cannot find any other diagonal such that it has common points with $A_1A_2$ and $A_1A_n$ both. Therefore, the answer is $k_n = n$.

Now, if we don't have a regular $n$-gon, this argument still holds because $A_1A_2$ and $A_1A_n$ are two sides of the triangle $A_1A_2A_n$ and all other vertices $A_i$ (with $i \ne 1,2,n$) of $n$-gon cannot be placed such that $\angle A_1A_2A_i > 180^\circ$ or $\angle A_1A_nA_i > 180^\circ$ because $n$-gon is convex (Also notice that even the angle was $180^\circ$, since in this case $A_1A_2 \cap A_1A_i = A_1A_2$ there would have been more than one mutual points). Therefore for all $A_i$, $A_1A_i$ intersects $A_nA_2$. And the same reasoning for $k_n=n$ to be maximum is still valid.