prove this fact about siteswaps
Johannes Waldmann
for all sequences of n numbers x1, x2, .. xn
whose sum is a multiple of n,
there is a permutation of these numbers
that is a valid siteswap.
example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
a valid permutation is 3 1 4 1 1.
can you prove this? i'll post the solution in a few days. regards,
--
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
-- j...@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
colin
this is actually an hypothesis, it will only become a theorem when someone
can prove it based on specific assumptions, (normally this would be
mathematical proof).
Regards,
Colin.
"Johannes Waldmann" <j...@informatik.uni-leipzig.de> wrote in message
news:8ugviu$8i$1...@news.uni-leipzig.de...
Alan Mackenzie
14:09:34 GMT:
> at the Erlangen convention recently, Alan Mackenzie suggested this
> theorem:
> for all sequences of n numbers x1, x2, .. xn
> whose sum is a multiple of n,
> there is a permutation of these numbers
> that is a valid siteswap.
> example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
> a valid permutation is 3 1 4 1 1.
> can you prove this? i'll post the solution in a few days. regards,
Well, not quite, though I've had a few thoughts.
First of all, thanks for the tip that you can reduce/increase each number
in a siteswap by the same amount. It's obvious, really, (once somebody's
told you :-) that the landing sites for all throws are simply all moved
back/forward by the same amount, so everything balances.
Secondly, you were talking about using this strategy to get to a stage
where a sequence like 4 0 0 0 or 3 0 0 or 2 0 could be isolated and
removed from the ss, leaving a shorter length. I think that rather than
the above, simply use the next (simpler) member of that sequence, namely
1. :-)
************************************************************************
So here's my "proto-proof". I'm using the following terminology:
By "_rotating_" a siteswap, I mean taking throws off one end and moving
them onto the other, such as 3 1 4 1 1 -> 4 1 1 3 1. It's essentially
the same siteswap, just written differently.
By a throw "_wrapping round_", I mean that the notional line from its
throwing position to its landing site passes "off the end" of the ss and
comes back through the beginning. For example, in 3 1 4 1 1, the 4 and
the last 1 wrap round. In 4 1 1 3 1, the 3 and the last 1 wrap round. In
5 3 4, ALL throws wrap round, the 4 doubly so. It's easy enough to see
that the number of wrap rounds in a pattern is equal to the number of
props in it.
[A quick explanation of "induction" for non mathematicians: You start by
noting that a proposition is true for small numbers, like 1 or 2. You
continue by proving that _if_ the proposition holds for 1, 2, ...., n,
_then_ it also holds for n+1. Since it is true for 1 and 2, it must then
also be true for 3. Since it's true for 1, 2, 3, it must also hold for 4.
Just like a row of dominoes toppling, it is then true for all n. The
proposition in question here is "if the sum of n integers is divisible by
n, they can be permuted into a valid siteswap".]
OK, here goes!. Given x1, ....., xn, whose sum is divisible by n. Assume,
without loss of generality, that the xm's all lie between 0 and n-1. I'm
going to proceed by induction on the length of the siteswap. The
proposition is manifestly true for small n, like 1 or 2:
e.g., start with 1 1 1 3 4, five numbers whose sum is divisible by 5.
1/- Reduce/increase each xn by the same amount, if necessary, so that (at
least) one of the xm's is a 1. label this xn.
e.g. 1 1 3 4 1 (reduction/increase wasn't necessary here).
2/- Remove this 1 from the set, leaving x1, .....,x(n-1), whose sum is
one less than a multiple of n.
e.g. 1 1 3 4
3/- Add 1 to one of the above (no, I don't know if it's important which
xm, this being a hole in my "proto-proof".), leaving x1, x2, ....
x(n-1), whose sum is a multiple of n. Label the altered one xi (i for
"incremented").
e.g. 1 2 3 4
^ (The ^ denotes xi)
4/- Subtract n from as many xm's as is necessary, INCLUDING XI, so that
their sum is zero. Some of the xm's, including xi, will now be negative,
but that's OK. Again, I haven't worked out how to determine which xm's to
adjust. This is another hole.
e.g. 1 -3 3 -1
^
5/ The sum of the adjusted numbers x1, ...., x(n-1) is zero, hence also
divisible by (n-1). By the inductive hypothesis, these can be permuted
into a valid siteswap. Do this. x1, ...., x(n-1) is now a valid siteswap
of length (n-1). There may well be "negative" as well as "positive"
wraparounds.
e.g. -3 3 1 -1
^
6/- Rotate the siteswap so that the landing site of xi (the one we
incremented in step 3) is x1.
e.g. 3 1 -1 -3
^
7/- Conjecture that we can always perform the foregoing steps such that
the siteswap we now have has _no_ wraparounds. Decrement xi (restoring
it's original value (mod n)) and restore xn (which is 1). xi now lands on
xn, and xn lands on x1. We now have a valid length n siteswap.
e.g. 3 1 -1 -4 1
^
8/- Reverse the transformations of steps 4 and 1. We now have the
original x1, ...., xn permuted into a valid siteswap.
e.g. 3 1 4 1 1
^
************************************************************************
How am I doing, Joe?
By the way, that 7-ring 1-count passing pattern was _fun_ :-).
> Johannes Waldmann
--
Alan Mackenzie (Munich, Germany)
Email: aa...@muuc.dee; to decode, wherever there is a repeated letter
(like "aa"), remove one of them (leaving, say, "a").
miwenble
A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the xi's is
divisble by n AND x1+1 # x2+2 # ... # xn+n
(Note: # is the nearest I can get to 'is not equal to' on my keyboard)
The solution works using moduo arithmetic. Since X is congruent to 0 modulo
n, the xi's can be replaced by a series R = {r1, r2,..., rn} where the sum
of the ri's = 0 and -n/2 <= ri <= n/2 for all i. This is achieved by
reducing the xi's by appropriate multiples of n.
(Note 2: <= means 'less than or equal to'. Oh for an APL keyboard.)
For example, consider the series {6,7,8,11}. This is of length 4 and the sum
is 32 which is divisible by 4. By subtracting 4,8,8 and 12 respectively, it
can be replaced by the series {2, -1, 0, -1} which sums to 0.
Next, we need to demonstrate that there is a permutation of the first n
natural numbers {1,2,..., n} ({a1, a2,...,an}, say), such that {r1+a1,
r2+a2, ... rn+an} = {1,2,...,n}. Since the numbers 1 to n are all different,
this will complete the proof.
The fact that the ri's sum to 0 means that the series {r1+a1,r2+2,...,rn+an}
will have the same sum as {a1,a2,...,an}, viz., n(n+1)/2. Since all of the
ri's are less than or equal to n/2, the ai's can be chosen in such a way
that all of the (ri+ai)'s are positive and less than or equal to n. Now, at
this point I get a bit hazy, but I think that the Pigeonhole Principle can
be used to show that the series {ri+ai} must therefore be a permutation of
the sequence {1,2,...,n}. Hence the {ri+ai} are all different, which
completes the proof
So, continuing with the above example, rearrange {1,2,3,4} into the sequence
{1,2,4,3}. Add this to the series {2,-1,0,-1} from the earlier paragraph to
get {3,1,4,2} . These are all different, and hence the original sequence can
be re-arranged into a siteswap.
There is an interesting corollary of this theorem. If all elements of the
original series X are divisible by n, then EVERY permutation of X is a valid
siteswap. This follows because the series X can be reduced to {0,0,...,0},
from which the proof is immediate.
Mike W
> "Johannes Waldmann" <j...@informatik.uni-leipzig.de> wrote in message
> news:8ugviu$8i$1...@news.uni-leipzig.de...
> > at the Erlangen convention recently, Alan Mackenzie suggested this
> theorem:
> >
> > for all sequences of n numbers x1, x2, .. xn
> > whose sum is a multiple of n,
> > there is a permutation of these numbers
> > that is a valid siteswap.
> >
> > example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
> > a valid permutation is 3 1 4 1 1.
> >
> > can you prove this? i'll post the solution in a few days. regards,
Steve Otteson
miwenble wrote in message <3a0ed...@news2.vip.uk.com>...
>Nice problem!
>
>A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the xi's is
>divisble by n AND x1+1 # x2+2 # ... # xn+n
>
The condition "x1+1 #x2+2 ..." does not guarentee a valid siteswap.
Consider {6,7,8,11}. The sum is divisible by 4 and 6+1 # 7+2 # 8+3 # 11+4.
The sequence fits the above criteria for a valid siteswap, but it is not
valid because
the 6, 8, and 11 land at the same time.
The condition will work if you reduce each sum by an appropriate
multiple of n so
that the result is bigger than zero and less than n. For example, 6+1=7.
Subtract
4 from 7 to get 3. Subtracting 8 from 7+2, 8 from 8+3, and 12 from 11+4
gives us
3,2,3,3, which fails the second condition.
>(Note: # is the nearest I can get to 'is not equal to' on my keyboard)
>
>The solution works using moduo arithmetic. Since X is congruent to 0 modulo
>n, the xi's can be replaced by a series R = {r1, r2,..., rn} where the sum
>of the ri's = 0 and -n/2 <= ri <= n/2 for all i. This is achieved by
>reducing the xi's by appropriate multiples of n.
>
>(Note 2: <= means 'less than or equal to'. Oh for an APL keyboard.)
>
>For example, consider the series {6,7,8,11}. This is of length 4 and the
sum
>is 32 which is divisible by 4. By subtracting 4,8,8 and 12 respectively, it
>can be replaced by the series {2, -1, 0, -1} which sums to 0.
>
>Next, we need to demonstrate that there is a permutation of the first n
>natural numbers {1,2,..., n} ({a1, a2,...,an}, say), such that {r1+a1,
>r2+a2, ... rn+an} = {1,2,...,n}. Since the numbers 1 to n are all
different,
>this will complete the proof.
>
>The fact that the ri's sum to 0 means that the series
{r1+a1,r2+2,...,rn+an}
>will have the same sum as {a1,a2,...,an}, viz., n(n+1)/2. Since all of the
>ri's are less than or equal to n/2, the ai's can be chosen in such a way
>that all of the (ri+ai)'s are positive and less than or equal to n. Now, at
>this point I get a bit hazy, but I think that the Pigeonhole Principle can
>be used to show that the series {ri+ai} must therefore be a permutation of
>the sequence {1,2,...,n}. Hence the {ri+ai} are all different, which
>completes the proof
The hazy part is the proof that the permutation of the first n numbers
exists such that {r1+a1, r2+a2,...,m+an} = {1,2,...,n}. Does the Pigeonhole
Principle help to prove that the permutation exists? I do not know much
about the Pigeonhole Principle.
It seems reasonable that the permutation exists, but if I had one less
drop during my juggling endevours for every time that I said "It seems
reasonable" and was wrong, I would be dropless. No, I would have
negative drops, ... I would have juggled before I knew how to juggle!
(Steve ponders this for a moment.) I am sorry that I got carried away. It
will never happen again.
If the permutation exists, we are still left with the problem of finding
it.
>
>So, continuing with the above example, rearrange {1,2,3,4} into the
sequence
>{1,2,4,3}. Add this to the series {2,-1,0,-1} from the earlier paragraph to
>get {3,1,4,2} . These are all different, and hence the original sequence
can
>be re-arranged into a siteswap.
It seems reasonable that there is a relationship between the
permutation
and the valid siteswap? ( Oh-oh, I'm doing it again.) For example, in your
permuted sequence, you switched the 3rd and 4th elements, so, switching
the 3rd and 4th elements of {6,7,8,11} yields {6,7,11,8} which is a valid
siteswap. Coincidence?
Steve Otteson
miwenble wrote in message <3a0ed...@news2.vip.uk.com>...
>>Nice problem!
>>
>>A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the xi's
is
>>divisble by n AND x1+1 # x2+2 # ... # xn+n
>>
>>
is
>>divisble by n AND x1+1 # x2+2 # ... # xn+n
>>
>snip
> The second condition will work if you reduce each sum by an appropriate
>multiple of n so that the result is bigger than zero and less than n. For
>example, 6+1=7. Subtract 4 from 7 to get 3. Subtracting 8 from 7+2, 8 from
>8+3, and 12 from 11+4 gives us 3,2,3,3, which fails the second condition.
>
>big snip
What if someone wrote a computer program that would test all possible
sequences {x1,x2,...,xn} where the sum of the xi's is an natural multiple of
n, to see if the x's can be permuted into a valid siteswap. (The program
would be easy to write.) Let x range from 0 to 30 and let n range from 3 to
20. If the program fails to find a sequence that cannot be permuted into a
valid siteswap, would the program be accepted as proof?
If not, for what values of x and n would make the computer program accepted
as proof? Maybe the program could be considered as a "practical" proof. By
"practical" I am referring to the upper limits of x and n that a juggler on
Earth would use for their siteswaps. For the extra-terrestrial jugglers ( I
know you are out there) I will entertain your suggestion for upper limits
for x and n.
There are 3 methods to prove something: let someone else do it (this is the
easiest), use a computer program (Do this only if it is easier than the next
method), or prove it myself (the most desperate).
I'm going to look at Alan's "proto-proof" first. If I'm not convinced, I'll
dust the C++ compiler and see what comes up.
Steve
Alan Mackenzie
> miwenble wrote in message <3a0ed...@news2.vip.uk.com>...
>>>Nice problem!
>>>A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the
>>>xi's is divisble by n AND x1+1 # x2+2 # ... # xn+n
>>>(Note: # is the nearest I can get to 'is not equal to' on my keyboard)
>>>A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the
>>>xi's is divisble by n AND x1+1 # x2+2 # ... # xn+n
>>snip
>>The second condition will work if you reduce each sum by an appropriate
>>multiple of n so that the result is bigger than zero and less than n.
>>For example, 6+1=7. Subtract 4 from 7 to get 3. Subtracting 8 from
>>7+2, 8 from 8+3, and 12 from 11+4 gives us 3,2,3,3, which fails the
>>second condition.
>>big snip
> What if someone wrote a computer program that would test all possible
> sequences {x1,x2,...,xn} where the sum of the xi's is an natural
> multiple of n, to see if the x's can be permuted into a valid siteswap.
> (The program would be easy to write.) Let x range from 0 to 30 and let
> n range from 3 to 20. If the program fails to find a sequence that
> cannot be permuted into a valid siteswap, would the program be accepted
> as proof?
No. Think of a^n + b^n = c^n (for a, b, c integers, n an integer > 2).
This was known to be unsatisfiable for all n below N, for very large
values of N, but it took a heroic proof (the mathematical proof of the
century) to prove that it was unsatisfiable for _all_ n.
> If not, for what values of x and n would make the computer program
> accepted as proof?
It would likely be accepted as a "proof" by physicists for moderate
values of x and n, and most certainly by astronomers, for much lower
values, but mathematicians demand certainty, for _all_ values of x and n.
:-)
> Maybe the program could be considered as a "practical" proof. By
> "practical" I am referring to the upper limits of x and n that a
> juggler on Earth would use for their siteswaps. For the
> extra-terrestrial jugglers ( I know you are out there) I will entertain
> your suggestion for upper limits for x and n.
There are celestial bodies with arbitrarily low gravity, and let us posit
extra-terrestrial jugglers with arbitrarily high strength and accuracy. I
refuse to entertain any upper limits on x or n. I want a proof valid for
_all_ n.
> There are 3 methods to prove something: let someone else do it (this is
> the easiest), use a computer program (Do this only if it is easier than
> the next method), or prove it myself (the most desperate).
> I'm going to look at Alan's "proto-proof" first. If I'm not convinced,
> I'll dust the C++ compiler and see what comes up.
My proto-proof needs refinement. Any and all suggestions are welcome.
> Steve
Alan Mackenzie
-0000:
>> "Johannes Waldmann" <j...@informatik.uni-leipzig.de> wrote in message
>> news:8ugviu$8i$1...@news.uni-leipzig.de...
>> > at the Erlangen convention recently, Alan Mackenzie suggested this
>> theorem:
>> > for all sequences of n numbers x1, x2, .. xn
>> > whose sum is a multiple of n,
>> > there is a permutation of these numbers
>> > that is a valid siteswap.
>> > example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
>> > a valid permutation is 3 1 4 1 1.
>> > can you prove this? i'll post the solution in a few days. regards,
>> > --
>> > -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
>> > -- j...@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
> Nice problem!
> A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the
> xi's is divisble by n AND x1+1 # x2+2 # ... # xn+n
> (Note: # is the nearest I can get to 'is not equal to' on my keyboard)
> The solution works using moduo arithmetic. Since X is congruent to 0
> modulo n, the xi's can be replaced by a series R = {r1, r2,..., rn}
> where the sum of the ri's = 0 and -n/2 <= ri <= n/2 for all i. This is
> achieved by reducing the xi's by appropriate multiples of n.
No, not quite. The combination {1, 1, 1, 1} already has it's elements
between -2 and +2, but its sum is 4, not 0. But what you're basically
saying is that xi = ri (mod n).
> (Note 2: <= means 'less than or equal to'. Oh for an APL keyboard.)
> For example, consider the series {6,7,8,11}. This is of length 4 and
> the sum is 32 which is divisible by 4. By subtracting 4,8,8 and 12
> respectively, it can be replaced by the series {2, -1, 0, -1} which
> sums to 0.
> Next, we need to demonstrate that there is a permutation of the first n
> natural numbers {1,2,..., n} ({a1, a2,...,an}, say), such that {r1+a1,
> r2+a2, ... rn+an} = {1,2,...,n}. Since the numbers 1 to n are all
> different, this will complete the proof.
...and the site swap will be built up by placing rm in the am'th
position.
Agreed, modulo n.
> The fact that the ri's sum to 0 means that the series
> {r1+a1,r2+2,...,rn+an} will have the same sum as {a1,a2,...,an}, viz.,
> n(n+1)/2. Since all of the ri's are less than or equal to n/2, the ai's
> can be chosen in such a way that all of the (ri+ai)'s are positive and
> less than or equal to n.
I think you're right, but I can't see it for sure. I think this step
needs a rather more solid proof.
> Now, at this point I get a bit hazy, but I think that the Pigeonhole
> Principle can be used to show that the series {ri+ai} must therefore be
> a permutation of the sequence {1,2,...,n}. Hence the {ri+ai} are all
> different, which completes the proof
No: If your R is {-2, -1, 0 3} and your A is {3, 2, 1, 0}, adding them
together produces {1, 1, 1, 3}, which isn't satisfactory. Here, of
course, there is a suitable choice of A, namely {2, 3, 1, 0}, but it
remains to be proven that there is _always_ such a suitable A.
[ .... ]
> Mike W
Jake Cooper
"Steve Otteson" <ot...@mwt.net> wrote in message
news:QeWQ5.203$aX.9...@homer.alpha.net...
>
> miwenble wrote in message <3a0ed...@news2.vip.uk.com>...
> >Nice problem!
> >
> >A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the xi's
is
> >divisble by n AND x1+1 # x2+2 # ... # xn+n
>
> The condition "x1+1 #x2+2 ..." does not guarentee a valid siteswap.
> Consider {6,7,8,11}. The sum is divisible by 4 and 6+1 # 7+2 # 8+3 #
11+4.
> The sequence fits the above criteria for a valid siteswap, but it is not
> valid because
> the 6, 8, and 11 land at the same time.
> The condition will work if you reduce each sum by an appropriate
> multiple of n so
> that the result is bigger than zero and less than n. For example, 6+1=7.
> Subtract
> 4 from 7 to get 3. Subtracting 8 from 7+2, 8 from 8+3, and 12 from 11+4
> gives us
> 3,2,3,3, which fails the second condition.
While I can hardly follow this math, I know that it might be easier to *not*
reduce the numbers by using mod n. You could take the highest number (11,
in this case) divide it by n (4), and round up and add 1 (add one because
you've already gone partway through the siteswap once) to find the maximum
number of "wrap-arounds". So this siteswap will "wrap around"
ceiling-function( 11 / 4 ) + 1 = 4 times. Now you can test if x1 # x2+1 #
x3+2 # x4+3 # x1+4 # x2+5 ... until you've wrapped around the appropriate
number of times. In this case, x4+3 cannot = x1+8 which cannot = x3+6.
Since 11+3 = 6+8 = 8+6, the siteswap isn't valid.
On rereading what I wrote, maybe your way is easier to think through. Mine
might be easier to program. No, probably not that either. Oh well, I
tried...
Um, the rest of the math has been snipped, as I don't like reading things
that far above my head.
Jake Cooper
Steve Otteson
Alan Mackenzie wrote in message <5tpju8...@acm.acm>...
>> theorem:
>
>> for all sequences of n numbers x1, x2, .. xn
>> whose sum is a multiple of n,
>> there is a permutation of these numbers
>> that is a valid siteswap.
>
>> example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
>> a valid permutation is 3 1 4 1 1.
>
>> can you prove this? i'll post the solution in a few days. regards,
>
You incremented the second element, so the carrot-top should be under the 2.
>
>4/- Subtract n from as many xm's as is necessary, INCLUDING XI, so that
>their sum is zero. Some of the xm's, including xi, will now be negative,
>but that's OK. Again, I haven't worked out how to determine which xm's to
>adjust. This is another hole.
>
>e.g. 1 -3 3 -1
> ^
The carrot-top should be under the -3.
>
>5/ The sum of the adjusted numbers x1, ...., x(n-1) is zero, hence also
>divisible by (n-1). By the inductive hypothesis, these can be permuted
>into a valid siteswap. Do this. x1, ...., x(n-1) is now a valid siteswap
>of length (n-1). There may well be "negative" as well as "positive"
>wraparounds.
>
>e.g. -3 3 1 -1
> ^
>
>6/- Rotate the siteswap so that the landing site of xi (the one we
>incremented in step 3) is x1.
>
>e.g. 3 1 -1 -3
> ^
The carrot-top should be under the -3. ( The carrot-top for step 5 is
correct.
That's a good boy!)
>
>7/- Conjecture that we can always perform the foregoing steps such that
>the siteswap we now have has _no_ wraparounds. Decrement xi (restoring
>it's original value (mod n)) and restore xn (which is 1). xi now lands on
>xn, and xn lands on x1. We now have a valid length n siteswap.
>
>e.g. 3 1 -1 -4 1
> ^
The carrot-top should be under the -4.
Why is it neccessary to have the siteswap with no wraparounds? Consider
{6,7,8,11}. For step 1 reduce each number by 5 to get
1,2,3,6.
Drop the 1 and add 1 to the 6 (steps 2 and 3):
2,3,7
^
For step 4, subtract all by 4:
-2,-1,3
^
Step 5 isn't needed because -2,-1,3 is a valid siteswap. After step 6:
3,-2,-1
^ Note that there are 2 wraparounds.
After we increment xi and restore xn:
2,-2,-1,1
Unlike your claim in step 7, xi does not land on xn.
Restoring the transformations of step 1 and step 4 respectively:
7,3,4,6 -> adding 5 to all elements.
11,7,8,6 which is a valid siteswap in spite of the 2 conditions in step
7.
There is another example where your method is followed exactly as
above, but at the end of step 7, xn does not land on xi. The other
conditions
of step 7 hold and the method succeeds to its end.
My conclusion is that the conditions in step 7 are not needed.
>
>8/- Reverse the transformations of steps 4 and 1. We now have the
>original x1, ...., xn permuted into a valid siteswap.
>
>e.g. 3 1 4 1 1
> ^
>************************************************************************
In step 5 you refer to the inductive hypothesis. This is an interesting
place in your method because it implies a computer programming
technique called recursion.
You started with a sequence of n numbers whose sum is a multiple of n and
reduce it to a sequence of n-1 numbers whose sum is a multiple of n-1. At
this point (step 5) you tell us to permute the sequence of n-1 numbers into
a valid siteswap. If we apply your method to the new sequence we would have
a
recursive method: a method that uses (or "calls") itself.
The recursive process will end when the problem is reduced to a trivial
case. For your method the trivial case is when there are 2 numbers in the
sequence. All 2-number sequences with even sums are valid siteswaps
I bring recursion up because if we start with a 20 number sequence and
try to convert it into a siteswap (20 number siteswaps are the average, I'm
sure!) some of us might be intimidated at step 5 when we are supposed to
permute 19 numbers into a valid site swap. Using recursion will make the
task easy.
Let's get to work!
Steve O.
miwenble
> >A sequence X = {x1,x2,...,xn} is a valid siteswap if the sum of the xi's
is
> >divisble by n AND x1+1 # x2+2 # ... # xn+n
> >
>
>
> The condition "x1+1 #x2+2 ..." does not guarentee a valid siteswap.
> Consider {6,7,8,11}. The sum is divisible by 4 and 6+1 # 7+2 # 8+3 #
11+4.
> The sequence fits the above criteria for a valid siteswap, but it is not
> valid because
> the 6, 8, and 11 land at the same time.
> The condition will work if you reduce each sum by an appropriate
> multiple of n so
> that the result is bigger than zero and less than n. For example, 6+1=7.
> Subtract
> 4 from 7 to get 3. Subtracting 8 from 7+2, 8 from 8+3, and 12 from 11+4
> gives us
> 3,2,3,3, which fails the second condition.
>
Oops. My mistake. I was guilty of sloppy thinking: I extrapolated from 123
(which is a valid siteswap) and 321 (which isn't), without recognising that
they are both in their reduced form. What I should have said was that if the
sum of {x1,x2,.,xn} is divisible by n and all cyclical permutations of the
series {x1,x2,.,xn} share the property that x1+1 # x2+2 # .# xn+n , then
x1,x2,.,xn is a valid siteswap.
{6,7,8,11} is not a valid siteswap because the arrangement {11,6,7,8} fails
this test (11+1=8+4).
> >Next, we need to demonstrate that there is a permutation of the first n
> >natural numbers {1,2,..., n} ({a1, a2,...,an}, say), such that {r1+a1,
> >r2+a2, ... rn+an} = {1,2,...,n}. Since the numbers 1 to n are all
> different,
> >this will complete the proof.
> >
> >The fact that the ri's sum to 0 means that the series
> {r1+a1,r2+2,...,rn+an}
> >will have the same sum as {a1,a2,...,an}, viz., n(n+1)/2. Since all of
the
> >ri's are less than or equal to n/2, the ai's can be chosen in such a way
> >that all of the (ri+ai)'s are positive and less than or equal to n. Now,
at
> >this point I get a bit hazy, but I think that the Pigeonhole Principle
can
> >be used to show that the series {ri+ai} must therefore be a permutation
of
> >the sequence {1,2,...,n}. Hence the {ri+ai} are all different, which
> >completes the proof
>
>
> The hazy part is the proof that the permutation of the first n numbers
> exists such that {r1+a1, r2+a2,...,m+an} = {1,2,...,n}. Does the
Pigeonhole
> Principle help to prove that the permutation exists? I do not know much
> about the Pigeonhole Principle.
Correct again. This was not so much sloppiness as deliberate obfuscation on
my part. It seems to me that, since the reduced series {r1,r2,.,rn} EITHER
consists of not more than n/2 negative numbers OR it consists of not more
than n/2 positive numbers , then it should be possible to add the positive
numbers to 1,2,., n/2 and the negative numbers to (n+1)/2,.n so as to ensure
that the series of (ai+ri)'s are all <= n, but I couldn't prove it.
If it is possible to show that the (ai+ri)'s are all different and <= n,
then the last part of the proof is, on reflection, fairly obvious and doesn'
t require the Pigeonhole Principle. The series {1,2,.,n} sums to n(n+1)/2.
The sum of any other n different (and positive) numbers must be greater than
n(n+1)/2. Therefore if an arbitrary series of n different positive integers
sums to n(n+1)/2, it must be a permutation of {1,2,.,n}
> If the permutation exists, we are still left with the problem of
finding
> it.
>
Finding it is Applied Maths. I am (or rather, was) a Pure Mathematician, so
such mundane issues are beneath me :-)
>
> It seems reasonable that there is a relationship between the
> permutation
> and the valid siteswap? ( Oh-oh, I'm doing it again.) For example, in
your
> permuted sequence, you switched the 3rd and 4th elements, so, switching
> the 3rd and 4th elements of {6,7,8,11} yields {6,7,11,8} which is a valid
> siteswap. Coincidence?
>
No I don't think it is coincidence. The process of reduction doesn't alter
the sequence of the permutation, so a switch of two elements creates a
sequence that belongs to a different cyclical arrangement.
(I've re-read that last sentence half a dozen times and I still don't
understand it. What I am trying to say is that {1,2,3} {3,1,2} and {2,3,1}
are cyclical arrangements of the same sequence and are all valid siteswaps.
Or to put it another way, they are all length-3 slices from the infinite
sequence 1,2,3,1,2,3,1,2,3,... Switching two elements creates {1,3,2} ,
{2,1,3} and {3,2,1}, none of which are siteswaps.).
Alan Mackenzie
> theorem:
> for all sequences of n numbers x1, x2, .. xn
> whose sum is a multiple of n,
> there is a permutation of these numbers
> that is a valid siteswap.
> example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
> a valid permutation is 3 1 4 1 1.
> can you prove this? i'll post the solution in a few days. regards,
OK, JOE, YOU'VE HAD YOUR FEW DAYS!!
Now, please post your proof. The suspense is killing me!
> -- Johannes Waldmann
Edward Smith
If n natural numbers sum to a multiple of n
and the n natural numbers are not all the same then
you can pick less than n of these numbers that also sum to a multiple of n.
e.g. 1 5 2 4 3 9 4 sum = 4*7
but 5+2 sum = 7
and 1+4+3+9+3 sum = 3*7
Can anyone help me out with the proof of this ? Or find a counterexample ?
Ed
Jake Cooper
I believe 5551 won't work. Sorry : (
Jake Cooper
Loh Koah Fong
> From: Edward Smith [mailto:edward...@worc.ox.ac.uk]
> Posted At: 01 December 2000 07:53
> Posted To: juggling
> Conversation: prove this fact about siteswaps
> Subject: Re: prove this fact about siteswaps
>
>
> I reckon I can prove this if I can prove that:
>
> If n natural numbers sum to a multiple of n
> and the n natural numbers are not all the same then
> you can pick less than n of these numbers that also sum to a
> multiple of n.
>
> e.g. 1 5 2 4 3 9 4 sum = 4*7
>
> but 5+2 sum = 7
> and 1+4+3+9+3 sum = 3*7
>
I think you mean to say:
1+4+3+9+4 sum = 3*7
***
Right?
koah fong
Juggling: http://www.ntu.edu.sg/home/kfloh/juggling.htm
Singapore Jugglers : http://www.juggling.org/~singapore
> Can anyone help me out with the proof of this ? Or find a
> counterexample ?
>
> Ed
>
>
Edward Smith
than n and greater than or equal to 0,
Ed
"Edward Smith" <edward...@worc.ox.ac.uk> wrote in message
news:906p3n$6tj$1...@news.ox.ac.uk...
> I reckon I can prove this if I can prove that:
>
> If n natural numbers sum to a multiple of n
> and the n natural numbers are not all the same then
> you can pick less than n of these numbers that also sum to a multiple of
n.
>
> e.g. 1 5 2 4 3 9 4 sum = 4*7
>
> but 5+2 sum = 7
> and 1+4+3+9+3 sum = 3*7
>
Alan Mackenzie
23:52:58 -0000:
> I reckon I can prove this if I can prove that:
> If n natural numbers sum to a multiple of n
> and the n natural numbers are not all the same then
> you can pick less than n of these numbers that also sum to a multiple
> of n.
> e.g. 1 5 2 4 3 9 4 sum = 4*7
> but 5+2 sum = 7
> and 1+4+3+9+3 sum = 3*7
> Can anyone help me out with the proof of this ? Or find a counterexample ?
YES!! Here's a proof:
***********************************************************************
By "n natural numbers not all the same" you obviously mean "n natural
numbers not all the same modulo n".
Suppose you have n such numbers, u1, u2, ....., un as described. Consider
the following sums:
S1 = u1
S2 = u1 + u2
...
S(n-1) = u1 + u2 + .... + u(n-1)
Sn = u1 + ..............+ u(n-1) + un (this we know to be 0 (mod n))
_OBSERVATION_ _1_ If Sa = Sb (mod n) for any distinct a, b
then u(a+1) + .... + ub = 0 (mod n)
and we have our result.
So suppose S1, S2, ....., Sn are all different (mod n). By counting them,
it will be seen that the S's are (in some order) exactly 0, 1, 2, .....
........, (n-1) (mod n).
By the hypothesis, not all the u's are the same. Therefore, there will be
two adjacent u's, say ui and u(i+1), which are unequal. Swap these two
u's and recalculate the S's:
S1 = u1
S2 = u1 + u2
...
Si = u1 + u2 + ..... + u(i-1) + u (i+1) !!!!!!
S(i+1) = u1 + u2 + .... + u(i-1) + u(i+1) + ui
.....
Sn = ... = 0.
It is clear that the new Si is different from the old Si, but all the
other S's remain unchanged. This the new Si must be the same as some
other S (mod n). Thus by OBSERVATION 1, we have our result.
Quod erat demonstrandum
************************************************************************
For those who missed the beginning of the thread, my original proposition
was that if the sum of n numbers is a multiple of n, they can be permuted
into a valid site swap.
GO FOR IT, ED!!!
> Ed
--
Alan Mackenzie (Munich, Germany)
Email: aa...@muuc.dee; to decode, wherever there is a repeated letter,
Steve Otteson
>For those who missed the beginning of the thread, my original proposition
>was that if the sum of n numbers is a multiple of n, they can be permuted
>into a valid site swap.
>
>GO FOR IT, ED!!!
>
>> Ed
>
>--
>Alan Mackenzie (Munich, Germany)
>Email: aa...@muuc.dee; to decode, wherever there is a repeated letter,
>(like "aa"), remove one of them (leaving, say, "a").
>
Here is my version of the proof. I basically used Johannes Waldmann's
"proto-proof" and added a twist:
Given a sequence X = {x1, x2,..., xn}, where the sum of the xi's is
divisible by n, prove that the xi's can be permuted into a valid siteswap.
The following postulates are assumed to be true:
(1) Any element of a valid siteswap can be increased/decreased by n,
where n = the number of numbers in the siteswap. The modified element will
land at the same site that it did before the modification.
(2) You can add/subtract the same amount to every element of a valid
siteswap and still have a valid siteswap.
(3) A rotated siteswap is unchanged. "Rotating" a siteswap means taking
throws off one end and moving them onto the other, such as
3 1 4 1 1 = 4 1 1 3 1.
(4) The number of "wrap-arounds" of a siteswap pattern is equal to the
number of props in the pattern, which is equal to the sum of the numbers
divided by the number of numbers. By a throw "wrapping around", I mean that
the notional line from its throwing position to its landing site passes "off
the end" of the sequence and comes back through the beginning. For example,
in 2 3 4, the 3 wraps around once and the 4 wraps around twice.
(5) Assume that our theorem is true for n = 1, 2, and 3.
(6) It is possible to convert an n-number siteswap into an n-1 or an n+1
number siteswap (the steps are outlined below).
Remember that the landing site of a number in a siteswap pattern is
found by decreasing the number by one for every position that you move to
the right. The landing site is where the number reaches zero. In 1 2 3, for
example, the 1 lands on the 2, the 2 lands on the 1, and the 3 lands on the
3. For negative numbers, increment the number as you move to the left
until it becomes zero.
Recall that for a siteswap to be valid, each site will have exactly one
landing.
Assume that u1, u2,..., un is a valid siteswap. Perform the following steps
to generate n+1 valid siteswaps that are n+1 numbers long.
Step1. Subtract n from as many um's as is necessary so that their sum is
zero with no wrap-arounds( You might have to rotate the siteswap to
eliminate the wrap-arounds). This is possible because of the postulates(1)
and (4).
Step 2. Decrement the element that lands on u1, and insert a 1 at the
right end of the pattern. We now have a valid siteswap of n+1 numbers.
Step 3. Add 1 to each of the n+1 numbers from step 2.
Step 4. Repeat step 3 n-1 times so that we end up with n+1 valid
siteswap patterns for n+1 numbers.
Assume W = { S1, S2,..., Sm } = the set of all possible valid siteswaps
for n numbers. The number m is finite because I am assuming that every
element s in every siteswap S is between 0 and n-1. ( If you want to
compute the value of m, use graph theory or probability theory.)
Prove that the 4 steps above, when applied to each Si in W, will
generate all possible valid siteswaps for n+1 numbers:
The steps will take turns inserting the numbers 0, 1,..., n into every
possible siteswap pattern for n numbers. There are no other possibilities.
Let's assume that there exists a valid n+1 number siteswap that was
"missed" by the 4 steps. We can use the steps in reverse to reduce the n+1
siteswap to an n siteswap (postulate (6) ). Since W contains every possible
siteswap for n numbers, the n+1 pattern must have been generated by the 4
steps.
Assume that there is a set on n numbers that sum to a multiple of n, that
cannot be permuted into a valid siteswap. Using the steps from above in
reverse, exactly the way Johannes did in his proto-proof, reduce the n
numbers to n-1. The n-1 numbers might not be a valid siteswap, but it will
be a multiple of n-1. Can these n-1 numbers be permuted into a valid
siteswap? If so, we can claim that the n numbers can be permuted into a
siteswap by using the n-1 numbers as a "seed"
If you think that the n-1 numbers cannot be permuted, the n-1 numbers
can be reduced until there are 3 numbers in the pattern. Since all 3 number
sequences that sum to a multiple of 3 can be permuted into a siteswap, we
can generate valid siteswaps back from where we came, ending with our n
numbers permuted into a valid siteswap. Q.E.D.
****************************************************************************
********
What a mess! You should have lots of fun with this.
Steve O.
jbo...@my-deja.com
"miwenble" <miwe...@ccn.go-free.co.uk> wrote:
>
> There is an interesting corollary of this theorem. If all elements of the
> original series X are divisible by n, then EVERY permutation of X is a valid
> siteswap. This follows because the series X can be reduced to {0,0,...,0},
> from which the proof is immediate.
>
> Mike W
This comment tickled a neuron from long ago.
These patterns have some interesting properties, as
discussed in the following posting of mine from
JuggleN (pre-rec.juggling):
http://www.juggling.org/bin/mfs/JIS/rj/1991/10/02-
015312?45
Jack
Sent via Deja.com http://www.deja.com/
Before you buy.
Steve Otteson
Alan Mackenzie wrote in message <0u1909...@acm.acm>...
Actually, we have enough information to finish the proof. If one of the
S's is zero, then all of the other u's have to sum to a multiple of n, i.e.
if S(i) = 0 (mod n), then S(n) - S(i) = 0 (mod n), so the set { u(i+1),
u(i+2),..., u(n) } is the subset that sums to a multiple of n. Quod erat
demonstrandum.
>By the hypothesis, not all the u's are the same. Therefore, there will be
>two adjacent u's, say ui and u(i+1), which are unequal. Swap these two
>u's and recalculate the S's:
>
>S1 = u1
>S2 = u1 + u2
>...
>Si = u1 + u2 + ..... + u(i-1) + u (i+1) !!!!!!
>S(i+1) = u1 + u2 + .... + u(i-1) + u(i+1) + ui
>.....
>Sn = ... = 0.
>
>It is clear that the new Si is different from the old Si, but all the
>other S's remain unchanged. This the new Si must be the same as some
>other S (mod n). Thus by OBSERVATION 1, we have our result.
>
>Quod erat demonstrandum
>
>************************************************************************
>
Alan Mackenzie
>>***********************************************************************
No! If the _last_ S is zero, then {u(i+1) .... } is an empty set. Note
that thus far, we have not yet used the hypothesis that the u's are not
all the same. Therefore we could only expect a proof here if this
hypothesis were redundant. That this is not the case can be seen from the
counter example {1, 1, 1, 1} already provided.
>>By the hypothesis, not all the u's are the same. Therefore, there will be
>>two adjacent u's, say ui and u(i+1), which are unequal. Swap these two
>>u's and recalculate the S's:
>>S1 = u1
>>S2 = u1 + u2
>>...
>>Si = u1 + u2 + ..... + u(i-1) + u (i+1) !!!!!!
>>S(i+1) = u1 + u2 + .... + u(i-1) + u(i+1) + ui
>>.....
>>Sn = ... = 0.
>>It is clear that the new Si is different from the old Si, but all the
>>other S's remain unchanged. This the new Si must be the same as some
>>other S (mod n). Thus by OBSERVATION 1, we have our result.
>>Quod erat demonstrandum
>>************************************************************************
>>For those who missed the beginning of the thread, my original proposition
>>was that if the sum of n numbers is a multiple of n, they can be permuted
>>into a valid site swap.
>>GO FOR IT, ED!!!
Hey, are you still there, Ed?
Steve Otteson
continue our discussion on the newsgroup. The dialog below the line is our
last correspondance. I will try to review our discussion.
Dean needed detailed instructions on how to convert a sequence of n
numbers that sum to a multiple of n into a sequencer of n-1 numbers that
would be easier to permute into a siteswap.
<Steve wrote:
<At this point, you have too many wrap-arounds. There should only be 2:
<the 1, which is a positive wrap-around, and the negative element that
<will land on the 1, which is a negative wrap-around. Actually, there are
<no wrap-arounds because the negative one cancels out the positive <one.
<Dean wrote:
<(I’m not sure what that last sentence means. But I don’t think it
matters.)
<Steve wrote:
<With 1,2,3,3,1 subtract 5 from the 3’s: 1,2,-2,-2,1. Now arrange so a -2
<lands on the one: 1,-2,2,-2,1. Notice that there is a positive and
<negative wrap-around. Add 1 to -2 and remove the 1: 1,-1,2,-2. <Arrange
into a siteswap so that there are no wrap-arounds and so that <the element
that the -1 lands on the first number of the sequence: 2,-<1,1,-2.
<Dean wrote:
<But how do you know you can always make this work? The induction
<hypothesis says that you can rearrange a given bunch of n-1 numbers <to
make a valid siteswap, not that you can make one with no <wraparounds, and
not that you can make one in which a particular <number lands on the first
number of the sequence.
<Let’s look at another example:
<Start with: 1,1,3,3,4,4,5
<Rotate so the first 1 is at the end: 1,3,3,4,4,5,1
<Subtract 3 7’s to make the sum 0: -6,3,3,-3,-3,5,1
<Rearrange so that a negative number lands on the 1: 5,3,3,-3,-3,-6,1
<Increment the -6 and delete the 1: 5,3,3,-3,-3,-5
<Now the sum is 0 and there are no wraparounds, but there’s no way to
<rearrange this to make a valid siteswap without wraparounds. (For the
Yes there is, but it comes with a price. We have 5,3,3,-3,-3,-5, which is a
sequence of 6 numbers that is a multiple of 6. Adding 6 to the negative
numbers yields: 5,3,3,3,3,1, which still sums to a multiple of 6. Arrange
into a siteswap: 1,3,3,3,5,3. Rotate so that the 1 is on the left, and
subtract 6 from it: 3,3,3,5,3,-5. Subtracting 6 so that there are no
wrap-arounds: 3,3,3,-1,-3,-5. Inserting the 1 and subtracting 1 from the
negative five yields: 3,3,3,-1,-3,-6,1. Adding 7 to the negative numbers:
3,3,3,6,4,1,1, which is a siteswap, but not the sequence of numbers that we
started with. See my next comment below.
<5 to not wrap, it would have to be in the first position. Then, for the 3
’s <to not wrap they’d have to be in the 2nd and 3rd positions. But then
the <5 and the 2nd 3 both land in the same place.)
<In this case, we could have subtracted the 3 7’s differently, and
<continued to obtain a valid siteswap. For example:
<Subtract 3 7’s: 1,3,-4,-3,4,-2,1
<Rearrange so that a negative number lands on the 1: 4,3,-3,1,-4,-2,1
<Increment the -3 and delete the 1: 4,3,-2,1,-4,-2
<Rearrange to a wrapless siteswap: 3,4,-2,1,-2,-4
<Decrement the -2 and append the 1: 3,4,-3,1,-2,-4,1
<Add back the 3 7’s: 3,4,4,1,5,3,1
<But I found this by trial and error. I see nothing in what you’ve said so
<far that guarantees that it always works.
Notice the first time that you subtracted the 7's you arranged the numbers
so that the 1 (which became -6) landed on the 1 on the left end of the
sequence. When you subtracted the 7's the second time, you had the 4 (which
became -3) landing on the 1 on the left end of the sequence, and this
worked.
At this point you can see that the technique works if you pick the correct
number that lands on the 1 that will be removed from the sequence. This
makes sense because for any siteswap, only one number (modulo n) can land on
any given site.
It seems that I need more details to guarantee that the right choice exists.
I will work on this patch. It might be possible to bypass the patch by
showing that the method of generating all n+1 numbered siteswaps from the
set of all n numbered siteswaps will generate all possible sequences that
sum to a multiple of n+1. In other words, show that the set of all possible
siteswaps for n numbers contains, or is the same as, the set of all possible
combinations of n numbers that sum to b times n where 0 =< b < n.
I won't have a lot of time to work on this as I am getting ready for Madfest
by updating our club passing website.
<Steve wrote:
<I am not sure that re-posting Johannes’ proof will help.
<Dean wrote:
<Maybe not, but I’d still like to see it, if only to satisfy myself that it’
s not <useful.
<Steve wrote:
<If you still want to see it, look in deja.com under juggling.rec for all
<posts from Steve Otteson (there are not that many).
<Dean:
<I looked. In your posting dated Nov. 17, you quote and comment on the
<proto-proof by Alan Mackenzie, but I don’t see anything from Johannes
<except his original question.
<Steve:
<We really should have our discussions on the newsgroup, because the <2
clarifications that we discussed would benefit all. If you post your next
<question in the group, I will include the 2 clarifications aside from my
<answer.
<Dean:
<I’ll follow you there: If you’ll post a more detailed proof, I’ll send any
<further questions to the newsgroup. If you want to explain that you’re
<posting more details because of an email conversation with me, feel <free
to do so. (And you have my permission to quote anything that I’ve <said.)
<Dean Hickerson
<de...@math.ucdavis.edu
I'll re-post Johannes' proto-proof.
Proof by Magic Wand Wavingly Yours,
Steve O.
Dean Hickerson
> Dean and I have been discussing my proof and I suggested that we
> continue our discussion on the newsgroup. The dialog below the line is our
> last correspondance. I will try to review our discussion.
> It seems that I need more details to guarantee that the right choice exists.
I was afraid of that. I've been thinking a lot about this, but haven't
been able to prove it. Can anyone else help?
And what ever happened to Johannes Waldmann's solution which he said on
Nov. 11 that he would post in "a few days"?
Dean Hickerson
de...@math.ucdavis.edu
Steve Otteson
>Nov. 11 that he would post in "a few days"?
>
>Dean Hickerson
>de...@math.ucdavis.edu
The re-post of Johannes' proto proof is below. Sorry about the delay.
Procrastinatingly Yours,
Steve O.
Alan Mackenzie wrote in message <5tpju8...@acm.acm>...
>Johannes Waldmann <j...@informatik.uni-leipzig.de> wrote on 10 Nov 2000
>14:09:34 GMT:
>> at the Erlangen convention recently, Alan Mackenzie suggested this
>> theorem:
>
>> for all sequences of n numbers x1, x2, .. xn
>> whose sum is a multiple of n,
>> there is a permutation of these numbers
>> that is a valid siteswap.
>
>> example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
>> a valid permutation is 3 1 4 1 1.
>
>> can you prove this? I'll post the solution in a few days. regards,
Why is it necessary to have the siteswap with no wraparounds? Consider
{6,7,8,11}. For step 1 reduce each number by 5 to get
1,2,3,6.
Drop the 1 and add 1 to the 6 (steps 2 and 3):
2,3,7
^
For step 4, subtract all by 4:
-2,-1,3
^
Step 5 isn't needed because -2,-1,3 is a valid siteswap. After step 6:
3,-2,-1
^ Note that there are 2 wraparounds.
After we increment xi and restore xn:
2,-2,-1,1
Unlike your claim in step 7, xi does not land on xn.
Restoring the transformations of step 1 and step 4 respectively:
Steve O.
*****************************************************************
Dean Hickerson
: And what ever happened to Johannes Waldmann's solution which he said on
: Nov. 11 that he would post in "a few days"?
Actually that was Nov. 10, not Nov. 11.
Steve Otteson <ot...@mwt.net> wrote:
: The re-post of Johannes' proto proof is below. Sorry about the delay.
:
: Procrastinatingly Yours,
:
: Steve O.
:
:
: Alan Mackenzie wrote in message <5tpju8...@acm.acm>...
: >Johannes Waldmann <j...@informatik.uni-leipzig.de> wrote on 10 Nov 2000
: >14:09:34 GMT:
: >> at the Erlangen convention recently, Alan Mackenzie suggested this
: >> theorem:
: >
: >> for all sequences of n numbers x1, x2, .. xn
: >> whose sum is a multiple of n,
: >> there is a permutation of these numbers
: >> that is a valid siteswap.
: >
: >> example: given 4 3 1 1 1 (whose sum is 10 which is a multiple of 5),
: >> a valid permutation is 3 1 4 1 1.
: >
: >> can you prove this? I'll post the solution in a few days. regards,
: >
: >Well, not quite, though I've had a few thoughts.
If I'm reading that correctly, the proto-proof is from Alan Mackenzie,
not Johannes. Lines starting with two '>'s are from Johannes; that's just
the ones shown above. Nonempty lines starting with one '>' are from Alan;
that's most of the post from "Well, not quite" on.
Checking on Dejanews, I can't find any posts by Johannes after his original
question. Apparently he never posted a proof, nor has anyone else. (I'm
not convinced that the gaps in Alan and Steve's proto-proof can be filled,
but I'd be happy to be proved wrong.)
Johannes, if you're still listening, do you have a proof?
Does anybody else have one?
Dean Hickerson
de...@math.ucdavis.edu
Dean Hickerson
than I do, about this question, and he said that it had been asked and
answered about 50 years ago in the more general context of finite abelian
groups. A proof is given in "A combinatorial problem on abelian groups"
by Marshall Hall, Jr., Proceedings of the American Mathematical Society,
vol. 3 (1952), pp. 584-587.
I've read the proof and it appears to be correct. Unfortunately it's a bit
too long and typographically messy to give here. The basic idea is to start
with the trivial siteswap 00...0 and change two numbers at a time (keeping
the sum divisible by n) until the desired set of numbers is reached. Hall
shows that at each step the siteswap can be changed to another siteswap with
the new set of numbers in some order.
Dean Hickerson
de...@math.ucdavis.edu
Steve Otteson
Dean Hickerson wrote in message <93lq6g$sp7$1...@woodrow.ucdavis.edu>...
>I asked a colleague of mine (Sherman Stein), who knows more combinatorics
>than I do, about this question, and he said that it had been asked and
>answered about 50 years ago in the more general context of finite abelian
>groups. A proof is given in "A combinatorial problem on abelian groups"
>by Marshall Hall, Jr., Proceedings of the American Mathematical Society,
>vol. 3 (1952), pp. 584-587.
>
>I've read the proof and it appears to be correct. Unfortunately it's a bit
>too long and typographically messy to give here. The basic idea is to
start
>with the trivial siteswap 00...0 and change two numbers at a time (keeping
I was thinking that I had to change one at a time (after you start with
two).
>the sum divisible by n) until the desired set of numbers is reached. Hall
>shows that at each step the siteswap can be changed to another siteswap
with
>the new set of numbers in some order.
>
>Dean Hickerson
>de...@math.ucdavis.edu
For 3 non-zero numbers the solution is trivial ( see my last post) , but
with 4 or more non-zero numbers I was going to show that there are so many
possible siteswaps that all possible sequences of 4 numbers whose sum is 0,
n, 2n, or 3n, must all be included in the set of siteswaps generated.
Basically it's a proof by overwhelming redundancy, because there are many
sequences that have lots of different siteswaps. The example I gave had at
least 5.
How did he show that his set of siteswaps contained all possible sets of
numbers that summed to a multiple of n?
Inquisitively,
Steve O.
Martin Frost me at stanford edu
> A proof is given in "A combinatorial problem on abelian groups"
> by Marshall Hall, Jr., Proceedings of the American Mathematical Society,
> vol. 3 (1952), pp. 584-587.
Curious. Marshall Hall, Jr., was a professor at Caltech when I was
there in the 60's, majoring in math. I either took a class from him
or we used his book (it was long ago). At any rate, his son, also
named Marshall Hall, was also a student there at the time and was a
friend of mine. Never did his dad tell me, though, about site swaps.
Maybe I would have started juggling sooner if he had? (;-) I didn't
start till four years after I graduated, alas.
Martin
Alan Mackenzie
+0000 (UTC):
> I asked a colleague of mine (Sherman Stein), who knows more
> combinatorics than I do, about this question, and he said that it had
> been asked and answered about 50 years ago in the more general context
> of finite abelian groups. A proof is given in "A combinatorial problem
> on abelian groups" by Marshall Hall, Jr., Proceedings of the American
> Mathematical Society, vol. 3 (1952), pp. 584-587.
> I've read the proof and it appears to be correct. Unfortunately it's a
> bit too long and typographically messy to give here.
Any change you could state (in group-theoretical language) exactly what
it was he proved?
> The basic idea is to start with the trivial siteswap 00...0 and change
> two numbers at a time (keeping the sum divisible by n) until the
> desired set of numbers is reached. Hall shows that at each step the
> siteswap can be changed to another siteswap with the new set of numbers
> in some order.
> Dean Hickerson
> de...@math.ucdavis.edu
--
Alan Mackenzie (Munich, Germany)
Email: aa...@muuc.dee; to decode, wherever there is a repeated letter
Dean Hickerson
> I asked a colleague of mine (Sherman Stein), who knows more
> combinatorics than I do, about this question, and he said that it had
> been asked and answered about 50 years ago in the more general context
> of finite abelian groups. A proof is given in "A combinatorial problem
> on abelian groups" by Marshall Hall, Jr., Proceedings of the American
> Mathematical Society, vol. 3 (1952), pp. 584-587.
Alan Mackenzie asked:
> Any change you could state (in group-theoretical language) exactly what
> it was he proved?
Sure: If G = {a[1], ..., a[n]} is a finite abelian group (written
additively) of cardinality n, and b[1], ..., b[n] are n elements of G
(not necessarily distinct) whose sum is zero, then there exists a
permutation of G,
( a[1] ... a[n] )
( c[1] ... c[n] ),
such that the differences c[1]-a[1], ..., c[n]-a[n] are the same as
b[1], ..., b[n] in some order.
For the application to siteswaps, let G be the cyclic group of order n;
i.e. the set of numbers from 0 to n-1 under addition mod n. For example,
suppose we want a siteswap that's a rearrangement of 1,1,2,3,3. Here
n is 5, so we take G = {0,1,2,3,4} under addition mod 5. A permutation
that works is
( 0 1 2 3 4 )
( 1 3 0 4 2 )
Here the differences c[i]-a[i] are 1-0=1, 3-1=2, 0-2=3, 4-3=1, and
2-4=3, so one siteswap that works is 1,2,3,1,3.
Dean Hickerson
de...@math.ucdavis.edu
Dean Hickerson
> A proof is given in "A combinatorial problem on abelian groups"
> by Marshall Hall, Jr., Proceedings of the American Mathematical Society,
> vol. 3 (1952), pp. 584-587.
>
> I've read the proof and it appears to be correct. Unfortunately it's a bit
> too long and typographically messy to give here. The basic idea is to start
> with the trivial siteswap 00...0 and change two numbers at a time (keeping
> the sum divisible by n) until the desired set of numbers is reached. Hall
> shows that at each step the siteswap can be changed to another siteswap with
> the new set of numbers in some order.
Steve Otteson <ot...@mwt.net> wrote:
> I was thinking that I had to change one at a time (after you start with
> two).
Sorry, I didn't state that clearly. Hall's proof does not involve induction
on the length of the siteswap. Given a list of n numbers that we want to
rearrange to form a siteswap, he starts with the trivial siteswap 0...0
of the same length and then changes 2 numbers at a time until he reaches
the desired list of numbers. At each stage the length of the list is n.
For example, suppose we want a siteswap of length 6 that's a rearrangement
of 253422. Hall transforms 000000 to 253422 as follows:
000000
240000
255000
253200
253440
253422
At each stage the sum of the numbers is divisible by 6 and one more number
matches the desired list. He shows that if you have a siteswap that's a
rearrangement of one line above, then it can be modified to give a siteswap
that's a rearrangement of the next line. That's not trivial to prove; it
takes him a page and a half to do it.
> How did he show that his set of siteswaps contained all possible sets of
> numbers that summed to a multiple of n?
I'll try to describe his proof in a subsequent post; I haven't figured out
a good way to do so yet. It uses lots of subscripts and double subscripts,
so typing it in would be a pain. I'd like to scan it and put it on a web
page, but that's probably a copyright violation.
Dean Hickerson
de...@math.ucdavis.edu
Gerald R. Martin
stanford edu <nos...@cs.stanford.edu> wrote:
> Dean Hickerson <de...@math.ucdavis.edu> writes:
>
> > A proof is given in "A combinatorial problem on abelian groups"
> > by Marshall Hall, Jr., Proceedings of the American Mathematical Society,
> > vol. 3 (1952), pp. 584-587.
>
> Curious. Marshall Hall, Jr., was a professor at Caltech when I was
> there in the 60's, majoring in math. I either took a class from him
> or we used his book (it was long ago).
Small world: Professor Hall was my graduate adviser at Caltech for most of
a year. He had a fine sense of humor, though we never really hit it off;
it's a little odd to picture him juggling, but it's not at all odd to
picture him getting straight to the heart of the combinatorics of
*anything*.
-Jerry M.
M.Sc. Mathematics, 1970
Steve Otteson
Steve Otteson wrote in message ...
Here are some details that fill in the blanks that I left in my proof. I
have made 2 insertions that will make the inductive part clearer then
before. I think that the proof is now complete. Any critique, questions, or
comments will be appreciated.
Demonstrably,
Steve O.
>Here are the details that fill out the proof that I proposed 2 posts ago.
I
>think I resolved the question I asked in my last post. I don't use abelian
>groups, in fact, all I use are linear equations, simple combinatorics, and
>induction:
>
>Assume that n is the number of numbers in our sequence S.
>
>Assume that each number in S ranges from 0 to n-1.
>
>Start with x1 and x2 as the only 2 non-zero numbers in S. If x1 lands on
>x2, and x2 lands on x1, then x1 + x2 = n. Clearly every possible
>combination of x1 and x2 such that x1 + x2 = n (there are n/2 possible
>ways) can be permuted to a siteswap with the n-2 zeros. The proof is
>finished for this case.
>
>Start with x1 and x2 from above, and pick a different non-zero site x3.
>Without loss of generality (WLOG) assume x1 will land on x3 and x3 will
land
>on x2. We then have (x1 - x3) + x3 + x2 = n or 2 times n. Remember that
>x1-x3 is a number from 1 to n-1 because of modulo arithmetic.
Let's modify the above paragraph. Pick a value from 1 to n-1 for x2. Once we
have x2, x1 could be anything from 1 to n-1 because all of the landing
sites are available. Is x2 available as a landing site? If x1 lands on x2,
then x3 will be zero, and we already covered this case. If we have x1 and
x2, x3 is forced to be n - x1 - x2.
>It should be clear that each combination of x1, x2, and x3 that fit the
>equation above can be permuted, with the remaining n-3 zeros, into a
>siteswap. I should also be clear that these siteswaps contain all possible
>sets of 3 numbers such that their sum is n or 2n. The proof is finished
for
>this case.
>
>Now for some classic induction: let p < n-2 and assume that the proof is
>complete for p non-zero numbers, x1, x2,...,xp. Prove the case for p+1.
>
>Assume the xi's make one circuit so that x1 lands on x2, x2 lands on
x3,...,
>xp lands on x1. Let xq be the p+first non-zero element that will be
>"grafted" into the circuit. Assume WLOG that x1 will land on xq, and xq
>will land on x2.
>
>Replace x2 with y2 = (x2 + x3 +...+ xp) modulo n, and replace x3, x4,...,
xp
>with zeros( given any siteswap, if x1 lands on x2 then you can replace x1
>with (x1 + x2) modulo n, and replace x2 with zero.). Our task has been
>reduced to inserting xq into the circuit x1 and y2. We already did this
and
>conclude that every possible sequence of p+1 non-zero numbers, such that
>their sum is a multiple of n (up to p times n), is contained in the
>siteswaps generated by the grafting of xq.
Let's clarify the paragraph above:
After we reduce the above to x1, y2, xq, and n-3 zeros, I claim that x1 can
range from 1 to n-1. This is the same as saying that x1 can land anywhere.
But having y2 implies that there are lots of sites that were filled by x's.
That's ok because if x1 lands on another xi that was already there, then
some of the x's will become zero (as x3 became zero when we considered that
x1 landed of x2 for our 3-non-zero number case).
Letting x1 range from 1 to n-1 gives all possible (siteswaps and)
combinations of numbers that sum to n or 2n. Expanding the y2 back to the
x's will give all possible (siteswaps and) combinations of sequences that
sum to
n, 2n, 3n, ..., or pn.
>If the p numbers make more than one circuit, then xq will have to be
grafted
>into a circuit of numbers that are less than p. Since any circuit can be
>reduced to 2 numbers, as shown above, we arrive at the same conclusion.
>
>In general, we can conclude that the grafting of xq to each of the
siteswaps
>of p non-zero numbers and n-p zeros, will contain all possible sequences of
>p+1 numbers that sum to a multiple of n (up to p times n). The proof for
>p+1 is complete.
>
>Letting p = n - 2 shows us that any sequence of n numbers that sum to a
>multiple of n can be permuted into a siteswap. Q.E.D.
>
> Combinatorically,
>
> Steve O.
>
>
>
>
Steve Otteson
formula that gets the total number of siteswaps when given n, the number of
numbers in the siteswap. I decided that this wouldn't help the proof, but
continued the search for the formula.
I wrote a program to generate all siteswaps for all n from 4 to 9, with some
analysis that will be explained. Please consider the first magic triangle:
Total number | Number of
n | Siteswaps that sum to multiples of n of Siteswaps
| Sequences
----|-----------------------------------------------------------------------
---|-----------|----------------
1: 1
1 1
2: 1 1
2 2
3: 1 2 1
4 4
4: 1 4 4 1
10 10
5: 1 6 14 6 1
28 26
6: 1 12 55 55 12 1
136 80
7: 1 18 171 346 171 18 1
726 246
8: 1 34 546 1969 1969 546 34 1
5,100 810
9: 1 58 1628 9812 17364 9812 1628 58 1 40,362
2,704
Look at the 6th row for an example on how to read the triangle. The total
number of 6-numbered siteswaps is 136, which is found in the first column
past the triangle.
The first number after the 6 is a 1. This means that there is 1 siteswap
whose elements sum to zero. The next number, 12, means that there are 12
siteswaps where the sum of the elements of each siteswap = 6. There are 55
siteswaps that sum to 12, 55 siteswaps that sum to 18, 12 siteswaps that sum
to 24, and 1 siteswap that sums to 30.
The second magic triangle counts the circuits (Hamiltonian circuits for you
graph theory enthusiasts) in all of the siteswaps.
Total number | Number of
n | Number of circuits in each siteswap of Siteswaps
| Sequences
----|-----------------------------------------------------------------------
---------------|----------------
1: 1
1 1
2: 1 1
2 2
3: 2 1 1
4 4
4: 3 4 2 1
10 10
5: 8 10 7 2 1
28 26
6: 24 50 41 17 3 1
136 80
7: 108 252 232 105 25 3 1
726 246
8: 640 1648 1655 858 251 43 4 1
5,100 810
9: 4492 12184 13132 7484 2497 506 62 4 1 40,362
2,704
Let's look at the 6th row to see how to read the triangle. There are 24 (out
of 136 total) siteswaps that have one circuit. There are 50 siteswaps that
have 2 circuits, 41 siteswaps have 3 circuits, 17 siteswaps have 4 circuits,
3 siteswaps have 5 circuits, and 1 siteswap has 6 circuits.
A circuit is a loop that starts from one landing site, goes to the next
landing site, and continues until you reach the starting site. The siteswaps
0,1,2,3,4 and 0,2,4,1,3 have 2 circuits each. The siteswap 0,3,1,4,2 has 3
circuits. Remember that a zero is a circuit by itself.
Notice that the 3 siteswaps in the last paragraph are made up from one
sequence of numbers. The last column to the right of each triangle gives the
number of sequences (that sum to a multiple of n) that make up all of the
siteswaps. For n less than 5, the number of siteswaps is the same as the
number of sequences. For n = 5, there is one sequence that has 3 siteswaps.
For n greater than 5, the number of siteswaps sky-rockets compared to the
number of sequences. I was astonished to see this.
I thought that once I had a look at the triangles, the formula for the
number of siteswaps would hit me like a cool slap in the face. After looking
at them for a couple of hours, the only thing that came across my face was
my own hand (I was falling asleep).
I'll let you all play with the numbers while I take a nap. Wake me up if you
find anything.
Serendipitously,
Steve O.
Steve Otteson
Steve Otteson wrote in message ...
>formula that gets the total number of siteswaps when given n, the number of
>numbers in the siteswap. I decided that this wouldn't help the proof, but
>continued the search for the formula.
>
>I wrote a program to generate all siteswaps for all n from 4 to 9, with
some
>analysis that will be explained. Please consider the first magic triangle:
>
>
-
>1: 1
>2: 1 1
>4: 1 4 4 1
>5: 1 6 14 6 1
>
>number of 6-numbered siteswaps is 136, which is found in the first column
>past the triangle.
>
>The first number after the 6 is a 1. This means that there is 1 siteswap
>whose elements sum to zero. The next number, 12, means that there are 12
>siteswaps where the sum of the elements of each siteswap = 6. There are 55
>siteswaps that sum to 12, 55 siteswaps that sum to 18, 12 siteswaps that
sum
>to 24, and 1 siteswap that sums to 30.
>
>The second magic triangle counts the circuits (Hamiltonian circuits for you
>graph theory enthusiasts) in all of the siteswaps.
>
>
>
-
>1: 1
>2: 1 1
>4: 3 4 2 1
>5: 8 10 7 2 1
>
(out
>of 136 total) siteswaps that have one circuit. There are 50 siteswaps that
>have 2 circuits, 41 siteswaps have 3 circuits, 17 siteswaps have 4
circuits,
>3 siteswaps have 5 circuits, and 1 siteswap has 6 circuits.
>
>A circuit is a loop that starts from one landing site, goes to the next
>landing site, and continues until you reach the starting site. The
siteswaps
>0,1,2,3,4 and 0,2,4,1,3 have 2 circuits each. The siteswap 0,3,1,4,2 has 3
>circuits. Remember that a zero is a circuit by itself.
>
>Notice that the 3 siteswaps in the last paragraph are made up from one
>sequence of numbers. The last column to the right of each triangle gives
the
>number of sequences (that sum to a multiple of n) that make up all of the
>siteswaps. For n less than 5, the number of siteswaps is the same as the
>number of sequences. For n = 5, there is one sequence that has 3 siteswaps.
>For n greater than 5, the number of siteswaps sky-rockets compared to the
>number of sequences. I was astonished to see this.
I tried to put the following figures to the right of the magic triangles,
but they got mangled.
n | Number of | Number of
| Siteswaps | Sequences
--------------------------------------
1 1 1
2 2 2
3 4 4
4 10 10
5 28 26
6 136 80
7 726 246
8 5,100 810
9 40,362 2,704
mini
Kaskade magazine
Maksim has a very interestihng if confusing article
On Sat, 3 Feb 2001 06:30:42 -0600, "Steve Otteson" <ot...@mwt.net>
wrote:
->
->Steve Otteson wrote in message ...
->>While I was looking for a way to prove the theorem, I considered
using a
->>formula that gets the total number of siteswaps when given n, the
number of
->>numbers in the siteswap. I decided that this wouldn't help the
proof, but
->>continued the search for the formula.
->>
->>I wrote a program to generate all siteswaps for all n from 4 to 9,
with
->some
->>analysis that will be explained. Please consider the first magic
triangle:
->>
->>
->>n | Siteswaps that sum to multiples of n
->>----|----------------------------------------------------------------------
->-
->>1: 1
->>2: 1 1
->>3: 1 2 1
->>4: 1 4 4 1
->>5: 1 6 14 6
1
->>6: 1 12 55 55 12 1
->>7: 1 18 171 346 171 18 1
->>8: 1 34 546 1969 1969 546 34 1
->>9: 1 58 1628 9812 17364 9812 1628 58 1
->>
->>Look at the 6th row for an example on how to read the triangle.
The total
->>number of 6-numbered siteswaps is 136, which is found in the first
column
->>past the triangle.
->>
->>The first number after the 6 is a 1. This means that there is 1
siteswap
->>whose elements sum to zero. The next number, 12, means that there
are 12
->>siteswaps where the sum of the elements of each siteswap = 6. There
are 55
->>siteswaps that sum to 12, 55 siteswaps that sum to 18, 12 siteswaps
that
->sum
->>to 24, and 1 siteswap that sums to 30.
->>
->>The second magic triangle counts the circuits (Hamiltonian circuits
for you
->>graph theory enthusiasts) in all of the siteswaps.
->>
->>
->>
->>n | Number of circuits in each siteswap
->>----|----------------------------------------------------------------------
->-
->>1: 1
->>2: 1 1
->>3: 2 1
1
->>4: 3 4 2
1
->>5: 8 10 7 2
1
->>6: 24 50 41 17 3
1
->>7: 108 252 232 105 25 3
1
->>8: 640 1648 1655 858 251 43 4 1
->>9: 4492 12184 13132 7484 2497 506 62 4 1
->>
->>Let's look at the 6th row to see how to read the triangle. There
are 24
->(out
->>of 136 total) siteswaps that have one circuit. There are 50
siteswaps that
->>have 2 circuits, 41 siteswaps have 3 circuits, 17 siteswaps have 4
->circuits,
->>3 siteswaps have 5 circuits, and 1 siteswap has 6 circuits.
->>
->>A circuit is a loop that starts from one landing site, goes to the
next
->>landing site, and continues until you reach the starting site. The
->siteswaps
->>0,1,2,3,4 and 0,2,4,1,3 have 2 circuits each. The siteswap
0,3,1,4,2 has 3
->>circuits. Remember that a zero is a circuit by itself.
->>
->>Notice that the 3 siteswaps in the last paragraph are made up from
one
->>sequence of numbers. The last column to the right of each triangle
gives
->the
->>number of sequences (that sum to a multiple of n) that make up all
of the
->>siteswaps. For n less than 5, the number of siteswaps is the same
as the
->>number of sequences. For n = 5, there is one sequence that has 3
siteswaps.
->>For n greater than 5, the number of siteswaps sky-rockets compared
to the
->>number of sequences. I was astonished to see this.
->
->
->I tried to put the following figures to the right of the magic
triangles,
->but they got mangled.
->
->n | Number of | Number of
-> | Siteswaps | Sequences
->--------------------------------------
->1 1 1
->2 2 2
->3 4 4
->4 10 10
->5 28 26
->6 136 80
->7 726 246
->8 5,100 810
->9 40,362 2,704
->>
->>I thought that once I had a look at the triangles, the formula for
the
->>number of siteswaps would hit me like a cool slap in the face.
After
->looking
->>at them for a couple of hours, the only thing that came across my
face was
->>my own hand (I was falling asleep).
->>
->>I'll let you all play with the numbers while I take a nap. Wake me
up if
->you
->>find anything.
->>
->> Serendipitously,
->>
->> Steve O.
->>
->>
->>
->>
->
Greg Warrington
various interpretations) can be found at
http://www.research.att.com/~njas/sequences/
Hope that helps,
greg
In article <nVSe6.1$_q3.49@client>, Steve Otteson <otto...@mwtSPAM.net> wrote:
>
>Steve Otteson wrote in message ...
>...
John J. Lee
> While I was looking for a way to prove the theorem, I considered using a
> formula that gets the total number of siteswaps when given n, the number of
> numbers in the siteswap. I decided that this wouldn't help the proof, but
> continued the search for the formula.
[...]
Isn't this in the 'juggling drops and descents' paper (by our own Colin
Wright, and others)?
I don't remember where it was published.
John
Peter Blanchard
The article you're refering to is "Juggling Drops and Descents" in The American
Mathematical Monthly, Volume 101, Number 6, June-July 1994, p 507-519
Peter
colin_d...@my-deja.com
mi...@juggler.net wrote:
> for those into the theories of siteswaps check the latest
> issue of Kaskade magazine Maksim has a very interestihng
> if confusing article
Any denger of more information about this? It's not easy for
me to find a copy of Kaskade from where I am.
cdw
luke burrage
Another semi-serious, totally un-thought-through musing, luke comments
thus:
I think people are forgetting that you don't juggle siteswaps, rather
siteswaps are there to describe juggling patterns. I hardly ever see a
siteswap and try and juggle it. I much prefer working out a pattern by
juggling it and then, maybe, worki out what the steswa might be. Saying
that, I call about 8 different patterns "high, low low".
Lukas
(can someone please work out the siteswap for a 5 ball cascade, then
catching them all in one hand, then throwing them all in a multiplex
throw back into a 5 ball cascade, thanks)
In article <zoGd6.786$7e6.2...@homer.alpha.net>,
"Steve Otteson" <otto...@mwtSPAM.net> wrote:
>
> Steve Otteson wrote in message ...
>
> Here are some details that fill in the blanks that I left in my
proof. I
> have made 2 insertions that will make the inductive part clearer then
> before. I think that the proof is now complete. Any critique,
questions, or
> comments will be appreciated.
>
> Demonstrably,
>
> Steve O.
>
--
email - lu...@juggler.net
luke burrage's thing on the net - http://www.lukeburrage.co.uk
Gunnar Andersson
On Thu, 8 Feb 2001, luke burrage wrote:
> I think people are forgetting that you don't juggle siteswaps, rather
> siteswaps are there to describe juggling patterns. I hardly ever see a
> siteswap and try and juggle it. I much prefer working out a pattern by
> juggling it and then, maybe, worki out what the steswa might be. Saying
> that, I call about 8 different patterns "high, low low".
I don't think I had come across the pattern 633 ("high, low, low") if
it weren't for siteswaps.
A good thing about siteswaps is that you don't have to be actually be
able to *juggle* them in order to realize that they're jugglable.
Being a mathematician at heart, this attitude is rather natural for
me :) But I also think that some of the variations of e.g. the
5-ball cascade are much easier to come up with when thinking in the
terms of siteswaps (94444, 75751 etc).
> (can someone please work out the siteswap for a 5 ball cascade, then
> catching them all in one hand, then throwing them all in a multiplex
> throw back into a 5 ball cascade, thanks)
One of the things that siteswaps are good for is to give a terse
description of a trick - precisely what you did above without
resorting to mathematics.
As an aside: Can you actually throw a 5-way multiplex and continue
with a 5-ball cascade?
/ Gunnar
luke burrage
Gunnar Andersson <gun...@nada.kth.se> wrote:
>
>
> On Thu, 8 Feb 2001, luke burrage wrote:
>
> > I think people are forgetting that you don't juggle siteswaps,
rather
> > siteswaps are there to describe juggling patterns. I hardly ever
see a
> > siteswap and try and juggle it. I much prefer working out a pattern
by
> > juggling it and then, maybe, worki out what the steswa might be.
Saying
> > that, I call about 8 different patterns "high, low low".
>
> I don't think I had come across the pattern 633 ("high, low, low") if
> it weren't for siteswaps.
I think I came across it by seeing juggler juggle it. They might have
found it by doing math.
>
> A good thing about siteswaps is that you don't have to be actually be
> able to *juggle* them in order to realize that they're jugglable.
> Being a mathematician at heart, this attitude is rather natural for
> me :) But I also think that some of the variations of e.g. the
> 5-ball cascade are much easier to come up with when thinking in the
> terms of siteswaps (94444, 75751 etc).
I can't really appriciate them written down like that. They are
probably really hard but as a few numbers on a screen they just don't
inspire me to to try them. Now, if I saw someone juggling these and
they looked ood, I'd give them a go.
>
> > (can someone please work out the siteswap for a 5 ball cascade, then
> > catching them all in one hand, then throwing them all in a multiplex
> > throw back into a 5 ball cascade, thanks)
>
> One of the things that siteswaps are good for is to give a terse
> description of a trick - precisely what you did above without
> resorting to mathematics.
>
That was my point. I say "five ball multipex throw into a 5 ball
cascade" and you go "cool!". I say "55552{938475}(whatever)" you
say "What's that then?".
> As an aside: Can you actually throw a 5-way multiplex and continue
> with a 5-ball cascade?
There's a video clip of me doing it on my website. You can also see Ben
Beever doing a 4 ball multiplex throw in a 7 ball cascade. I've
actually done a 5 ball multiplex throw into a 7 ball cascade. Once. The
chances of me catching it on film at the moment are slim to none, so
don't expect it any time soon.
Lukas
Ps; http://www.enkil.demon.co.uk/Pages/NigelGreen.htm
colin_d...@my-deja.com
luke burrage <lu...@juggler.net> wrote:
> I think people are forgetting that you don't juggle siteswaps, rather
> siteswaps are there to describe juggling patterns. I hardly ever see a
> siteswap and try and juggle it.
On the other hand (so to speak) I do this frequently.
> (can someone please work out the siteswap for a 5 ball cascade, then
> catching them all in one hand, then throwing them all in a multiplex
> throw back into a 5 ball cascade, thanks)
... 555554321[12345]555 ...
should do it. I'd like to see it.
cdw
--
\\// ko ze'u jmive gi'e snada
Chris Emerson
> In article <95u5ff$il9$1...@nnrp1.deja.com>,
> luke burrage <lu...@juggler.net> wrote:
>
> > I think people are forgetting that you don't juggle siteswaps, rather
> > siteswaps are there to describe juggling patterns. I hardly ever see a
> > siteswap and try and juggle it.
>
> On the other hand (so to speak) I do this frequently.
As do I. I like siteswaps. It's unfortunate that there aren't many
interesting ones for one hand. Still, the cast should come off soon.
:-)
> > (can someone please work out the siteswap for a 5 ball cascade, then
> > catching them all in one hand, then throwing them all in a multiplex
> > throw back into a 5 ball cascade, thanks)
>
> ... 555554321[12345]555 ...
>
> should do it. I'd like to see it.
I would have said:
... 5555525[22]5[222]0[2222]0[12345]555 ...
In my version the balls still land in the multiplexing hand one by one,
rather than all at once.
Chris
--
Chris Emerson, obsessed Cambridge juggler
E-mail: ceme...@chiark.greenend.org.uk
Web page: http://www.chiark.greenend.org.uk/~cemerson/
Henry Segerman
:> (can someone please work out the siteswap for a 5 ball cascade, then
:> catching them all in one hand, then throwing them all in a multiplex
:> throw back into a 5 ball cascade, thanks)
: ... 555554321[12345]555 ...
: should do it. I'd like to see it.
That would be a proper 5 ball reverse multiplex followed by 5 ball multiplex.
eeek. Yeah I'd like to see that too.
My first thought was more like:
...5555525[22]5[222]0[2222]0[12345]55555...
Though 1 multiplexes are going to be very very hard to do. Maybe slightly
'easier' would be:
...5555525[22]5[222]0[2222]0[34567]0055555...
Incidentally Colin, I saw one of your lectures when I was still at school
about 5 years ago, and it really inspired me. I wouldn't be where I am with
juggling if I hadn't seen it. Thanks :)
--
,-. Henry Segerman
uewJa6aS hJuaH `-'
colin_d...@my-deja.com
Henry Segerman <sjoh...@sable.ox.ac.uk> wrote:
> Incidentally Colin, I saw one of your lectures when
> I was still at school about 5 years ago, and it really
> inspired me. I wouldn't be where I am with juggling if
> I hadn't seen it. Thanks :)
<fx: blush> Thank you ...
Which school?
Henry Segerman
: As do I. I like siteswaps. It's unfortunate that there aren't many
: interesting ones for one hand. Still, the cast should come off soon.
: :-)
Theres a fun 3 ball one I've been playing about with:
[32]1
Good for practising big multiplex splits to the same hand, which are nice in
the 5 ball cascade as a ...55525[53]555...
:> > (can someone please work out the siteswap for a 5 ball cascade, then
:> > catching them all in one hand, then throwing them all in a multiplex
:> > throw back into a 5 ball cascade, thanks)
:>
:> ... 555554321[12345]555 ...
:>
:> should do it. I'd like to see it.
: I would have said:
: ... 5555525[22]5[222]0[2222]0[12345]555 ...
: In my version the balls still land in the multiplexing hand one by one,
: rather than all at once.
Snap, must be right then. BTW, when are we doing the varsity this year?
luke burrage
>
> :> (can someone please work out the siteswap for a 5 ball cascade,
then
> :> catching them all in one hand, then throwing them all in a
multiplex
> :> throw back into a 5 ball cascade, thanks)
>
> : ... 555554321[12345]555 ...
>
> : should do it. I'd like to see it.
>
You can see a video clip of it on my website. Or you could if there
wasn't a bandwidth restiction where I keep some of the video files.
That video has been downloaded 72 times in the past 24 hours and has
reached the 90000mb limit. Other videos on the 'movie select' page
still work but that for that one (and a few other recent ones like the
nine ball flash with a back of the neck catch and 8 squash raquet
flash) you'll have to try again tomorrow.
Also that siteswap isn't right. It looks a bit impossible. Sort of a
cross between this trick and Lukes Barrage.
> My first thought was more like:
> ...5555525[22]5[222]0[2222]0[12345]55555...
>
> Though 1 multiplexes are going to be very very hard to do. Maybe
slightly
> 'easier' would be:
The 1 wouldn't be that hard. What would be hard is holding the 2 in
your hand while throwing the 1 sideways and the 3, 4 and 5 up.
> ...5555525[22]5[222]0[2222]0[34567]0055555...
That's more like it. Maybe the 7 isn't quite as high as a 7 and the 3
is more of a 1 or a crossed 2. My original point: "5 ball multiplex
throw into a 5 ball cascade" sounds much better than "5555525[22]5[222]0
[2222]0[34567]0055555".
Lukas
--
email - lu...@juggler.net
luke burrage's thing on the net - http://www.lukeburrage.co.uk
Sent via Deja.com
http://www.deja.com/
Chris Emerson
Henry Segerman <sjoh...@sable.ox.ac.uk> wrote:
> Chris Emerson <ceme...@chiark.greenend.org.uk> wrote:
>
> : As do I. I like siteswaps. It's unfortunate that there aren't many
> : interesting ones for one hand. Still, the cast should come off soon.
> : :-)
>
> Theres a fun 3 ball one I've been playing about with:
> [32]1
Can you split them enough not to have to snatch the 2? I can't. (I
might also write it [21]).
(Is there a notation for showing the number of hands to use with a
siteswap?)
I've tried 42, which I can generally do once. 531 isn't that interesting,
and 522 is impossible without a really high ceiling, and nearly impossible
without.
> Good for practising big multiplex splits to the same hand, which are nice in
> the 5 ball cascade as a ...55525[53]555...
Hmm, I've tried that but never succeeded. I shall have to do so when
my other arm's sufficiently recovered. I can do ...33323[31]333...
though, which is slightly silly.
> Snap, must be right then. BTW, when are we doing the varsity this year?
Ooh, dunno. I'll try to mention it to the pres.
Henry Segerman
: In article <95ums9$t3j$1...@news.ox.ac.uk>,
:>
:> Theres a fun 3 ball one I've been playing about with:
:> [32]1
: Can you split them enough not to have to snatch the 2? I can't. (I
I've been practising it a lot. Needs a lot of wrist, and sortof need to
slightly grip the lower ball as you release it so it doesnt have much height.
Barnsey bags probably help too.
: might also write it [21]).
I think thats different, the 1 in [21] could be held, so its like juggling
2 in one hand with a third held.
: (Is there a notation for showing the number of hands to use with a
: siteswap?)
Ben Beever's extended siteswap notation will do it, but for most purposes
nobody uses anything other than 2 hands.
: I've tried 42, which I can generally do once. 531 isn't that interesting,
: and 522 is impossible without a really high ceiling, and nearly impossible
: without.
Yeah, gets hard quick.
:> Good for practising big multiplex splits to the same hand, which are nice in
:> the 5 ball cascade as a ...55525[53]555...
: Hmm, I've tried that but never succeeded. I shall have to do so when
: my other arm's sufficiently recovered. I can do ...33323[31]333...
: though, which is slightly silly.
Weird grabbing that 1 while avoiding the 3 :)
:> Snap, must be right then. BTW, when are we doing the varsity this year?
: Ooh, dunno. I'll try to mention it to the pres.
We're supposed to be going over there this time aren't we?
Henry Segerman
: In article <95ujdg$sac$1...@news.ox.ac.uk>,
: Henry Segerman <sjoh...@sable.ox.ac.uk> wrote:
:> Incidentally Colin, I saw one of your lectures when
:> I was still at school about 5 years ago, and it really
:> inspired me. I wouldn't be where I am with juggling if
:> I hadn't seen it. Thanks :)
: <fx: blush> Thank you ...
: Which school?
Manchester Grammar. Finale of 3 clubs on a giraffe unicycle and you were
terrified of mounting the giraffe in the miniscule amount of space available.
Henry Segerman
:> ...5555525[22]5[222]0[2222]0[34567]0055555...
: That's more like it. Maybe the 7 isn't quite as high as a 7 and the 3
: is more of a 1 or a crossed 2. My original point: "5 ball multiplex
: throw into a 5 ball cascade" sounds much better than "5555525[22]5[222]0
: [2222]0[34567]0055555".
True. But it is more precise - we've had 3 interpretations of what
"5 ball multiplex throw into a 5 ball cascade" might be. Of course, theres
plenty of room for both ways of talking about it to be useful in different
contexts.
Dean Hickerson
"A combinatorial problem on abelian groups", Proc. Amer. Math. Soc.,
vol. 3 (1952), pp. 584-587. Here it is. I've changed the terminology
somewhat to fit the current context and audience, and, to make typing
easier, I've rewritten everything without using subscripts.
Throughout this discussion, all additions and subtractions will be done
mod n, where n is the length of the siteswaps being constructed. So, for
example, when I say that the sum of a bunch of numbers is zero, I mean
that it's divisible by n.
Suppose we're given n numbers whose sum is zero, and we want to rearrange
them to form a siteswap. We'll do this by starting with the length-n
siteswap 00...0 and then changing two numbers at a time, keeping the sum
equal to zero, until we get the desired bunch of numbers. For example,
if we start with the 6 numbers 023355, then we could successively change
000000 to 024000 to 023100 to 023340 to 023355, rearranging at each step
to get a siteswap.
We will show that each time we replace two numbers in a siteswap by two
other numbers with the same sum (so that the sum of all of the numbers is
still zero), we can rearrange the new numbers to form a new siteswap.
We start by writing the original siteswap in a 3-row format: The top row
contains the numbers 0, 1, ..., n-1. The second row has the n numbers of
the siteswap. Each element of the third row is the sum of the two numbers
above it (mod n). The defining property of siteswaps is that the third
row contains the numbers 0, 1, ..., n-1 in some order.
For example, suppose we start with the length-8 siteswap 53052630. In 3-row
format this looks like:
0 1 2 3 4 5 6 7
5 3 0 5 2 6 3 0
5 4 2 0 6 3 1 7
(View this in a fixed-width font.)
Next we erase the 2 numbers in the second row that are being changed, and
write the 2 numbers that they're being changed to at the right. We also
delete the corresponding 2 numbers in the third row and put them at the
right. We'll call the resulting display a "partial siteswap".
In the example above, suppose we want to change the 0 and 2 in columns 2
and 4 to a pair of 1's. (We then have the numbers 53151630; the sum of
these is zero, but they don't form a siteswap.) We erase the 0 and 2 from
the middle row of the display above, and put the 1's on the right. We
also delete the corresponding elements of the bottom row (2 and 6) and
put them on the right:
0 1 2 3 4 5 6 7
5 3 - 5 - 6 3 0 1 1
5 4 - 0 - 3 1 7 2 6
Call the columns with missing elements a0 and a1. Call the two numbers at
the right end of the second row b0 and b1, and the two numbers at the right
end of the third row c0 and c1. (In the example, a0=2, a1=4, b0=b1=1,
c0=2, and c1=6.) Note that
a0 + a1 + b0 + b1 = c0 + c1; (*)
this is true because b0 and b1 have the same sum as the 2 numbers that were
deleted from the original siteswap.
We start by checking to see if the sum of a0 and either b0 or b1 is equal
to c0 or c1. Suppose, for example, that a0+b1=c0. From equation (*), we
also have a1+b0=c1. Hence we can move the b1 to column a0 and the b0 to
column a1 and get a valid siteswap. Similarly, in the other 3 cases we can
move b0 and b1 to columns a0 and a1 in some order and obtain a siteswap.
If not, then let x=c0-b0. Note that x is neither a0 nor a1, so column x is
not empty. Let b2 and c2 be the numbers in the second and third rows of
column x. We swap b2 and b0, and move c0 to column x, c1 to the c0 position,
and c2 to the c1 position. I.e. we change this:
... x ...
... b2 ... b0 b1
... c2 ... c0 c1
to this:
... x ...
... b0 ... b2 b1
... c0 ... c1 c2
Note that x+b0=c0, so this is still a valid partial siteswap. Also,
a0+a1+b2+b1 = a0+a1+b0+b1 + b2-b0
= c0+c1 + b2-b0
= c1+b2 + c0-b0
= c1+b2 + x
= c1+b2 + c2-b2 = c1+c2;
thus equation (*) still holds for the new partial siteswap.
In the example, we have x = c0-b0 = 2-1 = 1. Column 1 has 3 and 4 in the
second and third rows, so b2=3 and c2=4. Hence we change the partial
siteswap above to:
0 1 2 3 4 5 6 7
5 1 - 5 - 6 3 0 3 1
5 2 - 0 - 3 1 7 6 4
Now we repeat the process: We relabel the numbers on the right b0, b1, c0,
and c1. (Note that b1 hasn't changed; neither have a0 and a1.) Then we
check to see if a0 plus either b0 or b1 equals either c0 or c1; if so we're
done. If not, then we let x=c0-b0 and rearrange things again. We repeat
this as often as necessary; we'll either get a valid siteswap after some
number of steps, or we'll keep rearranging forever.
Before giving Hall's proof that the process can't continue forever, I'll
finish the example. In the display above, we have b0=3, b1=1, c0=6, and
c1=4. We still have a0=2 and a1=4. If we add a0 to either b0 or b1, we
don't get either c0 or c1, so we need to rearrange again. We have
x = c0-b0 = 6-3 = 3, b2=5, and c2=0. So we change the partial siteswap to:
0 1 2 3 4 5 6 7
5 1 - 3 - 6 3 0 5 1
5 2 - 6 - 3 1 7 4 0
After relabeling again, we still don't have a0 plus either b0 or b1 equal
to c0 or c1. We now have x = 4-5 = 7. (Recall that our arithmetic is
being done mod n=8.) Rearranging gives:
0 1 2 3 4 5 6 7
5 1 - 3 - 6 3 5 0 1
5 2 - 6 - 3 1 4 0 7
Now we have x = 0-0 = 0, and we get:
0 1 2 3 4 5 6 7
0 1 - 3 - 6 3 5 5 1
0 2 - 6 - 3 1 4 7 5
This time we have a0+b0=c0; i.e. 2+5=7. So also a1+b1=c1; i.e. 4+1=5.
Hence we can move b0=5 to column 2 and b1=1 to column 4, and we've found
our new siteswap:
0 1 2 3 4 5 6 7
0 1 5 3 1 6 3 5
0 2 7 6 5 3 1 4
The net result of all of this is that we started with the siteswap
53052630, changed the first 0 and the 2 to 1's, and rearranged the new
numbers to get the siteswap 01531635.
We still need to show that the process must eventually stop. To do so,
we'll show that the numbers x that occur during the process are all
distinct. Since there are only finitely many values that x can have (n-2
to be specific, since x can't be a0 or a1), this will imply that the
process stops after a finite number of steps.
So suppose that some value of x occurs twice. Among all such values, pick
the one that occurs first. So at one stage we change
... x ... ... x ...
... b2 ... b0 b1 to ... b0 ... b2 b1
... c2 ... c0 c1 ... c0 ... c1 c2
and at a later stage we change
... x ... ... x ...
... b2' ... b0' b1 to ... b0' ... b2' b1
... c2' ... c0' c1' ... c0' ... c1' c2'
but before this later stage, no repetitions have occurred.
The fact that this is the first repetition implies that c1 is not equal
to c1': Both of these numbers were moved to the rightmost position in
the display at some earlier stage, either from the original column a1
or from the column that was labelled "x" at some previous stage. But
we'll now show that c1 = c1', giving a contradiction:
From equation (*) for the two partial siteswaps on the left, we have
a0 + a1 + b0 + b1 = c0 + c1
and
a0 + a1 + b0' + b1 = c0' + c1'.
Subtracting these gives
b0 - b0' = c0 + c1 - c0' - c1'.
But from the definition of x in the same two partial siteswaps, we have
x + b0 = c0
and
x + b0' = c0'.
Hence
b0 - b0' = (x + b0) + c1 - (x + b0') - c1'
= b0 - b0' + c1 - c1',
so
c1 = c1'.
We've reached a contradiction, so we conclude that the columns x are all
distinct, and the process must finish after a finite numbers of steps,
yielding a siteswap that's a rearrangement of the new set of numbers.
To conclude, let's work through one complete example, starting with a list
of numbers that we want to rearrange to a siteswap. Let's try the 10
numbers 1123345777. We'll start with the siteswap 0000000000 and then
change the list successively to:
1900000000
1180000000
1126000000
1123300000
1123346000
1123345100
1123345740
1123345777
Since the first two lines above are already siteswaps, we'll start with
the second one, 1180000000, and apply Hall's method to change the 8 and
one 0 to 2 and 6:
0 1 2 3 4 5 6 7 8 9
1 1 - - 0 0 0 0 0 0 2 6
1 2 - - 4 5 6 7 8 9 0 3
x=8, so this becomes:
0 1 2 3 4 5 6 7 8 9
1 1 - - 0 0 0 0 2 0 0 6
1 2 - - 4 5 6 7 0 9 3 8
a0+b1=c1, so we get the siteswap 1160000020:
0 1 2 3 4 5 6 7 8 9
1 1 6 0 0 0 0 0 2 0
1 2 8 3 4 5 6 7 0 9
Now we'll change the 6 and a 0 to two 3's:
0 1 2 3 4 5 6 7 8 9
1 1 - - 0 0 0 0 2 0 3 3
1 2 - - 4 5 6 7 0 9 8 3
x=5, so this becomes:
0 1 2 3 4 5 6 7 8 9
1 1 - - 0 3 0 0 2 0 0 3
1 2 - - 4 8 6 7 0 9 3 5
a0+b1=c1, so we get the siteswap 1130030020:
0 1 2 3 4 5 6 7 8 9
1 1 3 0 0 3 0 0 2 0
1 2 5 3 4 8 6 7 0 9
Next we change two 0's to 4 and 6:
0 1 2 3 4 5 6 7 8 9
1 1 3 - - 3 0 0 2 0 4 6
1 2 5 - - 8 6 7 0 9 3 4
x=9, so this becomes:
0 1 2 3 4 5 6 7 8 9
1 1 3 - - 3 0 0 2 4 0 6
1 2 5 - - 8 6 7 0 3 4 9
a0+b1=c1, so we get the siteswap 1136030024:
0 1 2 3 4 5 6 7 8 9
1 1 3 6 0 3 0 0 2 4
1 2 5 9 4 8 6 7 0 3
Now change 6 and 0 to 5 and 1:
0 1 2 3 4 5 6 7 8 9
1 1 3 - - 3 0 0 2 4 5 1
1 2 5 - - 8 6 7 0 3 9 4
a0+b1=c1, so we get the siteswap 1131530024:
0 1 2 3 4 5 6 7 8 9
1 1 3 1 5 3 0 0 2 4
1 2 5 4 9 8 6 7 0 3
Change a 1 and a 0 to 7 and 4:
0 1 2 3 4 5 6 7 8 9
- 1 3 1 5 3 - 0 2 4 7 4
- 2 5 4 9 8 - 7 0 3 1 6
x=4, so this becomes:
0 1 2 3 4 5 6 7 8 9
- 1 3 1 7 3 - 0 2 4 5 4
- 2 5 4 1 8 - 7 0 3 6 9
x=1, so this becomes:
0 1 2 3 4 5 6 7 8 9
- 5 3 1 7 3 - 0 2 4 1 4
- 6 5 4 1 8 - 7 0 3 9 2
x=8, so this becomes:
0 1 2 3 4 5 6 7 8 9
- 5 3 1 7 3 - 0 1 4 2 4
- 6 5 4 1 8 - 7 9 3 2 0
a0+b0=c0, so we get the siteswap 2531734014:
0 1 2 3 4 5 6 7 8 9
2 5 3 1 7 3 4 0 1 4
2 6 5 4 1 8 0 7 9 3
Finally, change 4 and 0 to two 7's:
0 1 2 3 4 5 6 7 8 9
2 5 3 1 7 3 - - 1 4 7 7
2 6 5 4 1 8 - - 9 3 0 7
x=3, so this becomes:
0 1 2 3 4 5 6 7 8 9
2 5 3 7 7 3 - - 1 4 1 7
2 6 5 0 1 8 - - 9 3 7 4
a0+b0=c0, so we get the siteswap 2537731714:
0 1 2 3 4 5 6 7 8 9
2 5 3 7 7 3 1 7 1 4
2 6 5 0 1 8 7 4 9 3
Note that 2537731714 is indeed a rearrangement of our original list,
1123345777.
Dean Hickerson
de...@math.ucdavis.edu
Dean Hickerson
> A proof is given in "A combinatorial problem on abelian groups"
> by Marshall Hall, Jr., Proceedings of the American Mathematical Society,
> vol. 3 (1952), pp. 584-587.
Gerald R. Martin replied:
> Small world: Professor Hall was my graduate adviser at Caltech for most of
> a year. He had a fine sense of humor, though we never really hit it off;
> it's a little odd to picture him juggling, but it's not at all odd to
> picture him getting straight to the heart of the combinatorics of
> *anything*.
I don't know if Hall is or was a juggler, but I doubt that his article was
inspired by juggling: Siteswap notation wasn't invented until much later.
Hall's paper attributes the question, at least for cyclic groups, to someone
named George Cramer, but doesn't say how it arose. But to an abelian grouper
the question seems rather natural, so it's not surprising that someone
thought of it long ago.
Dean Hickerson
de...@math.ucdavis.edu
Dean Hickerson
: Here are some details that fill in the blanks that I left in my proof. I
: have made 2 insertions that will make the inductive part clearer then
: before. I think that the proof is now complete. Any critique, questions, or
: comments will be appreciated.
...
:>Now for some classic induction: let p < n-2 and assume that the proof is
:>complete for p non-zero numbers, x1, x2,...,xp. Prove the case for p+1.
:>
:>Assume the xi's make one circuit so that x1 lands on x2, x2 lands on x3,...,
:>xp lands on x1. Let xq be the p+first non-zero element that will be
:>"grafted" into the circuit. Assume WLOG that x1 will land on xq, and xq
:>will land on x2.
:>
:>Replace x2 with y2 = (x2 + x3 +...+ xp) modulo n, and replace x3, x4,..., xp
:>with zeros( given any siteswap, if x1 lands on x2 then you can replace x1
:>with (x1 + x2) modulo n, and replace x2 with zero.). Our task has been
:>reduced to inserting xq into the circuit x1 and y2. We already did this and
:>conclude that every possible sequence of p+1 non-zero numbers, such that
:>their sum is a multiple of n (up to p times n), is contained in the
:>siteswaps generated by the grafting of xq.
: Let's clarify the paragraph above:
: After we reduce the above to x1, y2, xq, and n-3 zeros, I claim that x1 can
: range from 1 to n-1. This is the same as saying that x1 can land anywhere.
: But having y2 implies that there are lots of sites that were filled by x's.
: That's ok because if x1 lands on another xi that was already there, then
: some of the x's will become zero (as x3 became zero when we considered that
: x1 landed of x2 for our 3-non-zero number case).
I don't understand this. You start with x1, ..., xp, each landing on the
next. So the sum x1 + x2 + ... + xp is divisible by n. Now you want to
graft a new number xq into that. But the sum x1 + ... + xp + xq is
congruent to xq, not to zero. So how can you hope to graft xq in? Also,
the process that you describe involves changing the numbers, so how do you
end up with the numbers that you want to have in the siteswap?
Could you give some examples to show how this works?
Dean Hickerson
de...@math.ucdavis.edu
Chris Emerson
Henry Segerman <sjoh...@sable.ox.ac.uk> wrote:
> Chris Emerson <ceme...@chiark.greenend.org.uk> wrote:
> : In article <95ums9$t3j$1...@news.ox.ac.uk>,
> :>
> :> Theres a fun 3 ball one I've been playing about with:
> :> [32]1
>
> : Can you split them enough not to have to snatch the 2? I can't. (I
>
> I've been practising it a lot. Needs a lot of wrist, and sortof need to
> slightly grip the lower ball as you release it so it doesnt have much height.
> Barnsey bags probably help too.
Indeed, Barnsey bags seem to be good for many things.
> : might also write it [21]).
>
> I think thats different, the 1 in [21] could be held, so its like juggling
> 2 in one hand with a third held.
It could be held, but doesn't have to be. But ok, [32]1 may be more
explicit about it.
> Ben Beever's extended siteswap notation will do it, but for most purposes
> nobody uses anything other than 2 hands.
Is there an online description of it, or is it in his book?
> : I've tried 42, which I can generally do once. 531 isn't that interesting,
> : and 522 is impossible without a really high ceiling, and nearly impossible
> : without.
>
> Yeah, gets hard quick.
Which is good, 'cause otherwise it wouldn't be as fun. :-)
> : Hmm, I've tried that but never succeeded. I shall have to do so when
> : my other arm's sufficiently recovered. I can do ...33323[31]333...
> : though, which is slightly silly.
>
> Weird grabbing that 1 while avoiding the 3 :)
I'd like to do continuous [31], but it's rather odd.
Henry Segerman
:> : might also write it [21]).
:>
:> I think thats different, the 1 in [21] could be held, so its like juggling
:> 2 in one hand with a third held.
: It could be held, but doesn't have to be. But ok, [32]1 may be more
: explicit about it.
You're right, its pretty much the same in terms of what gets thrown, but
the rhythm is (for whatever I'm doing anyway) more [32]1.
:> Ben Beever's extended siteswap notation will do it, but for most purposes
:> nobody uses anything other than 2 hands.
: Is there an online description of it, or is it in his book?
Book. ISTR htmling something of Ben's but I don't think it ever made it to
the web.
:> Yeah, gets hard quick.
: Which is good, 'cause otherwise it wouldn't be as fun. :-)
Well of course :)
:> : Hmm, I've tried that but never succeeded. I shall have to do so when
:> : my other arm's sufficiently recovered. I can do ...33323[31]333...
:> : though, which is slightly silly.
:>
:> Weird grabbing that 1 while avoiding the 3 :)
: I'd like to do continuous [31], but it's rather odd.
Woo, weird. I can't do the [31] so I'm trying it like a [53] throw but with
big pauses. Hmm. I think this pattern is easier with 1 hand than with 2! There
can't be many like that :)
Steve Otteson
Dean Hickerson wrote in message <960jpc$dmb$1...@woodrow.ucdavis.edu>...
When we graft xq, assume that x1 will land on xq and xq will land on x2.
This means that x1 will change. In fact, x1 = y1 + xq (modulo n), where y1
is the new x1.
Suppose n = 6, x1 = 2, and x2 = 4 so that the siteswap is 2,0,4,0,0,0.
I claimed that any number from 1 to n can be grafted. If xq = 4, for
example, place xq so it lands on x2: 2,0,4,0,4,0. Now change x1 so that x1
lands on xq: x1 has to be a 4. Replace the 2 with a 4 yields: 4,0,4,0,4,0.
Steve O.
Dean Hickerson
> When we graft xq, assume that x1 will land on xq and xq will land on x2.
> This means that x1 will change. In fact, x1 = y1 + xq (modulo n), where y1
> is the new x1.
>
> Suppose n = 6, x1 = 2, and x2 = 4 so that the siteswap is 2,0,4,0,0,0.
> I claimed that any number from 1 to n can be grafted. If xq = 4, for
> example, place xq so it lands on x2: 2,0,4,0,4,0. Now change x1 so that x1
> lands on xq: x1 has to be a 4. Replace the 2 with a 4 yields: 4,0,4,0,4,0.
This is still too vague. I certainly agree that if you have a valid
siteswap (like 2,0,4,0,0,0 in your example), you can change the numbers
in it to include some given number (4 in your example). But if you're
trying to create a siteswap with n specific numbers, then it seems that
the changes that you're making (like changing x1 to 4 above) can mess
things up.
For example, suppose we want a siteswap that's a rearrangement of
1,2,3,0,0,0. We might start with 2,0,4,0,0,0 as above, and try to graft
in xq=3. Place xq so that it lands on x2: 2,0,4,0,0,3. Now change x1
so that x1 lands on xq: 5,0,4,0,0,3. We've grafted 3 into the original
siteswap, but we've ended up with the wrong numbers in the result. If
we'd changed the 4 we'd be OK, but we changed the 2.
So how do you guarantee that you can graft a specific number without
messing up the other numbers that you already have? I agree that it
can be done; that's essentially how Marshall Hall's proof works. But
you seem to be trying to give a simpler method than Hall's, and I don't
think you've given enough details of how it's supposed to work.
Dean Hickerson
de...@math.ucdavis.edu
Steve Otteson
shows that all sequences that sum to a multiple of n are generated when you
generate all siteswaps.
Mr. Hall's proof contains an algorithm that takes a specific sequence and
converts it to a siteswap.
I need more time to digest his proof.
Distinguishably,
Steve O
Dean Hickerson wrote in message <967mor$78t$1...@woodrow.ucdavis.edu>...
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Wolfgang Schebeczek
>at the Erlangen convention recently, Alan Mackenzie suggested this theorem:
>
> for all sequences of n numbers x1, x2, .. xn
> whose sum is a multiple of n,
> there is a permutation of these numbers
> that is a valid siteswap.
[...]
>can you prove this? i'll post the solution in a few days. regards,
And while the original author kept silent (at least according to my
news feed), Dean Hickerson has brought us the proof that Alan was
right and that this result is known in mathematics already for 50
years. First I want to say thank you to Dean for his detailed
explanations, which saved us the work looking up and digging through
the original paper.
Second, I would like to know more about the history of Alan's
conjecture. I don't want to diminish Alan's contribution, at least it
started this thread and all the collective work which was put in here.
But I guess jugglers have thought about it already before Erlangen
convention. That the sum-is-a-multiple-of-n-condition is not
sufficient for a numbers' sequence being a valid siteswap is easiest
shown by starting with a valid siteswap, and permuting the numbers in
a way that collisions occur. It's obvious that this method of finding
a counter example does not work if one wants to try to disproof Alan's
conjecture. I recall that starting at this point, I tried mutually to
proof it and to find counter examples some years ago (with no
success). I guess, others have done this too, as the question arises
more or less automatically.
I do not recall that the question has been debated in any publication,
but maybe it has been discussed already in this or another discussion
group. Maybe someone had written in past a computer program that at
least showed that under some restrictions (concerning n, maximum
heigth etc.) there is no counter example to be found etc.
As the question is solved in a satisfying way now, I don't consider
such historical anecdotes as to important. But both in juggling and in
mathematics there seems to be the law that the longer it takes to
master a problem the more the result is appreciated, at least by
in-siders. While Alan's conjecture by far cannot be compared this way
with e.g. Fermat's theorem, it's history could shed a light on all the
amount of time which already has been wasted on it. Many jugglers have
contributed to this thread with their "half proofs". I guess, many
more had tried their luck, but their "results" went rather to the
paper basket before being published here. At least for me that
happened. And seeing Hall's proof I don't feel ashamed.
I want to drop a note about this thread and its results in next issue
of Kaskade. Also for this purpose I would like to know more about the
history of the problem.
wolfgang
P.S.: Any objections against calling the theorem "Alan's conjecture"?
I am aware that it is no conjecture anymore, and that this name
diminishes the role of Hall who proved it and Dean who told us that.
And not to forget: Johannes, whose claim to possess a proof kept the
whole discussion alive until a solution appeared. (At least the last
point justifies the comparison with Fermat's theorem. By the way, any
idea why he still is remaining silent? (Johannes, not Fermat ;-))
----------------------------------
Wolfgang Schebeczek <ws...@EUnet.at>
Dean Hickerson
> My proof does not generate a specific siteswap from a given sequence. It
> shows that all sequences that sum to a multiple of n are generated when you
> generate all siteswaps.
No, it doesn't. You've stated that all sequences are generated, but you
haven't given a proof.
Dean Hickerson
de...@math.ucdavis.edu
Dean Hickerson
> While I was looking for a way to prove the theorem, I considered using a
> formula that gets the total number of siteswaps when given n, the number of
> numbers in the siteswap. I decided that this wouldn't help the proof, but
> continued the search for the formula.
...
> n | Number of | Number of
> | Siteswaps | Sequences
> --------------------------------------
> 1 1 1
> 2 2 2
> 3 4 4
> 4 10 10
> 5 28 26
> 6 136 80
> 7 726 246
> 8 5,100 810
> 9 40,362 2,704
...
> For n less than 5, the number of siteswaps is the same as the
> number of sequences. For n = 5, there is one sequence that has 3 siteswaps.
> For n greater than 5, the number of siteswaps sky-rockets compared to the
> number of sequences. I was astonished to see this.
>
> I thought that once I had a look at the triangles, the formula for the
> number of siteswaps would hit me like a cool slap in the face. After looking
> at them for a couple of hours, the only thing that came across my face was
> my own hand (I was falling asleep).
>
> I'll let you all play with the numbers while I take a nap. Wake me up if you
> find anything.
Obtaining formulas for these is somewhat complicated, and probably not of
great interest to most people reading rec.juggling, so I'll just summarize
the ideas and results.
When we count siteswaps, we consider two sequences that are cyclic
permutations of each other to be the same. E.g. 1223, 2231, 2312, and
3122 all represent the same siteswap. Call each of these sequences a
"siteswap representation". Obviously the number of siteswap representations
of length n (with all elements between 0 and n-1) is equal to the number of
permutations of a set of n elements, namely n!. Most siteswaps of length n
have exactly n representations, so we may expect that the number of
siteswaps of length n is about n!/n = (n-1)!, and this agrees well with
the numbers in Steve's second column:
n 1 2 3 4 5 6 7 8 9
(n-1)! 1 1 2 6 24 120 720 5040 40320
# of siteswaps 1 2 4 10 28 136 726 5100 40362
To get an exact count, we have to take into account the fact that some
siteswaps of length n have fewer than n representations; e.g. 042042 has
only 3. With a bit of work we can obtain the formula
d-1
# siteswaps of length n = SUM phi(n/d) (n/d) (d-1)!
d|n
where phi(n) is the Euler totient function, which counts the number of
numbers in {0, 1, ..., n-1} which are relatively prime to n, and the
sum is over all positive integers d which are divisors of n. (Note that
the d=n term dominates the sum, and equals the estimate given above.)
For example, if n=6, then the number of siteswaps is
0 1 2 5
phi(6) 6 0! + phi(3) 3 1! + phi(2) 2 2! + phi(1) 1 5!
= 2 1 1 + 2 3 1 + 1 4 2 + 1 1 120
= 2 + 6 + 8 + 120
= 136.
For Steve's third column, we can again get an estimate fairly easily:
We want to count multisets of n elements from {0, 1, ..., n-1} in which
the sum is divisible by n. (A multiset is a list of numbers, not
necessarily distinct, in which the order is ignored.) If we drop the
"divisible by n" condition, then it's easy to count the multisets; a
standard result in enumerative combinatorics says that the number of
multisets of size m in a set of n elements is the binomial coefficient
m+n-1 choose m, which equals
(m+n-1)!
---------.
m! (n-1)!
In our case that's
(2n-1)!
---------.
n! (n-1)!
It's reasonable to guess that about 1 n'th of these have sums divisible
by n, so the number in Steve's third column is about
(2n-1)!
-------.
2
n!
Again this agrees with Steve's numbers:
n 1 2 3 4 5 6 7 8 9
(2n-1)!/(n!)^2 1 1.5 3.3 8.8 25.2 77 245.1 804.4 2701.1
# of sequences 1 2 4 10 26 80 246 810 2704
(Entries in the middle row have been rounded.)
Obtaining an exact formula for these seems to be more difficult. As
Greg Warrington <gw...@math.harvard.edu> mentioned, this sequence appears
in Neil Sloane's On-Line Encyclopedia of Integer Sequences, at
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/
eisA.cgi?Anum=A003239
(That should all be on one line.)
Sloane's database gives two meanings of the sequence, and explains why they're
equivalent to each other. One is the number of rooted planar trees with
n non-root nodes. The other is the number of necklaces with n beads of one
color and n beads of another color. A "necklace" is a sequence of symbols,
called beads; two necklaces are considered identical if one can be obtained
by a cyclic permutation of the other. For example, if n=4, then there are
10 necklaces with 4 0's and 4 1's:
00001111 00010111 00011011 00011101 00100111
00110011 00101101 00101011 00110101 01010101
It's not at all obvious that the number of necklaces is the same as the
n'th number in Steve's third column. Further experimentation suggests the
following more general result: The number of multisets of m elements from
{0, 1, ..., n-1} with sum divisible by n is equal to the number of necklaces
with m 0's and n 1's. I've managed to prove this by working with generating
functions and roots of unity, but I'd like to see a simpler proof. (Or a
reference; such a pretty result must have been discovered before.)
A formula is given in Sloane's database:
1 (2d)!
# sequences of length n = -- SUM phi(n/d) -----
2n d|n 2
d!
(As before, the d=n term dominates the sum, and equals the estimate given
earlier.)
For example, for n=9 this gives
1 2! 6! 18!
-- ( phi(9/1) --- + phi(9/3) --- + phi(9/9) --- )
18 2 2 2
1! 3! 9!
= (6 2 + 2 20 + 1 48620)/18 = 2704.
Finally, if we divide the estimates for Steve's two columns, we obtain an
estimate for the average number of siteswaps corresponding to a given
sequence of length n:
2 3
(n-1)! n! 2 n!
---------- = -----.
(2n-1)! (2n)!
Stirling's formula gives an approximation to n! that's accurate for large n,
namely n! ~ sqrt(2 pi n) (n/e)^n. Using that here gives
n+1
2 sqrt(2) pi n
-----------------
n
(4e)
As Steve mentioned, this does indeed skyrocket. For example, for n=20,
there are about 35 million siteswaps per sequence. Of course that's just
an average; some sequences (like 000...0) only have one corresponding
siteswap. It would be interesting to see which sequences have the largest
number of corresponding siteswaps, and how that maximum compares to the
average.
Dean Hickerson
de...@math.ucdavis.edu
Dean Hickerson
proof was unclear. I agree, so here's a clarification of it. Note that
this was my fault, not Hall's; in my attempt to translate the proof for
nonmathematicians I messed up part of it.
The problem was in the proof that the process must stop. I said:
> We still need to show that the process must eventually stop. To do so,
> we'll show that the numbers x that occur during the process are all
> distinct. Since there are only finitely many values that x can have (n-2
> to be specific, since x can't be a0 or a1), this will imply that the
> process stops after a finite number of steps.
>
> So suppose that some value of x occurs twice. Among all such values, pick
> the one that occurs first. So at one stage we change
>
> ... x ... ... x ...
> ... b2 ... b0 b1 to ... b0 ... b2 b1
> ... c2 ... c0 c1 ... c0 ... c1 c2
>
> and at a later stage we change
>
> ... x ... ... x ...
> ... b2' ... b0' b1 to ... b0' ... b2' b1
> ... c2' ... c0' c1' ... c0' ... c1' c2'
>
> but before this later stage, no repetitions have occurred.
>
> The fact that this is the first repetition implies that c1 is not equal
> to c1': Both of these numbers were moved to the rightmost position in
> the display at some earlier stage, either from the original column a1
> or from the column that was labelled "x" at some previous stage.
That last sentence doesn't justify the claim that c1 is not equal to c1'.
Instead, let's label the 4 partial siteswaps shown above: At one stage
we change
... x ... ... x ...
... b2 ... b0 b1 to ... b0 ... b2 b1
... c2 ... c0 c1 ... c0 ... c1 c2
Call these partial siteswaps A and B.
At a later stage we change
... x ... ... x ...
... b2' ... b0' b1 to ... b0' ... b2' b1
... c2' ... c0' c1' ... c0' ... c1' c2'
Call these partial siteswaps C and D.
Consider what happens after partial siteswap B. We compute x' = c1 - b2,
and move c1 to the bottom of column x'. It will stay there unless a
subsequent value of x is also equal to x'. Since we're assuming that
the value of x in partial siteswaps A and C is the first one to be repeated,
x' can't reoccur as a value of x until after partial siteswap C. So in
partial siteswap C, c1 is still at the bottom of column x', and it
can't be equal to c1'.
Dean Hickerson
de...@math.ucdavis.edu