Points and Triangles on a Circle
-
N points are arranged uniformly around a circle. How many triangles can
be formed which have three of these points as vertices?
-
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)?
-
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):
- 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.)
- 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.
- The number of triangles is simply (N Choose 3) = N(N-1)(N-2)/6.
- No good strategey can be defined (or none has been sent to me, yet.)
- 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:
-
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.
-
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?)