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
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 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.
No comments:
Post a Comment