IBM Ponder This: April 2018 Solution

April 2018's Question

The question for IBM Ponder This April 2018 is as follows:

There are nine balloons in nine different colors. Each balloon has a different lifting capability, from one through nine grams (1, 2, 3...9) respectively. Alice knows the lifting capacities of each balloon, and she wants to use the smallest possible combinations of balloons to prove to Bob the identity of the 1-gram balloon. She can tie together any subset of balloons to a 9.5-gram weight that will stay put if and only if the total lifting power of the balloons is less than 9.5 grams. Otherwise the weight will lift off and fly away. 
How does Alice prove to Bob the color of the 1-gram balloon by doing as few "experiments" as possible? 
Each demonstration should use a subset of the balloons that does not lift the weight. Supply your answer as a list of weights per experiment.

For example, here is a (non-optimal) solution for a similar problem with only six balloons with 1-6 gram lifting capacities and a 6.5-gram weight:
1,2 
1,3 
1,4 
1,5
In each one of the four experiments, Alice uses a subset of the balloons that does not lift the weight and that has a total lift capacity of six grams or less. Therefore, Bob can conclude that the balloon that is common to all the experiments must be the one with the 1-gram lift capacity.
Two wrong answers for the six-balloon example include the following:

1. A single experiment: "1,2,3" - this is the only combination of three balloons that won't lift the weight, but Bob can't know from this experiment alone which of the three balloons has the 1-gram lifting capacity.
2. Three experiments: "1,2" "1,3" and "1,5" - Bob can't distinguish between that and "2,1" "2,3" and "2,4". Both sets of experiments look exactly the same to him, so he can't be sure if the repeated balloon has a 1-gram or 2-gram lifting capacity.

---

Summarizing The Problem Statement

Let's restate the problem statement, highlighting the key points:

• There are nine distinct balloons (each has a different color and a different lifting capacity).
• There's a 9.5 gram weight that can be tied to one or more balloons to form a "subset"/"experiment".
• The subset/experiment must always make it so that the balloons don't fly away. (Meaning, we can't make a subset of balloons with a lifting capacity of over 9.5 grams in total.)
• We want to come up with a set of experiments to show to Bob, such that Bob knows which balloon the 1 gram balloon is. 

As an example, (1, 2, 3) form a valid experiment/subset, because the balloons add up to a total of 6 grams of lifting capacity, which is less than the 9.5 gram weight. However, (2, 9) is not a subset because those balloons add up to 11 grams of lifting capacity, which would make the balloons fly away since the weight is only 9.5 grams.

To begin our solution, let's start by thinking about which valid balloon subsets we can actually choose. 

---

Which Subsets To Choose?

What's the maximum number of balloons we can have in a subset? 

Can we have four balloons in a subset? The smallest four-balloon-subset we can make is (1,2,3,4), which adds up to 10 grams. So we cannot have four or more balloons in a subset.

​Can we have three balloons in a subset? The smallest three-balloon-subset we can make is (1,2,3), which adds up to 6 grams, which is valid. So we can have three-balloon-subsets. 

​With a little work, we can see that there are seven possible three balloon subsets:

(1,2,3)
(1,2,4)

(1,2,5)
(1,2,6)

(1,3,4)
(1,3,5)

(2,3,4)

The two-balloon subsets that are possible are:
(8,1)
(7,2) (7,1)
(6,3) (6,2) (6,1)
(5, 4) (5,3) (5,2) (5,1)
(4,3) (4,2) (4,1)
(3,2) (3,1)
(2,1)

And of course, each balloon can be weighed by itself. 

(1) 

(2)  ​

(3) ​

(4) ​

(5)

(6) ​

(7) ​

(8)

(9)

With this knowledge in mind, let's start thinking of solutions. ​

---

Six Experiment Solution

To have Bob be able to determine which the 1 gram balloon is, we can exploit the fact that there are only seven possible three-balloon-subsets. 

