I'm trying to do the following problem:

In a cuboid shaped room a hook is placed in the centre of each wall, the floor, and the ceiling. Every pair of hooks has either a piece of red or blue string tied between them. As this task is being performed triangles will be formed between sets of three hooks with edges being red or blue.

Prove that it is impossible to complete this task without forming at least one triangle of the same colour.

I am totally stuck and have been for some hours (although by the rated difficulty it should not be that hard :( ).

What I've concluded is that there's: 6 hooks, 15 strings and 20 triangles. I, however, can't find any way to prove that at least one triangle should have the same color.

I've tried creating a map of all the strings and triangles but this very quickly becomes really confusing so that's not the way to go.

Hints are very much appreciated.

  • $\begingroup$ Google 'Ramsey numbers'. $\endgroup$ – TokenToucan Jan 9 '16 at 22:07

A hint: suppose there is no such triangle, and then see what happens if you look at just one of the hooks.

The proof benefits from a picture - if we assume there is no such triangle, the PHP guarantees that one of the nodes will either be in a triangle or induce a triangle in its neighbors, so we have a contradiction. Suppose we have the given situation ($6$ nodes, every possible edge colored either blue or red). Assume that there is no such triangle, and we will arrive at a contradiction. Work with a fixed node/hook $v$. By the (strong) pigeonhole principle, there are at least $3$ strings of one color extending from this node; WLOG, let this color be blue and three nodes they reach be $w_1,w_2,w_3$. By hypothesis, none of $w_1,w_2,w_3$ can be connected to each other by a blue string because this would give a blue triangle $\{v,w_i,w_j\}$ contradicting the hypothesis. This means they are all connected by red string, but that gives a red triangle $\{w_1,w_2,w_3\}$ so we arrive at a contradiction. Then our hypothesis was incorrect, so there must be some triangle that with all blue or all red edges.

  • $\begingroup$ Thank you so much! :) It is quite confusing but it's much more clear than when I started. Just one question though: Am I supposed to just get this stuff after just finished high school or at what level is this problem solving? $\endgroup$ – Arcthor Jan 10 '16 at 0:07
  • $\begingroup$ I think most discrete mathematics courses cover this, so probably in your first or second year of college. Lots of this stuff can be fun to learn on your own too! Martin Gardner's math puzzles might interest you if you like this kind of thing. $\endgroup$ – TokenToucan Jan 10 '16 at 0:38

Try to color them avoiding a single color triangle. Start with hook A. There are seven strings connected to it. At least three are the same color (as there are only two colors and seven strings). Wolog let that color be blue and let the strings from A to B C and D be blue. Then the strings between B and C is green (else triangle ABC is all blue). Likewise string between C and D is green, as is string between D and B. So triangle BCD is all green. We failed. We must construct at least one triangle in a single triangle.

  • $\begingroup$ I think there are only five strings connected to hook A, but there are still at least three of the same color, and the rest of the answer works. $\endgroup$ – David K Jan 9 '16 at 22:57
  • $\begingroup$ Thank you! Really helpful :) $\endgroup$ – Arcthor Jan 10 '16 at 0:07

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.