Interleaving: Difference between revisions
| Line 39: | Line 39: | ||
Proof: Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. |''A''| = 1 implies that ''k'' = 1 mod |''w''|, so |''A''| ≥ 2 and contains at least two intervals '''w'''<sub>1</sub> and '''w'''<sub>2</sub>. | Proof: Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. |''A''| = 1 implies that ''k'' = 1 mod |''w''|, so |''A''| ≥ 2 and contains at least two intervals '''w'''<sub>1</sub> and '''w'''<sub>2</sub>. | ||
Say |''A''| = 2. (If |''A''| ≥ 3 then the proof is easy.) Suppose the (''k'' - 1)-step subword σ of ''S'' has size '''w'''<sub>1</sub>, and assume WOLOG that σ ends in '''Z'''. Then '''Z'''σ and σ'''W''' are subwords, where '''W''' is a non-'''Z''' letter. Assume WOLOG '''W''' = '''X'''. Then we have that the word σ'''X''' = '''V'''τ for some non-'''Z''' letter '''V''' and subword τ. | Say |''A''| = 2. (If |''A''| ≥ 3 then the proof is easy.) Suppose the (''k'' - 1)-step subword σ of ''S'' has size '''w'''<sub>1</sub>, and assume WOLOG that σ ends in '''Z'''. Then '''Z'''σ and σ'''W''' are subwords, where '''W''' is a non-'''Z''' letter. Assume WOLOG '''W''' = '''X'''. Then we have that the word σ'''X''' = '''V'''τ for some non-'''Z''' letter '''V''' and subword τ where the size of τ is '''w'''<sub>2</sub>. | ||
=== Proof of Theorem === | === Proof of Theorem === | ||