In a space , there are given $p(n) =[en!]+1$ points. Each pair is connected by a line, and each line is coloured with one of $n$ colours. How to prove that there is ar least one triangle with same colour? (Here $[\cdot ]$ is the greatest integer function and $e$ is Euler's number.)

I have been able to prove its special cases for n= 2 and 3 by using the pigeonhole principle or box principle, but can not understand how to prove that for general cases . I thought of proving that $[([en!]+1)/n] = [e(n-1)!]+1$, but unable to do it.

(I am just promoted to class 12. Please give help accordingly. Thanks in advance.)


Claim 1. $n \nmid \left \lfloor en! \right \rfloor$ and $\left \lfloor \dfrac{\left \lfloor en! \right \rfloor}{n} \right \rfloor=\left \lfloor e(n-1)! \right \rfloor$.

Proof. The second one is true since $\left \lfloor \dfrac xn \right \rfloor = \left \lfloor \dfrac{\left \lfloor x \right \rfloor }{n} \right \rfloor$ for any $x \in \mathbf{R}, n \in \mathbf{Z}$. For the first one, assume the contrary that $n \mid \left \lfloor en! \right \rfloor$ then $$\dfrac{\left \lfloor en! \right \rfloor}{n}= \left \lfloor \dfrac{\left \lfloor en! \right \rfloor}{n} \right \rfloor= \left \lfloor e(n-1)! \right \rfloor. \tag{1}$$ On the other hand, we have $e= \displaystyle \sum_{i=0}^{\infty} \frac{1}{i!}$ so the fractional part of $e(n-1)!$ is $$ \left\{ e(n-1)! \right\} = \left\{ (n-1)! \sum_{i=0}^{\infty} \frac{1}{i!} \right\} = \left \{ (n-1)! \sum_{i=n}^{\infty} \frac{1}{i!} \right \}. $$ Note that $$\begin{align*} (n-1)!\sum_{i=n}^{\infty} \frac{1}{i!} & = \frac 1n + \frac{1}{n(n+1)}+\frac{1}{n(n+1)(n+2)}+ \ldots \\ & < \frac 1n + \sum_{i=n}^{\infty} \frac{1}{i(i+1)} <\frac 2n<1. \end{align*}$$ Therefore, $(n-1)!\sum_{i=n}^{\infty} \frac{1}{i!}$ is the fractional part of $\left \{ e(n-1)! \right \}$. Note that from the above $(n-1)!\sum_{i=n}^{\infty} \frac{1}{i!}>\frac 1n$ so $\{ e(n-1)! \}>\frac 1n$. Hence, $$\left \lfloor e(n-1)! \right \rfloor=e(n-1)!-\{ e(n-1)! \}< e(n-1)!-\frac 1n< \frac{\left \lfloor en! \right \rfloor}{n}.$$ This contradicts to (1). Thus, we must have $n \nmid \left \lfloor en! \right \rfloor$. $\square$

From $n \nmid \left \lfloor en! \right \rfloor$ we follow $$\left \lceil \frac{\left \lfloor en! \right \rfloor}{n} \right \rceil=\left \lfloor \dfrac{\left \lfloor en! \right \rfloor}{n} \right \rfloor+1=\left \lfloor e(n-1)! \right \rfloor+1.$$

Back to the problem, we induct on $n$. Assume the problem is true for $\left \lfloor e(n-1)! \right \rfloor+1$ points. Consider the case for $\left \lfloor en! \right \rfloor+1$ points. Consider arbitrary point $A_1$ among these points $A_i$ and all the lines from $A_1$ to other $\left \lfloor en! \right \rfloor$ points. By Pigeonhole Principle, there exists $\left \lceil \frac{\left \lfloor en! \right \rfloor}{n} \right \rceil=\left \lfloor e(n-1)! \right \rfloor+1$ lines out of $\left \lfloor en! \right \rfloor $ lines $A_1A_i$ that have the same colour $X_1$. Let $B_1, \ldots, B_{\left \lfloor e(n-1)! \right \rfloor+1}$ be the points that are in such lines, i.e. All lines $A_1B_i$ have same colour $X_1$.

Consider $\left \lfloor e(n-1)! \right \rfloor+1$ points $B_i$. If there exists two points $B_i,B_j$ so $B_iB_j$ is coloured $X_1$ then triangle $AB_iB_j$ has three sides having same colour $X_1$. If there doesn't exists any such two points then that means any two lines formed from $B_i$ can only be coloured with one of $n-1$ colours $X_2, \ldots, X_n$. Hence, by inductive hypothesis, there exists a triangle $B_iB_jB_k$ with same colour.

Thus, by induction, we obtain the desired result. $\square$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.