0
$\begingroup$

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

$\endgroup$

closed as off-topic by Alconja, greenturtle3141, Glorfindel, hexomino, Omega Krypton Jul 3 at 10:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Alconja, greenturtle3141, Glorfindel, hexomino, Omega Krypton
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 at 12:17
  • $\begingroup$ Computer searches are fine, I've tried by hand and it's painful! $\endgroup$ – JonMark Perry Jul 2 at 12:22
5
$\begingroup$

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.

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

$\endgroup$
  • $\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 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 at 14:36
3
$\begingroup$

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

$\endgroup$
  • $\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 at 15:20
0
$\begingroup$

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)){
data$combin[i]<-nchoosek(data$n[i],data$k[i])
}
data$check<-2^50
data$diff<-data$combin-data$check

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

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