mathematics - Lots of Gold Stacks and a Balance Scale

You are given X amount of stacks of golden coins, each stack consisting of ten (10) golden coins and a digital balance scale with perfect precision that shows how much difference between weights you put on. For example, if you put 10 kg on the left side and 20 kg on the other side, it will show -10, otherwise +10.

You know that all X stacks of coins are made from gold and all their weights (gold coins and stacks) are the same except one stack which has fake heavier golden coins inside. Fake coins have the same weights among themselves as well.

So you have only 3 tries on the digital balance scale, what is the maximum amount of stacks possible that guarantee to find the fake stack after 3 tries on balance?

Note: You can take/put back any amount of coins from/to any stack.

Answer

The greatest X for which you can find the stack with the fake coins in 3 weighings is:

7491 stacks.

Unfortunately, the strategy isn't as easy to describe as the one in my previous answer (you can read it in the edit history if it helps understanding this one). Here it is:

To get this number of stacks, we will need to abandon the thought of finding the exact weight of the fake coins immediately. Every different weighing result can be described with a triple of 3 integers: $(A,B,C)$, denoting how many times the difference between the weight of a fake and a real coin appeared in each weighing ($-10 \le A,B,C \le 10$). Our weighing procedure has to associate any such result to a unique stack.

However, we have a huge issue in that we don't know what the weight of a fake coin is, so we can't necessarily associate a result of our weighing to an A,B,C triple uniquely. For instance, if all 3 weighings come out as +10, does that mean that we put 10 fake coins in the right on all weighings, or does it mean that a single fake coin weighs 10 more than a real coin? There's no way to tell. More generally, if $g = gcd(A,B,C) \ne 1$, then the results of $(A,B,C)$ and $(A/g, B/g, C/g)$ are indistinguishable. Because of that, let's just focus on triples of integers such that $gcd(A,B,C)=1$.

An exhaustive search shows me there are 7490 such triples, plus one for the triple (0,0,0). Our strategy is then to associate each stack with one of these triples, and place as many fake coins as necessary to produce the given result. For example, for the stack associated with the triple (-10, 5, 3), you would place 10 coins in the left pan in the first weighing, 5 coins in the right pan in the second weighing, and 3 coins in the right pan in the third weighing.

Here is the full list of the weighings you should make: https://gist.github.com/anonymous/c6688386dd4d9aa0a1ae31f0f53e94f5

An example on how to interpret the weighing results:

If the results are, say, 48.3kg, -32.2kg and 64.4kg, do the following to convert it to a triple: divide all of them by the smallest one, obtaining a triple of rational numbers (3/2, -1, 2), then multiply all numbers by the LCM of the denominators, getting the triple (3, -2, 4). Then look at the table to check which stack had 3 coins in the right pan for the first weighing, 2 coins in the left pan for the second weighing, and 4 coins in the right pan for the last weighing. This stack is your fake.

To brute-force find the selections (a list of the tuples) in the generic case of a given stack size and some number of weighings (>=2) using Python:

from fractions import gcd
from itertools import product

def getSelections(stackSize=10, weighings=3):
    res = [tuple(0 for i in range(weighings))]
    for potential in product(range(-stackSize, stackSize + 1), repeat=weighings):
        g = gcd(potential[0], potential[1])
        c = 2

        while c < len(potential) and abs(g) != 1:
            g = gcd(g, potential[c])
            c += 1
        if abs(g) == 1:
            res.append(potential)
    return res