3
$\begingroup$

Scenario:

Lets say you have 100 trillion unique locks and their corresponding 100 trillion unique keys. You scramble them up, and then place all the locks and all the keys in two separate boxes.

You want to find a compatible key/lock combination.

Options:

You can choose to try one of three search methods to find a compatible combination:

  1. You randomly select one lock. Repeatedly, you randomly select a key, try it with the lock, and return the key to its box.

  2. You randomly select one key. Repeatedly, you randomly select a lock, try it with the key, and return the lock to its box.

  3. Repeatedly, you select a random lock and a random key, check if the key opens the lock, then return both to their corresponding box.

For all three search methods, you stop when you've found a successful key/lock combination.

Questions:

  • Are all three options equally likely to take the same amount of time before finding a compatible lock and key? If not, why?

  • Is there a more efficient search method that can be used to find a valid combination? In other words, Can we make this process faster?


Further:

To Extend this question, consider two separate, mutually-exclusive alterations to the problem:

  1. Of the 100 trillion locks and keys, lets now say that only 1000 of each are compatible with each other.

  2. Of the 100 trillion locks and keys, lets now say each key is compatible with 1000 different locks, and each lock is compatible with 1000 different keys.

Will any search method work better than any other, to find a matching combination?


Thanks!

*Disclaimer: This is my very first post here.

$\endgroup$
  • 3
    $\begingroup$ My gut feeling is that options (1) and (2) are equivalent. But they are guaranteed to succeed. Option (3) has no such guarantee: in theory it could take an eternity and a day to find a matching pair. You can calculate the expected number of tries for some small number, say $N=4$ to prove that. $\endgroup$ – Oldboy May 23 at 8:33
  • $\begingroup$ Unless I am misunderstanding you, 1) sounds like: you take a lock. Now you try a key. If it doesn't work, you set the failed key aside, and pick another key from the box ... etc. Is that right? Your 'one by one' makes it sound like this ... but if so, it does not use replacement; replacement would be putting the failed key back into the box of keys. $\endgroup$ – Bram28 May 23 at 18:57
  • $\begingroup$ Good point. 'one by one' might be a bit misleading. They are all with replacement, so you're putting the key/lock back into their corresponding box. Next time you reach into whatever box, there is an equal probability of selected any lock/key, including those you've already selected. Does that make sense? $\endgroup$ – J Doug May 23 at 19:00
  • $\begingroup$ @It doesn't make sense to me. How are the three procedures different if you always put the key and lock back? $\endgroup$ – saulspatz May 23 at 19:10
  • 2
    $\begingroup$ If you're selecting with replacement, then it is analogous to rolling $2$ dice until you get a pair. Then it should be intuitively obvious that all 3 procedures are equivalent. $\endgroup$ – antkam May 24 at 19:57
3
$\begingroup$

A simple analogy is that one box contains red cards labeled 1 to $n$ and the other box contains green cards labeled 1 to $n$. A "match" occurs if you pick a red and green card with the same number. The probability of getting a match is the same for all 3 methods: If red card is picked first and its value is $r$, then the probability that the green card has the same value is $1/n$. It doesn't matter if you swap the order of picking cards, and pick the green card first (since card color is irrelevant). It doesn't matter if you keep the first card, and only repeat the draws of the other color, or if in each repetition select one card of each color.

Extension 1: the numbers 1 to 1000 exist for both sets of cards, and the remainder of the cards are blank. Method 1 and 2 will lead to no matches ever occuring if the first card drawn is blank. The probability of that happening is $(n-1000)/n$. Method 3 has a non-zero probability to get a match each trial: $1000/n \times 1/n$.

Extension 2: the analogy is more complicated. After drawing cards you would have to look up in a book to see if the red number and green number are "compatible". For each of the 3 methods, the probability of a compatible match is the same: $1000/n$.

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