To put it simply: six of the seven three-balloon-subsets have the 1 gram balloon in them. No other balloon can do that. (The next highest is the 2 gram balloon, which shows up in five three-balloon-subsets {(1,2,3), (1,2,4), (1,2,5), (1,2,6), (2,3,4)}.)

​Show Bob the following experiments:

(1,2,3)
(1,2,4)
(1,2,5)
(1,2,6)
(1,3,4)
(1,3,5)

(Remember that Bob doesn't see numbers, but he does see colors.)
Bob will see that a certain balloon shows up six times, and that's only possible for the 1 gram balloon. So that balloon is the 1 gram balloon. 

So we can determine the 1 gram balloon from six experiments. But can we do better?

---

Five Experiment Solution

We're going to change our strategy a bit. This time, we're going to show Bob [basically] ALL of the balloons in our experiments, and we're going to exploit something else that only the 1 gram balloon can do.

We need to make two observations:

1. The 9 gram balloon cannot form a subset with any other balloon. (Otherwise the total lifting power would be over 9.5 grams, and would lift the weight.)
2. The 8 gram balloon can only be paired with the 1 gram balloon. 

With that knowledge as our foundation, we'll show Bob the following balloon subsets in our experiments:
(2, 3, 4)
(1, 8)
(1, 7)
(1, 6)
(1, 5)

To Bob, the experiments look something like this:
(A, B, C)
(D, E)
(D, F)
(D, G)
(D, H)

With these experiments, Bob has seen eight of the nine balloons used in our experiments.

Bob must realize that the last balloon that wasn't used in the experiments must be the 9 gram balloon, because the 9 gram balloon is the only one that is unable to be weighed with other balloons. So balloons A, B, C, D, E, F, G, and H must each consist of the weights from {1, 2, 3, 4, 5, 6, 7, and 8} gram balloons (in some ordering). ​

Bob then recognizes that balloon D is paired with four other balloons. The 8 gram balloon is only able to be paired with the 1 gram balloon (and cannot belong to a three balloon subset, meaning the 8 gram balloon cannot be balloon A, B, or C), which means that regardless of whether balloon E, F, G, or H is the 8 gram balloon, balloon D must be the 1 gram balloon. ​

So in total, Alice needs to show Bob five balloon experiments. But can we do even better?

---

Four Experiment Solution

To think of a four experiment solution, we'll combine concepts from the previous two solutions.

Here's what we need to observe this time: ​

1. There are six numbers that show up in the three-balloon-subsets. (1, 2, 3, 4, 5, and 6. To say this another way: no three-balloon subset will contain a 7, 8, or 9.)
2. The 6 gram balloon can only show up in one three-balloon-subset (1,2,6). 
3. The 6 gram balloon can only be partnered with the 1 and 2 gram balloon.

With those observations in mind, we need to show some subset of balloons where the 1 gram balloon can only be the 1 gram balloon: that it would be impossible for that particular balloon to weigh anything else than 1 gram.

The instructions sound a little vague, but we'll work through the answer to see how this all works. Let's begin by giving an answer, working through the proof, and then looking at how to obtain that solution.

Show Bob the following balloons:​
​(1,2,4)
(1,2,6)
(1,3,4)
(1,3,5)

Which Bob sees as:
​(A,B,C)
(A,B,D)
(A,E,D)
(A,E,F)

Bob sees the balloons only by their color (which we label with arbitrary letters). We want to prove that the 1 gram balloon (which we have labeled as 'A') MUST be the 1 gram balloon.

To do this, we'll follow the steps we talked about before:
1. The 6 gram balloon can only show up once, which means it must be balloon C or balloon F.
2. The 6 gram balloon must be paired with the 1 gram balloon and the 2 gram balloon, which means that if the 6 gram balloon is balloon C, then balloons (A,B) must be either (1,2) or (2,1), or if balloon F is the 6 gram balloon, then balloons (A,E) must be either (1,2) or (2,1). 
3. We can then try all other possibilities (for the 3, 4, and 5 gram balloons).

Our solution works if balloon A can only be the 1 gram balloon. If any other combination is valid where A is not the 1 gram balloon, then the solution fails. 

To demonstrate the possibilities, look at the following picture:

In the above solution, we follow through with the steps, trying possible ways to assign weights {1,2,3,4,5,6} to all of the balloons. We can see that for every possible case where balloon A is the 2 gram balloon, one of the subsets doesn't work (would have led to a failure where the subset weighs over 9.5 grams).

(Also notice that there's no need to check the solutions where A=1, because that's what we're trying to achieve, regardless or what the other balloons could possible be. To say it another way, it doesn't matter if Bob can't tell whether balloon D is the 4 or 5 gram balloon: we only care about proving A as the 1 gram balloon.)

With this, we prove that balloon A MUST be the 1 gram balloon, and cannot weigh anything but 1.

Working out the proof wasn't difficult, but coming up with those experiments wasn't easy. To do so, I coded a C++ program to choose the experiments.

The code logic is as follows: 

1. Given all valid three-balloon-subsets {(1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5), (2,3,4)} ....
2. Try all combinations of picking four of these experiments to show to Bob.
3. Make sure that the four experiments we chose contain all balloons {1, 2, 3, 4, 5, and 6}.
4. Convert the experiments to generic lettering. (For example, "135" -> "ACE".}
5. Calculate all lettering value possibilities. (For example, (A=1,B=2,C=3), (A=2,B=4,C=1), etc.)
6. Try each set of four experiments with all lettering possibilities. 
7. Output the experiments if the lettering only works for A=1.

The code itself can be found below. (It's unoptimized and pretty ugly, but it gets the job done.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247

// Copyright srcmake.com 2018. #include <bits/stdc++.h> #include <string> #include <fstream> #include <streambuf> using namespace std; std::ofstream out("output.txt"); // Given a set of experiments (labeled as ) bool ValuesWork(vector<string> &experiments, vector<int> &values) { // Try the set of values for this experiment. int A = values[0]; int B = values[1]; int C = values[2]; int D = values[3]; int E = values[4]; int F = values[5]; // Go through each of the experiments we show Bob. for(int i = 0; i < experiments.size(); i++) { string subset = experiments[i]; int subsetsum = 0; // For each balloon in the subset... for(int j = 0; j < subset.size(); j++) { char c = subset[j]; // {'A', 'B', ..., 'F'} // Add this balloon's [theoretical] weight to the subsetsum. if(c == 'A') { subsetsum += A; } if(c == 'B') { subsetsum += B; } if(c == 'C') { subsetsum += C; } if(c == 'D') { subsetsum += D; } if(c == 'E') { subsetsum += E; } if(c == 'F') { subsetsum += F; } } // If the subsetsum is greater than 9.5, this subset is not valid. if(subsetsum > 9.5) { return false; } } return true; } // Given some generic experiments (what Bob sees), try each letter as a different number. vector< vector<int> > GetValuePossibilities() { vector< vector<int> > valuePossibilities; // Try all combinations of letter=# for(int a = 1; a <= 6; a++) { for(int b = 1; b <= 6; b++) { if(a == b) { continue; } for(int c = 1; c <= 6; c++) { if(c == a || c == b) { continue; } for(int d = 1; d <= 6; d++) { if(d == a || d == b || d == c) { continue; } for(int e = 1; e <= 6; e++) { if(e == a || e == b || e == c || e == d) { continue; } for(int f = 1; f <= 6; f++) { if(f == a || f == b || f == c || f == d || f == e) { continue; } // Try char A = a (the int from {1,6}) // Store the combination of possibilities in an array. vector<int> values; values.push_back(a); values.push_back(b); values.push_back(c); values.push_back(d); values.push_back(e); values.push_back(f); // Add this set of values to the total vector of possibilities. valuePossibilities.push_back(values); } } } } } } return valuePossibilities; } // Convert a set of experiments to generic strings (meaning 1243->ABCD) vector<string> ConvertExperimentsToGeneric(vector<string> &experiments) { vector<string> converted; // Map a char (number) to a char (letter). // Since randomization doesn't matter, just map 1->A, 2->B, etc. for(int i = 0; i < experiments.size(); i++) { string subset = experiments[i]; string genericsubset = ""; // Go through each balloon. for(int j = 0; j < subset.length(); j++) { char c = subset[j]; char letter = (c-'1')+'A'; genericsubset += letter; } converted.push_back(genericsubset); } return converted; } // Check that an experiment set is valid (meaning it has all 6 balloons). bool ExperimentsAreValid(vector<string> &experiments) { // An array that says whether we have a balloon for each type. bool has[6] = { false }; // Go through each subset. for(int i = 0; i < experiments.size(); i++) { string subset = experiments[i]; // Go through each balloon. for(int j = 0; j < subset.length(); j++) { char c = subset[j]; // Mark this number in "has" has[c-'1'] = true; // (There is no 0 gram balloon, so the first is 1. } } // Go through our has array and check that we saw all ballons. for(int i = 0; i < 6; i++) { // If we didn't see a certain balloon, return false. if(has[i] == false) { return false; } } // We saw all 6 balloons so return true. return true; } // Print a set of experiments to file and to console. int counter = 0; void PrintExperiments(vector<string> &experiments) { counter += 1; cout << "\n\nExperiment " << counter << "\n"; out << "\n\nExperiment " << counter << "\n"; for(int i = 0; i < experiments.size(); i++) { cout << experiments[i] << endl; out << experiments[i] << endl; } } int main() { cout << "Program began.\n"; // The possible three balloon subsets. const int n = 7; string subsets[n] = {"123", "124", "125", "126", "134", "135", "234"}; // Try choosing four of these subsets. for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { for(int k = j+1; k < n; k++) { for(int m = k+1; m < n; m++) { // A container to store the balloon subsets we choose as our experiments. vector<string> experiments; // The four subsets we want to check. experiments.push_back(subsets[i]); experiments.push_back(subsets[j]); experiments.push_back(subsets[k]); experiments.push_back(subsets[m]); bool hasAllBalloons = ExperimentsAreValid(experiments); // Move on to the next experiment set if this one doesn't have all balloons. if(hasAllBalloons == false) { continue; } // Convert these experiments to a generic lettered version. vector<string> genericexperiments = ConvertExperimentsToGeneric(experiments); // Get a list of all possible values for labeling (A=1, B=2, ...), (A=4, B=1, ..), etc. vector< vector<int> > allValuePossibilities = GetValuePossibilities(); // For this set of experiments, try the all possible values for each generic value. // Meaning if Bob sees (A, B, C), (D, A, B), then try all values of {1, 2, 3, 4} // for {A, B, C, D}. // True if the subset values work for the generic experiments. bool somethingElseCanBeA = false; for(int z = 0; z < allValuePossibilities.size(); z++) { vector<int> values = allValuePossibilities[z]; bool valid = ValuesWork(genericexperiments, values); // If the values are valid for anything other than A=1, then we can't use this experiment. // (We want to prove that A can only be 1.) if(valid == true && values[0] != 1) { // Stop checking. somethingElseCanBeA = true; break; } } // A can only be the 1 gram balloon! Success. if(somethingElseCanBeA == false) { // We have all six types, so try this set of experiments. PrintExperiments(experiments); PrintExperiments(genericexperiments); } } } } } out.close(); cout << "Program ended.\n"; return 0; }

The code actually gives two solutions:

​(1,2,4)
(1,2,6)
(1,3,4)
(1,3,5)

​(1,2,5)
(1,2,6)
(1,3,4)
(1,3,5)

Of course, we can prove the second solution is valid the same way we did the first. 

And so, Alice only needs to show Bob four experiments to let him determine which balloon the 1 gram balloon is.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake