# Challenge Math Challenge - February 2019

• Featured

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

Last edited:

#### QuantumQuest

Gold Member
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

Gold Member
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.

Last edited:

#### 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

Gold Member
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

Gold Member
...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$$

"Math Challenge - February 2019"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving