You randomly select two distinct integers between 1 and 100. What is the probability that the larger number is exactly twice the smaller number?

Question

I recently took a HackerRank test for a Data Science position and got this question wrong. I came to 1/200. Here's how:

There are 50 combinations that will make this true. (i.e. {1,2},{2,4},{3,6}...{50,100}). Probability of a specific number being chosen is 1/100. Probability that the specific set will be chosen is (1/100 * 1/100).

Since there are 50 sets,

P=50*(1/100)*(1/100)=1/200

I'm of course assuming that 1 and 100 are included. But this was the wrong answer. Can anyone help me understand my mistake?

Answer 1

Your first mistake is that there are 50 outcomes, there's actually 100 (Edit: See comment below for clarification). This is because getting (1,2) and (2,1) are the results of two seperate outcomes, but in each case the larger number is exactly twice the smaller number.

So the total possible ways of getting this is actually given by the set:

{ (1,2), (2,1), (2,4), (4,2), ..., (50,100), (100,50) }

Which is a list of 100 possible outcomes.

The total number of possible outcomes is $100 \times 99$

Since there are 100 possible numbers to choose the first time, and then 99 for the second since they must be distinct.

Hence the answer is given by:

$P = \frac{100}{100 \times 99} = \frac{1}{99}$

Using the same argument, it is straightforward to prove that the probability for the more general case of choosing numbers from $1, 2, ..., n$ where $n$ is some positive even number is given by:

$P = \frac{1}{n-1}$

Answer 2

The "Hacker" in the name of the test suggests we try to find a computing-oriented solution.

Let's therefore start with a program for brute-force enumeration of (a) the "favorable" cases where one integer is twice the other and (b) all possible cases. The answer would then be their ratio. I have coded a general solution. Its input is a positive integer n and its output is the probability.

n=100
all=favorable=0
for i=1 to n
    for j=1 to n
        if (i != j) all=all+1                  {1}
        if (j == 2*i) favorable = favorable+1  {2}
        if (i == 2*j) favorable = favorable+1  {3}
return(favorable / all)

(The proof of correctness relies on the fact that $i \ne 2i$ for any positive number $i$.)

This program requires $3$ tests and up to $3$ increments for each iteration of the inner loop. Therefore it needs between $3n$ and $6n$ calculations each time the inner loop is performed, or $3n^2$ to $6n^2$ overall. That's $O(n^2)$ performance: OK for small $n$ like $n=100$, but terrible once $n$ exceeds $10000$ or so.

As a hacker, one of the first things you will want to do is eliminate the quadratic performance by simplifying the inner loop (if possible). To this end, systematically go through the lines in the inner loop (as numbered) and note the following:

1. Line 1 is executed all but once for each value of i and therefore all is incremented $n-1$ times. Consequently, for the computation of all, the loop over j can be replaced by incrementing all by n-1.

2. Line 2 is executed exactly once when $2i \le n$ and otherwise not at all. Therefore it can be replaced by incrementing all by $1$ whenever $2i \le n$.

3. Line 3 is executed once provided i is even.

Here is the transformed program.

n=100
all=favorable=0
for i=1 to n
    all = all + (n-1)                      {1'}
    if (2*i <= n) favorable = favorable+1  {2'}
    if (even(i)) favorable = favorable+1   {3'}
return(favorable / all)

Can we go further and eliminate its loop?

1. Line 1' is executed $n$ times. Therefore all is incremented by n*(n-1).

2. Line 2' is executed only when $2i \le n$. One way to count this is $\lfloor n/2\rfloor$ (the greatest integer less than or equal to $n/2$).

3. Line 3' is executed only for even values of $i$. Again, that happens $\lfloor n/2 \rfloor$ times.

The second transformation of the program is:

n=100
all=favorable=0                     {0}
all = all + n * (n-1)               {1''}
favorable = favorable + floor(n/2)  {2''}
favorable = favorable + floor(n/2)  {3''}
return(favorable / all)

This is already a tremendous accomplishment: a $O(n^2)$ algorithm has been reduced to a $O(1)$ algorithm (which can be considered a "closed formula" for the answer).

Finally, there are some simple algebraic transformations we can make by rolling the initialization (line 0) into the first use of each variable and combining lines 2'' and 3'':

n=100
all = n * (n-1) 
favorable = 2 * floor(n/2) 
return(favorable / all)

At this point a human could execute the program. Let's do it with $n=100$:

all = 100 * (100-1) = 100*99
favorable = 2 * floor(100/2) = 2*50 = 100
favorable/all = 100 / (100*99) = 1/99

The output therefore is $1/99$.

To summarize, a brute-force algorithm can be transformed systematically using simple program rewriting rules into a sleek, elegant, $O(1)$ program.

Answer 3

First of all, you are sampling without replacement. Thus, there are 100*99 different outcomes, e.g. (1,1) is not a valid outcome.

Secondly, order does not matter. The larger must be exactly twice, not the second. Thus, remove symmetric pairs.

Thus, 50 out of (100)*99/2are positive, or 1/99