Probability that the sum of three integer numbers (from 1 to 100) is more than 100

Solution 1:

We have to count the number of three elements subsets of $\{1,\ldots,100\}$ having sum greater than $100$, or $\leq 100$. For first, we have that the number of lattice points $(x,y,z)\in[1,100]^3$ such that $(x+y+z)\leq 100$ is given by: $$\sum_{x=1}^{98}\left|\{(y,z)\in[1,100]^2:y+z\leq 100-x\}\right|=\sum_{x=1}^{98}\binom{100-x}{2}=\binom{100}{3}.$$ Obviously, not every lattice point gives a valid subset. Among the previously counted lattice points, there are $33$ points of the type $(x,x,x)$ and $3\cdot 2417=7251$ points of the type $(u,u,v),(u,v,u)$ or $(v,u,u)$ with $u\neq v$. Hence the number of three elements subsets of $\{1,\ldots,100\}$ with sum $\leq 100$ is given by: $$\frac{1}{6}\left(\binom{100}{3}-7251-33\right) = 25736 $$ so the wanted probability is: $$ 1-\frac{25736}{\binom{100}{3}} $$ that is between $\frac{280}{333}$ and $\frac{37}{44}$.

Solution 2:

It is often interesting to compare different methods, and usually a good idea to check theoretical work using computational methods.

In this instance, it is a simple one-liner to evaluate every possible way of choosing 3 different balls (without replacement) from 100 balls (numbered from 1 to 100), sum all the combinations, and compute the exact probability.

Here is Mathematica code to do this ... just a one-liner:

Z = Map[Total, Permutations[Range[100],{3}]];  Count[Z, x_ /; x>100]/Length[Z]

... which returns the exact solution as:

$$\text{P(sum > 100)} = \frac{33991}{40425}$$

... which is $\approx 0.840841$. It only takes a fraction of a second to evaluate.

By contrast:

The theoretical derivation posted by Jack D'Aurizio above obtained the result:

$$\text{P(sum > 100)} = 1-\frac{26561}{\binom{100}{3}} \approx 0.835739$$

The latter (accepted answer) appears to be in error. [ Update: Now resolved :) ]

Solution 3:

And in python:

import itertools
z=map(sum, itertools.permutations(range(1,101),3))
len(filter(lambda x: x>100, z))*1.0/len(z)

Yields:

0.8408410636982065

Solution 4:

Since I see other solutions relying on a bit of programing, I'll do it in SQL (which I often find very suited for combinatorics problems).

  WITH
     lvls AS (
        SELECT LEVEL AS lvl
        FROM dual
        CONNECT BY LEVEL <= 100
     ),
     combinations AS (
        SELECT
           l1.lvl AS nr_1,
           l2.lvl AS nr_2,
           l3.lvl AS nr_3,
           l1.lvl + l2.lvl + l3.lvl AS total,
           CASE
              WHEN l1.lvl + l2.lvl + l3.lvl > 100
              THEN 1
              ELSE 0
           END AS is_bigger
        FROM lvls l1
        JOIN lvls l2 ON (l1.lvl <> l2.lvl)
        JOIN lvls l3 ON (l1.lvl <> l3.lvl AND l2.lvl <> l3.lvl)
     )
  SELECT
     SUM(is_bigger) AS nr_bigger,
     COUNT(*) AS nr_total,
     SUM(is_bigger) / COUNT(*) AS chance
  FROM combinations;

Which yields (unsuprisingly) $$\frac{815784}{970200} \approx 0,840841 $$