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:
You randomly select one lock. Repeatedly, you randomly select a key, try it with the lock, and return the key to its box.
You randomly select one key. Repeatedly, you randomly select a lock, try it with the key, and return the lock to its box.
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:
Of the 100 trillion locks and keys, lets now say that only 1000 of each are compatible with each other.
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.
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$.