diff options
Diffstat (limited to 'src/speedcubing')
| -rw-r--r-- | src/speedcubing/slice-theory/slice-theory.md | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/src/speedcubing/slice-theory/slice-theory.md b/src/speedcubing/slice-theory/slice-theory.md index 784f5d7..e537a0b 100644 --- a/src/speedcubing/slice-theory/slice-theory.md +++ b/src/speedcubing/slice-theory/slice-theory.md | |||
| @@ -304,12 +304,12 @@ subsequence with sum 0, then k <= n. | |||
| 304 | *Clarification: non-trivial means that it contains at least one element | 304 | *Clarification: non-trivial means that it contains at least one element |
| 305 | and it is not the whole sequence.* | 305 | and it is not the whole sequence.* |
| 306 | 306 | ||
| 307 | **Proof** (thanks to Chiara for the nice proof). the Theorem can be | 307 | **Proof** (thanks to Chiara for the nice proof). It is enough to |
| 308 | re-stated as follows: any sequence of n elements of Z/nZ has a | 308 | prove that any sequence of n+1 elements of Z/nZ has a subsequence whose |
| 309 | subsequence whose sum is 0. To prove this equivalent statement, | 309 | sum is 0. To prove this, let, for l=1 to n+1, s\_l = a\_1 + ... + a\_l. |
| 310 | let, for l=1 to k, s_l = a_1 + ... + a_l. If s_i=0 for any i, we | 310 | If s\_i=0 for any i, we are done. Otherwise by the pigeonhole principle |
| 311 | are done. Otherwise by the pigeonhole principle there must be s_i | 311 | there must be s\_i and s\_j with s\_i = s\_j and, say, i < j. But then |
| 312 | and s_j with s_i = s_j and, say, i < j. But then the subsequence | 312 | the subsequence a\_(i+1), ..., a\_j has sum s\_j - s\_i = 0. This proves |
| 313 | a_(i+1), ..., a_j has sum s_j - s_i = 0. This proves the claim. | 313 | the claim. |
| 314 | 314 | ||
| 315 | More work needs to be done here. | 315 | More work needs to be done here. |
