Basically, for what $n$ is there a directed graph, $\vec{G}(V,E)$, of order $n$, such that every edge $(xy)\in E(G)$ is part of a directed triangle $x\to y\to z\to x$ (Note: $(xy)$ is the directed edge $x\to y$). If we have such a graph, $G$, with $|V|=k$ then we can introduce two new vertices $v_{k+1}$ and $v_{k+2}$ and make a new graph $G'$ such that $(x,y)\in E(G')\quad \text{iff}\quad \left\{ \begin{array}{c}((x,y)\in E(G)\ x=v_{k+1} \, , y\in V(G)\ x\in V(G) \, , y=v_{k+2}\ (x,y)=(v_{k+1},v_{k+2})\end{array}\right. $ It is easy to see that $G'$ also satisfies the condition and has $k+2$ vertices. There exists no base case for $n=4$, but there is for $n=3$ and $6$. ($n=3$ is just a directed triangle) so the answer is $n\not = 4$

Is there sth wrong? I think the problem is:A's losers are not all B's losers(Which means:at least one is and at least one not.) Or maybe I'm wrong.

If $A$ defeats $B$ then one of $A$'s losers is $B$, but $B$ is not his/her own loser so "$A$ defeats $B$" $\Rightarrow$ "$A$ is not out performed by $B$." On the other hand, if $A$ defeats $B$ then there must exist one of $A$'s losers, say $C$, such that $B$ defeats $C$. If the players are vertices in the graph then form the directed triangle $A\to B \to C \to A$. So it is enough to assume that the tournament can be represented by $\vec{G}$ where every edge is part of a directed triangle.

That's the tricky part of this problem. Some people miss the case that B is one of A's losers.

ocha wrote: but there is for $n=3$ and $6$. ($n=3$ is just a directed triangle) so the answer is $n\not = 4$ I have a question:Is $n=6$ possible? Plz show it,thanx.

$n=6$ is possible

Attachments:

Great！Thanx!

What if the problem is like this: There are $n$ $(n \ge 3)$ players in a table tennis tournament, in which any two players have a match. Player $A$ is called not out-performed by player $B$, if at least one of player $A$'s losers is not a $B$'s loser which is different from $B$.. Determine, with proof, all possible values of $n$, such that the following case could happen: after finishing all the matches, every player is not out-performed by any other player. It can be shown now n is not smaller than 7.

litongyang wrote: ...is not a $B$'s loser which is different from $B$.... Do you know this to be the correct interpretation? To me, it seems more natural that if $A$ beats $B$ then $B$ should not out-perform $A$. If it is the case, however, the answer is $n\ge 5$. We are looking for directed graphs where each edge is part of a directed quadrilateral. Base: For $n=5$ draw $K_5$ so vertecies form a pentagon with a "star" shape in the center, make the pentagon and star directed cycles both going clockwise. Inductive step: Take the graph $G$ with $k$ vertecies that satisfies the condition. We introduce a new vertex $v_{k+1}$ and create the new graph $G'$ as follows. In a move take $v\in G$; there is some directed quartilateral through $v$, say $v\to w\to x \to y\to v$. 1) If $x$ and $v_{k+1}$ are not already joined by an edge then create edges $(x,v_{k+1}),(v_{k+1},v)\in E(G')$ 2) If $(x,v_{k+1})\in E(G') \Longrightarrow (v_{k+1},v)\in E(G')$ 3) If $(v_{k+1},x)\in E(G') \Longrightarrow (v,v_{k+1}) \in E(G')$ Eventually $v_{k+1}$ is connected to all vertecies and we have a new graph with the desired property. All that is left is to show that $n=3,4$ don't work, but that's trivial because we need at least $4$ vertices to form a directed quadrilateral, say $v_1\to v_2 \to v_3\to v_4 \to v_1$, then we need at least another vertex to form a directed quadrilateral with edge $(v_1,v_3)$ or $(v_3,v_1)$ (whichever way it is directed).

ocha wrote: litongyang wrote: ...is not a $B$'s loser which is different from $B$.... Do you know this to be the correct interpretation? To me, it seems more natural that if $A$ beats $B$ then $B$ should not out-perform $A$. If it is the case, however, the answer is $n\ge 5$. We are looking for directed graphs where each edge is part of a directed quadrilateral. Base: For $n=5$ draw $K_5$ so vertecies form a pentagon with a "star" shape in the center, make the pentagon and star directed cycles both going clockwise. Inductive step: Take the graph $G$ with $k$ vertecies that satisfies the condition. We introduce a new vertex $v_{k+1}$ and create the new graph $G'$ as follows. In a move take $v\in G$; there is some directed quartilateral through $v$, say $v\to w\to x \to y\to v$. 1) If $x$ and $v_{k+1}$ are not already joined by an edge then create edges $(x,v_{k+1}),(v_{k+1},v)\in E(G')$ 2) If $(x,v_{k+1})\in E(G') \Longrightarrow (v_{k+1},v)\in E(G')$ 3) If $(v_{k+1},x)\in E(G') \Longrightarrow (v,v_{k+1}) \in E(G')$ Eventually $v_{k+1}$ is connected to all vertecies and we have a new graph with the desired property. All that is left is to show that $n=3,4$ don't work, but that's trivial because we need at least $4$ vertices to form a directed quadrilateral, say $v_1\to v_2 \to v_3\to v_4 \to v_1$, then we need at least another vertex to form a directed quadrilateral with edge $(v_1,v_3)$ or $(v_3,v_1)$ (whichever way it is directed). Thanks for replying. I'm sorry that I couldn't find the Chinese version because it has just been overed and the problem in the Chinese forum is even translated from here! For my question:My English is very poor and I think I didn't explain my idea clearly. I mean, between two different person A and B, there exists a person C, different from both A and B, such that A beat C and C beat B. I think n is not smaller than 7, because everyone should beat at least 3 people: At least 1 is trivial. Just one is not enough. If exactly two person were beated, assume they are B and C. WLOG B beat C. Then We can't find a person D, different from A and B, such that A beat D and D beat B. So we get n is not smaller than 7.

“如果选手A的手下败将不都是B的手下败将，则称A不亚于B。” I don't know chinese,sorry~ This is given by my friend.

ocha wrote: Do you know this to be the correct interpretation? No, it's not.