A marksman shoots n cans off a fence, the first anywhere and each later one next to a gap; in how many...

combinatorics/target.practice New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

A marksman shoots n cans off a fence, the first anywhere and each later
one next to a gap; in how many orders can the cans be knocked off?

A marksman has n cans on a fence that he intends to shoot at with his
gun.  His strategy is to shoot one can off the fence, and from that
point only shoot a can that is next to a gap left from where a can used
to be.  (So, to clarify, he has n ways of making his first shot, then 2
ways of making his shots from then on until he hits one at the end of
the row, and then he's forced to finish in only one way.)

In how many different orders can the n cans be knocked off?  Assume
that his aim is perfect.

-- Matthew Daly <mwdaly@pobox.com>

Show solution

Represent each possible "configuration" by the ordered pair (l,r) where
l is the number of cans in the left half and r is the number in the
right half.  From (l,r) we can move to either (l-1,r) or (l,r-1).

The number of moves to get from (l,r) to (0,0) is C(l+r,l).

The initial configuration is any of (0,n), (1,n-1), (2,n-2), ... (n,0).

The sum of the moves over all possible starting configurations is
SUM (l=0..n) C(n,l) = 2^n (by binomial thm., row of Pascal's triangle)

But this counts each initial move *twice*.  Thus, the number of
different orders is 2^(n-1)

-- Glenn <rhoads@paul.rutgers.edu>