- #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!
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.
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 soI'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})\,.##
##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##
##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.
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
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.
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.
...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.
##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.
Then in how many pairs is he / she involved?
@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.
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.I.
My reasoning above, which I wrote yesterday before and hastened, is based on that
That is, the number of existing involved relationships is counted in two ways.
- for each ##X## person, we count the number of pairs of individuals for which this ##X## is involved
- for each pair of ##X, Y## persons, count the number of other persons involved in this pair.
(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$$