diff options
| author | Sebastiano Tronto <sebastiano@tronto.net> | 2023-09-06 23:26:29 +0200 |
|---|---|---|
| committer | Sebastiano Tronto <sebastiano@tronto.net> | 2023-09-06 23:26:29 +0200 |
| commit | e1a43ad11e539368c82ff8182efef2f7c101d555 (patch) | |
| tree | fdc08deee35240cf09a68435804f4721032ce412 /src/speedcubing/slice-theory | |
| parent | 00fd6a40601cd5a859127c618f4888fad76467c4 (diff) | |
| download | sebastiano.tronto.net-e1a43ad11e539368c82ff8182efef2f7c101d555.tar.gz sebastiano.tronto.net-e1a43ad11e539368c82ff8182efef2f7c101d555.zip | |
fixed proof
Diffstat (limited to 'src/speedcubing/slice-theory')
| -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. |
