There are many variants of this problem. The one I am working with is
There are $17$ balls that weigh the same, and $1$ ball that could weigh either heavier or lighter than the other $17$. How many weighs on a balancing scale do you need to determine the odd one out and whether it's heavier or lighter?
The simpler case where you know if the the odd ball out is heavier or lighter can be found in $3$ weighs. The idea is to divide the $18$ balls into groups of $6$, say, $6A$, $6B$, $6C$. Weigh $6A$ and $6B$ on a scale. If they balance each other out, then $6C$ has the odd one out. If they don't balance each other out, and $6A$ is lower on the scale, then $6A$ has the heavier ball, and analogously for $6B$. So it takes a maximum of $1$ weigh to determine the group of $6$ with the heavier ball. Then you can divide this group of $6$ into $3$ groups of $2$, and using the same idea, you can find the odd group of $2$ out with a maximum of $1$ weigh. Then you're left with a group of $2$ and it takes $1$ weigh to determine the heavier ball. So, in total, you need $3$ weigh ins for this case.
But the harder variant of this problem is where you don't know if the odd ball out is heavier or lighter. In this case, I found that you need a maximum of $5$ tries to find the odd one out as well as to determine if it is heavier or lighter, but I have no idea if this is correct, or how to justify that this is the minimum number of maximum number of tries.
The idea is similar to the previous problem. Divide $18$ balls into $6A$, $6B$, $6C$. This time, it takes a maximum of $2$ tries to find the group of $6$. i.e., weigh $6A$ and $6B$ on a scale, if they match, then $6C$ is the odd group out. If $6A$ and $6B$ doesn't match, then we need an additional weigh to determine the odd one out. Hence, $2$ tries.
Now once we found the odd group of $6$, we apply the same idea, which takes another $2$ tries (maximum). Then we're left with a group of $2$. It takes exactly $1$ weigh because you can take $1$ ball from the group of $2$ and weigh it with one of the other $16$ balls that we know are the. If this ball is the same, then the remaining ball is the odd one out. So it takes a maximum of $2+2+1 = 5$ tries to find this odd ball out. We don't need an additional weigh to determine if this remaining ball is heavier or lighter.
This is because when we found the group of $6$, and the subsequent group of $2$, we took the maximum of $2$ tries. If it takes $2$ tries to find the odd group of $6$ out, then that means the 2nd weigh of the $2$ tries allows us to determine if this odd ball out is heavier or lighter.
For example, consider $6A$, $6B$, $6C$ again. Say we first weigh $6A$ and $6B$ and find they don't weigh the same. Then we weigh $6C$ with either $6A$ or $6B$. If we weigh $6A$ with $6C$ and find that $6A$ doesn't match $6C$, then $6A$ is the odd one out, but also if $6A < 6C (6A > 6C)$, then we know $6A$ has a ball that weights less (more).
Is this the most optimal approach or is there a method that takes only $4$ weigh ins? My gut is telling me there should be a $4$ weighing approach.
The $12$-ball variant of the problem and its solution is posted in here. You can see that they apply an analogous approach by breaking the $12$ balls into $3$ groups of $4$, but they apply some interesting mix and matching to find the odd one out in only $3$ moves.
Best Answer
I did not check the solution for the classic $12$ balls version here. But if it works, it trivially leads to a $4$ weighing solution for the $18$ balls case.
Really, given the classic, there is very little extra work to do!
First you weigh $3A$ vs $3B$. If they are unbalanced, say $3A > 3B$, you can find out with $3A$ vs $3C$ (all $3C$ are good) whether the bad ball is heavier or lighter. Then surely you can find the culprit among a group of $3$ with just one more weighing. Total $3$ weighings.
And if $3A = 3B$, then you are reduced to the classic $12$-ball problem which can be solved with $3$ additional weighings, for a total of $4$.
Further thoughts: In fact, $4$ weighings can solve $30$ balls, not just $18$.
In the above, the $3A \neq 3B$ branch always leads to $3$ total weighings, which is wasteful. Imagine you have $9+9+12 = 30$ balls. The first weighing can be $9A$ vs $9B$. If they are unbalanced, again a second $9A$ vs $9C$ (all good) will tell you if the bad one is heavy or light, and then you can use $2$ more weighings to find the culprit among $9$ (tri-nary search), for a total of $4$ weighings.
Even further, years ago I solved a case (an extension to the classic) where $13$ balls (unknown heavy/light) can be solved with $3$ weighings, provided you have access to extra balls known to be good -- IIRC you need $2$ such good extras. This means $9+9+13 = 31$ can be solved with $4$ weighings, coz in the $9A=9B$ case you are indeed left with $13$ suspects but many extra balls known to be good.
I suspect even $31$ is not the limit (for $4$ weighings). When you weigh $9A$ vs $9C$, only two outcomes can happen (since $9A > 9B$). This is very inefficient and further exploitation might be possible...
You probably know the classic bound that with $n$ weighings there are only $3^n$ possible results, so with $n=4, 3^n = 81$, you cannot solve $\ge 41$ balls ($\ge 82$ outcomes). I'm not saying $40$ is achievable, but there is a wide gap between $31$ and $40$...