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.