Searching for a counterfeit coin with b-balance

We consider the classical problem of searching for a heavier coin in a set of n coins, n-1 of which have the same weight. The weighing device is b-balance which is the generalization of two-arms balance. The minimum numbers of weighings are determined exactly for worst-case sequential algorithm, average-case sequential algorithm, worst-case predetermined algorithm, average-case predetermined algorithm.We also investigate the above search model with additional constraint: each weighing is only allowed to use the coins that are still in doubt. We present a worst-case optimal sequential algorithm and an average-case optimal sequential algorithm requiring the minimum numbers of weighings.     

搜索两个不同坏硬币的最优化方法

设n个外观相同的硬币的集合X中含有两个坏硬币，这两个坏硬币的重量彼此不同，但都比好硬币重，而假定好硬币有相同的重量．以g2（n）表示用天平从X中找出两个坏硬币的最少测试次数．本文证明了对任意的n成立［log3（n2）］≤g2（n）≤［log3（n2）］＋1．且对无穷多个n，文中所给的测试过程是最优的．     

搜索四个坏硬币的最优化方法

给出了用天平从ｎ个硬币的集合中搜索出４个坏硬币的最少测试次数的一个估计。     

两伪币的搜索问题

考虑两伪币的搜索问题:给定外观相同的n个硬币,其中有两个比较重的伪币,通过等臂天平在尽可能少的称量次数下去找出两个伪币.L~((2))(n)为最坏情况下找到两伪币的最小称量步数.对于任意的n≥2,满足log_3(_2~n)]≤L~((2))(n)≤[log_3(_2~n)]+1.猜想信息理论下界均可达.通过一个新的方法扩大了满足信息理论下界的n的取值范围.     

Searching for counterfeit coins

The well-known counterfeit problem asks for the minimum number of weighings necessary to determine all fake coins in a given set ofn coins. We derive a new upper bound when we know that at mostd coins are defective, improving a previous result of L. Pyber.     

Two counterfeit coins

We consider the problem of ascertaining the minimum number of weighings which suffice to determine the counterfeit (heavier) coins in a set of n coins of the same appearance, given a balance scale and the information that there are exactly two heavier coins present. An optimal procedure is constructed for infinitely many n's, and for all other n's a lower bound and an upper bound for the maximum number of steps of an optimal precedure are determined which differ by just one unit. Some results of Cairns are improved, and his conjecture at the end of [3] is proved in a slightly modified form.     

Construction of Weighing Matrices W(17, 9) Having the Intersection Number 8

It is unknown( [1], [2], [4] ) whether there exists a weighing matrix W(17,9) or not. The intersection number of W(17,9) is 6 or 8. We completed the classification of weighing matrices W(17, 9) having the intersection number 8. These matrices are classified into 925 non-equivalent classes. We shall show eight representative weighing matrices only together with their automorphism groups and g-distributions. Of these eight matrices, two have the same g-distribution.     

New weighing matrices constructed from two circulant submatrices

A number of new weighing matrices constructed from two circulants and via a direct sum construction are presented, thus resolving several open cases for weighing matrices as these are listed in the second edition of the Handbook of Combinatorial Designs.     

New Infinite Classes of Orthogonal Designs

In this paper we use some results on weighing matrices W (2 n ,9) constructed using two circulants to obtain infinite classes of orthogonal designs. We also present a method that is used to construct two directed sequences of length n and specific type. We apply this method to W (2 n , 9) and we obtain many new pairs of directed sequences of length n and type $(9 \cdot 2^m,9 \cdot 2^m), \ m=0,1,2,3.$ Using these directed sequences we can obtain many new infinite classes of weighing matrices W (2 n , k ), and orthogonal designs OD (2 n ; a,b) constructed from two circulants.     

How to find many counterfeit coins?

We propose an algorithm for findingm defective coins, that uses at most + 15m weighings on a balance scale, wheren is the number of all coins.