Snowman
Problem
| All the words in the Snowman language consist of exactly seven letters formed from the letters {s, no, wm, an} arranged in some order where the paired letters cannot be separated. For example ``snonono'' and ``sssanwm'' are words in the language but ``sssmwan'' and ``sssawmn'' are not. How many words are there in the Snowman language? | Image
|
Student Solutions
Words with one s
These words have 3
'doubles' which we denote by X, Y and Z, making words in 4
different ways, namely sXYZ, XsYZ, XYsZ or XYZs.
Each of the 'doubles can be any of the 3 choices - no, wm or an -
giving 3x3x3=27 choices of XYZ.
Hence there are 4x27=108 words containing one s.
Words with 3 s's
These words have 2
'doubles' X and Y making words in 10 different ways, namely sssXY,
ssXsY, ssXYs, sXssY, sXsYs, sXYss, XsssY, XssYs, XsYss,
XYsss.
Each of the 'doubles can be any of the 3 choices - no, wm or an -
giving 3x3=9 choices of XY.
Hence there are 10x9=90 words containing three s's.
Words with 5 s's
These words have 1
'double', denoted by X, making words in 6 different ways, namely
Xsssss, sXssss , ssXsss, sssXss, ssssXs, sssssX
The double can be any of the 3 choices.
Hence there are 6x3=18 words containing five s's.
Word with seven s's
There is one word
with seven s's.
For an
alternative method, you might like to try to do this by using the
fact that words with n letters are either formed by putting an s
before words with (n-1) letters or by putting any one of the three
'doubles' before words with (n-2) letters. Using
Wn for
the number of words with n letters this gives a formula:
Wn =
Wn-1 +
3Wn-2 where W1= 1 and
W2=4.
Using this formula you can find W3, W4, W5, W6 and W7.