| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
A problem, not for regular contributors, from an old Putnam competition: N stones are in a row. Pick them up, one at a time, starting with any stone in the row, and then always picking up a stone adjacent to the one you just picked up. If you've just picked up the end of the row, then you have only one choice of next stone, otherwise you have two choices (unless you're finished.) Problem: (1) given N, how many different ways are there to pick up the stones (see below for N=4.) (2) give a short, clear argument why that answer is true. For N=4, there are 8 ways to pick up the stones, labeled ABCD: A,B,C,D B,A,C,D B,C,A,D B,C,D,A C,B,A,D C,B,D,A C,D,B,A D,C,B,A [This problem was recently told to me by Dave Eklund.] John
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 651.1 | CLT::GILBERT | eager like a child | Tue Jan 20 1987 01:32 | 10 | |
>For N=4, there are 8 ways to pick up the stones, labeled ABCD: > > A,B,C,D B,A,C,D B,C,A,D B,C,D,A > C,B,A,D C,B,D,A C,D,B,A D,C,B,A While the number of ways is correct, there are some errors in the list. The following list corrects them: A,B,C,D B,A,C,D C,A,B,D C,B,A,D D,A,B,C D,B,A,C D,C,A,B D,C,B,A | |||||
| 651.2 | GNERIC::QUAYLE | Tue Jan 20 1987 14:06 | 29 | ||
Given N stones, the number of possible orders of picking up the stones
beginning with the stone in the Mth position is (N-1 M-1) where (N-1 M-1)
is shorthand for / N-1 \ (N-1)!
| | = ------------------
\ M-1 / (M-1)!(N-1-(M-1))!
Label the stones from the left as ABCDEFG... as before.
Given any starting stone, the stones to the left of it must be picked up in
reverse alphabetical order and the stones to the right of it must be picked
up in forward alphabetical order since only adjacent stones are allowed to
be removed. That is, if the first stone I pick up is the stone labeled C,
then I MUST pick up the stone labeled B BEFORE I pick up the stone labeled
A.
So, if I start at the stone in the Mth position, there will be M-1 stones
to the left of it and N-M stones to the right of it. The total number of
possible orders in which to pick up the stones is the number of ways of
merging two ordered sequences. The first sequence has length M-1 and the
second sequence has length N-M, so the total number of possible orders
starting from the Mth position is
(N-M+M-1 M-1)
= (N-1 M-1)
These are the coefficients in the binomial expansion of (1+x)^(N-1),
therefore the sum the number of orderings from all possible starting positions
is 2^(N-1).
Given N stones, they may be picked up according to the rules in 2^(N-1)
orders.
| |||||
| 651.3 | right | VINO::JMUNZER | Tue Jan 20 1987 15:31 | 6 | |
Re .2: very nice. I think that the proof can be even shorter, though.
Re .1: looks like a difference in assumptions behind the notation.
.2 certainly answered the problem the way I intended it.
John
| |||||
| 651.4 | A short proof | MODEL::YARBROUGH | Tue Jan 20 1987 17:03 | 8 | |
May I? Thank you. There are the same number of ways of placing stones in the n-row as of removing them. When placing each stone before the last, there are two places available - at each end of the empty space in the middle. Thus there are n-1 2-way decisions to be made, and just 2^(n-1) ways of doing that. Lynn | |||||
| 651.5 | How you look at problems | VINO::EKLUND | Dave Eklund | Thu Jan 22 1987 11:45 | 5 |
Yes, I believe that this was the intended approach - namely,
consider picking up the stones in reverse order! Always two
choices except for the last stone. It's all a matter of how you
look at the problem...
| |||||