Around a circular table sit $12$ people, and on the table there are $28$ vases. Two people can see each other, if and only if there is no vase lined with them. Prove that there are at least two people who can be seen.
Problem
Source:
Tags: combinatorics proposed, combinatorics
27.09.2010 14:17
I understand that the problem statement should be understood as "Prove that there are at least two people that can see each other". With the interpretation that I give to the problem statement, number the people around the table modulus $12$, so that person $i$ sits between people $i-1$ and $i+1$ for all $i$, and define a "line of sight" (LOS for short) as a line that passes through the positions of two people. Consider the LOS between $i$ and $i+k$ (we will denote such LOS's as $k$-LOS, ie LOS that join two people that are $k$ seats appart), clearly any other LOS that intersects this given LOS must pass through the position of one $i+j$ with $j\in\{1,2,\dots,k-1\}$, or each $k$-LOS may intersect another $k-1$ LOS's. Note also that the number of $k$-LOS's is $12$ for all $k\leq5$, and $6$ for $k=6$, for a total of $66=\binom{12}{2}$ LOS's. Assume henceforth that the problem statement is false, hence all $66$ LOS's must be covered. Denote a vase as a $k$-vase if it intersects $k$ LOS's. Therefore, it may intersect $j$-LOS's for $j\geq k$, but not for $j\leq k$; by the previous argument, let $j$ be the smallest difference such that the $k$-vase intercepts the line between $i$ and $i+j$; by convexity of the arrangement of people around the table, if it intercepts any LOS, it must be either the LOS between $i$ and $i+j$, or a loss joining $i+j'$ and some other person for $j'\in\{1,2,\dots,j-1\}$, and at most one such LOS for each one of these people, since otherwise three people would be collinear, absurd. Denote by $u_k$ the number of $k$-vases, thus $u_6\leq1$ iff all lines joining $i$ and $i+6$ are coincident and the $6$-vase is at their intersection. Note also that the number of LOS's covered is $u_1+2u_2+3u_3+4u_4+5u_5+6u_6=66$, while the number of vases is $u_1+u_2+u_3+u_4+u_5+u_6=28$. It follows that $u_2+2u_3+3u_4+4u_5+5u_6=38$, or $u_3+2u_4+3u_5+4u_6=10+u_1$. Note also that the number of LOS's covered by all $j$-vases, $j\geq k$, must be at most equal to the number of $j$-LOS's, $j\geq k$, ie $6u_6\leq6$, $5u_5+6u_6\leq18$, $4u_4+5u_5+6u_6\leq30$, and $3u_3+4u_4+5u_5+6u_6\leq42$. Now, $30+3u_1=3u_3+6u_4+9u_5+12u_6\leq2u_4+4u_5+6u_6+42$, or $6u_1-24\leq4u_4+8u_5+12u_6\leq3u_5+6u_6+30$, ie $10u_1-90\leq5u_5+10u_6\leq4u_6+18\leq22$, and $u_1\leq\frac{112}{10}<12$. We have reached a contradiction, because each one of the $12$ $1$-LOS's must be covered by a $1$ vase each by convexity, hence the assumption is false, and the problem statement is true.
27.09.2010 14:39
I forgot to copy down one little detail that is however important: when we assign value $k$ to a $k$-vase, we do it as follows: we start with the vases that cover $6$ LOS's, there may be at most one, then we consider the vases that cover $5$ LOS's that have NOT YET been covered, pick one and call it a $5$-vase, proceed with the rest of the possible $5$-vases such that the LOS's they covered have not been covered yet by any $6$-vase or any other $5$-vase, and so on. This way, we guarantee equality in both $u_1+u_2+u_3+u_4+u_5+u_6=28$ and $u_1+2u_2+3u_3+4u_4+5u_5+6u_6=66$...
27.09.2010 15:02
I solved it in a similar way, Consider the vases $v_1,v_2,...,v_{28}$, so $v_k$ is the set of pairs on the circle whose line of sight is covered by vase $v_k$. Notice that $|v_k| \le \min\{j | (i,i+j) \in v_k\}$, because if $(i,i+j)$ breaks the the circle into two halves each person on the smaller half of the circle can only look at the vase in $1$ way (which may or may not be a line of sight). Now in order to block all lines of sight there must exist some vases that cover the line of sight $(i,i+j)$ for all $j=1,2,...,6$. There are $12$ lines $(i,i+j)$ for $j=1,2,...,5$ and $6$ lines of sight $(i,i+6)$. So we need at least $12\cdot \left (1 + \frac{1}{2}+ \frac{1}{3}+ \frac{1}{4}+ \frac{1}{5}\right)+ 6\cdot \frac{1}{6} > 28$ vases. So we are done.
08.10.2010 16:29
Here is my solution, I define the k-lines like daniel73, and prove that if $k$ lines concur, then each of them is at least a k-line. Now let's pick a vase arrangement that covers all lines. If a vase in on the intersection of $k$ lines, assign each line $1/k$ of the vase. Then, every k-line has at least $1/k$ of a vase, and since for $k=1,2,3,4,5$ there are twelve k-lines, and there are six 6-lines,we have the minimum number of vases is $12(1+1/2+1/3+1/4+1/5)+6(1/6)=28.4$ so we need at least $29$ vases to cover all lines.
08.10.2010 18:12
See http://kam.mff.cuni.cz/~matousek/gblock.pdf for a very nice presentation. Other interesting articles can be obtained by googleing "minimum number of points to block visibility".
31.03.2020 23:34
Is this result sharp? The generic case (no three segments between people are concurrent) needs at least 12 + 54/2 = 39 vases. I played around with a dodecagon and needed 32 vases to cover all lines of sights. Can anyone do better in the dodecagon? Is there a configuration of people for which 29 vases are enough to block all sights?