In a chess tournament there are $n>2$ players. Every two players play against each other exactly once. It is known that exactly $n$ games end as a tie. For any set $S$ of players, including $A$ and $B$, we say that $A$ admires $B$ in that set if i) $A$ does not beat $B$; or ii) there exists a sequence of players $C_1,C_2,\ldots,C_k$ in $S$, such that $A$ does not beat $C_1$, $C_k$ does not beat $B$, and $C_i$ does not beat $C_{i+1}$ for $1\le i\le k-1$. A set of four players is said to be harmonic if each of the four players admires everyone else in the set. Find, in terms of $n$, the largest possible number of harmonic sets.
Problem
Source: Hong Kong National Olympiad 2013 Problem 4
Tags: geometry, geometric transformation, reflection, graph theory, combinatorics proposed, combinatorics
JBL
16.12.2013 18:46
As written the problem asserts that A admires B if ((A does not beat B) or (A does not beat B and some other conditions)), which reduces to (A does not beat B). Also, "$C_i$ does not beat $C_i$"? Perhaps you could check the statement?
TheChainheartMachine
16.12.2013 18:48
What I suspect: $A$ does not beat $C_1$ and $C_i$ does not beat $C_{i+1}$.
WakeUp
16.12.2013 18:55
Sorry, was a bit too quick typing it up. Edited.
devilstare4good
16.12.2013 19:43
i dont know if i have totally grasped the question but if the players be a1,a2,a3......,an and a1 does not beat a2, a2 does not beat a3 and so on and finally an does not beat a1 then everyone admires everyone so the number of harmonic sets is n(n-1)(n-2)(n-3)/24 correct me maybe i am wrong
mavropnevma
22.12.2013 11:46
I have slightly edited the statement, to reflect what I think is its true meaning. The relation of "admiration" from $A$ to $B$ depends on the set containing $A$ and $B$, so for a harmonic set we must have each admiring anybody else within that quatuor.
novawater
11.10.2014 10:26
“i dont know if i have totally grasped the question but if the players be a1,a2,a3......,an and a1 does not beat a2, a2 does not beat a3 and so on and finally an does not beat a1 then everyone admires everyone so the number of harmonic sets is n(n-1)(n-2)(n-3)/24 correct me maybe i am wrong” I don't think it is true because it should be in set S and there are also n ties
JBL
12.10.2014 00:09
Taking Mavropnevma's version and translating it from ridiculous competition language into mathematics, we get the following problem: Call a directed graph strongly connected if there exists a path from each vertex to every other. A tournament is an orientation of the complete graph. Among all tournaments on $n$ vertices, what is the largest possible number of strongly connected 4-vertex subgraphs?
novawater
12.10.2014 04:52
JBL wrote: Taking Mavropnevma's version and translating it from ridiculous competition language into mathematics, we get the following problem: Call a directed graph strongly connected if there exists a path from each vertex to every other. A tournament is an orientation of the complete graph. Among all tournaments on $n$ vertices, what is the largest possible number of strongly connected 4-vertex subgraphs? But how can we understand "tie"?
JBL
12.10.2014 06:29
I'm sorry, you're completely right that I overlooked that part of the question. There should be exactly $n$ bi-directed edges (so, not strictly a tournament in the graph theory sense).
novawater
13.10.2014 09:44
It's a nice question, and I'm glad to see the answer, how can I get it？
Stranger8
13.03.2016 17:01
1999 Chinese MO Q 3 can help solve this problem