In a competition, there were $2n+1$ teams. Every team plays exatly once against every other team. Every match finishes with the victory of one of the teams. We call cyclical a 3-subset of team ${ A,B,C }$ if $A$ won against $B$, $B$ won against $C$ , $C$ won against $A$. (a) Find the minimum of cyclical 3-subset (depending on $n$); (b) Find the maximum of cyclical 3-subset (depending on $n$).
Problem
Source: Italian TST , day 1, n°2
Tags: modular arithmetic, combinatorics proposed, combinatorics
01.06.2007 17:22
isn't the minimum 0? let the teams be 1,2,...,2n+1 suppose i beats j if i>j then there is no cycle..
02.06.2007 20:27
Ok Albanian Eagle... You've done the easy part; let's complete the solution!!
02.06.2007 21:47
I think the maximum is equal to $\frac{6n^{3}+n^{2}-n}{6}$
30.07.2007 11:54
I've done it the same way, you've just made some mistakes(for $ n\equiv 2\pmod{3}$ the number isn't even an integer). I think the result is something like:$ \frac{2n^{3}+3n^{2}+n}{6}$, and it is reached when there are exactly $ n$ edges pointing to each vertex.
29.07.2016 05:07
lol, what a shame... http://www.artofproblemsolving.com/community/c6h130647p740398
17.04.2018 05:37
This problem looked awfully familiar to me... turns out it's similar to https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_12B_Problems/Problem_20