Math Challenge - February 2019

[fbs7]

Holy choo-choo, what kind of high school is this? I can very barely follow these arguments, and I supposedly have a college degree!

 

[QuantumP7]

Just a little remark:
$$\exp \left( x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right) = e^x \left( 1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$$
could have had been a bit more elaborated in my opinion. Obviously we have
$$\exp \left( x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)=e^x \cdot \exp \left( - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$$
which raises the question why $\exp \left( - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)\stackrel{?}{=}\left(1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$. No big deal, but a little remark how you approximated here, just words, no equations, would have had improved readability a lot in my opinion.

I'm very curious about this. I've been pouring over this solution because I think it's REALLY neat. So far, I've been able to follow:

$$ \left( 1+ \frac{x}{n} \right)^{n} = e^{\ln \left( 1+ \frac{x}{n} \right)^{n}} = e^{n \ln \left( 1+ \frac{x}{n} \right)}$$

The series expansion for $\ln \left( 1+ \frac{x}{n} \right)$ is $\sum_{k=1}^\infty (-1)^{k+1} \frac{x^{k}}{kn^{k}}$ so that:
$$n \ln \left( 1+ \frac{x}{n} \right) = \sum_{k=1}^\infty (-1)^{k+1} \frac{x^{k}}{kn^{k-1}} = x- \frac{x^{2}}{2n} + \frac{x^{3}}{3n^{2}} - ... = x- \frac{x^{2}}{2n} + O \left( \frac{1}{n^{2}} \right)$$

Then,
$$\left( 1+ \frac{x}{n} \right)^{n} = e^{\ln \left( 1+ \frac{x}{n}\right)^{n}} = e^{n \ln \left( 1+ \frac{x}{n} \right)} = e^{ \left( x- \frac{x^{2}}{2n} + O \left( \frac{1}{n^{2}} \right) \right)} $$

So, in the parenthesis, we get $\left( \left( 1 + \frac{x}{n} \right)^{n} - e^{x} \right) = \left( e^{\left( x- \frac{x^{2}}{2n} + O \left( \frac{1}{n^{2}} \right) \right)} - e^{x} \right) = \left( e^{x} e^{- \frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} \right) - e^{x} = e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right)$

Then the whole expression becomes $\lim_{n \rightarrow \infty} n \left( \left( 1+ \frac{x}{n} \right) ^{n} - e^{x} \right) = \lim_{n \rightarrow \infty} n \left( e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right) \right)$How do we get from $\lim_{n \rightarrow \infty} n \left( e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right) \right)$ to $\lim_{n \rightarrow \infty} e^{x} \left( -\frac{x^{2}}{2} + O \left( \frac{1}{n} \right) \right) = -\frac{x^{2}}{2}e^{x}$?

 

[fresh_42]

I'm very curious about this. I've been pouring over this solution because I think it's REALLY neat. So far, I've been able to follow:

$$ \left( 1+ \frac{x}{n} \right)^{n} = e^{\ln \left( 1+ \frac{x}{n} \right)^{n}} = e^{n \ln \left( 1+ \frac{x}{n} \right)}$$

The series expansion for $\ln \left( 1+ \frac{x}{n} \right)$ is $\sum_{k=1}^\infty (-1)^{k+1} \frac{x^{k}}{kn^{k}}$ so that:
$$n \ln \left( 1+ \frac{x}{n} \right) = \sum_{k=1}^\infty (-1)^{k+1} \frac{x^{k}}{kn^{k-1}} = x- \frac{x^{2}}{2n} + \frac{x^{3}}{3n^{2}} - ... = x- \frac{x^{2}}{2n} + O \left( \frac{1}{n^{2}} \right)$$

Then,
$$\left( 1+ \frac{x}{n} \right)^{n} = e^{\ln \left( 1+ \frac{x}{n}\right)^{n}} = e^{n \ln \left( 1+ \frac{x}{n} \right)} = e^{ \left( x- \frac{x^{2}}{2n} + O \left( \frac{1}{n^{2}} \right) \right)} $$

So, in the parenthesis, we get $\left( \left( 1 + \frac{x}{n} \right)^{n} - e^{x} \right) = \left( e^{\left( x- \frac{x^{2}}{2n} + O \left( \frac{1}{n^{2}} \right) \right)} - e^{x} \right) = \left( e^{x} e^{- \frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} \right) - e^{x} = e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right)$

Then the whole expression becomes $\lim_{n \rightarrow \infty} n \left( \left( 1+ \frac{x}{n} \right) ^{n} - e^{x} \right) = \lim_{n \rightarrow \infty} n \left( e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right) \right)$How do we get from $\lim_{n \rightarrow \infty} n \left( e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right) \right)$ to $\lim_{n \rightarrow \infty} e^{x} \left( -\frac{x^{2}}{2} + O \left( \frac{1}{n} \right) \right) = -\frac{x^{2}}{2}e^{x}$?

