Problem
Consider the graph G0 with 3 components which are triangles. G0 has 9 vertices labeled A to I and 9 edges (A, B), (B, C) … as shown below. If each vertex of G0 is assigned a red or a green color, then we say that an edge is colored if its ends have different colors. Ajai and Rekha color the vertices of G0 in the following manner. Ajai proposes a color (red or green) and Rekha chooses the vertex to apply this color. After 9 turns, all the vertices of G0 are colored and the number of colored edges is counted. Suppose Ajai would like to maximize the number of colored edges while Rekha would like to minimize the number of colored edges. Assuming optimal play from both players, how many edges will be colored? Explain your reasoning.
The answer is 1.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
A mono triangle has all three vertices the same color. A doublecoloured triangle has 2 of one color and 1 of the other.
Ajai wants to create doubly coloured edges ie. Doublecoloured triangles. (2 colored edges) Rekha wants to create single coloured edges ie.Monocoloured Triangles. (0 colored edges).
The last turn can always create a doublecoloured triangle, so there will always be at least one of those.
(After 8 turns, the last triangle can be: (R G x) ... then it's already a Doublecoloured triangle or (R R x) or (G G x) and then calling the opposite color makes it a Doublecoloured triangle.)
There won't be three, because somewhere before the end, 3 of the same color must be called, and so at least one monocoloured can be formed.
The first 5 calls can be: a) 5 of one color, 0 of the other b) 4 + 1 or c) 3 + 2.
a) 5 + 0 (R R R) (R R x) (x x x) yields 1 doublecoloured triangle, 2 monocoloured triangle, if either all greens are called, or another red is called.
b) 4 + 1 (R R R) (R x x) (G x x) yields 1 doublecoloured triangle, 2 monocoloured triangle always matching what's already there
c) 3 + 2 (R R R) (G G x) (x x x) 1 doublecoloured triangle, 2 monocoloured triangle
So the vertex guy can always guarantee just 1 doublecoloured triangle, and 2 monocoloured triangle no matter what colors are called, by never creating a doublecoloured triangle until he has to, at the end.
And the color guy can always use the last move to make a doublecoloured triangle.
Thus there will always be just 2 colored edges. The answer provided is wrong