Many Red Triangles

Problem

Given 2n2n points in the plane (n>1n > 1), no three collinear, all segments between pairs are drawn and some n2+1n^2 + 1 of them are colored red. Prove that there are at least nn triangles with all three sides red.

Answer

Solution

Difficulty9/10
Topicscombinatorics, Graph Theory, Pigeonhole, Induction

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments
Log in to join the discussion.

No comments yet.