"Consider the set $X = \{1,2,3,4,5\}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the 2-element subsets of $X$. Can you put these 10 pigeons into the two holes in a way that there is no 3-element subset $S = \{a,b,c\} \subset X$ for which all pigeons go in the same hole? The answer the same question if $X = \{1,2,3,4,5,6\}$ with $15 = C(6,2)$ pigeons"
Currently working through Trotter & Keller and came across this problem. I can show the 10 pigeon case is possible but am unsure how to approach the 15 pigeon case with $$X = {1,2,3,4,5,6}$$
By the pigeonhole principle, there exists a hole with at least 8 pigeons but I am not sure how this is relevant to the question. I am conjecturing it has something to do with the fact that 8 is more than half the # of pigeons, while in the 10 pigeon case we had 5 pigeons in a hole by the PHP, where 5 is NOT more than 1/2 the total # of pigeons...
Hint: Did you know that in a complete graph of 6 vertices, with edges colored red or blue, there exists at least one (actually two) monochromatic triangles?