#TCS #CommonQuestion #BSC #BCA #Campusing #DICE 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. (A,B,C) (D,E,F) (G,H,I) 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? ANS: A mono triangle has all three vertices the same color. A hybrid has 2 of one color and 1 of the other. A wants to create hybrids. (2 colored edges) R wants to create monos. (0 colored edges). The last turn can always create a hybrid, so there will always be at least one of those. (After 8 turns, the last triangle can be: (R G x) ... then its already a hybrid or (R R x) or (G G x) and then calling the opposite color makes it a hybrid.) There wont be three, because somewhere before the end, 3 of the same color must be called, and so at least one mono 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 hybrid, 2 monos, 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 hybrid, 2 monos always matching whats already there c) 3 + 2 (R R R) (G G x) (x x x) 1 hybrid, 2 monos So the vertex guy can always guarantee just 1 hybrid, and 2 monos no matter what colors are called, by never creating a hybrid until he has to, at the end. And the color guy can always use the last move to make a hybrid. Thus there will always be just 2 colored edges.
Posted on: Tue, 27 Jan 2015 08:58:31 +0000
Trending Topics
Recently Viewed Topics
© 2015