# (romanian ioi team selection 2006) You are given a cyclic array A of n distinct elements. query(i, j, k) returns the order of the elements A[i], A[j] and A[k] (for example a result can be A[i] < A[j] < A[k] or A[i] < A[j] > A[k]). Find a local minimum using as few queries as possible.
# (Bulgarian OI) You are given a matrix A with n rows and m columns. An cell is considered a local minimum if it’s row and column neighbours have higher values. One query is what is the value of A[i][j]. Find a local minimum in as few queries as possible.
# (folklore) A celebrity in a group of n people is a person that is known by everybody but doesn’t know anybody. Given a group of n people you can query if person x knows person y. Using the fewest number of queries possible, find out if there’s a celebrity in that group.
# (CLRS) Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows:
# (CLRS) Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Less than n/2 chips are bad. Help the professor find the good chips using as few tests as possible. The four possible outcomes of a test are as follows:
** Chip A says: B is good, Chip B says: A is good, Conclusion: both are good, or both are bad
** Chip A says: B is good, Chip B says: A is bad, Conclusion: at least one is bad
** Chip A says: B is bad, Chip B says: A is good, Conclusion: at least one is bad
** Chip A says: B is bad, Chip B says: A is bad, Conclusion: at least one is bad
Less than n/2 chips are bad. Help the professor find the good chips using as few tests as possible.
# (martin gardner, romanian ioi team selection 98) On the bottom floor of a building there are 11 wire ends. On the top floor there are the other 11 ends of the wires. An electrician has to figure out which end above matches with which end below. To accomplish this he can do two things: 1) tie any two ends together on the same floor. 2) test for a closed circuit by applying a device to two ends. What’s a method that minimizes the number of times the electrician needs to climb the stairs.
When I ask for the minimum number of queries I'm talking about worse case behavior. Please discuss in the comments.
