Optimal search procedure on coin-weighing problem

The following coin-weighing problem is considered: suppose among the given n coins there are two counterfeit coins, which are either heavier or lighter than other n-2 good coins, this is not known beforehand. The aim is to find an optimal algorithm which identifies these two counterfeit coins using as few weighings as possible. It is proved that the minimal number of weighings is either equal to the information-theoretic lower bound, or exceeds it by 1. Moreover, the information-theoretic lower bound are achievable for even number of weighings; for odd number of weighings, our optimal interval is very close to the theoretic optimal interval. The ideas and techniques of this paper can be used to solve other search models.