Given a positive integer $n>1$. Denote $T$ a set that contains all ordered sets $(x;y;z)$ such that $x,y,z$ are all distinct positive integers and $1\leq x,y,z\leq 2n$. Also, a set $A$ containing ordered sets $(u;v)$ is called "connected" with $T$ if for every $(x;y;z)\in T$ then $\{(x;y),(x;z),(y;z)\} \cap A \neq \varnothing$. a) Find the number of elements of set $T$. b) Prove that there exists a set "connected" with $T$ that has exactly $2n(n-1)$ elements. c) Prove that every set "connected" with $T$ has at least $2n(n-1)$ elements.
Problem
Source: VMO 2020, Day 2 - P7
Tags: algebra, Sets
ThE-dArK-lOrD
29.12.2019 05:44
a) $2n(2n-1)(2n-2)$. b) Choose the set $\{ (x;y)\mid 1\leqslant x\neq y\leqslant n \text{ or }n+1\leqslant x\neq y\leqslant 2n\}$. c) It's equivalent to proving that in a directed graph of $2n$ vertices with more than $2n^2$ edges, there exists a cyclic $K_3$ subgraph. (There exists at most one edge connecting two fixed vertices in a fixed direction.) We prove this by induction on $n\geqslant 1$. The case $n=1$ is obvious. Inductive Step: Consider such graph on $2n$ vertices with at least $2n^2+1$ edges. There must exist a pair of vertices $(a,b)$ that have two edges connecting them in both direction. Between $a,b$ and the rest $2n-2$ vertices, there must be at least $(2n^2+1)-2-(2(n-1)^2)=4n-3$ edges. So, there is a vertex $v$ among the $2n-2$ vertices that connects with $a,b$ by at least three edges. We can easily find a cyclic $K_3$ subgraph whose vertices are $v,a,b$.
Eurika
26.04.2020 16:47
ThE-dArK-lOrD wrote: a) $2n(2n-1)(2n-2)$. b) Choose the set $\{ (x;y)\mid 1\leqslant x\neq y\leqslant n \text{ or }n+1\leqslant x\neq y\leqslant 2n\}$. c) It's equivalent to proving that in a directed graph of $2n$ vertices with more than $2n^2$ edges, there exists a cyclic $K_3$ subgraph. (There exists at most one edge connecting two fixed vertices in a fixed direction.) We prove this by induction on $n\geqslant 1$. The case $n=1$ is obvious. Inductive Step: Consider such graph on $2n$ vertices with at least $2n^2+1$ edges. There must exist a pair of vertices $(a,b)$ that have two edges connecting them in both direction. Between $a,b$ and the rest $2n-2$ vertices, there must be at least $(2n^2+1)-2-(2(n-1)^2)=4n-3$ edges. So, there is a vertex $v$ among the $2n-2$ vertices that connects with $a,b$ by at least three edges. We can easily find a cyclic $K_3$ subgraph whose vertices are $v,a,b$. There's a small flaw. It shouldn't be cyclic K3. It's (x,y), (x,z) and (y,z)