### Abstract

Given a set of m coins out of a collection of coins of k unknown distinct weights, we wish to decide if all the m given coins have the same weight or not using the minimum possible number of weighings in a regular balance beam. Let m(n, k) denote the maximum possible number of coins for which the problem can be solved in n weighings. It is known that m(n, 2) = n^{(1/2+o(1))n}. Here we determine the asymptotic behavior of m(n, k) for larger values of k. Surprisingly it turns out that for all 3 ≤ k ≤ n + 1, m(n, k) is much smaller than m(n, 2) and satisfies m(n, k) = Θ(n log n/log k).

Original language | English (US) |
---|---|

Pages (from-to) | 162-176 |

Number of pages | 15 |

Journal | Journal of Algorithms |

Volume | 25 |

Issue number | 1 |

DOIs | |

State | Published - Oct 1997 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Coins with Arbitrary Weights'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Kozlov, D. N. (1997). Coins with Arbitrary Weights.

*Journal of Algorithms*,*25*(1), 162-176. https://doi.org/10.1006/jagm.1997.0871