Skip to main content
added 8 characters in body
Source Link
Julian Rosen
  • 14.3k
  • 1
  • 53
  • 94

There is some literature on this problem. Lindström [2] and Cantor and Mills [1] independently give weighing strategies using 7 weighings, with the property that no weighing depends on the results of previous weighings. More generally, these papers prove that for every positive integer $k$, $2^{k}-1$ weighings suffice to determine which of $2^{k-1}k$ coins have which weights.

The weighing strategies are constructed recursively. The general process is a little involvedintricate, so I won't try to describe it here. If I understood everything correctly, the strategy given in [1] for 12 coins suggests putting the following coins on the scale:

  • 1, 2, 4, 5, 7, 9, 11
  • 2, 3, 5, 6, 12
  • 1, 3, 5, 7, 8, 10
  • 5, 6, 8, 9
  • 1, 2, 4, 6, 8, 10
  • 2, 3, 8, 9
  • 1, 3, 6, 9

$\,$

[1] Cantor, David G. and Mills, W.H.. Determination of a subset from certain combinatorial properties. Canad. J. Math. 18 1966 42-48

[2] Lindström, Bernt. On a combinatorial problem in number theory. Canad. Math. Bull. 8 1965 477-490

There is some literature on this problem. Lindström [2] and Cantor and Mills [1] independently give weighing strategies using 7 weighings, with the property that no weighing depends on the results of previous weighings. More generally, these papers prove that for every positive integer $k$, $2^{k}-1$ weighings suffice to determine which of $2^{k-1}k$ coins have which weights.

The weighing strategies are constructed recursively. The general process is a little involved, so I won't try to describe it here. If I understood everything correctly, the strategy given in [1] for 12 coins suggests putting the following coins on the scale:

  • 1, 2, 4, 5, 7, 9, 11
  • 2, 3, 5, 6, 12
  • 1, 3, 5, 7, 8, 10
  • 5, 6, 8, 9
  • 1, 2, 4, 6, 8, 10
  • 2, 3, 8, 9
  • 1, 3, 6, 9

[1] Cantor, David G. and Mills, W.H.. Determination of a subset from certain combinatorial properties. Canad. J. Math. 18 1966 42-48

[2] Lindström, Bernt. On a combinatorial problem in number theory. Canad. Math. Bull. 8 1965 477-490

There is some literature on this problem. Lindström [2] and Cantor and Mills [1] independently give weighing strategies using 7 weighings, with the property that no weighing depends on the results of previous weighings. More generally, these papers prove that for every positive integer $k$, $2^{k}-1$ weighings suffice to determine which of $2^{k-1}k$ coins have which weights.

The weighing strategies are constructed recursively. The general process is a little intricate, so I won't try to describe it here. If I understood everything correctly, the strategy given in [1] for 12 coins suggests putting the following coins on the scale:

  • 1, 2, 4, 5, 7, 9, 11
  • 2, 3, 5, 6, 12
  • 1, 3, 5, 7, 8, 10
  • 5, 6, 8, 9
  • 1, 2, 4, 6, 8, 10
  • 2, 3, 8, 9
  • 1, 3, 6, 9

$\,$

[1] Cantor, David G. and Mills, W.H.. Determination of a subset from certain combinatorial properties. Canad. J. Math. 18 1966 42-48

[2] Lindström, Bernt. On a combinatorial problem in number theory. Canad. Math. Bull. 8 1965 477-490

Source Link
Julian Rosen
  • 14.3k
  • 1
  • 53
  • 94

There is some literature on this problem. Lindström [2] and Cantor and Mills [1] independently give weighing strategies using 7 weighings, with the property that no weighing depends on the results of previous weighings. More generally, these papers prove that for every positive integer $k$, $2^{k}-1$ weighings suffice to determine which of $2^{k-1}k$ coins have which weights.

The weighing strategies are constructed recursively. The general process is a little involved, so I won't try to describe it here. If I understood everything correctly, the strategy given in [1] for 12 coins suggests putting the following coins on the scale:

  • 1, 2, 4, 5, 7, 9, 11
  • 2, 3, 5, 6, 12
  • 1, 3, 5, 7, 8, 10
  • 5, 6, 8, 9
  • 1, 2, 4, 6, 8, 10
  • 2, 3, 8, 9
  • 1, 3, 6, 9

[1] Cantor, David G. and Mills, W.H.. Determination of a subset from certain combinatorial properties. Canad. J. Math. 18 1966 42-48

[2] Lindström, Bernt. On a combinatorial problem in number theory. Canad. Math. Bull. 8 1965 477-490