$52$ cards reciprocal sum probability

The easiest thing is enumerate all the possibilities (few seconds of CPU).

There are 1431 ways to extract distinct cards such that the sum of their reciprocals is 1.

So the probability is $$ 1431 / {52\choose 10} \approx 9.0455\cdot 10^{-8} $$

Among those 1431, the first and last lexicographically are $$ \{2, 4, 16, 26, 30, 36, 39, 45, 48, 52\} $$ and $$ \{5, 6, 8, 9, 10, 12, 15, 18, 20, 24\} $$

My algorithm is very naive. The running time of the resulting program is less than 2 seconds.

Any good set (sum of reciprocals equal to $1$), can be divided in two subsets of $5$ elements, one with sum $s\le\frac{1}{2}$ and the other with sum $\frac{1}{2}\le s<1$.

There are only ${52\choose 5}=2598960$ quintets, so generating them is not a problem. In particular, I stored the $422730$ whose sum is between $\frac{1}{2}$ and $1$.

Then I generate again the quintets, looking for those with sum $s\le\frac{1}{2}$ and I checked if among those stored there were some with sum $1-s$ and with a non-overlapping set of numbers.

I stored on file the matching quintets ($180959$) and then I used another software to eliminate the duplicates (duplicates were generated because there were many cases of $\frac{1}{2}+\frac{1}{2}$ and I was too lazy to implement a filter inside the program, since I could eliminate the duplicates later with a couple of Mathematica instructions.

For what concernes the implementation, I used C++. I'm not a C++ programmer, I'm too old for that OOP, and normally I use C, but the STL contains so many data structures already implemented...)

So I used a multimap (a map which can contain multiple elements with the same key and can be searched efficiently for a specific key), where the key was a representation of the sum of 5 reciprocals and the associated data was a representation of the 5 cards.

In practice I used a 64 bit integer for the key and a 64 bit integer for the data.

Given five numbers $a$, $b$, $c$, $d$, $e$, below 52, it is easy to see that their product fits in a signed 32 bit integer, because $52\cdot51\cdot50\cdot49\cdot48=311875200 < 2^{31}$. So, if I reduce the fraction $$ \frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d}+\frac{1}{e}=\frac{p}{q} $$ where $(p,q)=1$, then I know that the value $p\cdot2^{32}+q$ will fit nicely in a 64 bit integer. This will be my key. When in the second part of the program I'm looking for matching quintes I will set my key to $\frac{q-p}{p}$, to search among those already stored one that added to the current one gives sum $1$.

The representation of the five numbers $a$, $b$, $c$, $d$, $e$ can be managed in various ways, but I decided to use an unsigned 64 bit number and set to $1$ the $a$-th, $b$-th, ..., and $e$-th bit. In this way it is easy to check if two quintuples have numbers in common since it is sufficient to check if the bit-wise AND is zero or not.

I think it's all.

Addendum. The algorithm above is due to my bad sight. When I computed the value ${51\choose 10}$ (the card '$1$' is useless) I did not realize it was just such a little number. I misread the exponent. Indeed it is only about $1.28\cdot 10^{10}$. With modern computers it is just a breeze. Indeed I hastily wrote a dumb C program that in about 36 seconds printed out the 1431 solutions.

Here is a short version (not to be taken as an example of good programming!)

#include<stdio.h>
int main()
{
  long double Inv[53],s0,s1,s2,s3,s4,s5,s6,s7,s8,s9,Err=6.0E-11;
  long double Min=1-Err, Max=1+Err;
  for (int i=1; i<53; i++) Inv[i]=1/(long double)i;
#define FOR(p,c) for(int i##c=52; i##c>i##p && (s##c=(s##p+Inv[i##c]))<Max;i##c--)
  int i0, cnt=0;
  for (i0=2, s0=0.5; i0<=52; s0=Inv[++i0])
  FOR(0,1) FOR(1,2) FOR(2,3) FOR(3,4)
  FOR(4,5) FOR(5,6) FOR(6,7) FOR(7,8) FOR(8,9)
  if (s9>Min) printf("%4d %.15Lf %d %d %d %d %d %d %d " 
  "%d %d %d\n",++cnt,s9, i0,i1,i2,i3,i4,i5,i6,i7,i8,i9);
  return 0; 
}

The a=6 case can be eliminated by pencil and paper.
Consider that 1/1 = 1, 1/2 = 7, 1/3 = 9, and 1/4 = 10, all mod 13. The only multiple of 13 we can get out of sums of these numbers is 7+9+10=26, which shows that 1/26+1/39+1/52=1/12 is feasible, but 1/13 must not appear in the sum.
Also 1/1 = 1, 1/2 = 6, 1/3 = 4, 1/4 = 3, all mod 11. The only multiple of 11 in this case is 1+6+4=11, so 1/44 is excluded, and if 1/11 is in the sum, then 1/22 and 1/33 must also be.
These two considerations alone mean that a=6 is impossible:

sum(1.0/[6,7,8,9,10,11,12,13,14,15]) =    1.034896
sum(1.0/[6,7,8,9,10,11,12,14,22,33]) =   0.9670634
sum(1.0/[6,7,8,9,10,12,14,15,16,17]) =   0.9883869

Similar considerations exclude a total of 20 cards. With that, along with the exclusion of card 1 by its magnitude, the deck is down to 31 cards and there are only 4 possibilities for the lowest card. Throw in an early-out test at about the seventh card and compiled code gets down to about 30 ms. The interpreted code should go through in tolerable time. Obviously not an improvement on brute force because that is quick enough and less error-prone.

Tags:

Probability

Recent Posts