Challenge Math Challenge - February 2019

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

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

244120


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

Science Advisor
Insights Author
Gold Member
838
431
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

Science Advisor
Insights Author
Gold Member
838
431
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:
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

Science Advisor
Insights Author
Gold Member
838
431
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.
 
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

Science Advisor
Insights Author
Gold Member
838
431
...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.
 
##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.)


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

 

Want to reply to this thread?

"Math Challenge - February 2019" You must log in or register to reply here.

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

Hot Threads

Top