Graph is Bell Curve. Why?

What is the value of positive integer n n such that ( 1000 n n ) \large { 1000 - n \choose n} is maximized?


The answer is 276.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

9 solutions

Thaddeus Abiy
May 8, 2014
1
2
3
4
5
6
def C(n, k):
    if k == 0:return 1
    return (n * C(n - 1, k - 1)) / k

Values = {C(1000-n,n):n for n in range(1,500)}
print Values[max(Values)]

:\ And now If i were to give C solution it would look plain boring- Y u do this python?

Soham Chanda - 7 years, 1 month ago

Log in to reply

C dialects kind of blow up (even when using the "double" data type.

Sean Roberson - 7 years, 1 month ago

what is this....

Max B - 7 years, 1 month ago

Log in to reply

It is python.

Thaddeus Abiy - 7 years, 1 month ago
Simona Vesela
Sep 28, 2014

We have aCb=a!/((a-b)!b!) we set a system of inequalities (a-(n-1)C n-1)<(a-nCn) and (a-nCn)>(a-(n+1)C(n+1)) first gives us(integers) unite(n<=276;n>724) and second 275<n<=723 we see that only 276 satisfies both

Joshua Hannah
May 24, 2014

I love Haskell:

Prelude> let fact n = if (n <= 0) then 1 else n*(fact (n-1)) 

Prelude> (snd.maximum)[(div (fact (1000 - n)) ((fact(1000-2*n))*fact n), n) | n<-[1..500]]
276
C Anshul
Jun 24, 2018

Use stirling approximation and then differentiate. We get n =276.369

Bill Bell
Dec 25, 2014

I used Alex Martelli's gmpy2 module on the grounds that he is a world-class programmer and would release only excellent code. Although the numbers are enormous this code runs very quickly.

Kenny Lau
Sep 5, 2014

java code:

public class brilliant201409061323{
    public static void main(String args[]){
        double max = 0;
        int n = 0;
        for(int i=0;i<=1000;i++){
            double c = C(1000-i,i);
            if(c>max){
                max = c;
                n = i;
            }
        }
        System.out.println(n+":"+max);
    }
    private static double C(int n,int r){
        double res = 1;
        for(double i=1;i<=r;i++){
            res *= n-i+1;
            res /= i;
        }
        return res;
    }
}
Rufus Lawrence
Aug 10, 2014

def factorial(n): m = 1 for i in range(1,n+1): m *= i return m

def combin(x,y): return(factorial(x)/(factorial(y)*factorial(x-y)))

coeffs = []

for n in range(1,1000): coeffs.append(combin(1000-n,n))

print(coeffs.index(max(coeffs)))

Bernardo Sulzbach
Jun 27, 2014

Sage code

print(max([(binomial(1000 - n, n), n) for n in xrange(1, 500)])[1])

returns

276
Sean Roberson
May 12, 2014

In Python, write:

def factorial(n):
product = 1
for i in range(n):
    product = product * (i+1)
return product

def combination(n,k):
combo = factorial(n)/(factorial(k) * factorial (n-k))
return combo

def binom_max(n):
binom_maximum = 0
k_max = 0
for j in range(n+1):
    comb_val = combination(n-j, j)
    if comb_val >= binom_maximum:
        binom_maximum = comb_val
        k_max = j
return k_max, binom_maximum

The maximum is achieved when the counter is at j = 276 j=276 .

By the way, if you do the whole thing in log-space (i.e. using logarithms instead of numbers), nothing blows up, you get to precompute all the factorials before (in linear time) and solving the whole problem takes just O(n) time.

Marcin Skwark - 7 years, 1 month ago

Log in to reply

Can you define this idea further? Give a little sample code maybe?

I am not a CS and I am interested about this.

Bernardo Sulzbach - 6 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...