*** Note: this problem has a lot of variations, and it takes me a long time to truly understand some steps (I hope I understand it thoroughly) ***

- First of all, we can just disregard the condition that there is a ball a weight either heavier or lighter.
   - we go back to the most basic form: how to find out the heavier ball in a set of balls?
   - the most basic case would be that there are 3 balls, since with three balls we can use two balls as majority to compare the weight.
   - we already know there is one heavier weight. Thus, it only takes 1 turn to find out the ball.

- How?
   - we compare the first and the second ball. Once we find where the imbalance is, we just select the heaiver one as the answer.
   - if they are equal, the last ball will be the heavier one.

- Oh that is quite simple, you may say, and it is easy to extend this relatonship to more balls:
   - for 9 balls, we just need to see 3 balls as "1" ball, split them into three groups consisting of 3 balls, and find the group with heaiver weight, one weighing.
   - then, it is like recursion ---> we "inherit" the one weighing from the 3 balls base case, so we only need to weigh it one more times.
   - the answer is 2 weighing.

- It is not difficult to extend it to other multiples of 3, like 27, 81, 243... the answer is just log₃n, and n is the number.
   - Note: here, log₃n is the least number of weighing. If there are, for example, 8 balls, we still need to do 2 weighings. since 8 > 3.
   - This rule can apply to find out the lighter ball too.

- That's nice. However, now we don't know whether the ball is heavier or lighter. What should we do?
   - There are twelve balls. If we split them in a half, 6 balls vs. 6 balls, and then 3 balls vs. 3 balls, ... we will never know which part is heavier or lighter in only 3 steps. One side can be light, but at the same time the other side can be heavier.

- What if we keep some parts the same in two comparisons, since they will act like a 'majority standard'?
   - for example, we still split 12 balls into 3 groups, A,B,and C, but we just do cross comparsion.
   - we use A to compare B first.
   - If we do that, we will have three situations:
   1. A = B.
     - that means that A, B are all standardized, and we need to check C.
   2. A > B | A < B.
     - that means now we know where the imbalance is ---> A or B, but there are still too many probabilities.

- Now we get stuck. How do we know more information about A and B, while we can use the previous conclusion that we know one is heavier?
   - we rotate the parts of the groups.
   - we split A, B and C into {1,3}, {1,3} and {1,3} ---> two internal piles.
   - we just use the 1 from group A combining with 3 from group B, and compare it to the 1 from group B pairing with the 3 from group C.

- Now we have three situations again. The 1,2,3 in the following denote the number of group, and A,B,C,D are the specific internal balls.
   1. {1A, 2B, 2C, 2D} = {2A, 3B, 3C, 3D}
     - that means the strange ball only exists in {1B, 1C, 1D}
     - in the previous step, we already know A > B or A < B.
     - combining with this condition, for {1B, 1C, 1D}, we only need one weighing ---> we know this from the beginning.

   2. {1A, 2B, 2C, 2D} < {2A, 3B, 3C, 3D}
     - if in the previous step, A > B, we know that know the sign reverses.
     - 1A cannot be the odd, and 2A cannot be the odd either.
     - If they have diferent weights, we will follow the same inequality.
     - Combining with the previous step, the problem will be located to {2B,2C,2D} ---> they are smaller.

     - but if sign doesn't change, we will know either 1A or 2A has problem, and the inequality in the last step has already told us the magnitude.
     - we just use a ball we know is normal (e.g. a ball fro group 3) to compare it with one ball.

   3. {1A, 2B, 2C, 2D} <>{2A, 3B, 3C, 3D}
   - it is just the same step as in 2, but the signs are reversed.

- Why do we split the pile into three piles?
   - we still want to use the results when we know one is heavier, and we want to use them in a MAXIMUM level.
- Why do we split 4 into 1 and 3?
- we want to use our previous conclusion in a MAXIMUM level, so the subgroups must be a number in the geometric sequence of 3.

- Now it becomes clear. We want to use the multiples of 3, and the maximum we can get in this situation is 27, so we have four groups, three having 27 and one having 9.

- We still want to use log₃n, so we just split 90 into 81 and 9.
- We denote the three groups as A, B, C, and D and we compare 27A and 27B, 27B and 27C.
   1. 27A = 27B, 27B = 27C
      - the odd is in 9D.
      - we use 9A to compare 9D, and then we will know the magnitude of 9D. Then, it only takes us 2 more weighings.

   2. 27A = 27B, 27B > 27C
      - we know that 27C is smaller, and log₃27 = 3, we need 3 more weighings.
      - that also works for other situations, since in this way we will know the magnitude of the group containing the odd one.

- Thus, we need 5 weighings.

- Is there any other way to interpret?

- From my understanding, the least number of weighning can be done in this way:
   - we just split them into three, and count the length of 3's geometric sequence.
   - and we add 1 ---> because in the beginning we must do two comparisons before we enter the rotation recursion.
   - we need something to compare, so we add 1 just to count the number of comparisons before the rotation.
   - however, if we have remainders in the subgroup, that means the current count is not enough, and we add 1 too.
      - e.g. 90 ---> we split it into 30, and 30 can be splited into {{1,3,9},17}, we are left with 17 coins, so we need len({1,3,9}) + 1 + 1 = 5 comparisons.

*** Note: I have written a simple code to generalize this problem. If you want to check, please click on this link:
https://github.com/Kexin996/brainteaser/blob/master/fake_coins.py