An Unurned Sum
 

An urn contains n balls numbered 1 through n, for integer n > 0.
The balls are removed randomly one by one.
What's the probability that, at some point, the sum of the values
on the removed balls is a multiple of n?

If you count permutations, or simulate random drawings to get
an expected value, find the probability for n = 1 through, say, 20.
There is, however, a shortcut (hint).

[SPOILER]for n odd, sum(n) is always a multiple of n, so the probabilty for all odd n is 1[/SPOILER]

[spoiler]
2 is trivially 1/2
4 is 9/24 = 3/8
6 is 221/720
[/spoiler]
I'll come back to this

[QUOTE=starrynte;172112][spoiler]
4 is 9/24 = 3/8
[/spoiler]
I'll come back to this[/QUOTE]

[spoiler]you sure about that?[/spoiler]

[quote=Orgasmic Troll;172197][spoiler]you sure about that?[/spoiler][/quote]
[spoiler]Hmmm...<double checks>4, (1,3), (3,1), (1,3,4),(1,4,3),(3,1,4),(3,4,1),(4,1,3),(4,3,1)</double checks> What was my mistake? (if there was an error then the probability for 6 is probably also wrong)[/spoiler]

[QUOTE=starrynte;172349][spoiler]Hmmm...<double checks>4, (1,3), (3,1), (1,3,4),(1,4,3),(3,1,4),(3,4,1),(4,1,3),(4,3,1)</double checks> What was my mistake? (if there was an error then the probability for 6 is probably also wrong)[/spoiler][/QUOTE]

[spoiler]hint: how are 4213 and 4231 counted in your scheme?[/spoiler]

So far, I have
[spoiler]n = 4 : 12/24
n = 6 : 440/720
n = 8 : 23688/40320
I do not see a way to simplify it yet
[/spoiler]

[quote=Orgasmic Troll;172354][spoiler]hint: how are 4213 and 4231 counted in your scheme?[/spoiler][/quote]
[spoiler]4213 and 4231 don't add up to a multiple of 4, they aren't counted...I don't follow.[/spoiler]

[QUOTE=starrynte;172656][spoiler]4213 and 4231 don't add up to a multiple of 4, they aren't counted...I don't follow.[/spoiler][/QUOTE]

[spoiler]4 is a multiple of 4[/spoiler]

[spoiler]OK I see now[/spoiler]

Here's a few more values - assuming my quick and dirty program is correct. I
can't see how to do this one analytically. Anyone have any insights?

[CODE]
[SPOILER]
-- ------------------- ---------- ------------------------------
n P(S) Simplified Decimal
-- ------------------- ---------- ------------------------------
2 1/2 1/2 0.5000000000000000000000000000
4 12/24 1/2 0.5000000000000000000000000000
6 440/720 11/18 0.6111111111111111111111111111
8 23688/40320 47/80 0.5875000000000000000000000000
10 2223936/3628800 429/700 0.6128571428571428571428571429
12 293639808/479001600 9931/16200 0.6130246913580246913580246914
-- ------------------- ---------- ------------------------------
[/SPOILER]
[/CODE]