MathDB
chain with "big vertex" exists in partial order set

Source: 2020ChinaTST test4 day2 P3

April 14, 2021
graph theoryPartial Orderscombinatorics

Problem Statement

Let n(≥2)n(\ge 2) be an integer. 2n22n^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 n316\frac{n^3}{16} draws. Proof that it is possible to choose n2n^2 contestants and label them Pij(1≤i,j≤n)P_{ij}(1\le i,j\le n), so that for any i,j,i′,j′∈{1,2,...,n}i,j,i',j'\in \{1,2,...,n\}, if i<i′i<i', then PijP_{ij} wins Pi′j′P_{i'j'}.
Back to ProblemsView on AoPS