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
850
434
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
850
434
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
850
434
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
850
434
...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$$

 

QuantumQuest

Science Advisor
Insights Author
Gold Member
850
434
@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.
 
Last edited:
@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

Science Advisor
Insights Author
Gold Member
850
434
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.
 
Last edited:

fresh_42

Mentor
Insights Author
2018 Award
10,702
7,303
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.
 

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