Coin weighing with a single weighing device

Question

You have 12 coins which each weigh either 20 grams or 10 grams. Each is labelled from 1 to 12 so you can tell the coins apart. You have one weighing device as well. At each turn you can put as many coins as you like on the weighing device and it will tell you exactly how much they weigh.

What is the minimum number of weighings that will always tell you exactly which coins weigh 10 grams and which weigh 20?

Clearly you can do it in 12 weighings by just weighing each coin separately.

---

There is now a solution using $7$ static weighings by Julian Rosen!

Current record found by computer search is $7$ (dynamic) weighings by Victor.

There is a hand developed record of $8$ (dynamic) weighings by Joel Rondeau.

---

Hint

Here are the first three lines of a solution that uses $7$ weighings.

0 0 1 0 1 1 1 0 0 0 0 0
1 0 0 1 0 1 1 1 0 0 0 0
1 1 0 0 1 0 1 1 1 0 0 0

---

Bounty awarded to Victor for the first correct answer. Julian Rosen gave a static solution with $7$ weighings but without an explanation yet (just external references).

I will award the "win" to the first static solution with $7$ weighings and an explanation.

Answer 1

I decided to try a different approach: Brute force.

So, I created a Java 8 program to brute-force the creation of a decision tree in order to find how to weight the 12 coins in 7 measurements, and it worked. Further, I could use it to prove that this is the optimum, because it said that with 6 there is no solution.

The program found a solution in 35 seconds on my computer. There are many solutions, most due to permutations.

The program creates a tree of nodes, where each one iterates through all 4096 possibles forms of choosing the coins, but it do variable renaming to eliminate permutations, i.e, this eliminates all but a tiny part of the permutations.

Then, for each measurement form, it simulates all the possibles combinations of light-or-heavy coins, already excluding possibilities eliminated by previous nodes in the tree. Then it checks if the generated node is able to separate different combinations, putting those in child nodes.

When a node passes the maximum depth (i.e. the maximum number of measurements), it is considered bad and is pruned. If it results in a single possibility, no further measurements are needed. If the node created only one child node, then the coin combination for the measurement is useless and the node is considered bad. A node that has bad nodes as children is considered bad and is pruned, even if not all of its child nodes were checked.

If a node tries every possible combination of coins to measure and is unable to determine all the possibilities uniquely, it is considered bad.

In the end, after encountering the solution, it is outputted.

I uploaded the human readable output to THIS LINK.

I also uploaded a JSON-formatted output IN THIS OTHER LINK.

I couldn't post either output here because they are too large. If you don't like the fact that the solution is provided in links, know that I don't like either, but again, it is simply too large to post here. You may just compile and run the program instead.

This is the program:

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author Victor
 */
public class BruteForce {
    // Change this to false to output in pretty-print mode.
    private static final boolean COMPACT = true;

    private final int coins;
    private final int maxDepth;
    private final int possibilities;

    public final class Node {
        private final boolean[] combs = new boolean[possibilities];
        private final boolean[] shouldWeight = new boolean[possibilities];
        private Node[] children = null;
        private int counts = 0;
        private final int level;
        private int lastCount = -1;
        private final Node parent;
        private Set<Integer> coinRenames;
        private int whichCoinsToWeight = -1;
        private int tag; // For writing it in some human readable format. Not used for creating and processing the tree.

        public Node() {
            this(0, null);
        }

        private Node(int level, Node parent) {
            this.parent = parent;
            this.level = level;
            if (parent != null) return;
            for (int i = 0; i < possibilities; i++) {
                count(i);
            }
        }

        public void count(int c) {
            combs[c] = true;
            counts++;
            lastCount = c;
            if (coinRenames == null) coinRenames = new TreeSet<>();
            int renamed = renameCoins(c);

            // Not really important, but if you want a solution in a few seconds instead of
            // waiting for some hundreds of years, keep this check here.
            if (coinRenames.add(renamed)) {
                shouldWeight[c] = true;
            }
        }