Let $f(x)=- \frac{x^{2}}{2n}+ O \left( \frac{1}{n^{2}} \right)$ for the moment. Then by the series expansion of the exponential function we have $\exp(f(x))=1+f(x)+\frac{1}{2}f(x)^2 +\ldots$ and so
\begin{align*}
n \left( e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right) \right)&=e^x \cdot n \cdot \left( e^{f(x)}-1 \right) \\
&= e^x \cdot n \cdot \left( f(x)+ \frac{1}{2}f(x)^2+ \frac{1}{6}f(x)^3+\ldots \right)\\
&= e^x \left\{ n \cdot \left( - \frac{x^2}{2n} + O(n^{-2}) \right) + n \cdot \frac{1}{2} \left( - \frac{x^2}{2n} + O(n^{-2}) \right)^2 + n \cdot g_1(x) \cdot O(n^{-3}) \right\}\\
&= e^x \left\{ -\frac{x^2}{2} +O(n^{-1}) + \frac{1}{2} \cdot \frac{x^4n}{4n^2} + g_2(x) \cdot O(n^{-2}) \right\}\\
&= e^x \left\{ -\frac{x^2}{2} \right\} + g_3(x) \cdot O(n^{-1})\\
& \to e^x \cdot \left( -\frac{x^2}{2} \right)
\end{align*}
with some functions $g_i(x)$ and where we have generously rounded the big-O expressions to $O(n^{-1})\,.$

 

[QuantumP7]

Let $f(x)=- \frac{x^{2}}{2n}+ O \left( \frac{1}{n^{2}} \right)$ for the moment. Then by the series expansion of the exponential function we have $\exp(f(x))=1+f(x)+\frac{1}{2}f(x)^2 +\ldots$ and so
\begin{align*}
n \left( e^{x} \left( e^{\frac{x^{2}}{2n}} e^{ \left( O \left( \frac{1}{n^{2}} \right) \right)} -1 \right) \right)&=e^x \cdot n \cdot \left( e^{f(x)}-1 \right) \\
&= e^x \cdot n \cdot \left( f(x)+ \frac{1}{2}f(x)^2+ \frac{1}{6}f(x)^3+\ldots \right)\\
&= e^x \left\{ n \cdot \left( - \frac{x^2}{2n} + O(n^{-2}) \right) + n \cdot \frac{1}{2} \left( - \frac{x^2}{2n} + O(n^{-2}) \right)^2 + n \cdot g_1(x) \cdot O(n^{-3}) \right\}\\
&= e^x \left\{ -\frac{x^2}{2} +O(n^{-1}) + \frac{1}{2} \cdot \frac{x^4n}{4n^2} + g_2(x) \cdot O(n^{-2}) \right\}\\
&= e^x \left\{ -\frac{x^2}{2} \right\} + g_3(x) \cdot O(n^{-1})\\
& \to e^x \cdot \left( -\frac{x^2}{2} \right)
\end{align*}
with some functions $g_i(x)$ and where we have generously rounded the big-O expressions to $O(n^{-1})\,.$

Aha! Thank you SO much! Awesome question and solution!

 

[Periwinkle]

$6$. Let $f: [0,1] \rightarrow \mathbb{R}$ be a continuous function with $f(0) = f(1)$ . Prove that the equation $f(x) = f(x + \frac{1}{n})$ has at least one real root, for all $n = 1, 2, 3,\dots$

For $n = 1$ the theorem is true, $x=0$ is the solution. Provided that $n \gt 1$ let $G(x)$ be the function defined for the $\left[0, \frac {n-1} n \right]$ interval $$G(x) = f\left(x+ \frac 1 n\right) - f(x).$$ If $G(0) = 0$ then the theorem is proved, $x=0$ is the solution.

If $G(0) \gt 0$, take the next equations

$$ 0= f(1)-f(0) =\\

f\left(\frac n n\right) - f \left(\frac {n-1} n \right) + f\left(\frac {n-1} n\right)- f\left(\frac {n-2} n\right)+ \dots + f\left(\frac 2 n\right)- f\left(\frac 1 n\right)+ f\left(\frac 1 n\right)- f(0) =

\\ G\left( \frac {n-1} n \right) + G\left( \frac {n-2} {n} \right) + \dots + G\left(\frac 1 n \right) + G(0). $$ Because $G(0) > 0$, it is necessarily one of the $G\left( \frac k n \right)$ should be negative. But then the $G(x)$ function at the point $\frac k n$ is negative, at the point $0$ it is positive, so it takes $0$ at an intermediate $x_0$ point according to to the Bolzano-Cauchy intermediate value theorem, where $f\left(x_0+ \frac 1 n \right) - f(x_0) =0$.

