17
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fabio Zottele Oct 1 '14 at 16:14
  • $\begingroup$ Just a small typo: The summation index of the second sum needs to be $x$. $\endgroup$ – Calculon Oct 1 '14 at 17:50
  • $\begingroup$ @Calculon: thanks, fixed. $\endgroup$ – Jack D'Aurizio Oct 1 '14 at 17:56
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $\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}$. $\endgroup$ – robjohn Oct 1 '14 at 15:07
  • $\begingroup$ @robjohn Nice to have confirmation by another method - thanks :) $\endgroup$ – wolfies Oct 1 '14 at 15:10
  • $\begingroup$ @wolfies: I just miscalculated the numerator of the fraction, my bound agrees with yours. $\endgroup$ – Jack D'Aurizio Oct 1 '14 at 15:38
  • $\begingroup$ 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 $\endgroup$ – Fabio Zottele Oct 1 '14 at 16:12
  • 4
    $\begingroup$ @FabioZottele The method used here is not simulation. It is exact. $\endgroup$ – wolfies Oct 1 '14 at 16:19
2
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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);

    Console.ReadLine();
}
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Oct 1 '14 at 16:33
  • 1
    $\begingroup$ @JackD'Aurizio, I get it now. Thanks. That was really bugging me. $\endgroup$ – user2023861 Oct 1 '14 at 16:39
0
$\begingroup$

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)
$\endgroup$
0
$\begingroup$

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.

To answer your question then,

When L = 100,

Int((L - 3) / 3) = 32

W_3(100) = 25,736

100_C_3 = 161,700

so your probability of drawing 3 balls whose sum exceeds 100 is:

(161,700 - 25,736) / 161,700 = 0.840841

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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