        // Convert an int to an array of boolean.
        private boolean[] asArray(int coinSet) {
            boolean[] array = new boolean[coins];
            for (int i = 0; i < coins; i++) {
                 array[i] = ((coinSet >> i) & 1) != 0;
            }
            return array;
        }

        private void summarizeCoinsUsedForWeighting(boolean[][] weightingCoinsPerLevel) {
            weightingCoinsPerLevel[level] = asArray(whichCoinsToWeight);
            if (parent != null) parent.summarizeCoinsUsedForWeighting(weightingCoinsPerLevel);
        }

        private int renameCoins(int thisLevelCoins) {
            // This arrays represent, for each level of the tree that is an ancestor to this node
            // the set of coins used for weighting, where each int corresponds to a sequence of
            // 0 and 1 bits representing which coins are being used.
            boolean[][] weightingCoinsPerLevel = new boolean[level + 1][coins];
            if (parent != null) parent.summarizeCoinsUsedForWeighting(weightingCoinsPerLevel);
            weightingCoinsPerLevel[level] = asArray(thisLevelCoins);

            // Transpose the array, so we have a new array, where for each coin, we have an int corresponding
            // to a sequence of 0 and 1 bits where the 1 bits are the levels in which the coin is used for weighting.
            // But since we do want that the levels near the root of the tree are represented by the most
            // significative bits, we reverse the bit order of the levels.
            int[] usingLevelsPerCoin = new int[coins];
            for (int i = 0; i <= level; i++) {
                for (int j = 0; j < coins; j++) {
                    if (weightingCoinsPerLevel[i][j]) usingLevelsPerCoin[j] |= 1 << (level - i);
                }
            }

            // Rename the coins to ensure that the most firstly-used coins are the first ones.
            // Coin-renaming serves to avoid recalculating combinations that are simply permutations to some
            // previously calculated position. Further, this coin renaming provides a single canonical representation
            // for each group of equivalent permutations. To ensure that, we simply sort the array, so the most used
            // coins with higher bits sets will be the LAST ones, I.E, the resulting array would still be in the reverse order.
            Arrays.sort(usingLevelsPerCoin);

            // We could untranspose the sorted array, so we have again coins per level, but with the coins are renamed.
            // However, now we are interested only in the last level, so we just get the last bit from each row on the array.
            // Further, we reverse the order of the bits that we get because the array is sorted in reverse order. This way it
            // will be in the right order again.
            int sortedCoinsOnLastLevel = 0;
            for (int j = 0; j < coins; j++) {
                sortedCoinsOnLastLevel |= (usingLevelsPerCoin[j] & 1) << (coins - j - 1);
            }

            return sortedCoinsOnLastLevel;
        }

        public boolean separate() {
            if (counts == 1) return true; // Just one possibility, it is in the lastCount variable.

            // If is recursing too deply and there is still at least 2 coins left in this possibility,
            // so there was a bad choice somewhere up in the decision tree.
            if (level >= maxDepth) return false;

            // The coins choosen to weight are the 1 bits. Start counting with 1 because there is no sense to weight zero coins.
            // This means that it will choose every possible combination of coins to weight, until it founds a good one or resigns.
            // Save it in an instance field, so it can be remembered when the solution is found.
            a: for (whichCoinsToWeight = 1; whichCoinsToWeight < possibilities; whichCoinsToWeight++) {

                // If this is just a permutation of some previously tested combination, just skip it.
                if (!shouldWeight[whichCoinsToWeight]) continue;

                children = null;
                int childCount = 0;

                // Iterate every possible valuation for the coins.
                b: for (int selectedCoinsCombination = 0; selectedCoinsCombination < possibilities; selectedCoinsCombination++) {

                    // If the choosen valuation never happens in this place, skip it.
                    if (!combs[selectedCoinsCombination]) continue;

                    // Weight the coins. This works by setting 0 to coins which
                    // are not being weighted, leaving 0 for light coins and 1 for heavy ones.
                    int bits = Integer.bitCount(whichCoinsToWeight & selectedCoinsCombination);

                    // Now start to populate the children. If it does not have any, create the array.
                    if (children == null) children = new Node[coins + 1];

                    // Choose the appropriate children node in the decision tree.
                    Node child = children[bits];

                    // If the selected node still do not exist, create it.
                    if (child == null) {
                        child = new Node(level + 1, this);
                        children[bits] = child;
                        childCount++;
                    }

                    // Add the selected coins combination as possible to the child node.
                    child.count(selectedCoinsCombination);
                }

                // If we have just one child, then the selected coins to weight did not gave any information,
                // so discard this choice and proceed to the next one.
                if (childCount <= 1) continue;

                // Now, perform the separation recursively in each children.
                // If some of them fails, then the selected coins to weight combination is useless and should
                // be discarded, even if just some of the nodes were tested.
                for (Node n : children.clone()) {
                    if (n == null) continue;
                    boolean r = n.separate();
                    if (!r) continue a;
                }

                // Yeah, found some useful combination!
                return true;
            }

            // We tried every combination of coins to weight and none of them was useful.
            return false;
        }

