# How to prove that there is at least 1 triangle of same colour?

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$