$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
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.
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
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.
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
14.03.2017 01:15
It's given that the total number of conversations in any quadruple is even, English and Chinese together.
14.03.2017 01:20
Perhaps I misread, but do any conversations even need to be in English?
14.03.2017 01:24
Could you rephrase your question?
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!
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.
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.
13.06.2020 06:17
It's way too easy for a tst2, unless I fakesolved.
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
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.
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.