In problem 6 from Olimpiada Matemática Española 1996 there are 16 spies. Each spy spies some of their colleagues; moreover, given any two spies A and B, if A spies B then B does not spy A. We also know that if we take any subset of 10 spies it is possible to sort them in a chain where the first spies the second, the second the third, and so on with the tenth which spies the first. The problem asks to show that for each group of 11 spies such a chain can be made.

The solution starts with defining three numbers for each spy $A_i$. $a_i$ is the number of spies spied by $A_i$; $b_i$ is the number of spies who spy $A_i$; $c_i$ is the number of spies never spying not spied by $A_i$. Then it says that $a_i+b_i+c_i = 15$, and that's clear. But is also says that $a_i+c_i \le 8$ and $b_i+c_i\le 8$, "because otherwise it is not possible to order 10 spies as required" (if my understanding of Spanish is correct). I cannot understand the reason of this. Can somebody help me?

  • 1
    $\begingroup$ Supposing by way of contradiction that $a_i+c_i\ge 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies. $\endgroup$ Dec 24, 2018 at 18:46
  • $\begingroup$ silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it? $\endgroup$
    – mau
    Dec 24, 2018 at 20:45
  • $\begingroup$ Well, I do not feel the need to write an answer, do what you like. $\endgroup$ Dec 24, 2018 at 22:11
  • $\begingroup$ It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum. $\endgroup$ Dec 25, 2018 at 11:31


You must log in to answer this question.

Browse other questions tagged .