The Wonder Island Intelligence Service has $16$ spies in Tartu. Each of them watches on some of his colleagues. It is known that if spy $A$ watches on spy $B$, then $B$ does not watch on $A$. Moreover, any $10$ spies can numbered in such a way that the first spy watches on the second, the second watches on the third and so on until the tenth watches on the first. Prove that any $11$ spies can also be numbered is a similar manner.
Problem
Source: Baltic Way 1994 - 19
Tags: combinatorics unsolved, combinatorics
24.02.2005 18:03
zhaoli wrote: Each of them watches on some of his colleagues. Does it mean that every spy may watch only on one person? If it is true, then I understand nothing!
24.02.2005 19:43
I think, any spy can watch several other spies from what I understand Remike
02.03.2005 04:31
as always we shall work in the context of digraphs.here we have a digraph $D$ on $16$ vertices with the following property: for any $10$ vertices $v_1,v_2,\dots ,v_{10}$ there is a permutation $\pi \in \mathcal{S}_{10}$ such that $v_{\pi(1)}\rightarrow v_{\pi(2)}\rightarrow\dots \rightarrow v_{\pi(9)}\rightarrow v_{\pi(10)}\rightarrow v_{\pi(1)}$ is a directed cycle in the graph $D$. we wish to show the same for any $11$ vertices as well. firstly note that for every vertex $v,7\leq d^+(v)\leq 8;7 \leq d^-(v) \leq 8$.indeed suppose $d^+(v)<7$.then a set of $10$ vertices(including $v$) in $\{v\} \cup \overline{N^+(v)}$ cannot contain any directed cycle on it.Similarly,if $d^+(v)\geq 9$, then $\{v\}\cup N^+(v)$ cannot contain any directed cycle in it.the same hold for $d^-(v)$ as well (arguing in a similar way). now consider any $11$ vertices,$v_1,v_2,\dots,v_{11}$. suppose for some vertex (say $v_1$) all the other vertices are either in $N^+(v_1)$ or in $N^-(v_1)$.(as usual $N^+(v)=\{w|v\rightarrow w\},N^-(v)=\{w|w\rightarrow v\}$).note that there are vertices in both these sets ,i.e. both $N^+(v_1)\neq \emptyset,N^-(v_1)\neq \emptyset$. by assumption there is a directed $10$ cycle on $v_2,v_3,\dots,v_{11}$.then there exist vertices $v_i,v_j$ such that these vertices are adjacent in the directed cycle with $v_i\rightarrow v_j$ and further $v_i\in N^-(v_1),v_j \in N^+(v_1)$. in that case we can get a directed cycle on all $11$ vertices by the following 'detour':$\dots\rightarrow v_i\rightarrow v_1 \rightarrow v_j\rightarrow\dots $, where the rest is along the cycle already determined by $v_2,v_3,\dots v_{11}$.Thus in this case we are through. now we show that in the case of $11$ vertices the above scenario will always occur for atleast one vertex $v$.We have already seen that $7\leq d^+(v)\leq 8;7\leq d^-(v) \leq 8$. since $N^+(v)\cap N^-(v)=\emptyset$, for every vertex $14\leq d^+(v)+d^-(v)\leq 15$, i.e. any vertex is not adjacent to atmost one vertex in the corresponding undirected gaph.so considering the complement of the undirected graph,any 11 vertices must have a matching of size atmost 5 and so there has to be an isolated vertex,i.e. there has to be a vertex $v$ among the $11$ vertices such that all the other vertices belong either to $N^+(v)$ or $N^-(v)$ and by the above we are through.