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]

Ok, my brute force program has come to the end of its usefulness. The case n=14 took 50 minutes to run and rolled into the 64 bit integer domain. Time to exercise more of the gray matter on the problem.

[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
14 53925490944/87178291200 1800397/2910600 0.6185655878513021370164227307
-- ----------------------- --------------- ------------------------------
[/SPOILER]
[/CODE]

[spoiler]Purely based upon inspection of the numbers posted by tmorrow above, I would hazard a guess of the Golden Ratio Conjugate.[/spoiler]

[SPOILER]Nice one Retina, (sqrt(5)-1)/2 = 0.6180339887498948482045868344... might be the limit (if it exists). Now to work out why it might be so.[/SPOILER]

Isn't the limit Exact?

[quote=davar55;179629]Isn't the limit Exact?[/quote]

Let me rephrase that -- can someone program the next several data
points to ensure that this is in fact approaching the Golden Ratio as
a limit, as a prelude to trying to actually prove this? I thnk it would
be an interesting result if true.

What, by the way, is the value of the Golden ratio, to fifty decimals?

If these two numbers match for fifty decimal digits, don't you think
that they are equal in the limit?

How do you count?
 

[FONT=Tahoma]There is some ambiguity in the original posing of this question.
It would appear that everyone posting answers has made the same assumption :-

For each of the possible n! combinations, start summing the numbers. As soon as you find a multiple of n, count 1, stop.

This effectively assumes that all the balls are drawn before the n possible sums of each drawing are examined, and this only constitutes a single case. A completely reasonable interpretation of the problem.

However, consider for example, the case of n=4. At some point we come to 1,3,4,2
1 = NO
1,3 = YES
1,3,4 = YES
1,3,4,2 = NO
So one drawing, two instances of divisibility by n.
Or is that to be considered as 4 separate drawings (nowhere does it state that all the balls are drawn)?
That is, you check after each ball is drawn and increment the count appropriately. In which case there are 64 possibilities, of which only 9 sums are divisible by 4 (the ones listed by [B]starrynyte[/B])
[/FONT][FONT=Tahoma]Just another way of looking at the same problem.[/FONT]

Since every integer n > 0 is finite, all the balls are drawn.

[QUOTE=davar55;242681]What, by the way, is the value of the Golden ratio, to fifty decimals?

If these two numbers match for fifty decimal digits, don't you think
that they are equal in the limit?[/QUOTE]
(sqrt(5)-1)/2 to fifty digits is:
[CODE]0.61803398874989484820458683436563811772030917980576[/CODE]
courtesy of PARI-GP.

Some thoughts on a non brute force method.
 

I've also written a brute force program to count the permutations and the results agree with tomorrow's post #11 & 12 back in 2009.
My run time for the case n=14 is similar and I confirm it needed 64 bit integers.
I haven't worked out all the details of an analytical approach, but would make the following observations.
[SPOILER]1) All permutations starting with n meet the criteria straight away and there are (n-1)! of them - the remaining n-1 numbers can be arranged in (n-1)! ways.
2) All permutations starting n-k , k (0<k<n, k != n/2) meet the criteria and there are (n-2)*(n-2)! of them - k can have all n values except n & n/2 and the remaining n-2 numbers can be arranged in (n-2)! ways.
3) Permutations starting n-k, n-j, j+k (0<k<n & 0<j<n & j != k & j+k < n j+k != n-k or n-j). I can't quite work out how many of these there are as a multiple of (n-3)!
4) And so on, getting more and more complicated conditions.

But then there are the combinations where the sum equals some multiple of n rather than just n.

If the first k balls add up to a multiple of n then there are a total of (n-k)! combinations that have this feature. Is there any way of speeding up the brute force method by skipping the generation and testing of all these and counting them as a block?[/SPOILER]

Nice preliminary analytic analysis.

If only the superb programmers here talked to the math people.

Further thoughts on an analytical method
 

[SPOILER]You only need to generate all the possible combinations of the n digits. As soon as you find a combination of k digits who's sum is divisible by n you know that there are k! ways of arranging those digits and (n-k)! ways of arranging the remaining ones. Hence you have found k!(n-k)! solutions in one test.
However there is a complication, see the example below.

for k = 1 to n
1) Generate all possible combinations of k out of n numbers
2) increment count by k!(n-k)! for each combination who's sum is divisible by n, but see note below.
3) increment k
4) repeat steps 1 to 4 for all remaining combinations.

Thus, take the easy case of n=4
count=0
k=1
1 - no
2 - no
3 - no
4 - yes count= count + 1!*3! = 6
k=2
1,2 - no
1,3 - yes count= count + 2!*2! = 10
1,4 - no
2,3 - no
2,4 - no
3,4 - no
k=3
1,2,3 - no
1,2,4 - no
1,3,4 - yes, but counts as only 2, count = count + 2 = 12 *
2,3,4
k=4
1,2,3,4 - no
done

* Only count these as 2 rather than 3!. If you find a combination of k digits where sum is divisible by n AND sum/n > 1 you test all the sub-combinations of those k digits to see if any match the previously marked shorter combinations and adjust the contribution accordingly. So if a sub-combination of j of the k digits is also divisible by n then only count (k-j)!(n-k)!2!. The 2! is because the two groups of number can be arranged in 2! ways.
In the case of 1,3,4 k=3 and each has a subset 1,3 so j=2, therefore count (3-2)!(4-3)!2! = 2 .

Note that this only requires 14 steps rather than 24 for a brute force attack and I'm pretty certain the as n increases the advantage becomes greater.

Anyone out there see how to simplify the additional test step?

Further musings

Question - if sum/n > 1 will there ALWAYS be a sub-combination divisible by n?
In the case of 4 the answer is yes.

Can we use the information that if you find a sub-combination divisible by n, but not containing n then appending n to that combination will generate a new combination that is also divisible by n. Example, append 4 to 1,3 gives 1,3,4.

Would an attack that first found all combinations of digits that added up to n and then worked on combinations of these subsets work? You could only count the mutually exclusive combinations - maybe.
So n=6 has combinations 6 1,5 2,4 & 1,2,3.
6 counts as 1!5! = 120
1,5 counts as 2!4! = 48
2,4 counts as 2!4! = 48
1,2,3 counts as 3!3! = 36

1,5 & 6 counts as 2!3! = 12
2,4 & 6 counts as 2!3! = 12
1,2,3 & 6 counts as 3!2! = 12
1,5 & 2,4 counts as 2!2! = 4 - no it's 32 using pencil and paper! All 16 combinations of the 4 digits not starting 1,5 or 2,4 which have already been taken into account and the remaining 2 digits 3,6 can be arranged in 2! ways.

But these do not add up to the known answer of 440, so I've missed something, such as 3,4,5 (=12) which has no subset divisible by 6 and counts as 3!3! = 36. Well that answers my above question! Then all 9 combinations of 3,4,5,6 that don't start 6 or 3,4,5 count as 18.[/SPOILER]

Slight error in "further musings" #2 above

[SPOILER][COLOR=black][FONT=monospace]for "sub-combination divisible by n" read[/FONT][/COLOR][COLOR=black][FONT=monospace] "combination divisible by n"[/FONT][/COLOR][/SPOILER]

Strange, I didn't get an "Edit" button.