3
$\begingroup$

Consider the following problem:

You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can be in a different order). Using balance scales (the outcomes are $>$, $=$ or $<$) at most $k$ times, determine whether the labels are correct.

I'm not exactly interested in how to solve the problem: the original problem was for $n=6$ and $k=2$, and I know solutions. What I'm interested in is the following: when I heard the problem, I first tried to determine whether a solution even exists from the information-theoretic standpoint. I.e. is the amount of information revealed by $k$ weighings even potentially enough? I don't know how to approach it.

For example, for $n=6$ and $k=2$ there exist $2$ solutions:

compare $1,2,3$ with $6$ and then compare $3,5$ with $1,6$
compare $1,3$ with $5$ and then compare $1,2,5$ with $3,6$

But if we estimate the amount of information naively, then we conclude that with $2$ weighings we can only distinguish $3^k=9$ permutations, which is much less than required $6!$.

Improve this question
$\endgroup$
5
  • $\begingroup$ You obviously don't need to distinguish all 6! permutations, because you only need to know if the permutation is 1, 2, 3, 4, 5, 6 or not. Still, a really interesting problem. $\endgroup$
    – gnasher729
    Sep 30, 2020 at 19:57
  • $\begingroup$ Just realised: If you know the coins have all different weights from 1 to n in unknown order, then you can also "sort" the array in O(n). $\endgroup$
    – gnasher729
    Sep 30, 2020 at 22:13
  • $\begingroup$ Do you have a name or a source for the original problem? I find it quite interesting. $\endgroup$
    – Tassle
    Nov 1, 2020 at 19:10
  • $\begingroup$ @Tassle, sorry, it was from personal communication. I heard it was asked at some show. $\endgroup$
    – user114966
    Nov 2, 2020 at 5:09
  • $\begingroup$ @Dmitry Ok, thanks :) $\endgroup$
    – Tassle
    Nov 2, 2020 at 10:49

2 Answers 2

Reset to default
0
$\begingroup$

You don't need to distinguish n! permutations. You only need to decide whether you have one particular permutation or not.

You start with a set of n! possible permutation. Then you make a measurement, and some permutations in that set are compatible with your measurement, and some are not. So you replace the set of permutations with one that is compatible with your measurement.

For sorting, your measurement is a comparison of two elements. What you need to achieve is that no matter what the outcome is, you are finally left with a set containing one permutation only. To achieve this, you will try to find a comparison that splits your set into two halves that are as close together in size as possible, in case the outcome of the comparison leaves you with the bigger set.

For your problem, you just need to decide whether the permutation (1, 2, 3, ..., n) is in the set of permutations compatible with your measurements or not. You will therefore make a measurement where one of the two possible outcomes means that (1, 2, 3, ..., n) is in your set, and as few other permutations as possible. So you want to split the set as unevenly as possible.

That's what you did. Comparing (1, 2, 3) against 6 means that only twelve permutations including the perfectly ordered one will be compatible with the result: (1, 2, 3) can be ordered in six ways, and (4, 5) can be ordered in two ways. If the comparison is not equal, then there are 708 permutations compatible with that, but that is fine since you have your answer.

Obviously each coin except one must be part of some weighing (if you leave out two coins you can't know if they are in the right order). If you had a limit like "at most four coins can be weighed" that would give you a lower bound. Since you are allowed to weigh all coins in one measurement you'd have to come up with something more clever to find a useful lower bound.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I see, so a possible bound will be $$k \ge \log_{n! / s} n!$$ where $s$ is the smallest surviving set after the first comparison? $\endgroup$
    – user114966
    Sep 30, 2020 at 20:57
1
$\begingroup$

I don't think information theory is going to be useful here. From $k$ weighings, you obtain up to $k \lg 3$ bits of information. The output of the algorithm is binary: either "yes, the labels are correct" or "no they are not", which requires only a single bit to encode. Thus, a naive information-theoretic bound will say that as long as $k \lg 3 \ge 1$, you might have enough information to decide.

There is no requirement to distinguish all $n!$ permutations. There are many cases where I can tell that the labels are incorrect without knowing what are the correct labels.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sometimes you can show that in order to know the answer, you have to be certain of some side information, and that could be used to give an information-theoretic lower bound. $\endgroup$
    – Yuval Filmus
    Sep 30, 2020 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.