$2017$ engineers attend a conference. Any two engineers if they converse, converse with each other in either Chinese or English. No two engineers converse with each other more than once. It is known that within any four engineers, there was an even number of conversations and furthermore within this even number of conversations: i) At least one conversation is in Chinese. ii) Either no conversations are in English or the number of English conversations is at least that of Chinese conversations. Show that there exists $673$ engineers such that any two of them conversed with each other in Chinese.
Problem
Source: China TSTST 2017 Test 2 Day 1 Q2
Tags: graph theory, combinatorics
math90
13.03.2017 21:07
Graph theory formulation: fattypiggy123 wrote: Let $G$ be a graph with $2017$ vertices. Any two vertices in $G$, if they are adjacent, are connected to each other in either red or blue. It is known that within any four vertices in $G$, there is an even number of edges and furthermore within this even number of edges: i) At least one edge is red. ii) Either no edges are blue or the number of blue edges is at least that of red edges. Show that there exists $673$ vertices in $G$ such that any two of them are connected to each other in red.
By Turán's theorem, the number of red edges in $G$ is at least
$\binom{2017}{2}-\left(1-\frac{1}{3}\right)\frac{2017^2}{2}=\frac{2017^2}{6}-\frac{2017}{2}=\frac{2017\cdot 2014}{6}$
So the sum of red degrees in $G$ is at least $\frac{2017\cdot 2014}{3}$.
Hence by PHP there exists a vertex $v$ whose red degree is at least
$\lceil\frac{1}{2017}\cdot\frac{2017\cdot 2014}{3}\rceil=\lceil\frac{2014}{3}\rceil=672$
Let $v_1,\dots,v_{672}$ be neighbors of $v$ by a red edge. Consider three indices $i<j<k\leq 672$, such that among $\{v_i,v_j,v_k\}$ there is at least one red edge. By conditions (i) and (ii) on $\{v,v_i,v_j,v_k\}$, there are either one red edge or three red edges with the vertices $v_i,v_j,v_k$. Also by condition (i), there are at most three connected components in the induced subgraph $H=\{v_1,\dots,v_{672}\}$, with ignoring the blue edges. Furthermore, the relation 'adjacent by a red edge' is transitive for any three distinct vertices in $H$. Hence $H$ is a disjoint union of three red cliques $A$, $B$, $C$ (possibly empty). If only $A$ is nonempty, then $\{v\}\cup A$ is a red clique of cardinality $673$, as desired. Similarly if only $B$ or only $C$ is empty. So assume that at least two sets among $A,B,C$ are nonempty. WLOG $|A|\geq|B|\geq|C|$, so $|A|\geq 3$ and $|B|\geq 1$. Consider four vertices $a,b,c,d$, where $a,b,c\in A$ and $d\in B$. Consider the set $\{a,b,c,d\}$. Since $ad,bd,cd$ are not red edges, then by condition (ii) they must be all blue edges. Hence among the edges with vertices in $\{v,a,b,d\}$, two edges are blue and four edges are red, contradicting condition (ii).
laegolas
13.03.2017 21:46
Math90, I agree that there are at most $\left(1-\frac{1}{3}\right)\frac{2017^2}{2}$ blue edges, but how do we know that there is a red edge between every pair where there isn't a blue edge? Edit: i see now
math90
13.03.2017 21:55
I used a stronger fact, that there are at most $\left(1-\frac{1}{3}\right)\frac{2017^2}{2}$ edges which are not red.
rafayaashary1
14.03.2017 00:58
Why does language matter in this problem? In particular, doesn't it suffice to solve the simpler Quote: Show that in a simple graph $G$ on $2017$ vertices such that there must be an edge amongst any four of them, and furthermore an even number of such edges, there must be a $K_{673}$ as a subgraph. If a graph satisfies the above, then by making every edge Chinese, it satisfies the original problem. Also, in order for a graph to satisfy the problem, it must (by definition) satisfy the above, so the two sets of graphs are equivalent
math90
14.03.2017 01:15
It's given that the total number of conversations in any quadruple is even, English and Chinese together.
rafayaashary1
14.03.2017 01:20
Perhaps I misread, but do any conversations even need to be in English?
math90
14.03.2017 01:24
Could you rephrase your question?
rafayaashary1
14.03.2017 01:26
My question is does the presence of English affect the solution? In particular, given a valid graph of conversations, can't we just make every conversation Chinese (if it isn't already), and then solve the easier problem? Edit: I spent so much time checking that no condition was violated...that I forgot to read carefully the desired claim!
math90
14.03.2017 01:34
Just turning every English into Chinese will not work, since you add additional Chinese conversations. Maybe you can do something more clever.
Vlados021
19.05.2019 23:02
That's interesting that after manipulating with some cases it follows that the first two statements about quadruples (an even number of edges and at least one edge in each quadruple) imply that $G$ is complete, and after that there is no use of them.
CANBANKAN
13.06.2020 06:17
It's way too easy for a tst2, unless I fakesolved.
Rephrase in graph theory: connect a red edge between two vertices if their respective engineers talked in Chinese, a blue edge if they talked in English, and no edge if they didn't talk.
Consider the graph with blue edges and no edges. Since there is no $K_4$, by Turan, the number of such edges is at most $\frac{2}{3} \cdot \frac{2017^2}{2}$. Hence the number of red edges is at least $\binom{2017}{2}-\frac{2017^2}{3}=2017(1008-\frac{2017}{3})$. Hence there exist a vertex with at least $\lceil 2(1008-\frac{2017}{3}) \rceil = 672$. Call that vertex $r$ and 672 of its red neighbours $v_1,\cdots,v_{672}$
Suppose $v_iv_j$ is blue. Consider $r,v_i,v_j,v_k,v_l$. By ii), $v_jv_k$, $v_iv_k$, $v_iv_l$, $v_jv_l$ are blue. Now consider $r,v_k,v_j,v_l$ to get $v_kv_l$ is blue, so $v_i,v_j,v_k,v_l$ forms a clique, contradicting (i).
(Remark: It can be proven with ii) $v_1,\cdots,v_{672}$ is a clique)
Hence there are no blue edges between $v_iv_j, 1\le i,j\le 672$.
If there there exist (wlog) $v_1v_2v_3$ not a red clique, then by iii), they have one edge, wlog $v_1v_2$. Consider $v_1v_2v_3v_j$. I claim $v_1v_2,v_3v_j$ are the only edges among these vertices. If $v_1v_j$ is a red edge, then $v_2v_j$ must be a red edge. There are now 3 edges in $v_1v_2v_3v_j$ so there must exist another, so $v_3v_j$ must be an edge. However, $r,v_2,v_3,v_j$ have 5 edges between them, false. Hence $\forall 4\le i\le 672$, $v_i$ is adjacent to $v_3$ with a red edge and have no edge between $v_1v_i$ or $v_2v_i$. Consider $v_1v_2v_iv_j$ tells us $v_iv_j$ is an edge $\forall 4\le i<j\le 672$, but looking at $v_1v_3v_iv_j$, we have 3 edges, contradiction.
Aryan-23
11.11.2020 12:36
math90 wrote: Graph theory formulation: fattypiggy123 wrote: Let $G$ be a graph with $2017$ vertices. Any two vertices in $G$, if they are adjacent, are connected to each other in either red or blue. It is known that within any four vertices in $G$, there is an even number of edges and furthermore within this even number of edges: i) At least one edge is red. ii) Either no edges are blue or the number of blue edges is at least that of red edges. Show that there exists $673$ vertices in $G$ such that any two of them are connected to each other in red. Feels too convenient, hope that I'm not high
First note that there is no blue $K_4$, so by Turán, there are atmost $\tfrac {2017^2}2 \left(1-\tfrac 13 \right)$ blue edges. Hence there are atleast $ \tbinom {2017}2 - \tfrac {2017^2}{3} = \tfrac {2017\cdot 1007}3$ red edges. Hence there is a vertex with red degree atleast $\left \lceil \tfrac{2017\cdot 1007\cdot 2}{2017}\right \rceil=672$ red neighbours. Call that vertex $1$ and let its neighbours be $2,3\dots,673$. We will show that $1,2,3\dots,673$ is the desired red clique. Looking at $(1,i,j,k)$, for $1<i<j<k\leq 673$, we realize that if there is one blue edge then there must be a blue triangle. We prove this is impossible.
Look at $(1234)$. WLOG, $234$ is a blue triangle.
Look at $(1345)$, there are $3$ red and $1$ blue edges already, so both $54,53$ must be necessarily blue.
Look at $(2345)$. There are $5$ blue edges so $25$ must be red.
Look at $(1235)$. We have $4$ red edges ($12,25,13,15$) and $2$ blue edges ($23,35$), so we have a contradiction. $\square$
So now blue edge exists. Now assume FTSOC, that $23$ is not a red edge. We claim this is impossible.
Since $23$ is not edge, by looking at $(1234)$, we conclude that there must be either $24$ or $34$ is a red edge and the other is not. WLOG $34$ is red.
Look at $(2345)$, we can have exactly one or all of $25,53,54$ be red edges.
Suppose $54$ is a edge. Then looking at $(1345)$, $53$ must be a edge. This means $25$ must be a edge. Similarly if $35$ edge is present, the other two must also be present.
Hence we have two cases :
Only $25$ is a edge.
$25,53,54$ are all edges.
Now consider the first case. Looking at $(1235)$ means that $23$ must be a edge, contradiction.
So now we consider the second case. From the previous case, we noticed that if there exists a $i>4$ with $2-i$ and $3-i$ both edge, we are done. But note that by previous logic, $2-x$ is a edge for all $x>4$.
Look at $(2567)$, WLOG $56$ is a edge. Then look at $(2456)$. We must have that $46$ or $45$ is red. Hence by previous reasoning, either $35$ or $36$ is a edge, contradiction.
$\square$
Having exhausted all cases we are done. $\blacksquare$
remarksWorking on this problem felt very similar to ISL 2001 C3. The main task was understanding the conditions and spamming that in some quadruples chosen smartly.
mathleticguyyy
29.07.2022 10:53
If we replace $2017$ with $3n+1$ and $673$ with $n+1$, then the problem statement doesn't hold for $n=2,3$. There's also a straightforward inductive solution assuming $n=4$, but that case can't be feasibly brute-forced.
We proceed with induction. The base case $n=4$ is trivial.
For the inductive step, suppose that among any $3n-2$ vertices, there exists a red $K_n$. Then, consider $X$, any $K_n$ on the $3n+1$ vertices, and choose a triangle $abc$ from it; among the remaining $3n-2$ vertices, there must be another $K_n$, call it $Y$.
Note that for any vertex $d$ in $Y$, either one of $ad,bd,cd$ is connected by a red edge, all three are connected by red edges, or all three are connected by blue edges.
If $ad,bd,cd,ae$ are any edges but $be,ce$ aren't, then among $a,b,d,e$ there are 5 edges. If $ad,be$ are red edges but $ae,ce,bd,cd$ don't exist, then among $c,a,d,e$ there are 3 edges. If $ad,bd,cd$ are red edges but $ae,be,ce$ are blue, then among $a,b,d,e$ there are 4 red edges and 2 blue edges.
Hence, either all three are connected by red edges to everything in $Y$, in which case we are done; one is connected by red edges to everything in $Y$, in which case we are also done; or $a,b,c$ connected by blue edges to everything in $Y$. In the final case, clearly $X,Y$ are disjoint, so we can repeat this process for all triangles in $X$ to get that any vertex in $X$ and any vertex in $Y$ are joined by a blue edge.
If the remaining $n+1$ vertices form a red $K_{n+1}$, we are done. If any of the remaining $n+1$ vertices is adjacent to everything in $X$ or everything in $Y$ by red edges, we are also done. Otherwise, suppose that $g$ outside $X$ and $Y$ is adjacent to $h,i\in X$ in red edges, but not $j\in X$, then among $g,h,i,j$ there are either 5 edges, or 5 red edges and 1 blue edge. Hence, anything outside $X$ and $Y$ is adjacent by red edges to at most 1 vertex in $X$ and at most one in $Y$.
There exists two vertices $k,l$ outside $X$ and $Y$ that aren't connected by a red edge, a vertex $x\in X$ adjacent to neither $k$ nor $l$ by red edge, and a vertex $y\in Y$ adjacent to neither $k$ nor $l$ by red edge. Then, there is no red edge between any two of $k,l,x,y$.
sdninajanlari
11.10.2023 10:34
We will deal with the generalised version by changing 2017 to 3n+1 when n>5. Let's utilize the same formulation as #1. Let C be the largest "red" clique and let that clique include c vertices. It is clear that c is more than or equal to 4 (using the same arguments made in the previous posts). Now, FTSOC, assume that c is less than n+1. Seperate this clique from the other vertices, and consider the remaining graph, say G'. If a vertex v in G' communicated with at least one engineer in C in English, let v be in the set U. Otherwise, let v be in the set W. Consider a w in set V. w has at least c-2 neighbours among the vertices in C (If x,y,z are not neighbours of w, we take x,y,z,w. there are 3 edges between this group, hence contradiction.). So, w has at least 2 neighbours in C. w cannot be adjcent to all vertices in C because C is the largest red clique. Let x,y in C be neighbours of w, and let z not be neighbour of w. take x,y,z,w; there are 5 edges in the group, which results in contradiction! So, W is an empty set. Consider a vertex u in set U. Let u have a blue edge between a vertex x in C. Take two arbitrary vertices (different from x), u, and x. Because of ii) , u has blue edges between every vertice in C. By this, we get that among three vertices in U, there is at least one red edge (take 3 vertices in U and a vertice in C). Also, U is a clique when we ignore the colours of edges (take 2 vertices from C and two from U). (*) Now delete all vertices in C and their incident edges. There are at least 2n+1vertices in U. Let's get the largest red clique in U, call it P. If P has p vertices in it, we again obtain that p is more than or equal to 4 (Perform a kind of double counting, we get that there exists a vertex with at least (2n+1).2n/1.2.3>4 red edges. It is obvious that there exists a red clique with size 4, made up from this vertex and its neighbours.). We assume that p is less than or equal to c, which is less than n+1. Let Q be the set of vertices which has at least one blue edge incident to a vertex in C. Let R be the set of remaining vertices. By the same arguments made above, we see that R is a empty set; all edges between P and R are blue. Hence, two vertices in R must have a red edge between them (this is due to (*)). So, R is a red clique. However, R has at least 3n+1-n-n=n+1 vertices. Contradiction! Thus, there is at least a group of n+1 peopl who communicated with each other in Chinese. Remark: If we change 4 in the problem to m, and 3n+1 to (m-1)n+1, probably there exists a red clique of size n+1.