Ambassadors at a Round Table
2n ambassadors are invited to a banquet. Every ambassador has at most n-1 enemies. Prove that the ambassadors can be seated around a table, so that nobody sits next to an enemy [Engel, p. 5].
The applet below may help gain insight into the problem. A number of small circles - call them vertices - representing ambassadors are placed in a regular fashion around a big circle. Vertices corresponding to unfriendly ambassadors are joined by - what else? - edges. Thus the problem is well represented by a graph. A graph, as a collection of nodes and edges, does not depend on its particular depiction as a set of circles joined by straight line segments. However, for the problem at hand, we mix graph-theoretic and geometric notions. The nodes of a graph are situated at the vertices of a regular polygon, with some diagonals and sides drawn. Is it possible to rearrange the vertices so that the resulting polygon will not show any of its sides?
The applet allows one to swap any two vertices and, along the way, all the vertices in-between the two. Click on one vertex and then on the second one. All vertices starting with the first and ending with the second selection (counting counterclockwise) will be swivelled around the angle bisector of the so chosen circular sector.
| |
|
Discussion
References
- A. Engel, Problem-Solving Strategies, Springer, 1998
|Activities|
|Contact|
|Front page|
|Contents|
|Algebra|
|Eye opener|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
2n ambassadors are invited to a banquet. Every ambassador has at most n-1 enemies. Prove that the ambassadors can be seated around a table, so that nobody sits next to an enemy
The condition stated in the problem is sufficient (and this is what we are required to prove) but is not necessary: It is quite possible to imagine a situation where each of the 2n ambassadors has more than n-1 enemies whereas they are seated so each is only next to one's friendly ambassadors. For example, this is the case where in the polygonal representation all the diagonals but none of the sides have been drawn. (We assume that the ambassadors are friendly - at least externally - unless they are from enemy states. Also, we do not assume anything as to the transitivity of the enmity relationship. An enemy of one's enemy need not be one's friend. On the other hand, the enmity relationship is symmetric, i.e. one can't be a friend of a fellow who perceives him as an enemy. This is what allows a graphical representation of the problem.)
The applet assists in working out an algorithmic solution. First seat the ambassadors anyhow and count the number of mishaps where the two neighbors are enemies. Then make up a procedure whose application to a seating reduces the number of such pairs by at least one. If the procedure can be applied to any seating subject to the conditions of the problem then, obviously, after a repeated application we shall arrive at a seating with no enemy neighbors, as required in the problem.
| |
|
Let AB be such a pair of hostile neighbors. Starting with B traverse the present seating away from A and look for a pair B'A' such that B' is not an A's enemy while A' is not an enemy of B. If there is such a pair, we may turn the whole "arc" BB'. In the new seating the number of hostile pairs will be one less than before.
Now, why does such a lucky pair B'A' exist? By the conditions of the problem, A has at most n-1 enemies leaving at least n friends (not counting himself.) These have n neighbors to their right. As B also has at most n-1 enemies, one of these neighbors, say B', is bound to be "B-friendly" (counterclockwise) neighbor A'. As was already explained, being able to find such a pair solves the problem.
|Activities|
|Contact|
|Front page|
|Contents|
|Algebra|
|Eye opener|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
| 
