Interleaving: Difference between revisions
| Line 69: | Line 69: | ||
(d) is similar to (a) | (d) is similar to (a) | ||
(b) We have '''Z'''b('''XZ''', '''YZ'''), '''Z'''c('''XZ''', '''YZ'''), b('''XZ''', '''YZ''')'''X''' and c('''XZ''', '''YZ''')'''Y'''. If the sizes of b('''XZ''', '''YZ''')'''X''' and c('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have | (b) We have '''Z'''b('''XZ''', '''YZ'''), '''Z'''c('''XZ''', '''YZ'''), b('''XZ''', '''YZ''')'''X''' and c('''XZ''', '''YZ''')'''Y'''. If the sizes of b('''XZ''', '''YZ''')'''X''' and c('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same interval in ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''. | ||
(c) is similar to (b) | (c) is similar to (b) | ||