Im trying to prove that for any number n the complete graph with $p(n)$ vertices whose edges have been colored with n colors in some way has a monochromatic triangle (a triplet of nodes that are connected with edges of the same color) regardless of the way the coloring has been made.
$$p(n) = \lfloor (e*n!) \rfloor+1$$
I have proven the statement using pigeonhole principle for $n=1,2,3$.
For $n=2$, $p(n) = 6$. We pick a node and it has $5$ outgoing edges. From pigeonhole principle at least $3$ are colored the same, say red. Now let $A,B,C$ be the receiving vertices of these edges. If there is at least one red edge in $ABC$ were done. If not were still done.
For $n=3$, $p(n) = 17$. Same logic. Pick a node, $16$ edges spawn from it. At least $6$ (notice that this is $p(2)$) have the same color and the receiving nodes of these 6 edges form a complete graph with $p(2)$ nodes. The problem is recursively transformed into something we have already solved. For the general case i try to apply the same logic: pick a node. From there $p(n)-1$ edges are left.
$\lceil (p(n)-1)/n\rceil$ of those edges are the same color, say red. If in that smaller graph a red edge exists we're done. If not, we have $n-1$ colors to paint the edges of a complete graph with $\lceil(p(n)-1)/n \rceil$ nodes. This can be done if $ \lceil(p(n)-1)/n \rceil = p(n-1)$. From here i want to transform this recursion into the formula i gave in the problem description. Any ideas?
You’ve shown that your argument will work provided that $p$ satisfies the inequality
$$\left\lceil\frac{p(n)-1}n\right\rceil\ge p(n-1)\tag{1}$$
for each $n$. Recall that $e=\sum_{k\ge 0}\frac1{k!}$, so that $\lfloor en!\rfloor=\sum_{k=0}^n\frac{n!}{k!}$.
Assume that
$$p(n-1)=\lfloor e(n-1)!\rfloor+1=1+\sum_{k=0}^{n-1}\frac{(n-1)!}{k!}\;;$$
then $(1)$ holds if and only if
$$\frac{p(n)-1}n>p(n-1)-1\;,$$
i.e., if and only if
$$\frac{p(n)-1}n>\sum_{k=0}^{n-1}\frac{(n-1)!}{k!}\;.$$
This is equivalent to
$$p(n)>1+\sum_{k=0}^{n-1}\frac{n!}{k!}=\sum_{k=0}^n\frac{n!}{k!}\;,$$
which is satisfied if we set
$$p(n)=1+\sum_{k=0}^n\frac{n!}{k!}=\lfloor en!\rfloor+1\;.$$
The result now follows by induction.
Added: To see that $\lfloor en!\rfloor=\sum_{k=0}^n\frac{n!}{k!}$ for $n\ge 1$, it suffices to show that $\sum_{k\ge n+1}\frac{n!}{k!}<1$. But
$$\begin{align*} \sum_{k\ge n+1}\frac{n!}{k!}&=\sum_{k\ge n+1}\frac1{\prod_{i=n+1}^ki}\\ &=\sum_{k\ge 1}\frac1{\prod_{i=1}^k(n+i)}\\ &\le\sum_{k\ge 1}\frac1{\prod_{i=1}^k(1+i)}\\ &=\sum_{k\ge 1}\frac1{(k+1)!}\\ &=\sum_{k\ge 2}\frac1{k!}\\ &=e-2\\ &<1\;. \end{align*}$$