Interleaving: Difference between revisions
Tags: Mobile edit Mobile web edit |
Tags: Mobile edit Mobile web edit |
||
| Line 41: | Line 41: | ||
Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. {{pipe}}''A''{{pipe}} = 1 implies that ''k'' = 1 mod {{pipe}}''w''{{pipe}}, so {{pipe}}''A''{{pipe}} ≥ 2 and contains at least two intervals '''w'''<sub>1</sub> and '''w'''<sub>2</sub>. | Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. {{pipe}}''A''{{pipe}} = 1 implies that ''k'' = 1 mod {{pipe}}''w''{{pipe}}, so {{pipe}}''A''{{pipe}} ≥ 2 and contains at least two intervals '''w'''<sub>1</sub> and '''w'''<sub>2</sub>. | ||
Say {{pipe}}''A''{{pipe}} = 2. (If {{pipe}}''A''{{pipe}} ≥ 3 then the proof is easy.) Say ''B'' is the set of all subwords of ''w'' (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords | Say {{pipe}}''A''{{pipe}} = 2. (If {{pipe}}''A''{{pipe}} ≥ 3 then the proof is easy.) Say ''B'' is the set of all subwords of ''w'' (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords of ''w'' subtending '''w'''<sub>2</sub>. | ||
Choose ''b'' in ''B'' and ''c'' in ''C'' and consider the subwords ''b''('''XZ''', '''YZ''') and ''c''('''XZ''', '''YZ''') of ''S''. | Choose ''b'' in ''B'' and ''c'' in ''C'' and consider the subwords ''b''('''XZ''', '''YZ''') and ''c''('''XZ''', '''YZ''') of ''S''. | ||