0
$\begingroup$

I was looking at the following question, which asked about the probability that you pick two numbers between $1$ and $10$ without replacement such that they differ by two or more. The accepted answer says

Pick two numbers from $1,2,\ldots,9$ and increase the largest number by one. The resulting pair of numbers will always differ by at least 2 and be numbers in the range $1,\ldots,10$.

This gives a bijection between the problem of choosing two numbers of the 9 and the problem of choosing two numbers of the 10 such that they differ by at least 2. It is important that it is a bijection, i.e. two (or more) pairs of the 9 can't map to the same pair of the 10 that differ by at least two and every pair of the 10 that differ by at least 2 gets mapped to by some pair of the 9. In this case it is trivial to see that $(a,b) \mapsto (a,b+1)$ is indeed a bijection.

but I fail to see how there being a bijection between the two helps you reach the answer of

$$\frac{\binom{9}{2}}{\binom{10}{2}}$$

$\endgroup$
  • 2
    $\begingroup$ The reason why counting the answers to the other problem gives the answers to the original problem is because for finite sets $A$ and $B$, if there exists a bijection between them then there must be the same number of elements in each. Indeed, a set "having $n$ elements" is defined as the set having a bijection with $\{1,2,\dots,n\}$ in the first place, and if both $A$ and $B$ have bijections to $\{1,2,\dots,n\}$ then they must have bijections with each other as well. $\endgroup$ – JMoravitz Oct 12 '17 at 3:44
  • 2
    $\begingroup$ That being said, your question seems to be about counting the number of ways you can choose, however the linked question and cited answer are about calculating the probability of such a selection occurring. $\endgroup$ – JMoravitz Oct 12 '17 at 3:46
  • $\begingroup$ @bof ah my mistake in transcribing the problem... $\endgroup$ – m0meni Oct 12 '17 at 3:47
  • 2
    $\begingroup$ As for counting in the first place, assuming that order doesn't matter and you are wanting to count the number of ways of selecting two elements from $\{1,2,\dots,10\}$ such that they differ by at least two, I would note that $\binom{10}{2}$ is a good start and counts the number of ways of selecting two distinct elements without regard to how far spread they are but some of the selections are bad, namely those who have consecutive numbers. $9$ of those selections were bad, giving a count of $\binom{10}{2}-9$. This seems to vary from the linked question where order apparently matters. $\endgroup$ – JMoravitz Oct 12 '17 at 3:50
  • $\begingroup$ I think the easiest way to solve the problem is to note that there are $\binom{10}2=45$ ways to pick two numbers, and $9$ ways to pick two consecutive numbers (1&2, 2&3, . . ., 9&10), so there are $45-9=36$ ways to pick two nonconsecutive numbers. $\endgroup$ – bof Oct 12 '17 at 4:06
0
$\begingroup$

This uses the property that:

If $f:A\to B$ is a bijection, then $\lvert A \rvert = \lvert B \rvert$. That is, the cardinality of both sets is same.

Hence, when it is difficult to determine $\lvert A \rvert$ directly, we use a bijection to get $B$ such that we can easily evaluate $\lvert B \rvert$ .

Hope this helps you.

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