握手问题

Handshake Problem

在这篇文章中我们提出并解决一个称为握手问题的组合问题。该问题是受马丁·加德纳在[1]中提出的外科医生问题的启发而提出的。

In this paper, we propose and solve a combinatorial optimization problem, called handshake problem, motivated by the surgeon problem proposed by Martin Gardner in his book Aha! Insight. The problem is as follow. In an area, there is a strange contagious disease. A person with the disease carry bacteria on his hand. n persons from the area want to shake hands with each other. What makes it difficult is that no one has the knowledge about whether a person has the disease or not. To prevent possible spread of the bacteria among them, the persons decide to use gloves in their handshakes. How many pairs of gloves are required if each two persons must shake hands once, and there does not exist any possibility of spread of the bacteria among the personsLet f(n) denote the minimum pairs of gloves. The main result of the paper is the following theorem.Theorem (1) f(1) = 0, f(2) = 1, f(3)=2;(2) f(n) = [2n/3], for each n≥4.