## Party Acquaintances

22.45

Diposting oleh Melany Christy

Prove that at a party of six people either there are three mutual acquaintances or there are three mutual strangers. |

The problem is naturally modelled on a 2-color graph. To remind, K_{n} is the standard notation for a complete graph with n vertices. Assume the edges of K_{6} are all colored into two colors: red or blue. The problem is equivalent to the statement that for any such coloring there is always a monochromatic triangle (a K_{3}). In fact, it has been shown by A. W. Goodman (1959) that the number of monochromatic triangles is at least 2!

The applet allows to experiment with the problem and its generalizations. To draw an edge, click on one of the nodes, move the cursor to another node, and click there too. If the AutoColor box is checked, the edges are drawn with alternating colors. Otherwise, you can choose color to sraw an edge with by checking either Red or Blue box.

On K_{5} there exist bichromatic colorings without monochromatic K_{3} subgraphs. (Think of five people sitting by a round table such that each of them is friends only with his immediate neighbors.) Therefore, 6 is the smallest number k with the property that, for any bichromatic coloring, K_{k} contains either red K_{3} or blue K_{3}. This is written as

(*) | R(3, 3) = 6, |

(Note that the Friendship Theorem states that *Ramsey number* _{N}, there is either red K_{n} or blue K_{m}. As an example, it is obvious that, for any

It is also known that

(**) | R(4, 3) = 9, R(5, 3) = 14, R(4, 4) = 18, R(6, 3) = 18, R(7, 3) = 23 R(5, 4) = 25. |

The exact value of R(5, 5) is still unknown, except for the bounds

42 <> |

In the 1960s, Gustavus J. Simmons redressed (*) as a game, that became known as the *Game of Sim* [Gardner, p. 111]. In the game, two players alternate drawing edges of two colors. The loser is the player who first creates a triangle of his or her color. Since (*) has been shown to be correct, Sim can't end in a draw. Since K_{6} has 15 edges and 15 is an odd number, the second player has an obvious advantage. However, the game is not quite trivial and several strategies have been published in the 1970s in the *Journal of Recreational Mathematics* and *Mathematics Magazine*.

Martin Gardner mentions an observation by F. Harary that (*) affords at least three other types of games. He classified the SIM as the game of avoidance. In the game of achievement the player to complete a monochromatic triangle first wins. This game is trivial. But the other two are not. In the latter games the play continues until all the edges are drawn, after which the players count the number of triangles of their color. The winner may be the player with the most or fewest number of triangles. These last two games are the hardest to analyze.

Helpful in proving (**) is a recursive inequality:

(1) | R(m, n) ≤ R(m-1, n) + R(m, n-1). |

For the proof [Balakrishnan, **1.98**], introduce

In case R(m-1, n) and R(m, n-1) are both even (1) can be strengthened [Balakrishnan, **1.100**]:

(2) | R(m, n) ≤ R(m-1, n) + R(m, n-1) - 1. |

To see this, set p = R(m-1, n), q = R(m, n-1) and r = p + q. Consider a group _{i} be the number of people known to person I. Since being an acquaintance is a mutual relationship, the sum Sd_{i} of all d_{i}'s is even. However, by our assumption, r is even, so that r-1 is odd. It follows that d_{i} ought to be even for at least one person. For the definiteness sake, suppose d_{1} is even and let M and N be the sets of all people known and, respectively, not known to person 1. Denoting the number of elements in a set X as |X|, _{1},

Thus, for example,

R(4, 3) ≤ R(3, 3) + R(4, 2) = 6 + 4. |

But since both R(3, 3) and R(4, 2) are even, we have a stronger inequality:

R(4, 3) ≤ R(3, 3) + R(4, 2) - 1 = 9. |

To see that R(4, 3) > 8, imagine 8 people sitting at a round table, with each person knowing exactly the two immediate neighbors and the fellow across the table.

By (1),

R(5, 3) ≤ R(4, 3) + R(5, 2) = 9 + 5. |

To see that R(5, 3) > 13, imagine 13 people sitting at a round table such that each person is acquainted only with the fifth person on his left and the fifth person on his right. Under this assumption, there is no 3 mutual acquaintances and no 5 mutual strangers.

R(m, n) with m, n > 2 are known as *nontrivial* Ramsey numbers. There are also generalizations. Let k_{i}, _{i} ≤ m_{1}, ..., C_{t}_{1}, k_{2}, ..., k_{t}; m)-Ramsey_{i}-element subset B such that all m-element subsets of B belong to C_{i}. The smallest such n is called the generalized Ramsey number, _{1}, k_{2}, ..., k_{t}; m).

R(u, v) = R(u, v; 2). To see that, consider X = {1, 2, ..., n} and the collection C of its 2-element subsets. For a partition C = C_{1}C_{2}, think of C_{1} and C_{2} as containing pairs of mutual acquaintances and mutual strangers. If _{1}. In the latter case, a subset B exists with at least v elements, such that all its 2-element subsets belong to C_{2}. This implies that

The existence of R(k_{1}, k_{2}, ..., k_{t}; m) is claimed by *Ramsey's theorem* which is a fundamental part of an extensive *Ramsey theory*. The theory is concerned with the emergence of certain properties in objects as their scale becomes large. As a rather simple example, the pigeonhole principle is equivalent to the statement:

R(k_{1}, k_{2}, ..., k_{t}; 1) = k_{1} + k_{2} + ... + k_{t} - t + 1. |

The Friendship theorem itself has a curious application [Savchev, pp. 146-147, Honsberger, p. 3]. Six random points in space are joined pairwise by 15 line segments. Assume all the segments are of different length. Some segments form triangles. Prove that at least one of the 15 segments serves as the shortest side in one of the triangles it is in, and as the longest side in another. Six points taken by three form 20 triangles. In each, let's color the shortest side in red. It may happen that some of the sides will be painted more than once. Let's color the remaining segments blue. By the Friendship theorem, there is a monochromatic triangle. Since the triangle has a shortest side that had to be colored red, the whole triangle is red. In particular, its longest side is red as well. The fact that it is red means it's the shortest side in some other triangle.

## Reference

- M. Aigner, G. Ziegler,
*Proofs From The BOOK*, Springer, 2000 - V. K. Balakrishnan,
*Theory and Problems of Combinatorics*, Schaum's Outline Series, McGraw-Hill, 1995 - M. Gardner,
*The Colossal Book of Mathematics*, W. W. Norton & Co, 2001 - M. Gardner,
*Knotted Doughnuts and Other Mathematical Entertainments*, W.H.Freeman & Co., 1986. - M. Gardner,
*The Unexpected Hanging and Other Mathematical Diversions*, The University of Chicago Press, 1991 - M. Gardner,
*The Colossal Book of Short Puzzles and Problems*, W. W. Norton & Company, 2006, p. 10 - A. W. Goodman,
__On Sets of Acquaintances and Strangers at Any Party__,*Am Math Monthly*, v. 66, no. 9 (Nov., 1959), 778-783. - P. Hilton, D. Holton, J. Pederson,
*Mathematical Vistas*, Springer, 2002 - R. Honsberger,
*Mathematical Delights*, MAA, 2004 - L. E. Shader,
__Another Strategy for SIM__,*Math Magazine*, v. 51, No. 1 (Jan., 1978), pp. 60-64 - S. Savchev, T. Andreescu,
*Mathematical Miniatures*, MAA, 2003

mr. lordis (filmhoror)18 Maret 2010 23.11

i don't really understad about this article but i think is very good, nice post friend :)

marine blog19 Maret 2010 00.32

bersilaturahmi rutinitas........ salam sukses kawan.....