You want to design a set of yes/no questions for quickly searching the symmetric group. The questions have to be of the form "Does your permutation move $a_1$ to $b_1$ or $a_2$ to $b_2$ or ... or $a_k$ to $b_k$?" Given a random permutation, you will ask all of your questions about that permutation, and your goal is to know what the permutation is once you know the answers to your questions.

In particular, note that you aren't allowed to have later questions depend on the answers to earlier questions. You always ask the same questions of whichever random permutation you get.

Here's a slightly different way to phrase the type of question you're allowed to ask. If we represent the elements of the symmetric group by permutation matrices, then the questions you can ask involve picking a (0,1)-matrix and asking if the random permutation matrix has any 1 where your chosen matrix has a 1 (i.e., if I apply the componentwise AND function to the random matrix and your chosen matrix, do I get 0 or 1?)

Two questions:

1. How many such questions are needed in order to search $S_n$? How much bigger than $log_2 n$ is this?
2. Are there "good" strategies for designing sets of questions that can be used for any n? Can we achieve the minimum number of questions for each n with a single strategy?

You want to design a set of yes/no questions for quickly searching the symmetric group. The questions have to be of the form "Does your permutation move $a_1$ to $b_1$ or $a_2$ to $b_2$ or ... or $a_k$ to $b_k$?" Given a random permutation, you will ask all of your questions about that permutation, and your goal is to know what the permutation is once you know the answers to your questions.

In particular, note that you aren't allowed to have later questions depend on the answers to earlier questions. You always ask the same questions of whichever random permutation you get.

Here's a slightly different way to phrase the type of question you're allowed to ask. If we represent the elements of the symmetric group by permutation matrices, then the questions you can ask involve picking a (0,1)-matrix and asking if the random permutation matrix has any 1 where your chosen matrix has a 1 (i.e., if I apply the componentwise AND function to the random matrix and your chosen matrix, do I get 0 or 1?)

Two questions:

1. How many such questions are needed in order to search $S_n$? How much bigger than $log_2 n!$ is this?
2. Are there "good" strategies for designing sets of questions that can be used for any n? Can we achieve the minimum number of questions for each n with a single strategy?