# Pigeonhole principle application

Say there are $p_{1}$ red balls and $p_{2}$ green balls. We put all the balls in a circle with $p_{1}+p_{2}$ places in total. It is forbidden that a ball (red or green) is placed between two red balls.

Show that this is impossible if $p_{1}>p_{2}$.

Further on, say $p_{1}=p_{2}=p\geq10$. For which values of $p$ the ordination is possible?

Can somebody help me? Thanx in advance!

• So does this mean that between any two red balls there must be (at least) two green balls? – paw88789 Feb 14 '15 at 11:24
• Yes I think so. Other possibilities are not allowed. And this will bring us close to the answer?! – iJup Feb 14 '15 at 11:29
• Add the extra demand $p_2>0$ to avoid the trivial solution $p_1=2$ and $p_2=0$. – drhab Feb 14 '15 at 11:31
• Alternative interpretation: Between any two red balls there must be zero green balls, or at least two green balls. – TonyK Feb 14 '15 at 11:59

For ball $i$ let $G_i$ denote the number of its green neighbours and let $R_i$ denote the number of its red neighbours.
Then $G_i+R_i=2$ and $R_i\leq1\leq G_i$ so that: $$2p_1=\sum_{i}R_i\leq\sum_{i}G_i=2p_2$$ Every ball is counted twice since it is the neighbour of two balls.
Between two red balls must be zero green balls, or at least two green balls. => There are $\lfloor \frac{p_{2}}{2} \rfloor$ positions to place a green ball. You can place the maximal amount of red balls if you place two red balls the same time. So in total you can place: $2\cdot \lfloor \frac{p_{2}}{2} \rfloor \leq p_{2}$ red balls. Since $p_{1}> p_{2}$, there are less positions for red balls than the amount of red balls.