Periwinkle said:
I.
My reasoning above, which I wrote yesterday before and hastened, is based on that
- for each ##X## person, we count the number of pairs of individuals for which this ##X## is involved
- for each pair of ##X, Y## persons, count the number of other persons involved in this pair.
That is,
the number of existing involved relationships is counted in two ways.
(Why is it called "involved"? Because if I know both of the two people at the same time, or I don't know any of them, I will not say to either one that is unfavorable to the other. While in the other case, it can happen, and so I am
involved in their relationship.)
View attachment 2451261. For each ##A_i## person, we count the number of ##(X, Y)## pairs of individuals for which this ##A_i## is involved and not involved
Mark participants in the conference with ##A_1, A_2, \dots A_n##. Person ##A_i## knows ##k_i## other persons, does not knows ##l_i##. Then it is not involved in ## \binom {k_i} 2 ## pairs because
knows both of them, in case of ##\binom {l_i} 2 ## it is not involved, because
does not know any of them. Involved in ##k_i \cdot l_i## pairs.
There are a total of ##\binom n 2 ## pairs of persons, for each pair, there are ##n-2## individuals who are either involved or not.
$$\binom n 2 (n-2) = \sum_{i=1}^n \left[\binom {k_i} 2 + \binom {l_i} k + k_i \cdot l_i \right] $$ $$\binom n 2 (n-2) = \sum_{i=1}^n \left[ \frac {k_i(k_i-1)} 2 + \frac {l_i(l_i-1)} 2 + k_i \cdot l_i \right]$$ $$\frac {n(n-1)} 2 (n-2) = \sum_{i=1}^n \frac {{k_i}^2-k_i + {l_i}^2-l_i + 2k_i\cdot l_i} 2 $$ $$\frac {n(n-1)(n-2)} 2 = \sum_{i=1}^n \frac {{k_i}^2+{l_i}^2-(n-1)+ 2k_i\cdot l_i} 2 $$ $$\frac {n(n-1)(n-2)} 2 = -\frac {n(n-1)} 2 + \sum_{i=1}^n \frac {{k_i}^2+{l_i}^2+ 2k_i\cdot l_i} 2 $$ But $$\frac {k_i+l_i} 2 \geq \sqrt{k_il_i}$$ so $$k_i^2+l_i^2\geq2k_il_i$$ Consequently
$$\frac {n(n-1)(n-2)} 2 +\frac {n(n-1)} 2 \geq \sum_{i=1}^n {2k_i\cdot l_i} $$ $$\frac {n(n-1)(n-1)} 2 \geq \sum_{i=1}^n {2k_i\cdot l_i} $$ $$\frac {n(n-1)} 2 \frac {n-1} 2 \geq \sum_{i=1}^n {k_i\cdot l_i} $$
2. For each pair of ##(X, Y)## persons, count the number of other persons ##A_i## involved in this pair
For all ##n## natural numbers, $$ n- \left(\left[\frac n 2\right]-1 \right) \gt \frac {n-1} 2$$
Suppose the theorem is not true, so for each person pair, the number of people not involved in the pair is less than ##\left[ \frac n 2 \right]-1##. As a result of the above inequality, therefore, for each pair of persons, the number of persons involved is more than ##\frac {n-1} 2##. There are ##\binom n 2## pairs of people, so the total number of involved relationships is over $$\frac {n(n-1)} 2 \cdot \frac{n-1} 2$$ So
we got a contradiction because the number of involved relationships should not be more than ##\frac {n(n-1)} 2 \cdot \frac{n-1} 2## and at the same time less than or equal to ##\frac {n(n-1)} 2 \cdot \frac{n-1} 2##.
II.
To prove the inequality of the floor-integer value function
If ##n=2k##, then $$n-\left( \left[ \frac n 2 \right] -1 \right) = 2k-k+1 = k+1 > k-\frac 1 2 = \frac {n-1} 2$$
If ##n=2k+1##, then $$n-\left(\left[ \frac n 2 \right]-1 \right) = 2k+1-k+1 = k+2 > k = \frac {n-1} 2$$
I think this is basically correct, although it is difficult to read. This is partly due to the question itself and partly to the definition of "involved". I will present my version of the proof, which should be similar to the above, but what I think, easier to grasp.
Statement: (as I understood it)
There is a pair ##(r,s)## among the ##n## people ##S:=\{\,1,2,\ldots,n\,\}## of a conference, such that the number of persons which either know both of them or neither of them is at least ##\displaystyle{ \lfloor \dfrac{n-1}{2} \rfloor }\,.##
Preliminaries:
I will omit the notation ##A_1,\ldots,A_n## and call the persons by numbers for short.
The symbol ##\dot{\vee}## will denote either or (XOR) and ##|\, . \,|## will denote the number of elements in a set. Furthermore we are given a symmetric relation ##R\subseteq S\times S## which means ##(r,s)\in R ## iff ##r## knows ##s##. The number of relevant pairs due to symmetry is ##\binom{n}{2}##. Therefore if we write ##S^2## we actually mean ##S^2/\sim ##, i.e. all pairs modulo symmetry. We do not count any pairs ##(x,x)\in R\,.##
We define the complement of the set we are interested in as $$I(x) :=\{\,(r,s)\in S^2\,|\,(x,r)\in R \,\dot{\vee}\, (x,s)\in R\,\}\; , \;l(x):=|I(x)|$$
i.e. the number of pairs relative to a person ##x##, where ##x## knows exactly one of them. We will further need the set of all triplets
$$T:=\{\,(x;r,s)\,|\,x\in S\, , \,(r,s)\in I(x)\,\}$$
of persons and associated pairs, such that the person knows exactly one of the pair.
Proof: For a person ##x## who knows exactly ##k(x)## persons, we have ##l(x)=k(x)\cdot (n-1-k(x))##. This function takes its theoretical maximum at ##k(x)=\dfrac{n-1}{2}## so that we have
$$
\max_{x\in S} l(x) \leq \dfrac{n-1}{2} \cdot \left( n-1-\dfrac{n-1}{2} \right) = \left( \dfrac{n-1}{2} \right)^2
$$
hence ##|T| \leq n\cdot \left( \dfrac{n-1}{2} \right)^2 = \dfrac{n-1}{2} \displaystyle{\binom{n}{2}}\,.##
Let us assume that for all pairs ##(r,s)\in S^2## we had ##|\{\,x\,|\,(x;r,s)\in T\,\}|> \dfrac{n-1}{2}\,.## Then the disjoint union
$$
\dot{\bigcup}_{(r,s)\in S^2} \{\,(x;r,s) \in T\,\}
$$
has more than ##\displaystyle{\binom{n}{2}}\cdot \dfrac{n-1}{2}## many elements. However, as it is a subset of ##T## which has less elements, our assumption was wrong. This means there is a pair ##(r,s)\in S^2## such that ##|\{\,x\in S\,|\,(x;r,s)\in T\,\}| \leq \dfrac{n-1}{2}##. For this pair ##(r,s)## we thus have
$$
|\{\,x\,|\,(x;r,s) \notin T\,\}| > (n-1) - \dfrac{n-1}{2} = \dfrac{n-1}{2} \geq \displaystyle{ \lfloor \dfrac{n-1}{2} \rfloor }
$$
which is what we wanted to prove.
