There are $24$ robots on the plane. Each robot has a $70^{\circ}$ field of view. What is the maximum number of observing relations?
(Observing is a one-sided relation)
Very nice. This is undoubtedly my new favorite problem.
Let $N$ be the maximum number of observing relations. We will prove $N=468$.
Define a pair of robots to be connected if each one observes the other, and disconnected otherwise. Similarly, define a connection to be the relationship between a pair of connected robots, and define a disconnection to be the relationship between a pair of disconnected robots.
Lemma 1: Among any four robots, there must exist a pair of disconnected robots.
Proof: Consider each of the 4 robots as vertices of a quadrilateral, and draw all the diagonals and edges connecting the robots. (If any 3 robots are collinear then there is obviously a disconnected pair.) By the properties of a quadrilateral, at least one of the vertices must have a angle measure of at least 90. (The quadrilateral may be concave if one of the vertices is inside a triangle.) This means the corresponding robot is unable to observe all of the other robots, and thus there must exist a pair of disconnected robots.
Proof of $N\le 468$:
We will now demonstrate a proof by contradiction. Suppose that there are more than $468$ observations. This implies there can be at most $24\cdot 23-469=83$ pairs of disconnected robots, meaning there are a total of at most $166$ disconnections, and a total of at least $24\cdot 23-166=386$ connections. By pigeonhole, there must be a robot with at least $17$ connections. (This is very important - if there was even one less observation we would not be able to say this.) Let the robot with the maximum (or tied for maximum) number of connections be Robot-A, with $17+a$ connections.
Consider the $17+a$ robots that Robot-A is connected to - call this Set $A$. Since each of the other $7-a$ robots outside Set A must have at least $6-a$ disconnections, our $17+a$ robots in Set A have at most $166-(7-a)(6-a)$ total disconnections, meaning they have at least $(17+a)(16+a)-(166-(7-a)(6-a))=148+2a^2+20a$ total connections.
By pigeonhole, at least one of these $17+a$ robots has $\frac{148+2a^2+20a}{17+a}$ connections among the other robots in Set $A$. Testing values, we find that $\frac{148+2a^2+20a}{17+a}>8$ over all integers $0\le a\le 6$. Thus, there exists a robot in Set $A$ with at least $9$ connections among other robots in Set $A$. Let this robot with the maximum (or tied for maximum) number of connections be Robot-B, with $9+b$ connections. We will continue with a similar method used previously.
Consider the $9+b$ robots that Robot-B is connected to - call this Set $B$. Since each of the other $8+a-b$ robots in Set $A$ but outside Set $B$ must have at least $14-b$ disconnections, our $9+b$ robots in Set $B$ have at most $83-(8+a-b)(14-b)\le 83-(8-b)(14-b)$ total disconnections, meaning they have at least $(9+b)(8+b)-(166-(8-b)(14-b))=18+2b^2-5b$ total connections.
By pigeonhole, at least one of these $9+b$ robots has $\frac{18+2b^2-5b}{9+b}$ connections among the other robots in Set $B$. Testing values, we find that $\frac{18+2b^2-5b}{9+b}>1$ over all integer $0\le b\le 7$. Thus, there exists at least one robot in Set $B$ with at least $2$ connections among other robots in Set $B$. Let this robot be Robot-C, and let it be connected to Robot-D in Set $B$.
Consider Robot-A, Robot-B, Robot-C, and Robot-D. We defined Robot-A to be connected to all elements of Set $A$, which includes Robot-B, Robot-C and Robot-D. We defined Robot-B to be connected to all elements of Set $B$, which includes Robot-C and Robot-D. Finally, we defined Robot-C and Robot-D to be connected, which means every pair of these $4$ robots in connected. However, this is a direct contradiction to Lemma 1, which states that among any four robots, at least one pair must be disconnected. Thus, our original supposition, "Suppose that there are more than $468$ observations," is impossible. We have proven there can be no more than $468$ observations.
Construction for $N=468$:
Place 3 robots to be a the vertices of an equilateral triangle, with side-length say, 1000. Orient the robots such that they face directly at the center of the triangle. Place another three robots on the vertices of a smaller concentric triangle, with side-length 999. Again, make sure the robots face directly at the center of the triangle. Create 6 more smaller concentric triangles, in the same fashion (side lengths 998, 997, 996, etc.). At the end we should have 3 lines of 8 robots each. This construction has the property that any robot in a given row observes all 16 of the robots in the two other rows. In addition, there are $\binom{8}{2}$ observations within each row. This gives a total of $24\cdot16+3\cdot\binom{8}{2}=468$.
Summary:
We have proven that there can be no more than $468$ observations, and we have shown a construction with exactly $468$ observations. Thus, we have proven $N=468$, and we are done. $\blacksquare$
In my proof by contradiction section, if I had used the same method even but 469 to even 468, Set $A$ would have had only $16+a$ robots, Set $B$ would have had only $8+b$ robots, and we would not have been able to prove there existed a connected pair of robots in Set $B$.
Note that this result remains the same over all $d^{\circ}$ fields of view with $60<d<90$. There may be a nice generalization of this problem given $x$ robots and a $d^{\circ}$ field of view.
OlympiadCombo wrote:
Very nice. This is undoubtedly my new favorite problem.
Define a pair of robots to be connected if each one observes the other, and disconnected otherwise. Similarly, define a connection to be the relationship between a pair of connected robots, and define a disconnection to be the relationship between a pair of disconnected robots.
Lemma 1: Among any four robots, there must exist a pair of disconnected robots.
Proof: Consider each of the 4 robots as vertices of a quadrilateral, and draw all the diagonals and edges connecting the robots. (If any 3 robots are collinear then there is obviously a disconnected pair.) By the properties of a quadrilateral, at least one of the vertices must have a angle measure of at least 90. (The quadrilateral may be concave if one of the vertices is inside a triangle.) This means the corresponding robot is unable to observe all of the other robots, and thus there must exist a pair of disconnected robots.
I think you misread the problem( or I did), since the observing goes one way, there can be K4,and it is not actually a precise Turan theory problem since the two-way observation were counted twice
Shanghai wrote:
OlympiadCombo wrote:
Very nice. This is undoubtedly my new favorite problem.
Define a pair of robots to be connected if each one observes the other, and disconnected otherwise. Similarly, define a connection to be the relationship between a pair of connected robots, and define a disconnection to be the relationship between a pair of disconnected robots.
Lemma 1: Among any four robots, there must exist a pair of disconnected robots.
Proof: Consider each of the 4 robots as vertices of a quadrilateral, and draw all the diagonals and edges connecting the robots. (If any 3 robots are collinear then there is obviously a disconnected pair.) By the properties of a quadrilateral, at least one of the vertices must have a angle measure of at least 90. (The quadrilateral may be concave if one of the vertices is inside a triangle.) This means the corresponding robot is unable to observe all of the other robots, and thus there must exist a pair of disconnected robots.
I think you misread the problem( or I did), since the observing goes one way, there can be K4,and it is not actually a precise Turan theory problem since the two-way observation were counted twice
I think you may have misread the problem. When the problem statement says "observing is a one-sided relation," it implies that a two-way observation is counted twice. With this definition of an observation, K4 can not exist as I proved in my lemma above.
First of all we call vertices $i,j$ good if $i$see $j$ and $j$ see $i$ .assume a graph that we draw a edge between 2 vertices if they are good.we can easily check that in our new graph we don't have any $K_4$.assume that our graph has $a$ edges.hence there are $24*23/2 - a$ edges not drawn.call them bad edges.its obvious that every bad edge give us at most one observation and good edges give us exactly 2 observation.hence the total observations is $276-a + 2a = 276 +a$ .and by turan theorem we know that $a <= 24*24*2 /(3*2) = 192 $ (because we don't have $K_4$ hence the total obsevations $<=276+192=468$
We are done
for each 4 robots maximum observing is 5
for 24 robot we have 23*22*21 four then we have 5*23*22*21 observing . but we count each observing for 11*21 times .so maximum observing is (23*22*21*5)/(21*11)=23*5*2=230