PFunked

Coin Problem

Here's a puzzle.

I'm at a vending machine a couple minutes ago, I see something I want for $0.80. In my pocket is what we'll assume is an even distribution and infinite supply of nickels, dimes, and quarters. I pull a random coin out of my pocket and put it in the machine. It just so happens my total reaches exactly $0.80 and I stop inserting coins. What is the probability of this happening?

Try, Try Again

One way to approach this problem is to get an approximation of the probability by testing out random coins a hundred thousand times or so. Here's a quick brute-force PHP calculation...

<?php

$case_total = 0;
$case_target = 0;
$coin = 0;
$target = 80;
$iterations = 100000;

srand((double)microtime()*1000000);  

// an iteration for each entire attempt
for ($i=0; $i<$iterations; $i++) {

  // start with no coins
  $current_count = 0;
  
  // add coins until I have enough for my purchase
  while ($current_count < $target) {
    $coin = rand(1,3); 
    switch ($coin) {
      case 1: // nickel
        $current_count += 5; 
        break;
      case 2: // dime
        $current_count += 10;
        break;
      case 3: // quarter
        $current_count += 25;
        break;
    }
  }

  $case_total++;
  
  // if I had exact change...
  if ($current_count == $target) $case_target++;

}

echo "Probability estimate after "
    . $iterations . " iterations:<br />\n";
echo ($case_target / $case_total);

?>

Rat In A Vending Machine

Here's my idea for a second way to approach this from code. It is almost identical to the classic "Rat in a Maze" problem. We use recursion to efficiently check every possibility.

To correlate this code to real life, imagine that we're creating a tall stack of the coins. At each step we first try stacking a nickel, then a dime, then a quarter. While we have less than $0.80 in the stack, we add another coin. Once we hit $0.80 or more, we mark the results and remove the last coin. Once we've tried each of the three coins at a level, we remove the quarter and go back down to the previous level.

For example, this code will first stack 16 nickels, which will come to exactly $0.80. We remove the top nickel, put a dime on top, and we're at $0.85. Too much. We remove the dime and put a quarter, and we're at $1.00, also too much. We remove the quarter and the 15th nickel and place a dime on top. $0.80 again. Continue until all possibilities are explored.

In PHP:

<?php

$total = 0;
$target = 80;
$cases_exact_change = 0;
$cases_too_much_change = 0;
$probability = 0.0;
$coin_count = 0;

function coin($value) {
  global $total;
  global $target;
  global $cases_exact_change;
  global $cases_too_much_change;
  global $probability;
  global $coin_count;

  $total += $value;
  $coin_count++;

  if ($total < $target) {
    coin(5);
    coin(10);
    coin(25);
  }
  else if ($total == $target) {
    $cases_exact_change++;
    $probability += pow(1/3,$coin_count);
  }
  else { // $total > $target
    $cases_too_much_change++;
  }

  $total -= $value;
  $coin_count--;

}

/* main */

coin(5);
coin(10);
coin(25);
echo "Exact change in " 
    . $cases_exact_change . " out of " 
    . ($cases_exact_change + $cases_too_much_change) 
    . " possible cases.";
echo "<br />\n";
echo "Probability " . $probability;

?>

With this second solution, I at first stopped at 3142/8915, which is 0.3524, not quite our estimate. So I knew something was up. Of course, I'd forgotten that the probability of each case happening depends on the number of coins (you're more likely to get 3 quarters and a nickel than 16 nickels in a row). Engineer friend James "Jigawatt" to the rescue, who knew the probability was (1/3)^len, where len is the number of coins (and 1/3rd because there are three coin choices at each step).

He coded up a VBA solution that yielded 3142 out of 8915 and 36.98%. So I'm pretty sure this problem is officially solved. As James put it, "QED".