        // Output a JSON!
        public void reportResult(StringBuilder sb) {
            boolean first = true;
            sb.append("{");
            if (counts == 1) {
                sb.append("\"HEAVY\": [");
                for (int i = 0; i < coins; i++) {
                    if (((lastCount >> i) & 1) != 0) {
                        if (first) {
                            first = false;
                        } else {
                            sb.append(", ");
                        }
                        sb.append(i + 1);
                    }
                }
                sb.append("], \"LIGHT\": [");
                first = true;
                for (int i = 0; i < coins; i++) {
                    if (((lastCount >> i) & 1) == 0) {
                        if (first) {
                            first = false;
                        } else {
                            sb.append(", ");
                        }
                        sb.append(i + 1);
                    }
                }
                sb.append("]}");
                return;
            }
            if (!COMPACT) {
                sb.append("\n");
                ident(level + 1, sb);
            }
            sb.append("\"TO WEIGHT\": [");
            for (int i = 0; i < coins; i++) {
                if (((whichCoinsToWeight >> i) & 1) != 0) {
                    if (first) {
                        first = false;
                    } else {
                        sb.append(", ");
                    }
                    sb.append(i + 1);
                }
            }
            sb.append("]");
            for (int i = 0; i <= coins; i++) {
                if (children[i] == null) continue;
                sb.append(",\n");
                ident(level + 1, sb);
                Integer weighting = Integer.bitCount(whichCoinsToWeight);
                sb.append("\"").append((i + weighting) * 10).append(" grams\": ");
                children[i].reportResult(sb);
            }
            if (!COMPACT) {
                sb.append("\n");
                ident(level, sb);
            }
            sb.append("}");
        }

        private void ident(int level, StringBuilder sb) {
            for (int i = 0; i < level; i++) {
                sb.append(COMPACT ? " " : "  ");
            }
        }

        // Output a human readable algorithm!
        public void reportAlgorithm(StringBuilder sb) {
            this.tag = 1;
            for (int i = 0; i < maxDepth; i++) {
                reportAlgorithm(new int[maxDepth], i, sb);
            }
        }

        private void reportAlgorithmDone(StringBuilder sb) {
            if (counts != 1) return;
            boolean first = true;
            sb.append("Heavies = [");
            for (int i = 0; i < coins; i++) {
                if (((lastCount >> i) & 1) != 0) {
                    if (first) {
                        first = false;
                    } else {
                        sb.append(", ");
                    }
                    sb.append(i + 1);
                }
            }
            sb.append("]; Lights = [");
            first = true;
            for (int i = 0; i < coins; i++) {
                if (((lastCount >> i) & 1) == 0) {
                    if (first) {
                        first = false;
                    } else {
                        sb.append(", ");
                    }
                    sb.append(i + 1);
                }
            }
            sb.append("].\n");
        }

