32
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was going to say this was the same as this problem, but then I realized it's its own problem. $\endgroup$ – Joe Z. Nov 19 '14 at 20:12
  • $\begingroup$ Is this a balance or a scale? $\endgroup$ – warspyking Nov 19 '14 at 20:50
  • $\begingroup$ @warspyking It just gives you a single number when you put coins on it. $\endgroup$ – Lembik Nov 19 '14 at 20:51
  • 1
    $\begingroup$ Well if you put down 1 coin you can figure out the weight. If you put down 2 the worst case is a 30, so you don't know which is which. with 3 you cannot get a guarentee of what's what unless you get 30 or 60. etc. this goes until 12 meaning you cannot guarantee unless their all 10 or all 20? The best (worst case) is 12.... $\endgroup$ – warspyking Nov 19 '14 at 21:37
  • 1
    $\begingroup$ @Jason I assume they're all unique, otherwise a solution with only one weighing would be trivial $\endgroup$ – Sabre Nov 19 '14 at 23:12

11 Answers 11

13
+50
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Brute Force proofs are the best kinds of proofs. $\endgroup$ – No. 7892142 Nov 26 '14 at 14:03
  • 1
    $\begingroup$ Can you specify at least one human-readable/useable algorithm to solve it in 7? $\endgroup$ – frodoskywalker Nov 26 '14 at 14:07
  • 1
    $\begingroup$ Brute force would be more attractive I think if the choice of which coins to weigh didn't depend on previous outcomes. Then you could at least write down the solution succinctly. $\endgroup$ – Lembik Nov 26 '14 at 14:17
  • 1
    $\begingroup$ @Lembik That may be true, but "follow the tree given by the program" is at least some kind of algorithm that solves in 7 weighings everytime and hence, at least answers the main question. $\endgroup$ – No. 7892142 Nov 26 '14 at 14:28
  • 2
    $\begingroup$ I think this solution technically satisfies all requirements... the only thing would be a static schedule $\endgroup$ – d'alar'cop Nov 28 '14 at 8:38
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you've done it. I'm pretty sure 12 in 7 isn't possible. +1 $\endgroup$ – mdc32 Nov 23 '14 at 16:32
  • 1
    $\begingroup$ I am pretty sure it is :) $\endgroup$ – Lembik Nov 23 '14 at 19:18
  • 3
    $\begingroup$ It seems like you could extend this method to cover all 12 coins in 7 or less moves, but perhaps I'm missing something. It would simply take a large amount of cases. $\endgroup$ – For I In Range Nov 24 '14 at 12:17
  • $\begingroup$ +1. Nicely done and explained. I noticed that you break the coins into batches of 6. Instead if you extended your method to a batch of 8 and 4, you might be able to get 7 weighings. And ofcourse there will be more combinations to deal with $\endgroup$ – stackErr Nov 27 '14 at 17:49
  • $\begingroup$ @stackErr that would require getting 8 coins in 4 moves, which isn't possible, or 4 coins in 2 moves, which is also impossible. $\endgroup$ – mdc32 Nov 28 '14 at 5:08
14
$\begingroup$

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}\}$.

