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.