If $G(0)<0$, we apply the above proof to the $-f(x)$ function.

 

[Periwinkle]

$8$. In a conference there are $n$ persons. Show that there are two persons such that, from the rest $n - 2$ persons, there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons each of which knows both the aforementioned two persons or else knows no one from them. Suppose that "know someone" is a symmetric relation.

Originally, I interpreted the question as follows

there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons {each of which knows both the aforementioned two persons} or else {each of which knows no one from them}​

but I couldn't solve it.

However, if I interpret it as follows:

there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons each of which {knows both the aforementioned two persons or else knows no one from them}​

then I think I can solve the problem.

------------------------------------------------------------------------------------------------------------------------------------------------

It is a graph with $n$ vertices, in which if two people know each other, the two vertices are bound by a blue edge, if they do not know each other, then yellow edge. At the vertex $A$, the number of blue edges is $b_A$, the number of yellow edges is $y_A$, while in the $B$ the number of blue edges is $b_B$, the number of yellow edges is $y_B$.

$\left[ \frac n 2 \right] - 1 \lt \frac {n-1} 2$ inequality is true for all positive n.

Suppose that for each vertex $A$ and $B$ of the graph, there are fewer single-colored edge pairs than $\left[ \frac n 2 \right] - 1$, so it is false what the theorem says. In this case, for each pair of vertices $A$ and $B$, the number of edge pairs of different colors is greater than $\frac {n-1} 2$. Take one of these $A$ and $B$ pair of vertices.

The following two cases are possible:

(1) $b_A > \frac {n-1} 2$ and $y_B > \frac {n-1} 2$

(2) $y_A > \frac {n-1} 2$ and $b_B > \frac {n-1} 2$​

However, the above is true for vertices $A$ and $C$, so

(1) if $b_A > \frac {n-1} 2$ then $y_C > \frac {n-1} 2$,

(2) but if $y_A > \frac {n-1} 2$ then $b_C > \frac {n-1} 2$.​

However, with respect to the vertex $B$ and $C$ of the graph, we get a contradiction because in both the previous two cases

(1) if $b_A > \frac {n-1} 2$ then $y_C > \frac {n-1} 2$ and $y_B > \frac {n-1} 2$,

(2) but if $y_A > \frac {n-1} 2$ then $b_C > \frac {n-1} 2$ and $b_B > \frac {n-1} 2$.
​

ps

I see that I have to write $\frac {n-2} 2$ instead of $\frac {n-1} 2$ above.

 

[QuantumQuest]

Originally, I interpreted the question as follows

there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons {each of which knows both the aforementioned two persons} or else {each of which knows no one from them}
but I couldn't solve it.

However, if I interpret it as follows:

there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons each of which {knows both the aforementioned two persons or else knows no one from them}
then I think I can solve the problem.

I cannot really see what you mean here. I think that the wording of the problem is clear:

Show that there are two persons such that, from the rest $n - 2$ persons, there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons each of which knows both the aforementioned two persons or else knows no one of them

We simply have two persons, the rest remaining after subtracting them from $n$ is $n-2$ and from these we need to show that there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons each of which knows both the two initial persons or knows no one of them.

 

[QuantumQuest]

I see that I have to write $\frac {n-2} 2$ instead of $\frac {n-1} 2$ above.

True that. EDIT: I refer to $\left[ \frac n 2 \right] - 1 \lt \frac {n-1} 2$ you write. If you mean floor i.e. $\lfloor \frac{n}{2} \rfloor - 1\lt \frac {n-1} 2$ then it holds true and you can also write $\lfloor \frac{n}{2} \rfloor - 1\leq \frac {n-2} 2$.

Also, I see that you use the symbols "[" and "]" without being double brackets or boldface, so just for avoidance of any confusion, we talk about the greatest integer less than or equal to x i.e. floor(x). I think it's best to use $\lfloor$ and $\rfloor$ instead.

 

[Periwinkle]

True that. EDIT: I refer to $\left[ \frac n 2 \right] - 1 \lt \frac {n-1} 2$ you write. If you mean floor i.e. $\lfloor \frac{n}{2} \rfloor - 1\lt \frac {n-1} 2$ then it holds true and you can also write $\lfloor \frac{n}{2} \rfloor - 1\leq \frac {n-2} 2$.

Also, I see that you use the symbols "[" and "]" without being double brackets or boldface, so just for avoidance of any confusion, we talk about the greatest integer less than or equal to x i.e. floor(x). I think it's best to use $\lfloor$ and $\rfloor$ instead.