        private void reportAlgorithm(int[] levelCounters, int desiredLevel, StringBuilder sb) {
            boolean first = true;
            if (counts == 1) {
                reportAlgorithmDone(sb);
                return;
            }
            if (level < desiredLevel) {
                for (int i = 0; i <= coins; i++) {
                    if (children[i] != null && children[i].counts != 1) children[i].reportAlgorithm(levelCounters, desiredLevel, sb);
                }
                return;
            }
            sb.append(level + 1);
            if (level > 0) sb.append(".").append(tag);
            sb.append(". Weight the coins [");
            for (int i = 0; i < coins; i++) {
                if (((whichCoinsToWeight >> i) & 1) != 0) {
                    if (first) {
                        first = false;
                    } else {
                        sb.append(", ");
                    }
                    sb.append(i + 1);
                }
            }
            sb.append("]\n");
            for (int i = 0; i <= coins; i++) {
                if (children[i] == null) continue;
                Integer weighting = Integer.bitCount(whichCoinsToWeight);
                sb.append("  ").append((i + weighting) * 10).append(" grams: ");
                if (children[i].counts == 1) {
                    children[i].reportAlgorithmDone(sb);
                } else {
                    children[i].tag = ++levelCounters[level + 1];
                    sb.append("Go to ").append(level + 2).append(".").append(children[i].tag).append(".\n");
                }
            }
            sb.append("\n");
        }
    }

    public BruteForce(int coins, int maxDepth) {
        this.coins = coins;
        this.maxDepth = maxDepth;
        this.possibilities = 1 << coins;
    }

    public void run() {
        Node n = new Node();
        boolean ok = n.separate();
        if (!ok) {
            System.out.println("Impossible");
            return;
        }

        // Uncomment this to output as JSON.
        //StringBuilder sb = new StringBuilder(1024 * 1024);
        //n.reportResult(sb);
        //System.out.println(sb.toString());

        StringBuilder sb2 = new StringBuilder(1024 * 1024);
        n.reportAlgorithm(sb2);
        System.out.println(sb2.toString());
    }

    public static void main(String[] args) {
        int coins = 12; // You may change the number of coins if you want.
        int measures = 7; // You may change the number of measures, if you want.
        BruteForce b = new BruteForce(coins, measures);
        b.run();
    }
}

^{I am sorry that this site does not have syntax-coloring enabled.}

You may modify the program as you wish, specially to brute-force different combinations of number of coins and number of measurements. This is cool because you may also use this program to solve any number of desired coins and measurements (as long as you have enough time and memory).

If you change the int measures = 7; near the end of the program to 6, it will output that it is impossible, proving that 7 are indeed the minimum.

You may uncomment the code in the run() method to get a compact JSON output. You may also change the value of the COMPACT variable in the beginning to false and then the JSON output will be a better looking one, but will be still larger. You may get that JSON and use it to work with something else. Or you may simple keep just the human readable output.

You may argue that this is a very inelegant, ugly and stupid way of solving this problem, as the output of the program is basically a bunch of random-looking arbitrary measurements without any clear, simple or intuitive pattern. I agree, but nevertheless, the problem is solved: Just follow the measurements show in the output and you will find the weight for any combination of 10 or 20 grams coins in only 7 measurements.

Answer 2

I can manage it in 8 weighings.

I started with mdc32's answer and expanded on it. I was able to weigh 6 coins in 4 weighings. I suspect 12 can be done in 7 weighings, but I haven't figured out a way to do that yet.

Start with a group of coins $\{c_1,c_2,c_3,c_4,c_5,c_6\}$.

Weigh 1: $c_1 + c_2$. If the weight is either 20 or 40, follow mdc32's answer to weigh the other 4 in 3 weighings. Otherwise, the weight was 30, and proceed to the next weighing.

Weigh 2: $c_1 + c_3 + c_4$. If the weight is either 30 or 60, all of the weights of $c_1, c_2, c_3, c_4$ are known. Use weighing 3 for $c_5$ and 4 for $c_6$.

If the weight was 40, the 3 options for the group of coins weighing 20 are:
$\{c_1\}, \{c_2,c_3\}, \{c_2,c_4\}$. Proceed to 3a.

If the weight was 50, the 3 options for the group of coins weighing 20 are:
$\{c_1,c_3\}, \{c_1,c_4\}, \{c_2,c_3,c_4\}$ Proceed to 3b.

