Let's consider the complete graph whose vertices are the persons. Color red the edge $ A - B$ if $ A$ and $ B$ are knowing each other, and blue otherwise. Thus, we are looking for the maximum number of vertices of such a graph knowing that there is no red $ K_n$ and no blue $ K_3$. This maximum is $ R(n,3) - 1$, where $ R(.,.)$ is the Ramsey number. Therefore, the problem asks to prove that $ R(n,3) \leq \frac {n(n + 1)}2$. This upper bound follows easily from the well-known inequality $ R(a,b) \leq R(a - 1,b) + R(a,b - 1)$, which gives $ R(a,b) \leq \binom {a + b - 2}{b - 1}.$ Pierre.

Written in simple words. We will use induction on n and thus assume it is true for n-1. Choose a person. he will be friends with people in A and not with people in B. it is clear that then every two persons in B are friends. Thus |B| is at most n-1. Now because our person knows every one in A by the induction hypothesis A consists of at most $ \frac{(n-2)(n+1)}{2}$ people. thus we get a maximum of $ \frac{(n-2)(n+1)}{2}+1+(n-1)=\frac{(n-1)(n+2)}{2}$ for our set.

pohoatza wrote: Let $ n$ be a nonzero positive integer. A set of persons is called a $ n$-balanced set if in any subset of $ 3$ persons there exists at least two which know each other and in each subset of $ n$ persons there are two which don't know each other. Prove that a $ n$-balanced set has at most $ (n - 1)(n + 2)/2$ persons. Alternatively, work with the complementary graph $G^{*}$; which is triangle-free and has no independent set of size $n$. We prove that $|V(G)|<\binom{n+1}{2}$ by induction on $n \ge 2$; base case being obvious. The point is to delete no more than $n$ vertices from $G^{*}$ to reduce to the case where the induced sub-graph no longer has independent sets of size $n-1$ and apply induction hypothesis. Pick the vertex $v$ with maximal degree. Let $\{u_1, \dots, u_k\}$ be the neighbours of $v$. Observe that $N(v)$ must be an independent set else $G^{*}$ has a triangle. Thus, $k \le n-1$. Now delete $v$ along with $u_1, \dots, u_k$ from $G^{*}$ and suppose we still have an $(n-1)$ independent set $S$ in the induced subgraph. Then $v$ has no neighbours in $S$ (since all of them were deleted prior to constructing $S$). However, appending $v$ to $S$ yields an $n$-independent set in the original graph; a contradiction! Hence the induction hypothesis works!

Ramsey kills it...... Another problem is posted in Bosnia tst Ramsey kills it $R(r,s)\le R(r–1,s)+R(r,s–1)$ $R(r,s)\leq \binom {r+s–2}{r–1}$ Here $(r, s) =(n, 3)$ $R(r,s)\leq \binom {n+1}{n–1}$ $R(n,3)\le \frac{n(n+1)}{2}$ and thus...

