Problem

Source: Tournament of the Towns

Tags: combinatorics, graph theory, algorithms



a.) There are 2n+1 (n>2) batteries. We don't know which batteries are good and which are bad but we know that the number of good batteries is greater by 1 than the number of bad batteries. A lamp uses two batteries, and it works only if both of them are good. What is the least number of attempts sufficient to make the lamp work? b.) The same problem but the total number of batteries is 2n (n>2) and the numbers of good and bad batteries are equal. Proposed by Alexander Shapovalov