Points and Triangles on a Circle

  1. N points are arranged uniformly around a circle. How many triangles can be formed which have three of these points as vertices?
  2. Two players in turn draw lines between two of the points on the above circle, using red and blue marks respectively. The loser is the first to create a triangle in his/her color, with vertices on three of the N points. Is there a strategy to this game? How can one person play to win (or not to lose)?
  3. Can you analyze the game if the created triangle does not need all three vertices on the circle? (Vertices could be found within the circle if same-color lines cross.)
Added at archival (these are more puzzle-like):
  1. Can the above game end in a draw for any N? That is, can all possible lines be red or blue, but have no triangles of one color with vertices on the circle? (Ideally, the number of red and blue lines would differ by at most 1, but I'd be interested in solutions in which they differ by more.)
  2. What is the largest number of lines which can be drawn connecting the N points and not have a triangle with vertices on the circle? (Just a single color for this puzzle. To label your solution, it may be easiest to number the points 1-to-N, then just list the endpoints of the lines you didn't draw.)
If you want to focus, I'd be interested in numerical examples for N=4,5,6,7.

Source: Original, based on a game on a breakfast cereal box.


Solutions were received from Ravi Subramaniam, and Robert McQuaid.
  1. The number of triangles is simply (N Choose 3) = N(N-1)(N-2)/6.
  2. No good strategey can be defined (or none has been sent to me, yet.)
  3. If a strategy is found for question 2, the same strategy can be used for this question.
Walkovers@aol.com and Craig Gentry sent similar solutions to the last questions. Craig's solutions are below:
  1. If N is less than 6, it is possible to draw all possible lines red or blue without there being a monochromatic triangle. (For N=5, consider a red pentagon with a blue star inside.) If N is greater than or equal to 6, however, a monochromatic triangle is inevitable. Here's a proof:
    Point A, like all the points, is connected to N-1 (at least 5) other points by N-1 (at least 5) lines. At least 3 of these lines are the same color -- say, red. If the red lines connect A to points B, C and D, then if BC, CD or DB is also red, a red triangle is created. But if they're all blue, BCD is a blue triangle.
    If you search the Net for "Ramsey Numbers," you can get more info on this type of problem.

  2. For even N, the answer is (N^2)/4. For odd N, the answer is ((N^2)-1)/4.
    To see that this is true for even N, arrange the circle so that N/2 points are on the left, and N/2 are on the right. Connecting each left-point to each-right point creates (N^2)/4 lines, but no triangles.
    How can we be sure that it isn't possible to do more lines? Suppose that the most lines emanating from a single point -- say, point A -- is ((N/2) + k). Suppose that one of the points that point A is connected to is point B. Since A and B cannot be connected to any of the same points, lest a triangle be created, B is connected to at most ((N/2) - k) points. In fact, each of the ((N/2) + k) points that is connected to A, such as B, is connected to at most ((N/2) - k) points. The points that are not connected to A are connected to at most ((N/2) + k) points by assumption. Thus, the number of possible lines is:
    [((N/2) + k)((N/2) - k) + ((N/2) - k)((N/2) + k)]/2, which is maximized when k=0.
    You can verify the answer for odd N in a similar fashion.

Philippe Fondanaiche adds this commentary August 11, 1999:
The puzzle is a "classic" of the Graph theory. As mentioned by Craig Gentry, the Ramsey theory and the Ramsey number of a graph give the clues to solve the problem. In an issue of Pour la Science (french version of Scientific American) published in january 1978, Martin Gardner has presented the main characteristics of the Ramsey theory and,as an example,has given your puzzle for N=6,called "Sim's problem".Without providing any demonstration, he said that the winner is the second player. As another example,he has mentioned a similar problem published in june 1958 by The American Mathematical Monthly: Demonstrate that in a group of six people,there are at least either three of them who have already met or three of them who meet for the first time.

Six years later,Pierre Tougne in the same review Pour la Science (october 1984) has further developed the presentation of the Ramsey theory and has presented too your puzzle with the two cases:1) the winner is the first to create a monochrome triangle 2) this is the loser who creates the first monochrome triangle. In the first case,for N=5, he demonstrated easily that the winner was the first player.Concerning the second case,he said that the winner is the second player mentioning only that the demonstration is not difficult but longer than in the former case. For N>5, he added that the first player is at a disadvantage compared with the second player who has the winning strategy.Apparently,the demonstration remains relatively easy for N=6 but becomes more and more complex for the higher values. For example with N=7, there are 7*6/2 = 21 possible sides, 2^21 possible colourings and 21! possible graphs drawn by the two players. All the possible games are in very large numbers and the help of a powerful computer is compulsory.

Coming back to the case N=5, I have identified, unless I am mistaken, a good strategy for the second player P2. Let call a,b,c,d,e the vertices clockwise. L1, L3, L5, L7 and L9 are the red lines drawn by the first player P1 whereas L2, L4, L6, L8 and L10 are the blue lines drawn by P2. First,P1 draws the red line L1,for example ab. P2 draws the blue line L2 defined by the 2 vertices c and e adjacent to a and b.At the next step, if L3 has no common vertex with L2, P2 repeats the same strategy. If L3 has a common vertex with L2, P2 draws L4 which is the third side of the multicoloured triangle whose the two other sides are L2 and L3. In the next steps, the strategy of P2 is to lead P1 to draw two couples of red lines each of them having a common vertex and the third side of the corresponding triangles T and T' not yet drawn such as when P1 draws L9, this will be necessarily one of the third sides of the two triangles T and T'.Obviously P2 has to avoid to fall in the same trap.This can be found empirically on the basis of the possible configurations starting from L5.They are in more limited numbers as compared the original position.


Mail to Ken
My birthday was July 27! I finally reached the first 2-digit Mersenne prime! (How's that for a puzzler's birthday?)