Thank you very much for your comment. I realized that my proof was completely wrong. Interestingly, proving such an easy-to-understand theorem - at least for me is undoubtedly so difficult.

 

[QuantumQuest]

Interestingly, proving such an easy-to-understand theorem - at least for me is undoubtedly so difficult.

As a hint, you can start with two persons in the conference and regard a person as "involved" with this couple of persons, if this third person knows exactly one of the persons of the couple. You can generalize this and maybe use A.M. - G.M. along with some combinatorics and see what can it give you.

 

[Periwinkle]

As a hint, you can start with two persons in the conference and regard a person as "involved" with this couple of persons, if this third person knows exactly one of the persons of the couple. You can generalize this and maybe use A.M. - G.M. along with some combinatorics and see what can it give you.

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] $$ $$ \frac {n(n-1)(n-2)} 2 = -\frac{n(n-1)} 2 + \sum_{i=1}^n \frac {k_i^2+l_i^2+2k_il_i} 2 $$ It follows from arithmetic-geometric inequality that $k_i^2+l_i^2 \geq 2 k_i l_i$. Therefore $$ \frac {n(n-1)(n-1)} 2 \geq \sum_{i=1}^n 2 k_il_i $$ That is $$ \frac {n(n-1)} 2 \cdot \frac {(n-1)} 2 \geq \sum_{i=1}^n k_il_i $$ If for each person pair, the other $n-2$ people who are not involved are less than $\left[ \frac n 2 \right]-1$, then the involved is more than $\frac {n-1} 2$, which is a contradiction.

For integer value function ($[1.2] =1, [1.5] = 1, [1.7] =1$) the following is true:

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$

 

[QuantumQuest]

...Involved in $k_i \cdot l_i$ pairs.

In order to simplify symbols, let's say that a person knows exactly $k$ persons in the conference. Then in how many pairs is he / she involved?

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.

I think that it would be more useful to think in terms of the combinations of pairs - involved persons.

 

[Periwinkle]

$8$. In a conference there are $n$ persons. Show that there are two persons such that, from the rest $n - 2$ persons, there are at least $\lfloor \frac{n}{2} \rfloor - 1$ persons each of which knows both the aforementioned two persons or else knows no one of them. Suppose that "know someone" is a symmetric relation.

I.​

My reasoning above, which I wrote yesterday before and hastened, is based on that

1. for each $X$ person, we count the number of pairs of individuals for which this $X$ is involved
2. 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.)

1. 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$$

​

 

[QuantumQuest]

@Periwinkle, I see a lot of things written but, at times, I can't follow your solution. I asked you to use simpler symbols / notation like denoting with $k$ the number of persons which one person knows in the conference, as a way to simplify things. The question I put

Then in how many pairs is he / she involved?

was along the lines of a hint as also the second thing I proposed in post #82. In any case, I can't see / understand the sort of contradiction you talk about and where is all this leading to.

 

[Periwinkle]

@Periwinkle, I see a lot of things written but, at times, I can't follow your solution. I asked you to use simpler symbols / notation like denoting with $k$ the number of persons which one person knows in the conference, as a way to simplify things. The question I put
was along the lines of a hint as also the second thing I proposed in post #82. In any case, I can't see / understand the sort of contradiction you talk about and where is all this leading to.

In mathematical circles, if there is an error in a mathematical proof, they correctly specify where the error is located.

It was so memorable to me that even the great Newton taught in one of his books, solving the word problems for the students, or rather for their teachers. For example, I would like to calculate an ordinary definite integral, which would, of course, be given to me by a symbolic integration program, but then I would not learn anything.

 

[QuantumQuest]

In mathematical circles, if there is an error in a mathematical proof, they correctly specify where the error is located.

I see your point but on the other hand I cannot be inside everyone's mind to see / understand his / her way of thinking in every case, if it is not sufficiently explained / clear, at least for what my math knowledge allows me to understand. So, in order to be as helpful as I can, what can I tell is that I cannot make sense of what you write as a whole. Also, you go from one implicit way to another while you can prove what is asked directly - i.e. not in the way of involved and not involved, involved or not involved etc., in no more than ten lines, as I did for example - I don't claim any sort of superiority or anything; just an example, when I was given this problem at my nineteen in a mathematical contest.

Also, I see that you don't use my hints at all. This is perfect but they are along the lines of a direct way of proof for this problem and I think that they would be of help to you. In any case I won't try to surmise things that seem to lead somewhere; I ask for an explicit i.e. clear proof of what is asked.

 

[fresh_42]

I.​

My reasoning above, which I wrote yesterday before and hastened, is based on that

1. for each $X$ person, we count the number of pairs of individuals for which this $X$ is involved
2. 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 245126

1. 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.