Let $K$ be the set of all sides and diagonals of a convex $2010-gon$ in the plane. For a subset $A$ of $K,$ if every pair of line segments belonging to $A$ intersect, then we call $A$ as an intersecting set. Find the maximum possible number of elements of union of two intersecting sets.
Problem
Source:
Tags: inequalities, analytic geometry, email, combinatorics proposed, combinatorics
19.12.2010 11:38
Number the vertices clockwise $1,2,...,2010$ Answer: $4019$, when $A=\{(1,3), \, (2,i) , i\neq 2\}$ and $B=\{(4,6),\, (5,i) , i\neq 5\}$. Proof: Let $A$ be an intersecting set with $|A|=k$. We number the edges $\{i_m,j_m\}$ such that if we start at point $1$ and move clockwise we reach point $i_m$ before $j_m$. Wlog $1=i_1\le i_2 \le ...\le i_k \le j_1 \le j_2 \le ... \le j_k\le 2010$. If $i_{\ell}=i_{\ell+1}$ then $j_{\ell}\neq j_{\ell+1}$. Therefore, at least $k-1$ of those inequalities are strict, so $k-1 \le 2009$ and therefore $|A|\le 2010$. Equality occurs when $(i_{m+1},j_{m+1})=(i_m+1,j_m)$ or $(i_m,j_m+1)$ (*). Furthermore $i_1=1$, $i_{2010}=j_1$, and $j_{2010}=2010$ hence the relation still holds if we reduce $\mod 2010$ and let $2011=1$. So we can order the edges $a_1,a_2,...,a_{2010},a_1$ that cycles, that is, every two consecutive edges satisfy (*). Call such sets maximal We'll show that every two maximal intersecting sets share at least one element. Suppose we have two such sequences, $\{a_i\}$ and $\{b_i\}$. Since they cycle we can assume wlog that $a_1$ and $b_1$ both have edges adjacent to vertex 1, and the other coordinate is minimal. The the first terms are $(1,a)$ and $(1,b)$ and the last terms in the sequences must be $(a,2010)$ and $(b,2010)$ respectively**. Now if $a=b$ we done so assume wlog that $b>a$ it follows from $(*)$ that some term in those sequences coincide. So $|A\cap B|\ge 1$. The conclusion follows. $\square$ ** Since we assumed $a$ is minimal we cannot have $(1,a-1)$ in the sequence so we must have $(a,2010)$. Similarly for $b$. It's also the last element because the sum of the coordinates of the edges increase by 1 each term.
19.12.2010 17:41
This is not true. The elements of an intersecting set do not have to form a cycle. Take the edges $12, 23, 13, 24, 25$ for a pentagon for example.
20.12.2010 00:50
Oh sorry, you did not say that they form a cycle. I think there still might be some minor problems. In the argument about increasing the sum of coordinates at each step you need to take into account that your (*) is a modular relation, but this is good, you can just consider modulo 2010. Yet, for the two sets intersecting somewhere I don't know how you can say it right away.
20.12.2010 01:03
Umut Varolgunes wrote: This is not true. The elements of an intersecting set do not have to form a cycle. Take the edges $12, 23, 13, 24, 25$ for a pentagon for example. Sorry, by cycle I don't mean polygon, I meant simply that $(i_{2010},j_1)=(i_{2010},j_{2010}+1)$ so the relation (*) cycles through all edges. But, again this isn't true for all intersecting sets, just those with $2010$ elements. As for your other concern, since we chose $(1,a)$ so that $a$ is minimal, it is the edge with the minimal sum of it's end coordinates. If $(i,j)\in A$ with $i+j < 1+a$ then $1<i<j< a$, but then they wouldn't intersect. So, then $(a,2010)$ has the maximum sum, and it doesn't matter that we reduced $\mod 2010$ because all numbers are $\le 2010$ anyway. Finally, the sequence that takes $(1,a)\to (a,2010)$ consists of unit steps to the right and unit steps up. If you sketch those two points it should be immediately clear that their paths intersect with one from $(1,b)\to (b,2010)$.
20.12.2010 03:13
Well yeah, I guess you are right. The reason that I was so sceptical is that I proposed this question and my solution is a little longer than this. But, yes, nice solution.
20.12.2010 03:30
Umut Varolgunes wrote: Well yeah, I guess you are right. The reason that I was so sceptical is that I proposed this question and my solution is a little longer than this. But, yes, nice solution. Nice question. I would be interested to see the offical solution if you have time to write it out. Since you proposed a question on this exam, can you tell me which interpretation is intened for Question 1. That is i) the graph remains connected it you delete any $k$ roads from the capital city, or ii) there always exists $k$ roads that can be deleted from the capital city and leave the graph connected
20.12.2010 04:00
It's the second one. If you want I can e-mail you the solution.
22.12.2010 00:24
Ohh ; I also want to see your solution ; Umut Please send me through the email : loc_lhp@yahoo.com Many thanks
22.09.2019 03:51
We claim that the answer is $\boxed{4019}.$ Label the vertices of the convex $2010-$gon $1, 2, \cdots, 2010$ in clockwise order, and WLOG that our polygon is regular. We can get $4019$ by considering the union of sets $\{(1, 3)\} \cup \{(2, i) | i \neq 2\}$ and $\{(15, 17)\} \cup \{(16, i) | i \neq 16\}$, where each pair of vertices corresponds to a diagonal or a side. From now on, we will let sides also be called diagonals, for convenience. We'll now show that $4019$ is optimal. First, let's show the following. Lemma. Any intersecting set has at most $2010$ diagonals. Proof. Define the value of a diagonal connecting vertices $i, j$ to be the unique integer $k$ in $[0, 2010)$ so that $i+j \equiv k$ (mod $2010$). Observe that no two diagonals which have the same value can intersect, as they would then be parallel. Therefore, all diagonals in an intersecting set have distinct values, which implies the lemma. $\blacksquare$ By the lemma, the only way we could get more than $4019$ diagonals is if there existed two disjoint intersecting sets of size $2010$. We will show that this is not possible. Suppose, for contradiction, that $A, B$ are intersecting sets of size $2010$ which are disjoint. By the proof of the lemma, we know that each of $A, B$ contains exactly one diagonal of every value. Let $XY \in A, ZT \in B$ be of value $0.$ WLOG let $X, Y, Z, T$ lie on the circumcircle of the polygon in clockwise order. Let $d_1, d_2$ initially be $XY, ZT$ respectively at time $t = 0.$ At time $t = i$, we will change $d_1, d_2$ to the unique diagonals in $A, B$ respectively with value $i.$ Notice that since $A, B$ are intersecting sets, $d_1, d_2$ just pivot clockwise about one of their endpoints every time. Furthermore, $d_1$ must always have at least one endpoint somewhere in the arc $XY$ not containing $ZT$, and similarly for $d_2.$ These two observations are enough to imply that $d_1, d_2$ must eventually coincide, and this gives us our desired contradiction. In conclusion, $4020$ diagonals is unattainable, and so the answer is $\boxed{4019}.$ $\square$