Problem 1014
In a drawer, there is an even number of "AA" type electric batteries. We know that there are as many good as bad ones.To test them, Alice only has a flashlight, which turns on provided that the two batteries that are inserted there are good. She announces to Bob that it will take a maximum of 6 attempts to make the lamp work.
- 1A, 1B, 1C, 1D, 1E. How many "AA" type electric batteries are there in the drawer?
If there are several solutions, write them in ascending order on line 1, from the smallest to the largest number.
- 2A. After how many tries is Bob sure to see the lamp on?
The code written for this problem calculates, for a fixed number N of electric batteries, all the pairs of batteries, and then enumerates for increasing values of i, all combinations of i pairs until finding one that satisfies the criterion. To test this criterion, on must, for a given combination of i pairs, test whether all valid / invalid batteries configurations result in at least one pair containing 2 valid batteries.
This algorithm explodes of course very quickly combinatorially when the number of batteries increases: the maximum possible value for N is 12 (completion in less than a minute for 10, in nearly two hours for 12). Nevertheless, by testing it for 4, 6, 8, 10 and 12, we can see the pattern and deduce the construction for any number of batteries.
The code is available here.
This algorithm explodes of course very quickly combinatorially when the number of batteries increases: the maximum possible value for N is 12 (completion in less than a minute for 10, in nearly two hours for 12). Nevertheless, by testing it for 4, 6, 8, 10 and 12, we can see the pattern and deduce the construction for any number of batteries.
The code is available here.
- 1A, 1B. There are 4 or 6 "AA" type electric batteries in the drawer.
- 2A. With 20 electric batteries, Bob is sure to have the lamp on with a maximum of 13 attempts.