mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   An Unurned Sum (https://www.mersenneforum.org/showthread.php?t=11805)

tmorrow 2009-05-12 12:22

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]

retina 2009-05-12 12:32

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

tmorrow 2009-05-12 12:58

[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]

davar55 2009-07-02 19:47

Isn't the limit Exact?

davar55 2009-08-27 19:40

[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.

davar55 2010-12-19 22:50

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?

pjaj 2011-01-15 14:25

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]

davar55 2011-01-15 18:13

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

nuggetprime 2011-01-15 19:46

[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.

pjaj 2011-01-18 23:32

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]

davar55 2011-01-21 16:55

Nice preliminary analytic analysis.

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


All times are UTC. The time now is 05:35.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.