Weigh 3 (a or b): $c_2 + c_3 + c_5$. If the weight is either 30 or 60, all the weights of $c_1, c_2, c_3, c_4, c_5$ are known. Use weighing 4 for $c_6$.

If 3a and a weight of 40, the 2 options for coins weighing 20 are:
$\{c_1,c_5\}, \{c_2,c_4\}$. Proceed to 4a.

If 3a and a weight of 50, the 2 options for coins weighing 20 are:
$\{c_2,c_3\}, \{c_2,c_4,c_5\}$. Proceed to 4b.

If 3b and a weight of 40, the 2 options for coins weighing 20 are:
$\{c_1,c_3\}, \{c_1,c_4,c_5\}$. Proceed to 4c.

If 3b and a weight of 50, the 2 options for coins weighing 20 are:
$\{c_2,c_3,c_4\}, \{c_1,c_3,c_5\}$. Proceed to 4d.

Weigh 4a: $c_1 + c_5 + c_6$
If the weight is 30, the heavy coins are: $\{c_2,c_4\}$
If the weight is 40, the heavy coins are: $\{c_2,c_4,c_6\}$
If the weight is 50, the heavy coins are: $\{c_1,c_5\}$
If the weight is 60, the heavy coins are: $\{c_1,c_5,c_6\}$

Weigh 4b: $c_4 + c_5 + c_6$
If the weight is 30, the heavy coins are: $\{c_2,c_3\}$
If the weight is 40, the heavy coins are: $\{c_2,c_3,c_6\}$
If the weight is 50, the heavy coins are: $\{c_2,c_4,c_5\}$
If the weight is 60, the heavy coins are: $\{c_2,c_4,c_5,c_6\}$

Weigh 4c: $c_4 + c_5 + c_6$
If the weight is 30, the heavy coins are: $\{c_1,c_3\}$
If the weight is 40, the heavy coins are: $\{c_1,c_3,c_6\}$
If the weight is 50, the heavy coins are: $\{c_1,c_4,c_5\}$
If the weight is 60, the heavy coins are: $\{c_1,c_4,c_5,c_6\}$

Weigh 4d: $c_2 + c_4 + c_6$
If the weight is 30, the heavy coins are: $\{c_1,c_3,c_5\}$
If the weight is 40, the heavy coins are: $\{c_1,c_3,c_5,c_6\}$
If the weight is 50, the heavy coins are: $\{c_2,c_3,c_4\}$
If the weight is 60, the heavy coins are: $\{c_2,c_3,c_4,c_6\}$

Do the same for the other 6 coins, and all coins are known in 8 weighings.

Answer 3

There is a solution requiring a maximum of $9$ weighings. The strategy rests on a solution for $4$ coins $\{c_1,c_2,c_3,c_4\}$ in $3$ weighings - then performing the same operation on the remaining sets of $4$.

With 4 coins, weigh coins $c_1$ and $c_2$. If the amount is 20 or 40, then the coins weigh 10 or 20, respectively, and we can just weigh the remaining coins individually (for a total of 3 weighings). If $c_1$ and $c_2$ weigh 30 altogether, then all we know is that the weights are different. I will continue assuming this is the case.

Weigh coins $c_1$ and $c_3$. Like last time, if the amount is 20 or 40 then the weights for $c_1, c_2,$ and $c_3$ can be deduced. In this case, weigh $c_4$ giving you a total of 3 operations for 3 coins. If, however, this amount also ends up being 30, then all we know is that $c_2$ is the same as $c_3$. Again, I will assume this is the case.

Weigh $c_2, c_3,$ and $c_4$. These three coins could weigh 30, 40, 50, or 60 grams in total. If the weight is 30 or 40, then because coins $c_2$ and $c_3$ are the same weight, we know that they are both 10, with $c_4$ being 10 or 20 grams respectively. If the weight is 50 or 60, we can do the same thing, except with $c_2$ and $c_3$ both weighing 20 grams. $c_1$ and $c_2$ weigh 30 together, so we can deduce that coin $c_1$ is the opposite of $c_2$. This gives us all four coins in a worst case scenario of 3 weighings.

