Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two integers [not necessarily distinct] are chosen from the set {1,2,3,...,n}. What is the probability that their sum is <=k?

My approach is as follows. Let a and b be two integers. First we calculate the probability of the sum of a+b being equal to x [1<=x<=n]. WLOG let a be chosen first. For b= x-a to be positive, we must have 1<=a < x. This gives (x-1) possible values for a out of total n possible values. Probability of valid selection of a= (x-1)/n. For each valid selection of a, we have one and only one possible value of b. Only 1 value of b is then valid out of total n possible values. Thus probability of valid selection of b= 1/n. Thus probability of (a+b= x) = (x-1)/n(n-1).

Now probability of (a+b<=k) = Probability of (a+b= 2) + probability of (a+b= 3) + ... + probability of (a+b= k) = {1+2+3+4+5+...+(k-1)}n(n-1) = k(k-1)/n(n-1).

Can anybody please check if my approach is correct here?

share|improve this question
    
Is the answer reasonable? It says the probability the sum is $\le n$ is $1$. That is not so. –  André Nicolas Jun 3 '13 at 17:19
    
Can't the sum be more than $n$? –  Thomas Andrews Jun 3 '13 at 17:20
    
@Welcome: Welcome to MSE! It really helps readability to format questions using Mathjax (see FAQ). Regards –  Amzoti Jun 3 '13 at 17:24
add comment

3 Answers

Let's change the problem a little. Instead of drawing from the numbers $1$ to $n$, we draw from the numbers $0$ to $n-1$. We want to find the probability that the sum is $\le j$, where $j=k-2$. After we solve that problem, it will be easy to write down the answer of the original problem.

Draw the square grid of all points (dots) with coordinates $(x,y)$, where $x$ and $y$ are integers, and $0\le x\le n-1$, $0\le y\le n-1$.

Now imagine drawing the line $x+y=j$. Note that if $j=n-1$, we are drawing the main diagonal of the grid. If $j\gt n-1$, we have drawn a line above the main diagonal. If $j\lt n-1$, we have drawn a line below the main diagonal.

Deal first with the case $j\le n-1$. The points of the grid that are on or below the line $x+y=j$ form a triangular grid, which has a total of $1+2+\cdots +(j+1)$ points. This sum is $\dfrac{(j+1)(j+2)}{2}$. The grid has $n^2$ points, and therefore the probability that the sum is $\le j$ is $$\frac{(j+1)(j+2)}{2n^2}.$$

Now we deal with $m\lt j\le 2n-2$. In this case, the probability that the sum is $\le j$ is $1$ minus the probability that the sum is $\ge j+1$. By symmetry, this is the same as the probability that the sum is $\le (2n-2)-(j+1)$. Thus, by our previous work, the required probability is $$1-\frac{(2n-j-2)(2n-j-1)}{2n^2}.$$

Remark: Your basic approach was fine, at least up to the "middle." After the middle, think dice. There is symmetry between sum $\le k$ and sum $\ge 14-k$.

My switch to somewhat more geometric language is inessential, and was made mainly for rhetorical purposes.

share|improve this answer
add comment

Notice if $k\le 1$ the probability is $0$, and if $k\ge 2n$ the probability is $1$, so let's assume $2\le k\le 2n-1$. For some $i$ satisfying $2\le i\le 2n-1$, how many ways can we choose $2$ numbers to add up to $i$? If $i\le n+1$, there are $i-1$ ways. If $i\ge n+2$, there are $2n-i+1$ ways.

Now, suppose $k\le n+1$, so by summing we find:

$$\sum_{i=2}^{k}i-1=\frac{k(k-1)}{2}$$

If $k\ge n+2$, if we sum from $i=2$ to $i=n+1$ we get $\frac{(n+1)n}{2}$, and then from $n+1$ to $k$ we get:

$$\sum_{i=n+2}^k2n-i+1=\frac{1}{2}(3n-k)(k-n-1)$$

Adding the amount for $i\le n+1$ we get:

$$2kn-\frac{k^2}{2}+\frac{k}{2}-n^2-n$$

Since there are $n^2$ choices altogether, we arrive at the following probabilities:

$$\begin{cases}\frac{k(k-1)}{2n^2}&1\le k\le n+1\\\frac{4kn-k^2+k-2n^2-2n}{2n^2}&n+2\le k\le 2n\end{cases}$$

share|improve this answer
add comment

Let $s=a+b$

I will find $P(s=k)$.

Clearly for $k<0$ and for $k>2n$ then $P(s=k)=0$

The other cases are as follows.

Let $x$ be the total no. of pairs $a,b$

Case 1:$k\le n$

Total no. of ways of selecting $a,b$ as an ordered pair such that $s=k$ is $(k-1)$.

Now as according to the question there is no ordering so to remove this ordering we have to divide this by $2$ if $k$ is odd(Reason:as there are no case where $a=b$ so the no. of ways in which $a,b$ can occur as ordered tuple is twice their own number).If $k$ is even then we have to subtract $1$ from it then divide it by $2$ and then again add $1$ to it.

SO we have ,

$P(s=k)=\frac{k-1}{2x},\text{if k is odd}$

$P(s=k)=\frac{k}{2x},\text{if k is even}$

Case 2:$k>n$

Again we will take ordered $(a,b)$ at first.

In this case it is better to visualise the case using dots and bars.

There are $k$ dots.In between these $k$ dots we will put a bar and call the number of dots on left side of the bar as $a$ and the dots on the right side of the bar as $b$.

But there is a restriction that $a,b\le n$

We can easily handle this restriction by allowing to put the bar $k-n$ th dot and $n+1$ th dot.

So the number of places to put the dot equals $(n+1-k+n)=2n-k+1$

Now again if $2n-k+2$ is odd or $k$ is odd then we have to divide this by $2$ else we have to subtract $1$ and divide it by $2$ and then add $1$.

So we have,

$P(s=k)=\frac{2n-k+1}{2x},\text{if k is odd}$

$P(s=k)=\frac{2n-k+2}{2x},\text{if k is even}$

Now we will find $x$.

There are $n$ choices for each $a$ and $b$. So the no. of ordered pairs $(a,b)$ equals $n^2$

Now according to $n$ is even or odd we must have,

$x=n^2/2 \text{if n is even}$

$x=(n^2+1)/2 \text {if n is odd}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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