Math Challenge - February 2019

  • #71
fbs7
345
37
Holy choo-choo, what kind of high school is this? I can very barely follow these arguments, and I supposedly have a college degree!
 
  • #72
QuantumP7
68
0
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}##?
 
  • #73
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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})\,.##
 
  • #74
QuantumP7
68
0
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!
 
  • #75
Periwinkle
63
13
##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.
 
Last edited:
  • Like
Likes QuantumQuest
  • #76
Periwinkle
63
13
##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:
  • #77
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
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.
 
  • #78
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
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:
  • #79
Periwinkle
63
13
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.
 
  • #80
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
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.
 
  • #81
Periwinkle
63
13
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##
 
  • #82
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
...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.
 
  • #83
Periwinkle
63
13
##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$$

 
  • #84
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
@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:
  • #85
Periwinkle
63
13
@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.
 
  • #86
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
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:
  • #87
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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.
 
  • Like
Likes QuantumQuest

Suggested for: Math Challenge - February 2019

  • Last Post
2
Replies
67
Views
6K
  • Last Post
4
Replies
107
Views
13K
  • Last Post
3
Replies
91
Views
7K
  • Last Post
2
Replies
42
Views
4K
  • Last Post
2
Replies
48
Views
8K
  • Last Post
2
Replies
61
Views
5K
  • Last Post
2
Replies
42
Views
8K
  • Last Post
3
Replies
100
Views
4K
  • Last Post
2
Replies
43
Views
8K
  • Last Post
2
Replies
39
Views
9K
Top