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

I have an urn with $100$ balls. Each ball has a number in it, from $1$ to $100$. I take three balls from the urn without putting the balls again in the urn. I sum the three numbers obtained. What's the probability that the sum of the three numbers is more than $100$?

How to explain the procedure to calculate this probability?

• Wouldn't it be $\frac{1}{6}\sum_{S=101}^{297} {S+2 \choose 2}$ divided by $100\choose 3$? – Shash Oct 1 '14 at 12:59
• Sorry, this is wrong as it includes repeated numbers, also there is undercounting. – Shash Oct 1 '14 at 13:04

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

• I tried by simulation too. I sampled 3 elements from an array of integers from 1 to 100 with no replacement, and I set to TRUE if the sum of the elements was more tha 100. I repeated the samplong 10000 times. then set the probability as P = number_of_trues/10000. I repeated the procedure 1000 times and I calculated the mean value obtaining 0.8406877. The true result (your) is 0.8408411. So simulation differs for 0.02% from the true probability. I will present both approach trying to explain the two different approaches. – Fabio Zottele Oct 1 '14 at 16:14
• Just a small typo: The summation index of the second sum needs to be $x$. – Calculon Oct 1 '14 at 17:50
• @Calculon: thanks, fixed. – Jack D'Aurizio Oct 1 '14 at 17:56

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 :) ]

• $\frac{33991}{40425}$ is the answer I got from computing $$\prod_{k=1}^{100}(1-xy^k)$$ and summing the coefficients of $x^3y^k$ for $k\le100$, subtracting from $\binom{100}{3}$, and dividing by $\binom{100}{3}$. – robjohn Oct 1 '14 at 15:07
• @robjohn Nice to have confirmation by another method - thanks :) – wolfies Oct 1 '14 at 15:10
• @wolfies: I just miscalculated the numerator of the fraction, my bound agrees with yours. – Jack D'Aurizio Oct 1 '14 at 15:38
• I was writing my own code in R for the simulation approach. And I posted my result by Jack's answer. You and I got the same result, so thankyou I will present both approaches – Fabio Zottele Oct 1 '14 at 16:12
• @FabioZottele The method used here is not simulation. It is exact. – wolfies Oct 1 '14 at 16:19

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


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

Here's a C# solution. My original (wrong) solution divided by 1000000. It was wrong because it counted cases with duplicate numbers. This version below divides by the correct number.

static void Main(string[] args)
{
int count = 100 * 100 * 100;
int hits = 0;

for (int i = 1; i <= 100; i++)
{
for (int j = 1; j <= 100; j++)
{
for (int k = 1; k <= 100; k++)
{
if (i == j || i == k || j == k)
count--;

else if (i + j + k > 100)
hits++;
}
}
}

Console.WriteLine(hits);
Console.WriteLine(count);

double percent = (double)hits / (double)count;
Console.WriteLine(percent);

}

• Since you are excluding the triples $(i,j,k)$ with two or more equal elements, you have to divide by something smaller than $100^3$ in the last step. – Jack D'Aurizio Oct 1 '14 at 16:33
• @JackD'Aurizio, I get it now. Thanks. That was really bugging me. – user2023861 Oct 1 '14 at 16:39

I post here the simulation code written in R:

rm(list = ls())
space = seq(1:100)
replication = 10000
prob=c()
for (j in 1:1000) {
result = c()
for (i in 1:replication) {
draw = sample(space,3, replace=FALSE)
s = sum(draw)
outcome = FALSE
if (s > 100) {
outcome=TRUE
}
result = c(result, outcome)
}
prob = c(prob,sum(result)/replication)
}
P = mean(prob)


We know there are 100_C_3 ways to draw 3 numbers from 1 to 100 without replacement.

Let's look at counting the number of ways to draw three numbers that add up to 100 or less.

First, let's solve for drawing two numbers:

L = The limit

F = the first number

What is the number of ways to draw a second number S given the limit L and the first number F?

We know that F + 1 <= S <= L - F. If F + 1 > L - F, then there are 0 ways. If F + 1 <= L - F, then there are (L - F) - (F + 1) + 1 numbers in the range (F + 1) to (L - F). That reduces to L - 2F.

So:

W_2(L,F) = 0, If 2F+1 > L

W_2(L,F) = L - 2F, If 2F+1 <= L

We can compute W_2(L), for all valid F, by summing W_2(L,F) for F ranging from 1 to (L-1)/2:

...skipping the algebra...

If L is odd, W_2(L) = (L^2 - 2L + 1) / 4

If L is even, W_2(L) = (L^2 - 2L) / 4

Now, we can use this result in calculating the three-number problem:

If we have a first number F, then our second number, S, and third number, T, must satisfy: F < S < T F + S + T <= L

Assuming we have chosen an F small enough that there are S and T that can satisfy F + S + T <= L, then

W_3(L,F) = W_2(L - 3F)

W_3(L,F) = ((L-3F)^2-2*(L-3F)+1)/4, if 3F-L is odd

W_3(L,F) = ((L-3F)^2-2*(L-3F))/4, if 3F-L is even

Our upper limit for F is F + (F + 1) + (F + 2) <= L or F <= (L - 3) / 3

Finally, we can compute W_3(L) for all valid F, by summing W_3(L,F) for F ranging from 1 to I = Int((L-3)/3), where INT() rounds down to the nearest integer.

...skipping even more algebra...

If (L-3)/3 is even, W_3(L) = (6I^3-3(2L-5)I^2+2*(L^2-5L+5)I)/8

If (L-3)/3 is odd and L is even, W_3(L) = (6I^3-3(2L-5)I^2+2*(L^2-5L+5)I+1)/8

If (L-3)/3 is odd and L is odd, W_3(L) = (6I^3-3(2L-5)I^2+2*(L^2-5L+5)I-1)/8

For very large numbers, you can just use the first formula, since the adjustments only add or subtract 1/8.