@Paragdey12 This is highly of topic, but seeing your recent posts in HSO forum (the above post, #1 , #2 , #3 for example), I have no idea how what you're writing is either helpful or provides a full solution (or atleast sketch of a solution) - it seems (for example check #3) that you're simply writing random theorems related to the problem. Please don't spam threads in HSO with useless posts like this.

Note that $\frac{(k-1)(k+2)}{2}+1=\binom{k+1}{2}$. Thus, the contrapositive of the problem is asking us to show that a triangle free graph with at least $\binom{k+1}{2}$ has an independent size of at least $k$. This follows directly from Ramsey's theorem applied to $R(3,k)$, but we'll outline a proof here for completeness. We proceed by induction on $k$ with the base case of $k=1$ being obvious. Now suppose the problem is true for $k-1$, and suppose we have a graph $G$ on $\binom{k+1}{2}$ vertices that is triangle free. Let $v$ be any vertex. If the degree is at least $k$, then by the triangle free, the neighbors of $v$ form an independent set of size $k$. So WLOG, suppose that the degree of $v$ is at most $k-1$. Thus, there are at least $\binom{k+1}{2}-1-(k-1)=\binom{k}{2}$ vertices not connected to $v$, and by the inductive hypothesis, they have a $(k-1)$-independent set. Adding in $v$ solves the problem.

induction also work for this problem!

Create a graph in which two persons are connected if they don't know each other and replace $n$ with $k$. Induct on $k$. The result is trivial at $k=1$. For the induction step, suppose otherwise. By induction hypothesis, there exists an independent set $S$ of size $k-1$. As $\frac{(k-1)(k+2)}{2}-(k-1)=\binom{k}{2}$, there are more than $\binom{k}{2}$ non-elements of $S$. Let the set of non-elements of $S$ be $T$ and for each $v\in S$, let $T_v$ be the set of neighbors of $v$ in $T$. Observe that each element of $T$ must be in some $T_v$, as otherwise the result is clearly false. Consider a particular $T_v$. Observe that $T_v$ is an independent set because there are no triangles. If there are two or more vertices $u$ in $T_v$ such that there is no $v\ne x\in S$ with $u\in T_x$, we could replace $v$ with those two vertices to generate an independent set of size $k$, absurd. Thus over all vertices in $T$, at most $k-1$ (the number of $T_v$s) do not have edges to multiple elements of $S$. This implies the average cardinality of a $T_v$ is greater than \[\frac{2\cdot (\binom{k}{2}-(k-1))+(k-1)}{k-1} = k-2+1=k-1,\]so some $T_v$ is an independent set with size larger than $k-1$, contradiction.

Phrase this in graph theory terms, replace $n$ with $k$. Assume that $k$ is minimal, so there exists an independent set of size $k-1$, let that set be $S$. For every $v\in\S$, there is at most one vertex $w$ adjacent to $v$ such that no other vertex in the independent set is adjacent to $w$. This is because if two such vertices $w, x$ existed, then get rid of $v$ and add in $w,x$ into the independent set. This means there exists at most $k-1$ vertices that are adjacent to exactly one vertex in the independent set, so every other vertex is adjacent to at least $2$. Observe that the degree of each vertex $v$ is at most $k-1$, because if it was greater, then since the graph is triangle free, we can choose all the vertices adjacent to $v$ in our independent set, for an independent set of size $k$. Let $n$ be the number of vertices. The number of edges adjacent to a vertex in $S$ is at least $k-1 + 2(n-(k-1)-(k-1))$, since there are at most $k-1$ vertices not in the independent set adjacent to exactly one $v\in S$, and the other $n-(k-1)-(k-1)$ vertices not in the independent set are adjacent to at least $2$ $v\in S$. However, there are at most $(k-1)^{2}$ edges with one vertex in $S$, so \[(k-1)^{2} \geq (k-1) + 2(n-2(k-1)) \Rightarrow 2n\leq (k-1)((k-1) - 1 + 4) \Rightarrow n\leq \frac{(k-1)(k+2)}{2}\]This is our desired result.

Rephrase the question as prove that when we have at least $\frac{n(n+1)}{2}$ persons it is impossible to have a $n$-balanced set We shall proceed by induction on $n$ Base case $n=2$ Observe that $n \leq 2$ or else we will immediately form a triangle. At the same time , $\frac{(2-1)(2+2)}{2}=2$ Hence our base case holds Now, suppose that it holds for some $n=y$ , consider the $n=y+1$ case Consider the person with the maximal degree, let it be $Zhong Xina$ If $Zhong Xina$ has $\geq y+1$ neighbours, then we are done since the set of neighbours must form an independent set or else we have a triangle. So, suppose that $Zhong Xina$ has $\leq y$ neighbours This means that we have at least $\frac{(y+1)(y+2)}{2}-y-1=\frac{(y)(y+1)}{2} $ By induction hypothesis, this means that in the $\frac{(y)(y+1)}{2}$ vertices, we have at least one $y$ sized independent set Note that the vertices in this $y$ sized independent set all do not share any edge with $Zhong Xina$ since it is not its neighbour Hence the vertices and $Zhong Xina$ form a $y+1$ sized independent set Hence, by induction, our claim is true

Is ZhongXina a reference to the famous AoPSer JohnCena

We prove the contrapositive statement by induction on $k$: Every triangle-free graph with at least $\binom {k+1}{2}$ vertices has an independent set with size at least $k$. If some vertex has degree at least $k$, we are done. Otherwise, remove some vertex and its neighbors and induct down (we can now add this vertex to the independent set from the IH).

It suffices to show that any graph with at least ${k+1 \choose 2}$ edges that is triangle-free has an independent set of size $k$. We proceed by induction; assume for the sake of contradiction the result is false. Note that every vertex in the graph has degree at most $k-1$, else the set of all neighbors of that vertex would constitute such a set. But now delete that vertex and all its neighbors; we are left with at least ${k \choose 2}$ edges, so the remaining graph has a $k-1$-independent set. On the other hand, including that original vertex creates a desired set, contradiction.

The problem is equivalent to proving $R(n, 3) - 1 \leq \frac{(n - 1)(n + 2)}{2}$. From the well known inequality, we have: $$R(n, 3) \leq \binom{n + 1}{2} \implies R(n, 3) - 1 = \frac{(n + 1)n - 2}{2} = \frac{n^2 + n - 2}{2} = \frac{(n - 1)(n + 2)}{2}$$So, we are done.