![]() |
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. |
| All times are UTC. The time now is 05:35. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.