Logic : Ox-words (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

26
0
1. The problem statement, all variables and given/known data
Ox-words are sequences of letters a and b that are constructed according to the following
rules:
I. The sequence consisting of no letters is an Ox-word.
II. If the sequence W is an Ox-word, then the sequence that begins with a, followed
by W and ending in b, written aWb, is an Ox-word.
III. If the sequences U and V are Ox-words, then the sequence U followed by V , written
UV , is an Ox-word.
All Ox-words are constructed using these rules. The length of an Ox-word is the number
of letters that occur in it. For example aabb and abab are Ox-words of length 4.
(i) Show that every Ox-word has an even length.
(ii) List all Ox-words of length 6.
(iii) Let W be an Ox-word. Is the number of occurrences of a in W necessarily equal to
the number of occurrences of b in W ? Justify your answer.
You may now assume that every Ox-word (of positive length) can be written uniquely
in the form aWbW' where W and W' are Ox-words.
(iv) For n>= 0, let Cn be the number of Ox-words of length 2n. Find an expression for
Cn+1(where n+1 = subscript) in terms of C0(where 0 = subscipt),C1(where 1 = subscript), · · · Cn (n = subscript). Explain your reasoning.


2. Relevant equations
no equation


3. The attempt at a solution
(i)Using rule 1 we know that there when there are no letters the word is an ox-word which means we have a word of length zero which is even no. Using rule 2 we can make a word starting with a and containing W and ending in b which will also be even as W can contain no letters or a and b. Using rule 3 then according to rule 1 and rule 2 the song U and v will also be even so every ox-word will be even.
(ii)ababab, abaabb, aabbab, aababb, aaabbb

Pls tell me how to deal with (iv) part.
 
Take an Ox-word of length n. Then this word can be written as aWbW' where W and W' are unique. There are now n-2 cases:

1) W is in C0
Then W' must be in Cn-2. So the number of possible words in this case are C0.Cn-2

2) W is in C1
Then W' must be in Cn-3. So the number of possible words in this case are C1.Cn-3

3) .......


After these cases you just add up all te possible words in the separate cases.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top