- #1
jammed
- 26
- 0
Homework Statement
Songs of the Martian classical period had just two notes (let us call them x and y) and
were constructed according to rigorous rules:
I. the sequence consisting of no notes was deemed to be a song (perhaps the most
pleasant);
II. a sequence starting with x, followed by two repetitions of an existing song and
ending with y was also a song;
III. the sequence of notes obtained by interchanging xs and ys in a song was also a
song.
All songs were constructed using those rules.
(i) Write down four songs of length six (that is, songs with exactly six notes).
(ii) Show that if there are k songs of length m then there are 2k songs of length 2m+2.
Deduce that for each natural number there are 2^n songs of length (2^n+1) − 2.
Songs of the Martian later period were constructed using also the rule:
IV. if a song ended in y then the sequence of notes obtained by omitting that y was
also a song.
(iii)What lengths do songs of the later period have? That is, for which natural numbers n
is there a song with exactly n notes? Justify your answer.
Homework Equations
No equations needed.
The Attempt at a Solution
The (i) part was really easy. I used the second rule and third rule to produce the four songs of length 6. The four songs were as follow: xxyxyy, xyxyxy, yyxyxx and yxyxyx. In the second part I tried to use every method possible (even induction) but cannot come to a solution. Same is the case with (iii).
Last edited: