Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You are given the following recursive definition defining a set of strings. 1∈S; x∈S → x11∈S. What are the 4 shortest members of the set?

What does x11∈S mean?

share|improve this question
    
Probably the concatenation of the string $x$ with the string "11". –  Trevor Wilson Nov 7 '13 at 18:26
    
so would the answer be {1,111}? –  user1045845 Nov 7 '13 at 18:37
1  
If I understand correctly, those would be the two shortest members of the set. –  Trevor Wilson Nov 7 '13 at 18:38
add comment

1 Answer 1

The definition says that the string $1$ is in the set $S$, and if $x$ is any string in $S$, then so is the string $s11$ obtained by appending $11$ to $S$. Since $1\in S$, this rule implies that $111\in S$, which in turn implies that $11111\in S$, and so on. This already shows the three shortest elements of $S$, and it’s clear what the fourth shortest element will be.

One can prove, by the way, that $S$ is precisely the set of all strings consisting of an odd number of $1$’s. The

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.