$\endgroup$
  • $\begingroup$ Comments moved to chat $\endgroup$ – Kevin Nov 26 '14 at 3:56
  • $\begingroup$ hi mdc, it turns out the final solution was not really something one could just deduce. it almost needed a brute force effort... or at least some kind of reduction to some other problem. either way, it was not something one could just reason to with comfortable effort. $\endgroup$ – d'alar'cop Nov 29 '14 at 6:29
  • $\begingroup$ @d'alar'cop I am not sure I agree. It is something one can deduce. It's just not that easy. $\endgroup$ – Lembik Nov 29 '14 at 8:15
  • $\begingroup$ @Lembik Assuming that victors answer is the shortest possible correct answer (I doubt it is), then nobody could deduce that easily, if at all. It doesn't seem to follow a logical progression, because the amount of different cases in Victor's solution seems unrelated to the cases in Joel's. And like d'alar'cop said, it couldn't be deduced in a short enough period of time $\endgroup$ – mdc32 Nov 29 '14 at 14:58
  • 1
    $\begingroup$ @mdc32 7 is the minimum number of possible weighings for 12 coins that is guaranteed to work. His dynamic solution is too complicated to derive by hand. But I believe that there are static solutions one could at least explain after they have been found. $\endgroup$ – Lembik Nov 29 '14 at 15:05
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Whilst it's a known result with references etc, I can confirm that this works. +1 well done :) $\endgroup$ – d'alar'cop Nov 28 '14 at 22:16
  • $\begingroup$ Well then, I'm shutting down the really slow program I'm running to do this. $\endgroup$ – Joel Rondeau Nov 29 '14 at 0:33
  • 1
    $\begingroup$ @JoelRondeau interestingly, there's some property of matrices which also solves this. where for a weighing the 12 coins are a row and if it's on the scale it's 1 otherwise it's 0... if for 7 of these no two subsets of the columns have the same vector sum then it's a solution $\endgroup$ – d'alar'cop Nov 29 '14 at 0:40
  • 2
    $\begingroup$ I hope you don't mind but I gave the bounty to the first correct answer. Also, it would be better if your answer came with an explanation rather than just external references. I believe this is possible to do. $\endgroup$ – Lembik Nov 29 '14 at 8:14
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Nice, I'm just not sure about the i,j,k thing personally. It seems like that's a really important part of the solution. Good idea though :) $\endgroup$ – d'alar'cop Nov 22 '14 at 22:40
  • $\begingroup$ Doesn't work. All weighing 10g except 8 and 11 gives identical weightings to all weighing 10g except 7 and 12. $\endgroup$ – Joel Rondeau Nov 23 '14 at 0:44
  • $\begingroup$ @JoelRondeau Thanks! You're right, but in that case you know for sure the values of 1-4, 5, 6, 9, and 10. The ones in question are 7, 8, 11, and 12. And you could figure out all 4 of them by weighing any one of them. I'm currently trying to write a program that will show me the cases not covered by my original solution, unless someone can show me all the cases that aren't covered at the moment. $\endgroup$ – Shaz Nov 23 '14 at 0:55
  • 1
    $\begingroup$ @Ryan, that was just the first of many cases with identical weights. You should try to refine your solution. It may be that there's an alternate path for matching weighings. $\endgroup$ – Joel Rondeau Nov 23 '14 at 0:57
1
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ I don't think that this approach will work, since 6 of the 13 equations are found by taking the difference of two of the others. Those 6 won't be independent equations, no matter how you choose the coins. $\endgroup$ – Jason Patterson Nov 25 '14 at 17:23
  • $\begingroup$ To be clear, this weighing scheme might work, but the system of equations that you suggest should not. $\endgroup$ – Jason Patterson Nov 25 '14 at 19:24
  • $\begingroup$ Yes, I thought about this yesterday (in the shower), 7 of those equations at max would be independent. $\endgroup$ – No. 7892142 Nov 26 '14 at 8:52
1
$\begingroup$

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: Coin Writing

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: enter image description here

$\endgroup$
  • $\begingroup$ Chat $\endgroup$ – Kevin Nov 28 '14 at 4:38
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This doesn't seem any better than the naive approach in the worst case sadly. $\endgroup$ – Lembik Nov 19 '14 at 20:21
  • $\begingroup$ But in best case scenario, you weigh once. Effectively, by checking if a group of a power of 2 is all one or the other, you can skip some checks. $\endgroup$ – JonTheMon Nov 19 '14 at 20:23
  • 6
    $\begingroup$ Sure.. but here we care about the worst case :) $\endgroup$ – Lembik Nov 19 '14 at 20:26
-1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ this doesn't work, I just checked it programmatically $\endgroup$ – d'alar'cop Nov 28 '14 at 10:42
  • $\begingroup$ Aw. It was such a nice pattern, too. $\endgroup$ – No. 7892142 Nov 28 '14 at 10:48
  • $\begingroup$ As this is a just a guess, it should be in a comment not an answer. In the new puzzling.SE world order, answers should be associated with supporting evidence and should not just be unsupported guesses :) $\endgroup$ – Lembik Nov 28 '14 at 10:51
  • $\begingroup$ Duly noted. Sorry! $\endgroup$ – No. 7892142 Nov 28 '14 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.