A more formal solution can be found below, thanks to d'alar'cop.

---

Given the first group of $4$, $\{c_1,c_2,c_3,c_4\}$, we will perform our first weighing $c_1$ and $c_2$ giving $ W_1 = w(c_1) + w(c_2)$. It is clear that $W_1 \in \{20,30,40\}$.

$W_1 = 20 \rightarrow c_1 = 10 \land c_2=10$ and $W_1 = 40 \rightarrow c_1 = 20 \land c_2 = 20$. Either way, the weights of $c_1$ and $c_2$ are known. In this case, simply weigh $c_3$ and $c_4$ alone and the $4$ coins are solved in $3$ weighings.

If $W_1 = 30$ then all we know is that $c_1 \not= c_2$.

So, we weigh $c_1$ and $c_3$ giving $W_2 = w(c_1) + w(c_3)$. It is clear that $W_2 \in \{20,30,40\}$. $W_2 = 20 \rightarrow c_1 = 10 \land c_2 = 20 \land c_3=10$ and $W_2 = 40 \rightarrow c_1 = 20 \land c_2=10 \land c_3 = 20$. Thus $3$ are known in $2$ weighings. In this case, simply weigh $c_4$ alone and the $4$ coins are solved in $3$ weighings.

If $W_2 = 30$ then all we know is that for $c_1,c_2,c_3 \in \{10,20\}.(c_1 \not= c_2) \land (c_1 \not= c_3) \land (c_2 = c_3)$.

Finally, weigh $c_2$, $c_3$ and $c_4$ giving $W_3 = w(c_2) + w(c_3) + w(c_4)$. It is clear that $W_3 \in \{30, 40, 50, 60\}$.

Case $W_3 = 30$: $c_2 = c_3 = c_4 = 10 \land c_1 = 20$.
Case $W_3 = 40$: $c_2 = c_3 = 10 \land c_1 = c_4 = 20$.
Case $W_3 = 50$: $c_2 = c_3 = 20 \land c_1 = c_4 = 10$.
Case $W_3 = 60$: $c_2 = c_3 = c_4 = 20 \land c_1 = 10$.
This follows from the earlier inference that $c_2 = c_3$.

Thus, we have deduced the weights of coins $c_1,c_2,c_3,c_4$ in $3$ weighings. We may now perform the same operation on $c_5,c_6,c_7,c_8$ and $c_9,c_{10},c_{11},c_{12}$ for $3$ weighings each giving a total of $9$ weighings to deduce the weights of the $12$ coins $\{c_1, \cdots ,c_{12}\}$.

Answer 4

There is some literature on this problem. Lindström [2] and Cantor and Mills [1] independently give weighing strategies using 7 weighings, with the property that no weighing depends on the results of previous weighings. More generally, these papers prove that for every positive integer $k$, $2^{k}-1$ weighings suffice to determine which of $2^{k-1}k$ coins have which weights.

The weighing strategies are constructed recursively. The general process is a little intricate, so I won't try to describe it here. If I understood everything correctly, the strategy given in [1] for 12 coins suggests putting the following coins on the scale:

• 1, 2, 4, 5, 7, 9, 11
• 2, 3, 5, 6, 12
• 1, 3, 5, 7, 8, 10
• 5, 6, 8, 9
• 1, 2, 4, 6, 8, 10
• 2, 3, 8, 9
• 1, 3, 6, 9

$\,$

[1] Cantor, David G. and Mills, W.H.. Determination of a subset from certain combinatorial properties. Canad. J. Math. 18 1966 42-48

[2] Lindström, Bernt. On a combinatorial problem in number theory. Canad. Math. Bull. 8 1965 477-490

Answer 5

I have a static 7-weighing schedule:

• {3,5,6,7}
• {1,4,6,7,8}
• {1,2,5,7,8,9}
• {1,2,3,6,8,9,10}
• {2,3,4,7,9,10,11}
• {3,4,5,8,10,11,12}
• {1,4,5,6,9,11,12}

This can also be given in terms of ON/OFF (with 1/0) given the array of 12 coins:

