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. Summarizing The Problem Statement
Let's restate the problem statement, highlighting the key points:
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:
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.
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:
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:
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.
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:
The code itself can be found below. (It's unoptimized and pretty ugly, but it gets the job done.)
The code actually gives two solutions:
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 Comments are closed.
|
AuthorHi, I'm srcmake. I play video games and develop software. Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
![]() License: All code and instructions are provided under the MIT License.
|