Pigeonhole principle - Octahedron question

193 Views Asked by At

So I came across a pigeonhole principle question and was unable to complete this question. I was just wondering how to commence this question/what sort of reasoning I could use to "explain". Proof by contradiction is always an open method but I'm unsure how to apply it into this question here.

A regular octahedron has $6$ vertices. Each vertex is connected to each other vertex by a rod that is coloured yellow or blue.

$1.$ Each set of three vertices, together with the rods joining them, forms a triangle. Explain why there are $20$ such triangles.

$2.$ Explain why there will be at least one triangle whose rods all have the same colour.

2

There are 2 best solutions below

0
On

Five rods meet at each vertex. At vertex $A$, there must be at least three rods of the same color. Suppose that rods $AB$, $AC$, and $AD$ are yellow. If rod $BC$ is yellow that $\triangle ABC$ is yellow, so we may assume that $BC$ is blue. Similarly, we may assume rods $BD$ and $CD$ are blue, so that $\triangle BCD$ is blue.

0
On

$1.$ You pretty much answered your own question, what is $\binom {6}{3}$?

$2$. Call the vertices $P_1,\ldots,P_6$. Let’s concentrate on our favourite vertex $P_1$. What is the number of edges coming out of it? $5$. But there are only two available colours, so by pigeonhole principle there must be $3$ edges with same colour. WLOG assume the colour is blue. Now focus on the other endpoints (ie. vertices). WLOG (by relabelling if needed) we can assume the $P_1P_2, P_1P_3, P_1P_4$ are all blue edges. Now if any of the $ P_2P_3,P_3P_4,P_4P_2$ is coloured blue then you have your blue coloured triangle. If all of them are coloured yellow, then $P_2P_3P_4$ is the yellow triangle you’re looking for $\ldots$