• 0 0 1 0 1 1 1 0 0 0 0 0
• 1 0 0 1 0 1 1 1 0 0 0 0
• 1 1 0 0 1 0 1 1 1 0 0 0
• 1 1 1 0 0 1 0 1 1 1 0 0
• 0 1 1 1 0 0 1 0 1 1 1 0
• 0 0 1 1 1 0 0 1 0 1 1 1
• 1 0 0 1 1 1 0 0 1 0 1 1

I am still considering how to properly explain it in an intuitive way. The pattern in the above bit-array-set is obvious - i.e. some kind of shifting pattern. But as to how/why this achieves the goal (c.f. my other answer) is not yet clear.

Answer 6

This isn't an answer. It's just a potentially useful mathematical definition of the problem.

Let the coins be labelled $C = \{c_1, \cdots, c_{12}\}$ be mapped to a vector $V = (s_1, \cdots, s_{12})$ where $c_i = 10 \rightarrow s_i = 0$ and $c_i = 20 \rightarrow s_i = 1$. There are $2^{12}$ possible weight patterns for the $12$ coins. And, in fact the vector members concatenated map a unique binary integer to each of those possible weight patterns.

The possible binary strings are in the set $L_1 = \Big\{w\mid w = s_1s_2 \cdots s_{12} \land s_i \in \{0,1\} \Big\}$. $|L_1| = 2^{12} = 4096$. Let $H(x)$ be the Hamming weight (the count of non-zero digits) in the word $x$.

We select $x$ subsets, $S = \{v_1, \cdots ,v_x\}$ where $v_i \subseteq V$. We can be sure that $H(v_i)<=12$. So, consider the string $H(v_1)H(v_2) \cdots H(v_{12})$ and interpret this string as a number in base-13. The possible strings of this sort are in the set $L_2 = \Big\{w\mid w = v_1 \cdots v_x \land v_i \in \{0,\cdots,9,A,B,C\} \Big\}$. $|L_2| = 13^x$.

The problem is to define $S$ that minimises $x$ such that, regardless of any initial weights for the coins in $C$, there is a one-to-many mapping from $L_1$ to $L_2$ and all mappings from members of $L_1$ are disjoint.

We know that $x \geq 2$ (purely from the fact that $13^x$ must exceed $2^{12}$) although it's surely between $6$ and $8$.

This assumes that $v_j$ is not dependent on the results any combinations of $v_i$s where $i<j$.

Answer 7

I think this may lead to a unique solution but I'm not 100% sure. I think it can be done with six weighs.

Weigh(1, 2, 3, 4) = X

Weigh(5, 6, 7, 8) = Y

Weigh(1 - 12) = T (for total)

From this you can also calculate (9, 10, 11, 12) = Z = T - X - Y

Weigh[(1, 5, 9) + (2, 6, 10)] = A

Weigh[(1, 5, 9) + (3, 7, 11)] = B

Weigh[(1, 5, 9) + (4, 8, 12)] = C

So T = A + B + C - 2(1, 5, 9)

Do the algebra to get (1, 5, 9) = (A + B + C - T) / 2 All values on the right side are known, so we know what (1, 5, 9) equals. From there we can calculate

(2, 6, 10) = A - (1, 5, 9)

(3, 7, 11) = B - (1, 5, 9)

(4, 8, 12) = C - (1, 5, 9)

Now we can set up a matrix:

$\begin{bmatrix}1 & 2 & 3 & 4 & X\\5 & 6 & 7 & 8 & Y\\9 & 10 & 11 & 12 & Z\\i & j & k & l & T\end{bmatrix}$

Where 1 + 2 + 3 + 4 = X, 1 + 5 + 9 = i, etc.

Above we know X, Y, Z, i, j, k, and l and can use that information to determine the individual values of all coins. But, like I said at the beginning I'm not 100% sure if this leads to a unique solution. I tried coming up with combinations of 10s and 20s to test and they were all solvable. Horizontally for XYZ values, a 40 or 80 is a dead giveaway that all coins in that row are 10 or 20. Similarly, vertically for ijkl values, 30 and 60 do the same.

