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.

 

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Ambassadors at a Round Table


What if applet does not run?

Discussion

References

  1. A. Engel, Problem-Solving Strategies, Springer, 1998

|Activities| |Contact| |Front page| |Contents| |Algebra| |Eye opener|

Copyright © 1996-2017 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.

 

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Ambassadors at a Round Table


What if applet does not run?

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.


Related material
Read more...

  • Expansion of Integers in an Integer Base
  • Base (Binary, Decimal, etc.) Converter
  • Base Converter
  • Implementation of Base Conversion Algorithms
  • Conversion of Fractions in Various Bases
  • Scoring: the simplest of the impartial games
  • History of the Binary System
  • Calculation of the Digits of pi by the Spigot Algorithm of Rabinowitz and Wagon
  • Addition and Multiplication Tables in Various Bases
  • |Activities| |Contact| |Front page| |Contents| |Algebra| |Eye opener|

    Copyright © 1996-2017 Alexander Bogomolny

     62686632

    Search by google: