# Approximate this big number using a binomial [closed]

Mr. Magico is a greater believer in this number:

$$2^{50}=1,125,899,906,842,624‬$$

He also like to play cards, although he isn't fussy about the size of his deck, and nor does he care how many cards he pulls.

He wishes to find $$n,k$$ such that:

$$\binom{n}{k}\approx 2^{50}$$

and wants $$n$$ as small as possible, but also a very small error margin. $$2^{50}$$ cards gives $$100\%$$ accuracy, but is a very large pack of cards, probably too large for even Mr. Magico to carry around in his pocket!

With this in mind, we shall impose an upper limit of $$n\le500$$, although $$n\le100$$ would be better for Mr. Magico's posture!

What is Mr. Magico's ideal pack of cards, and how many cards should he pull?

For a start $$\dbinom{78}{14}=1,023,729,916,348,425$$, an error of $$\sim0.909$$.

• Clearly he should use a pack of $2^{50}$ cards and pull exactly one of them. More seriously, would you like to be a bit more precise about how you want the tradeoff between accuracy and feasibility to be made? And how do you feel about computer searches? – Gareth McCaughan Jul 2 '19 at 12:17
• Computer searches are fine, I've tried by hand and it's painful! – JMP Jul 2 '19 at 12:22
• Why is it "cIosed"? – Scratch---Cat Sep 23 '19 at 9:57

Choosing

16 cards from a deck of 67

gets to within about

0.2%

of the desired answer. I think this is best possible with <= 100 cards.

Found with the help of a computer, but purely as an aid to calculation. My approach was to

follow the "boundary" near to the number wanted, increasing or decreasing $$k$$ and then adjusting $$n$$ to get as near as possible. I had to try about 30 values.

Out of curiosity, I also ran a more automated search for the larger bound of n=500 mentioned in the OP. For this,

choosing 8 cards from 290 yields an error of about 0.03%.

The automated search also confirmed that the answer above is best for a maximum of 100 cards.

• Checked all solutions for n<=500 in R, and your (290,8) is optimal (and naturally (290,282) is as well). – Thomas Markov Jul 2 '19 at 14:20
• Checking all smaller values of k shows that the next best ones are (2671,5), (12824,4), (189041,3), (47453133,2), and finally ($2^{50}$,1). – AxiomaticSystem Jul 2 '19 at 14:36

Generalizing my comment on Gareth's solution, we can arrange Pascal's triangle as a right triangular array and ignore the right half ($$n < 2k$$) to obtain something like this:

1
1
1  2
1  3
1  4  6
...


We then, for any $$N$$,

notice that all columns are strictly increasing, with minimal values equal to the central binomial coefficients. This immediately produces an upper bound on $$k$$: the greatest value $$m$$ such that $$\binom{2m}{m} \leq N$$. We can then iterate down the remaining values of $$k$$, finding the values $$n$$ such that $$\binom{n}{k}$$ is closest to $$N$$ - these $$n$$ will also be increasing - and checking each one's relative error. This Python code does this fairly well, yielding the successive approximations $$\binom{53}{26}, \binom{54}{23}, \binom{67}{16}, \binom{290}{8}, \binom{12823}{4}, \binom{189040}{3}, \binom{47453133}{2}, \binom{2^{50}}{1}$$.

• (of course, I should probably convert real roots to integer solutions in a manner more rigorous than rounding, but puzzles are more about method ;)) – AxiomaticSystem Jul 2 '19 at 15:20

Gareth has found the optimal solutions, but here is an R script if anyone wants to mess around with the upper bounds for n, just change the value of the variable"UpperBound".

require(pracma)

UpperBound<-500

n<-rep(1:UpperBound,each=UpperBound)
k<-rep(1:UpperBound,times=UpperBound)

data<-as.data.frame(cbind(n,k))
colnames(data)<-c("n","k")

data<-data[data$$k<=data$$n,]

for(i in 1:length(data$$n)){ datacombin[i]<-nchoosek(datan[i],datak[i]) } data$$check<-2^50
data$$diff<-data$$combin-data\$check

data$$diff<-abs(data$$diff)
data[data$$diff==min(data$$diff),]