(I'm obviously terrible at formatting. I literally just looked up how to do a matrix with MathJax and that's about the limit of my abilities. If someone wants to make it prettier feel free).

Answer 8

There's absolutely nothing to support my suspicions, but I would guess that the most efficient way to determine the weight of each coin is to weigh half the coins at a time in multiple ways.

1. Begin by determining total weight of coins$\{c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9,c_{10},c_{11},c_{12}\}$

2. Determine combined weight of coins $\{c_1,c_2,c_3,c_4,c_5,c_6\}$ and subtract from total weight to determine weight of $\{c_7,c_8,c_9,c_{10},c_{11},c_{12}\}$

3. Determine combined weight of $\{c_2,c_4,c_6,c_8,c_{10},c_{12}\}$ and subtract from total weight to determine weight of $\{c_1,c_3,c_5,c_7,c_9,c_{11}\}$

After each weighing, the sum of the weights of six other coins can be deduced by subtracting the recently weighed coins from the total. After 7 total weighings, the weigher will have obtained 13 equations regarding the combined weights of the coins. Would this massive system of equations be solvable? This is not meant to be an answer, but hopefully this will point someone with the skills to actually solve this in the right direction. (Or in the wrong direction, I'm not sure.)

Answer 9

This is my revised guess and check strategy. You may argue that it's pointless and wastes time, but I don't want to spend the weekend reading up on college-level math.

Not sure if this is static or dynamic

First, weigh the below coins and note the weights.

• 1, 2, 4, 5, 7, 9, 11
• 2, 3, 5, 6, 12
• 1, 3, 5, 7, 8, 10
• 5, 6, 8, 9
• 1, 2, 4, 6, 8, 10
• 2, 3, 8, 9
• 1, 3, 6, 9

Thanks to @Julian for the weights... Then write all of them like this:

Substitute the ?$n$ for the actual weights. Then, see if there are any no guesses-like weighing $2$ being 100, or etc.

---

Guessing Tips

-Guess only when there are no more weights that can be deduced. -Try to only guess 1 weight at a time, never more than 2 -Use scratch paper and keep the un guessed version in case you messed up

Example of finished weights:

Answer 10

A way to bring the number of weighings down to about 1/2 would be to weigh all of them, record that weight (if it's 24 or 12, you know the weights). Then weigh 6, record those (again, 12 or 6, you know them). Then weigh 2 (4 or 2, you know). Then weigh 1. Based on that, you know the other. Repeat for the other sets of 2.

Worst case scenario, every set of 2 is mixed, which would lead to 12 weighings.

Let's take the scenario of 101101 101101 and do a binary search:
{101101 101101}
{101101} 101101
{101} 101 101101
{1}01 101 101101
1 {0}1 101 101101
1 0 1 {1}01 101101
1 0 1 1 {0}1 101101
1 0 1 1 0 1 {101} 101
1 0 1 1 0 1 {1}01 101
1 0 1 1 0 1 1 {0}1 101
1 0 1 1 0 1 1 0 1 {1}01
1 0 1 1 0 1 1 0 1 1 {0} 1

Now let's try with groups of 2:
{101101 101101}
{101101} 101101
{10} 1101 101101
{1}0 1101 101101
1 0 {11} 01 101101
1 0 1 1 {0}1 101101
1 0 1 1 0 1 {10} 1101
1 0 1 1 0 1 {1}0 1101
1 0 1 1 0 1 1 0 {11} 01
1 0 1 1 0 1 1 0 1 1 {0}1

Answer 11

This is obviously just from your hints and not proven to work in any case:

#1 - 0 0 1 0 1 1 1 0 0 0 0 0
#2 - 1 0 0 1 0 1 1 1 0 0 0 0
#3 - 0 1 0 0 1 0 1 1 1 0 0 0
#4 - 0 0 1 0 0 1 0 1 1 1 0 0
#5 - 0 0 0 1 0 0 1 0 1 1 1 0
#6 - 1 0 0 0 1 0 0 1 0 1 1 1
#7 - 0 1 0 0 0 1 0 0 1 0 1 1

(Victor's answer is already correct anyway.)