Mr. Magico is a greater believer in this number:


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

  • 4
    $\begingroup$ 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? $\endgroup$ – Gareth McCaughan Jul 2 '19 at 12:17
  • $\begingroup$ Computer searches are fine, I've tried by hand and it's painful! $\endgroup$ – JMP Jul 2 '19 at 12:22
  • $\begingroup$ Why is it "cIosed"? $\endgroup$ – Scratch---Cat Sep 23 '19 at 9:57


16 cards from a deck of 67

gets to within about


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.

[EDITED to add:]

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.

  • $\begingroup$ Checked all solutions for n<=500 in R, and your (290,8) is optimal (and naturally (290,282) is as well). $\endgroup$ – Thomas Markov Jul 2 '19 at 14:20
  • $\begingroup$ 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). $\endgroup$ – 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  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}$.

  • $\begingroup$ (of course, I should probably convert real roots to integer solutions in a manner more rigorous than rounding, but puzzles are more about method ;)) $\endgroup$ – 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".






for(i in 1:length(data$n)){


Not the answer you're looking for? Browse other questions tagged or ask your own question.