Ask The Wizard #357

There are permut(9,3)*permut(6,3)*permut(3,3)/fact(3) = 60,480 possible permutations to sort through to find the answer. I must admit I tried for at least an hour by trial and error and didn't find a solution.

So, I wrote a program to sort through all fact(9) = 362,880 ways to sort the nine digits and tested all of them. The tricky part was to sort through every possible way to order the nine numbers. Here is how to do it, using lexographic sorting.

1. Put all nine elements in an array, arranged from lowest to highest.
2. Find the last element in the array such that the following element is greater. If none are found, exit the program.
3. Starting with the element after that from step 2, find the last element in the array that is greater than that from step 2.
4. Swap the elements in the array from steps 2 and 3.
5. Reverse the elements in the array from the one after that from step 2 until the end.
6. Go back to step 2

Following this process, you'll find the correct answer six times, once for all six ways to order the three fractions.

I wrote the following code, to sort every digit from 1 to 9 in lexographic order and test each one if it was a solution.

void three_fraction(void)
{
 int i, x_max, y_max, temp_array[100], hold, pt;
 int lex_array[] = { 1,2,3,4,5,6,7,8,9 };
 int num_elements = sizeof(lex_array) / sizeof(lex_array[0]);
 int count = 0;
 bool stop = false;
 double tot3;
 cerr << "Number of elements =\t" << num_elements << "\n";
 do
 {
  count++;
  tot3 = (double)lex_array[0] / (double)(10 * lex_array[1] + lex_array[2]);
  tot3 += (double)lex_array[3] / (double)(10 * lex_array[4] + lex_array[5]);
  tot3 += (double)lex_array[6] / (double)(10 * lex_array[7] + lex_array[8]); 
  if (tot3 == 1.0)
  {
   cerr << count << "\t";
   cerr << lex_array[0] << "/" << lex_array[1] << lex_array[2] << " + ";
   cerr << lex_array[3] << "/" << lex_array[4] << lex_array[5] << " + ";
   cerr << lex_array[6] << "/" << lex_array[7] << lex_array[8] << "\n";
  } 
  x_max = -1;
  for (i = 0; i < (num_elements - 1); i++)
  {
   if (lex_array[i] < lex_array[i + 1])
    x_max = i;
  }
  if (x_max >= 0)
  {
   y_max = 0;
   for (i = x_max + 1; i < num_elements; i++)
   {
    if (lex_array[x_max] < lex_array[i])
     y_max = i;
   }
   hold = lex_array[x_max];
   lex_array[x_max] = lex_array[y_max];
   lex_array[y_max] = hold;
   if (x_max + 1 < num_elements - 1) // reverse
   {
    for (i = x_max + 1; i < num_elements; i++)
    {
     temp_array[i] = lex_array[i];
    }
    pt = 0;
    for (i = x_max + 1; i < num_elements; i++)
    {
     lex_array[i] = temp_array[num_elements - 1 - pt];
     pt++;
    }
   }
  }
  else
   stop = true;
 } while (stop == false);
}

Let j = volume of jug.

After the first time the jug was filled, there was 10-j gallons of wine left in the jug. After water replaced the wine, the ratio of wine to the entire keg was (10-j)/10.

After the jug scooped out the diluted wine, there was 10-j gallons of diluted wine left in the keg. The amount of pure wine in the diluted wine can be expressed as:

(10-j)*((10-j)/10) = 5

(10-j)^2 = 50

j^2 - 20j + 100 = 50

j^2 - 20j + 50 = 0

j = (20 +/- sqrt(400-200))/2

j = (20 +/- 10*sqrt(2))/2

j = 10 +/- 5*sqrt(2)

The jug can't be bigger than the keg, so we must use the negative sign:

j = 10 - 5*sqrt(2) =~ apx. 2.92893218813452 gallons.

I had to use a Markov Chain for this one. The following table shows the probability of each final total according to the running sum in the left column. Start with the obvious cases for totals of 13 to 18. Then, for running sums of 0 to 12, take the average of the six cells below.

The probabilities for the initial state can be found in the first row for a sum of 0.