School Friends Triad

Consider a student who has the largest number of friends from another school (just 1).

WLOG, this student (whom we call John) is from school A, and he has $b$ friends from B. Every other student has at most $b$ friends in another school.

Since $2018 > 2017$ , John has a friend from school C, which we will call Mike. Since Mike has at most $b$ friends in school A, this means that he has at least $(2018-b )$ friends in school B. Since John has $b$ friends in school B, and $(2018-b) + b = 2018 > 2017$ , hence these friends cannot all be distinct. This implies that there is at least 1 person in school B that is friend with both Mike and John. Thus, they form the group that we're looking for!

Suppose this is not true, i.e. there exists a configuration with no group of 3 that are all friends with each other.

Claim: For any $i < 2017$ , if there exists someone who is friends with $i$ people from just one school, then there exists someone who is friends with $i+1$ people from one school (Note that the schools do not have to be the same.)

Proof: Say $a$ from school $A$ is friends with $i$ people from school $B$ , call this set $B_a$ . Because $i< 2017$ and $a$ has $2018$ friends from other schools, then $a$ also has a friend $c$ from school $C$ . If $c$ is friends with any of the $i$ individuals from school $B$ that $a$ is friends with, these $3$ form a group that contradicts the starting hypothesis. Thus $c$ has at most $2017-i$ friends in $B$ . Because $c$ also has $2018$ friends, $c$ has at least $2017-(2017-i)=i+1$ friends in $A$ , proving our claim.

• Now, starting from an arbitrary person we can iteratively apply the above Claim until we find a person with 2017 friends from a single school. Without loss of generality, say that this person is $a$ from school $A$ with $2017$ friends from $B$ .

• Because $a$ has $2018$ friends, $a$ is also friends with some $c$ from $C$ . By a similar argument, $c$ has at most $2017$ friends from $A$ , and thereby has at least one friend, $b$ in $B$ . But then $a,b,c$ form a group of 3 mutual friends from different schools, a contradiction!

Note: This solution is incomplete.Any suggestions are always welcome. It considers a specific scenario and shows that it can be achieved. It does not explain why it can always be achieved.

First name the schools as $A,B,C$ and each school has $2017$ students.Consider the students as vertex and schools as set.Let's define

$A=(a_1,a_2,....a_{2017})$ $B=(b_!,b_2,......b_{2017})$ $C=(c_1,c_2,......c_{2017})$ .Each vertex in each set has at least $2018$ connection with other two sets..We will deal with minimum number of connections.Here each connection/edge indicates friendship.

Suppose each $a_i$ is connected to every $b_i$ which includes $2017$ friends and a friend from $C$ say $c_1$ .So, every $b_i$ is connected to $a_i$ which counts to $2017$ friends and a friend from $C$ say $c_2$ .So, two condition is satisfied.

Now third condition is that every vertex from $C$ should have at least $2018$ edges.Consider $c_1$ which has $2017$ connections from each $a_i$ .So, it needs at least one friend from set $B$ say $b_j$ .Then it is complete.

Now $a_i,b_j,c_1$ these three are pairwise connected.i.e. they are pairwise friends.

Therefore, we can always find a friend triad.

Not a patch on Andrew's solution but here's my explanation:

We can see all of the friendship connections as links from schools A,B and C. Each school has 2017x2018 connections and because each schools connections to other schools is identical, we can easily show that there are 2017x1009 connections between each school.

Now consider the number of possible links between a student at school A to a student at school B. There are 2017^2 of these. Extend these links from B to C then back to A, but restrict the link back to A to ignore the student who is the first link (this insures no triangular friendship link). There are 2017^3×2016 of these connections.

But with 2017x1009 connections between each school we have 2017^3×1009^3 potential routes from A to B to C and back to A. This figure is much greater than the number of routes which exclude any 3-way friendship.

So there will exist at least one such group.

Let $A, B$ and $C$ be the names of the schools.

Let $a∈A$ be a student from school $A$ .

$a$ has at least

$2018 > 2017 = \text{number of students of } B \text{ and } C$

friends, so all students from $B$ OR all students from $C$ are friends with $a$ .

Without loss of generality, let's assume all students of $B$ (that is, the $2017$ students) are friends with $a$ .

On top of that, $a$ has at least one remaining friend $c ∈ C$ from $C$ .

And as $c$ has $2018 > \text{number of students of } B \text{ and } C$ friends : $c$ has, likewise, at least one friend $b∈B$ from $B$ .

Finally, since all students from $B$ are friends with $a$ ,

$a, b \text{ and } c \text{ are friends with one another}$

Reduce the issue from 2017 and 2018 to 1 and 3 and it becomes immediately obvious what the truth is and why.

it is possible because there are many people and great amount of friends