0
$\begingroup$

We are given $N$ coins and a set of scales. We are told that there is a defective coin and we know whether it is lighter or heavier than the others. Our goal is to identify it in as few weighings as possible. I am trying to prove that we can identify it in a sample of up to $3^n$ coins in no more the $n$ measurements. When $N$ is a power of $3$, say $N=3^n$, there is a well-known solution based on an induction procedure:

We split the $N$ coins into three equal groups of size $3^{n-1}$ and compare any two subgroups on the scales. We immediately deduce which of the three subgroups contains the defective coin and therefore are left with a group of $3^{n-1}$ coins. Carrying on in the same way it takes $n$ weighings to go from a group of $3^n$ coins to a single coin.

I would like to generalise this to the case where $N$ is not a power of $3$, i.e. $3^{n-1}<N=3^{n-1}+M<3^n$, where $M$ is such that $0<M<3^n-3^{n-1}$. My first approach has been to look at some examples. When $N=90$, we see that $90=81+9$, so initially divide the coins into three subgroups of size $27$ and keep $M=9$ on the side. We compare any two of the three subgroups of size $27$ and. If the scales don't balance then we are left with $27$ coins which will just require an additional $3$ weighings. Otherwise the defective coin is either in the third group of $27$ or in the group of $M=9$. We then divide the $27$ into $3$ groups of $9$ and proceed in similar fashion to previously. This will take up to $5$ total weighings.

My problem is, however, when I look at examples like $N=242$. Should we just similarly use $3$ subgroups of size $27$ and a rest of $M=161$? My feeling is that this is not correct and we somehow need to make use of the ternary representation of the sample size $N$. In this case $N=22222$ in base $3$, but I am not sure how to proceed in terms of coin comparisons. Any ideas of references to literature would be greatly appreciated.

$\endgroup$
1
$\begingroup$

If the number of coins is between powers of $3$, you have flexibility in how you group them. If you have $n$ coins with $3^{k-1} \lt n \lt 3^k$ you will need $k$ weighings. You need to make sure that no group gets larger than the next lower power of $3$. If you have $n=242$ coins you should put $81$ on each pan and reserve the other $80$. If you only put $27$ on each pan and they balance, you still have $188$ left and that is too many to do in $4$ weighings. If you have $n=90$ you just need to get all the groups to $81$ or below, so could weigh any number from $5$ to $45$ per side and still be done in $5$ weighings.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I was wondering if it was possible to formulate this in terms of the ternary representation of the sample size $N$. For example $242=2\times3^4+2\times3^3+2\times3^2+2\times3^1+2\times3^0$, and $90=3^4+3^2$. Depending on whether the highest trit is set to $2$ or $1$, we use $2$ subgroups of $3^4$ in the first case plus a rest (which shall be less than $3^4$) and $3$ subgroups of $3^3$ plus a rest of $9$ in the second case. Maybe this is not very clear, but I believe there is something to be said according to this ternary representation. $\endgroup$ – user223935 Mar 8 '16 at 0:34
  • 1
    $\begingroup$ You can do that if you want, but it is not required. As I said, you just need all three batches to be below the next power of $3$ to make sure you can get done in the minimum number of weighings. The further you are from a power of $3$, the more flexibility there is in choosing how many coins to weigh. $\endgroup$ – Ross Millikan Mar 8 '16 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.