How to find the counterfeit coin?

Question

You are the treasurer and you have received information that a counterfeit coin has entered the treasury. All you know is that the counterfeit coin is lighter than the original.

Knowing how many coins you have in total and using only a balance scale, you need to determine the minimum number of weighings to determine which coin is counterfeit before it disappears from the treasury.

---

Your function must accept only one integer (which will be more than 1) and must output 2 things:

• the minimum number of weighings without lucky chances
• steps on how to find counterfeit coin

Step - a moment when you use balance scale

Without lucky chances means that your number must be the maximum among the minimum steps required. For example let's say that you have 5 coins:

1. You can split them to 3 groups by 2, 2 and 1 (this isn't a step)

2. Weighing the groups 2 and 2 (this is a step)

   2.1 If they are equal then the remaining coin is counterfeit

   2.2. If one of the groups is lighter then the counterfeit coin is in that group

3. Weigh each remaining coin (this is a step)

   3.1 The coin that is lighter is the counterfeit coin

So the minimum number of weighings without lucky chances is 2 but with lucky chances it is 1 because we can find the counterfeit coin at step 2.

The output steps must be easy to understand. Please add a detailed explanation of how to read the output steps. For example the previous example can be represented like this:

[5(2,2) 2(1,1)] - 2

Where the:

• [] - means the possible scenarios
• x(y,z) - x means remaining coins after previous step, (y,z) means how many coins (from x) on each side of balance scale I am weighing
• 'space' - means the next step/scenario
• - x - means the minimum number of weighings without lucky chances

Here is an example with 8. The output can be shown like this:

[8(3,3) [2(1,1)] [3(1,1)]] - 2

After first step we have two different scenarios because:

1. if the 2 groups of 3 are equal then the counterfeit coin is in the group of 2 coins
2. if the 2 groups of 3 aren't equal then the counterfeit coin is on one of the groups of 3

It is enough to to weigh only 2 different coins in each scenario to find the counterfeit coin. Regardless of the scenario, the minimum number of weighings without lucky chances is 2

Here are the possible outputs for 2 to 9 coins:

2 --> [2(1,1)] - 1

3 --> [3(1,1)] - 1

4 --> [4(2,2) 2(1,1)] - 2

5 --> [5(2,2) 2(1,1)] - 2

6 --> [6(2,2) 2(1,1)] - 2

7 --> [7(3,3) 3(1,1)] - 2

8 --> [8(3,3) [2(1,1)] [3(1,1)]] - 2

9 --> [9(3,3) 3(1,1)] - 2

You can output any of the possible steps of how to find the counterfeit coin. For example for 10 we have 5 different scenarios. You can output any of them:

10 --> [10(5,5) 5(2,2) 2(1,1)] - 3
10 --> [10(4,4) [2(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(3,3) [3(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(2,2) [2(1,1)] [6(3,3) 3(1,1)]] - 3
10 --> [10(1,1) 8(3,3) [2(1,1)] [3(1,1)]] - 3

The shortest code in each programming language wins!

Answer 1

Python, 77 bytes

-4 from @TheThonnu

f=lambda n:n<4and[1]or(m:=-~n//3,p:=n-2*m,f(m),f(p),max(f(m)[-1],f(p)[-1])+1)

Attempt This Online!

If input is 2 or 3, returns [1] meaning only one trivial weighing is required, otherwise returns a 5-tuple (number of coins to weigh on each side at this step, number of coins to set aside at this step, steps to follow with the lighter side of coins if there was a lighter side, steps to follow with the set-aside pile if the scale balanced, worst-case number of steps required). Naturally the third and fourth elements of the tuple recurse.

Answer 2

Charcoal, 44 bytes

⊞υＮＷ⊖⌈υ«≔⊕÷⊖ι³θ≔⁺⁻υ⟦⊕ι⟧⟦θ⁻⊕ι⊗θ⟧υ⟦⪫⟦⊕ιθＬ↨ι³⟧ 

Try it online! Link is to verbose version of code. Outputs sets of three integers: coins left, coins to weigh (per side), worst case number of remaining weighings. Explanation: Inspired by @ParclyTaxel's Python answer.

⊞υＮ

Start with n coins.

Ｗ⊖⌈υ«

Repeat until there is only 1 coin left.

≔⊕÷⊖ι³θ

Calculate how many coins to weigh.

≔⁺⁻υ⟦⊕ι⟧⟦θ⁻⊕ι⊗θ⟧υ

Update the set of possible numbers of remaining coins.

⟦⪫⟦⊕ιθＬ↨ι³⟧ 

Output the coins left, coins to weigh and steps left.

Answer 3

Mathematica, 106 bytes

Modified from @Parcly Taxel's answer

---

Golfded version, try it online!

Module[{m,p,fm,fp,maxF},If[n<4,{1},m=-⌈BitNot[n]/3⌉;p=n-2*m;{m,p,f@m,f@p,Max[Last@*f@m,Last@*f@p]+1}]]

Ungolfed version

f[n_] := Module[
  {m, p, fm, fp, maxF},
  If[n < 4,
    {1},
    m = -Ceiling[BitNot[n]/3];
    p = n - 2*m;
    fm = f[m];
    fp = f[p];
    maxF = Max[Last[fm], Last[fp]] + 1;
    {m, p, fm, fp, maxF}
  ]
]


f[73]//Print

Answer 4

Python, 2551 bytes,

import math

def find_counterfeit_coin(num_coins):
    steps = []
    
    # Base case
    if num_coins == 2:
        steps.append((2, (1, 1)))
        return 1, steps
    
    # Determine the largest power of 3 less than num_coins
    power = math.floor(math.log(num_coins - 1, 3))
    group_size = 3 ** power
    
    # First weighing
    remaining_coins = num_coins
    while remaining_coins > 2 * group_size:
        steps.append((remaining_coins, (group_size, group_size)))
        remaining_coins -= 2 * group_size
    
    # Split remaining coins into groups of size group_size or less
    group_sizes = []
    while remaining_coins > group_size:
        group_sizes.append(group_size)
        remaining_coins -= group_size
    if remaining_coins > 0:
        group_sizes.append(remaining_coins)
    
    # Weigh each group
    for group in group_sizes:
        if group == group_size:
            steps.append((group, (group_size, group_size)))
        else:
            steps.append((group, (1, 1)))
    
    # Determine which group contains the counterfeit coin
    if len(group_sizes) == 1:
        num_weighings = power + 1
        return num_weighings, steps
    
    elif len(group_sizes) == 2:
        if group_sizes[0] == group_sizes[1]:
            num_weighings = power + 1
            return num_weighings, steps
        else:
            num_weighings = power + 2
            steps.append((group_sizes[0], (1, 1)))
            return num_weighings, steps
    
    else:
        # Combine two groups of equal size to create a larger group
        combined_group_size = group_size * 2
        combined_groups = [sum(group_sizes[i:i+2]) for i in range(0, len(group_sizes), 2)]
        
        # Recursively find the counterfeit coin in the larger group
        recursive_weighings, recursive_steps = find_counterfeit_coin(sum(group_sizes))
        num_weighings = power + recursive_weighings
        
        # Add steps for weighing the smaller groups
        for group in combined_groups:
            steps.append((group, (1, 1)))
        
        # Add steps from recursive call
        steps += recursive_steps
        
        # Weigh the two groups that produced the combined group
        for i in range(0, len(group_sizes), 2):
            if group_sizes[i] == group_sizes[i+1]:
                steps.append((combined_group_size, (group_sizes[i], group_sizes[i+1])))
            else:
                steps.append((combined_group_size, (group_sizes[i], combined_group_size - group_sizes[i])))
        
        return num_weighings, steps

Attempt This Online!

---

Though it can be considered as an algorithm, it is a pathway for others to write short code from it.

This solution uses a recursive approach to find the minimum number of weighings required to find the counterfeit coin. The algorithm works by dividing the coins into groups and weighing the groups against each other, gradually reducing the number of remaining coins until the counterfeit coin is found. The number of groups and their sizes are chosen so that the maximum number of coins are weighed at each step.

The output of the function is a tuple containing the minimum number of weighings and a list of tuples representing the steps taken to find the counterfeit coin. Each tuple in the list represents a weighing, and contains the number of coins weighed and the sizes of the groups weighed against each other. The steps can be interpreted as a tree, where each level represents