Expert: Josh - 5/26/2006

Question
Here are three piles of cans, each pile containing three can. There is a number on the can which shows how much is it worth in dollars. This is how they are placed:

  $08  $10  $07
  $10  $07  $09
  $07  $09  $08

You get three throws and you can knock out only the first can of a pile. The first throw counts the original amount on a can, the second counts the double and the third counts the triple of the amount on the can. How can u make exactly $50.

Answer
This problem can be solved by graph theory and path finding algorithms, which are difficult subjects in their own right. Here, we will only consider an ad-hoc method.

In the most general sense, we want to satisfy the condition x+2y+3z=50, where x, y and z denote the amount on the can that we knock out in the first, second and third go, respectively.

From the diagram, it is easy to see that the value of x is limited to the set of numbers in S1={7,8,9}.

The value of y is conditioned upon the previous selection. If x was 7, then, the feasible values for y are given by S2a={8,9,10|x=7}. (Here, the vertical bar "|" reads "given that".)
The remaining sets of values for y, conditioned upon x are given by S2b={7,9|x=8} and S2c={7,8|x=9}.

Rather than working out the set values for S3, we attempt to solve x+2y+3z=50 directly, subject to the aforementioned constraints. Then, we will verify whether it is possible to obtain a particular value of z, given the path history.

Of course, z=[50-(x+2y)]/3 must be an integer.
If x=7 (first select from S1), y=8 (subsequently, select from S2a), we get z=[50-23]/3=9.

The situation depicted below shows that it is indeed possible for us to knock out a can with "$9" in the third go.

$08  $10  $07
$10  $07  $09
x1x  $09  x2x