Let $n$ be a positive integer. There are $3n$ women's volleyball teams in the tournament, with no more than one match between every two teams (there are no ties in volleyball). We know that there are $3n^2$ games played in this tournament. Proof: There exists a team with at least $\frac{n}{4}$ win and $\frac{n}{4}$ loss
Problem
Source: 2022 CGMO Day1 P2
Tags: combinatorics
MathLover_ZJ
12.08.2022 10:06
It should be P2...
zxypp001
12.08.2022 15:34
Suppose every team wins or loses less than $n/4$ , divide them into two types: 1. x teams of them win/lose no less than $n/4$ (but lose/win less than $n/4$ 2. (3n-x) teams of them win less than $n/4$ and lose less than $n/4$, which means each of them attended less than $n/2$ First delete the matches that the (3n-x) teams in type 2 played. Then delete the matches that the x teams win/lose in typed 1 which are the minority(if team 1 wins more than $n/4$ but loses less than $n/4$ then delete the game team 1 loses) After that, every team either wins every game or loses every game, so they formed a bigraph, which means there are less than $x^2/4$ edges in it. So we have $x^2/4>=3n^2-(3n-x)*n/2-x*n/4$ , but that is equivalent to $(x-3n)(x+2n)<=0$ which is certainly a contradiction!
giglio
10.01.2023 02:57
isnt it supposed to be >= 0 at the end?