chain with "big vertex" exists in partial order set

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

chain with "big vertex" exists in partial order set

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2020ChinaTST test4 day2 P3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathematics2003

16 posts

mathematics2003

#1 h Apr 14, 2021, 12:32 AM • 1 Y

Y by centslordm

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'}$ .

This post has been edited 1 time. Last edited by mathematics2003, May 14, 2021, 12:45 AM
Reason: sorry for my typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

165 posts

#2 h Apr 20, 2021, 5:17 PM • 4 Y

Y by centslordm, Mango247, Mango247, Mango247

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}$ ".

This post has been edited 2 times. Last edited by bumjoooon, Apr 20, 2021, 5:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#3 h Apr 21, 2021, 7:27 AM • 4 Y

Y by centslordm, Mango247, Mango247, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

67 posts

#4 h Apr 26, 2021, 10:29 AM • 2 Y

Y by centslordm, CyclicISLscelesTrapezoid

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.

This post has been edited 1 time. Last edited by Mr.Trick, Apr 26, 2021, 10:33 AM
Reason: Sorry for my terrible English and Latex

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathematics2003

16 posts

mathematics2003

#5 h May 14, 2021, 12:34 AM • 1 Y

Y by centslordm

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. :blush:

:blush:

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a