# Defective coin weighing problem and ternary representation when number of coins is not a power of 3

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.

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.
• 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. – user223935 Mar 8 '16 at 0:34
• 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. – Ross Millikan Mar 8 '16 at 2:08