Lots of Gold Stacks and a Balance Scale

Question

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 1

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

Answer 2

I will explain more on why @ffao's solution works.

First, we're only interested in the ratio of three weighing. Through simple brute force, we can find that there are total of 7491 different unique ratios. (As @ffao explained)

Second, this ratio is only important if each weigh compares same number of coins on both side. For example, if we have 10 coins on the left, we should also have 10 coins on the right. Otherwise the value doesn't have much meaning.

Third, notice that gcd(a, b, c) = 1 implies gcd(-a, -b, -c) = 1. Let's just call them "gcd pair".
This is important because it means that you can always find a gcd pair such that second rule is met.
Thanks to this fact, we can map any number of stacks (up to 7291) to unique ratios such that every weigh will compare same number of coins on both sides.


For example, if we have two stacks,x and y, just assign them "gcd pair"; lets say x:(-1, -7, 6), then y:(1, 7, -6).
Now, in the first round, put 1 coin from x to left, and put 1 coin from y to right.
In the second round, put 7 coins from x to left, and put 7 coins from y to right.
In the third round, put 6 coins from x to right, and put 6 coins from y to left.

Notice that in every round, same number of coins are compared. So, if x is a fake stack, you would get the ratio (-1, -7, 6). If y is a fake stack, you would get the ratio (1, 7, -6).
This also work even if you're working with odd number of stacks as you can simply map remaining one to (0, 0, 0) and leave it aside.

The trick is to find a proper mapping to stacks such that it doesn't violate second rule. And I just showed that it's always possible due to third rule I stated.

Answer 3

X must be...

Less than or equal to 27.

Because

In the first weighing, you put floor(x/3) stacks on each side, and the remainder off. If the scale reads 0, you know that the heavier stack is in the remainder, otherwise, it's in the heavier pile. Repeat 3 times. In one weighing, you can isolate 3 groups. In another, 9 groups (by subdividing the heavy group). In a third weighing (by subdividing the heavy group again) you can isolate the heavy stack out of up to 27. I do not believe that the exact amount heavier or lighter can be used to glean any additional information.

Answer 4

Based on a comment from f" which seems to have been deleted, using my previous logic I can get

15 if you always have one bag not on the scale, allowing for rounds of 3, then 7, then 15. This is definitely not maximal but it's better than 8

Edit: I now realize this can't be true due to this question so the answer is at least 12

My instinct is telling me:

8 stacks

Reasoning:

At the last try you have to have only two stacks left, one on the left one on the right. The previous try you could have two stacks on each side (since you could then split that up into one on each side), and then the first try you could have four stacks on each side (since you could then split that up into 2 on each side), giving a max of 8 stacks

Answer 5

Answer

27 stacks

Explanation:

First divide it in 3 groups (with 9 each). Weighing any two will reveal the faulty stack. Then divide the faulty group of 9 into three groups (with 3 stack). Weighing any two will reveal the faulty stack wit 3 stacks. Weigh any two in the faulty stack and you can easily get the stack with heavier gold coins.

Answer 6

I find

927

How

Split into A = 441, B = 441, C = 45 stacks. Weight A vs B.
If equal, split C into C1 = 21, C2= 21, C3 = 3. Weight C1 vs C2
If equal, last weighing of C3 gives the stack
Else, the diff of C1 and C2 gives the weight of the fake stack and of the fake coin. The stack is in the heavier between C1 and C2. Set a stack apart. Split in 2. Take an incrementing number of coin from each stack (1,2,3,4,...) of each group. Voilà.
Else (A > B or B > A), the weighting gives you the weight of the stack and of the coin. There are still 2 weightings to do. Using the same principle, put 21 stacks aside (And apply the same algorithm as for C if relevant), divide the remaining 420 in 2, divide each 210 in 10 groups, get an incrementing number of coins from each stack of each group (21x1, 21x2, 21x3, ...), weight one side against the other (210 stacks vs 210 stacks, each side represented by 22155 coins).
The result of the weighting gives you the group of 21 stacks containing the fake one. Use the last weighting as before to figure out which.