Let $n(\ge 2)$ be an integer. $2n^2$ contestants participate in a Chinese chess competition, where any two contestant play exactly once. There may be draws. It is known that (1)If A wins B and B wins C, then A wins C. (2)there are at most $\frac{n^3}{16}$ draws. Proof that it is possible to choose $n^2$ contestants and label them $P_{ij}(1\le i,j\le n)$, so that for any $i,j,i',j'\in \{1,2,...,n\}$, if $i<i'$, then $P_{ij}$ wins $P_{i'j'}$.
Problem
Source: 2020ChinaTST test4 day2 P3
Tags: graph theory, Partial Orders, combinatorics
20.04.2021 20:17
Question on translation. So $j$ is not important right? Maybe we need to require the condition to be "if $i<i^{\prime}$ and $j<j^{\prime}$".
21.04.2021 10:27
J is important because there will be n-1 partecipants with i=1, n-2 partecipants with i=2 and so on. In this way yo will have n^2 partecipants all labeled differently
26.04.2021 13:29
Because of (1), we can label players in a order $A_{1},A_{2},....,A_{2n^2}$ such that for any $1\le i<j\le 2n^2$,$A_{i}$ wins $A_{j}$ or they equalize. If $A_{i}$ and $A_{j}$ equalize, then for any $i\le k\le j$, the matches between $A_{k}$, $A_{i}$ and $A_{k}$, $A_{j}$ are atleast one draws. This means if $A_{i}$ and $A_{j}$ equalize, there will be atleast $j-i$ draws contain $A_{i}$ or $A_{j}$. $d$ is an undetermined integer. At each time we "delete" a pair of players $A_{i}$ and $A_{j}$($i<j$), if they equalize and $j-i\ge d$. Then label the other players again. We delete at least $d$ draws each time, but there are at most $\frac{n^3}{16}$ draws. So, we have deleted at most $\frac{n^3}{8d}$ players when there is no such pair of players. Which means atleast $n^2-\frac{n^3}{8d}$ players "survived". At this time, we let $A_{1},A_{2},....,A_{n}$ be $P_{1j}(1\le j\le n)$, let $A_{n+d},A_{n+d+1},....,A_{2n+d-1}$ be $P_{2j}(1\le j\le n)$ ,......., let $A_{n^2+(n-1)(d-2)},A_{n^2+(n-1)(d-2)+1},....,A_{n^2+(n-1)(d-1)}$ be $P_{nj}(1\le j\le n)$. Easy to testify those $P_{ij}(1\le i<j\le n)$ satisfies the request. So, all we need is $n^2+(n-1)(d-1)\le n^2-\frac{n^3}{8d} \Leftarrow d+\frac{n^2}{8d}\le n$. Just chose $d=\frac{n}{2}$ is OK! It seems that 16 can be improved to 8, so I don't sure am I right or not.
14.05.2021 03:34
bumjoooon wrote: Question on translation. So $j$ is not important right? Maybe we need to require the condition to be "if $i<i^{\prime}$ and $j<j^{\prime}$". @bumjoooon @Caio51-2 I'm so sorry that there was a typo in the question. The required $n^2$ contestants should be labeled $P_{ij}(1\le i ,j \le n)$, not $P_{ij}(1\le i < j \le n)$. (although this can be seen by the number $n^2$) I think $j$ just means we are required to find $n^2$ contestants and divide them into $n$ groups, each group having $n$ person to satisfy the winning condition.