0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you do 1? The octahedron does not matter. You really have a complete graph on six vertices because there is a rod between each pair of vertices. Usually we would not consider an octahedron to have rods between opposite vertices, but the problem specifies it in an effort to hide that this is just the graph $K_6$. $\endgroup$ – Ross Millikan Jun 23 at 2:26
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$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$

| cite | improve this answer | |
$\endgroup$

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.