GATE CS 2014 Set 1 Q.47 (CS Q.37): Combinatorics, Counting, Recurrence Relations and Generating Functions

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is ___.

Your answer

Official answer and solution

Official answer: 12
From: Official GATE 2014 answer key

Solution

Formulate a binary weight equation for the excess weight above the baseline 10 gm weight.

Let the 5 bags be labeled $1, 2, 3, 4, 5$ .
The number of coins picked from bags 1 to 5 are $1, 2, 4, 8, 16$ respectively.
Total number of coins picked = $1 + 2 + 4 + 8 + 16 = 31$ coins.

If all 31 coins had weight 10 gm each, the total weight would be:

31 \times 10 = 310\text{ gm}

Each coin of weight 11 gm adds $(11 - 10) = 1\text{ gm}$ of excess weight.
The actual measured total weight is $323\text{ gm}$ .
Therefore, the excess weight is:

323 - 310 = 13\text{ gm}

Let $x_i \in \{0, 1\}$ indicate whether bag $i$ has 11 gm coins ( $x_i = 1$ ) or 10 gm coins ( $x_i = 0$ ):

1 \cdot x_1 + 2 \cdot x_2 + 4 \cdot x_3 + 8 \cdot x_4 + 16 \cdot x_5 = 13

Expressing 13 in binary base 2:

13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0

So:

$x_1 = 1$ (bag 1 has 11 gm coins)
$x_2 = 0$
$x_3 = 1$ (bag 3 has 11 gm coins)
$x_4 = 1$ (bag 4 has 11 gm coins)
$x_5 = 0$

The bags containing 11 gm coins are bags 1, 3, and 4.
The product of their labels is:

1 \times 3 \times 4 = 12

Final answer

Common trap

Summing the labels ( $1 + 3 + 4 = 8$ ) instead of multiplying them ( $1 \times 3 \times 4 = 12$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 47 of 65, printed as CS Q.37
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source