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
Problem
Source: Tournament of the Towns
Tags: combinatorics, graph theory, algorithms
13.12.2016 01:20
a) There are n+1 good batteries and n bad batteries. We divide the batteries in sets of three. We need C23=3 attempts to verify all possible pairs of these three batteries. If the lamp don't works, we test the next set of three batteries and continue this process. Under the most unfavourable circumstances, each set contains 1 good battery and 2 bad batteries. For n even, is necessarily the test of n2 sets to eliminate all bad batteries, which means 3n2 attempts. All remained n2+1≥3 batteries are good. Results, for n even, we need at least 3n2+1 attempts to make surely the lamp to work. For n odd, after the test of n−12 sets (3(n−1)2\textnormalattempts), remains 1 bad battery and the other n+32≥3 batteries are good. In this case, we need at least 3(n−1)2+3=3(n+1)2 attempts to make surely the lamp to work. Using a closed form, the least number of attempts is N=3n+22+1+(−1)n+14. b) In this case, there are n good batteries and n bad batteries. We use the same method. For n even, after 3n2 attempts remain n2≥2 good batteries. For n odd, after 3(n−1)2 attempts remains 1 bad battery and the other n+12≥2 batteries are good. The result is the same, N=3n+22+1+(−1)n+14.
13.12.2016 07:44
algorithm works better (although I can't prove this is the best).
13.12.2016 09:20
Yes, you are right! In case a), n+2<N,∀n>2. And we can use your method, also, in case b). Divide the batteries in n groups of 2. If none of the groups works, each of those groups has one good and one bad battery. Then we test 2 groups, which contain 2 good and 2 bad batteries and this last step needs at most 6 trials. In this way, the total number of attempts is maximum n+6. Only for n∈{3,4,5,6,7,8},N<n+6; for n=9 and n=10, the two methods are similar. For n>10, your method is better. Final result for case b): {3(n+1)2\textnormalforn∈{3,5,7}3n2+1\textnormalforn∈{4,6,8}n+6\textnormalforn≥9.
13.12.2016 09:35
And a more efficient sequence for case b): We test the first n−2 groups of 2 batteries. If none of the groups works, each of those groups has one good and one bad battery and remain 2 good and 2 bad batteries. For the last 4 batteries we need 6 trials. In this way, the total number of attempts is maximum n+4. Final result for case b): {6\textnormalforn=37\textnormalforn=4n+4\textnormalforn≥5.
13.12.2016 11:11
a) The answer is n+2. Check the pairs (2k−1,2k) for all 1≤k≤n and then check the pairs (2k−1,2k+1) and (2k,2k+1). Assume that the first n checks fail. Since there are exactly n bad lamps, every pair (2k−1,2k) consists of a bad lamp and a good lamp and 2n+1 is a good lamps. Hence one of (2n−1,2n+1) and (2n,2n+1) is a pair of good lamps and we are done. For minimality, assume for contrary that we performed n+1 checks. We can assume that the strategy doesn't rely on the results of the checks, since we are only interested in the case that every lamp doesn't turn on. By PHP, there exists a lamp which was used twice. Take this lamp, and also take every lamp from every other check. We took at most n lamps, so we can assume that all these lamps are bad. Hence it can happen that all checks fail, contradiction.
22.03.2017 21:52
It turns out that the same idea works for both parts (only the computations are different).
22.03.2017 23:40
23.03.2017 01:37
18.02.2020 04:51
Solution with Aahan, Aatman Supkar, Aibek, Anshul, Archit, Arindam, Ethan Liu, G, Grant Yu, Maximus Lu, Naruto. D. Luffy, Paul Hamrick, R. Correaa , Rohan Goyal, yuanfeng: Part (a) We claim n+2 trials is the answer. To show n+2 steps are sufficient start by trying the batteries in disjoint pairs A_1 B_1, A_2 B_2, \dots, A_n B_n. If none of them work, the last battery Z is good and there is exactly one good battery in each pair we tried. Now use ZA_1 and ZB_1. To show n+1 steps is insufficient, we will prove for a graph G on 2n+1 vertices with at most n+1 edges there is a vertex cover with n vertices. First cover any vertex of degree at least 2 (it must exist); then cover any uncovered edges one by one (choosing the endpoint arbitrarily). Part (b) We claim the answer is n+3. First, try three batteries AB, BC, CA in that order. If none of them work, at least two batteries are good and then we can apply the previous odd case to N = 2n-3. This takes 3 + \left( (n-2)+2 \right) = n+3 steps. The proof of necessity is similar: given a graph G on 2n vertices with at most n+2 edges, we take any vertex of degree at least 2, cover it, and then apply the previous odd case.
04.07.2020 21:37
Part a) I claim that our answer is n+2. We can divide the batteries into n pairs with one left over. If one of the pairs works, then we are done. Suppose otherwise. With n pairs, come 2n batteries. If no pair has two good batteries, then each pair has at most one good battery, hence a total of at most n good batteries. This means we must have \geq n bad batteries, but since there are exactly n bad batteries, we must have n good and n bad batteries among the n pairs. Furthermore, each pair must have exactly one good and one bad battery or else some pair has both good batteries. The remaining battery must be good. Comparing the n pairs takes n attempts. Lastly, we take the remaining battery and compare it with both batteries of a chosen pair. One of the batteries in that pair is good, so 2 more attempts suffices. Hence, n + 2 tries is sufficient. Now we show that n+1 attempts is not enough. Consider a graph on 2n+1 vertices, where a vertex represents a battery. Notice that among the total \tbinom{2n+1}{2} = 2n^2 + n possible edges, exactly \tbinom{n+1}{2} = \tfrac{n(n+1)}{2} of them are good and the remaining are bad. Suppose that testing n+1 times is enough. Now let each test represent a connection; we have n+1 connections. I claim that there must be a K_{n+1} of all non-connected vertices. Since it is impossible to tell which batteries are good or not, we cannot locate the n+1-clique of all good batteries. So in fact, our claim suffices. Consider the complementary graph, with \tbinom{2n+1}{2} - (n+1) = 2n^2 -1 edges. By a certain Turan's Theorem, the largest number of edges for a graph on 2n+1 vertices without K_{n+1} is\left(1 - \frac{1}{n}\right)\cdot \frac{(2n+1)^2}{2} = 2n^2 - \frac{3}{2} - \frac{1}{2n} < 2n^2 - 1hence the complementary graph on 2n^2 - 1 edges must have a K_{n-1}, as desired. No matter how the n+1 tests are performed, among the remaining edges, there must exist a K_{n+1} clique, as desired. \blacksquare Part b) I claim that our answer is n+3. Take three batteries and perform three tests, pairwise. If none of them work, then we either have all three batteries bad, or one of them good and two of them bad. Either way, we throw out all three batteries and perform the above argument on 2n-3, yielding a total of ((n-2) + 2) + 3 = n+3 tries. The proof that n+2 tries doesn't work also follow from Turan's. Suppose that if two batteries are tested we connect them. We want to show there is a K_n in the \tbinom{2n}{2} - (n+2) = 2n^2 - 2n - 2 edges of the complementary graph. Indeed, we check that\frac{n-2}{n-1} \cdot \frac{4n^2}{2} < 2n^2 - 2n - 2so we are done. \blacksquare Remark: GRAF THERY. YUH!
05.07.2020 06:06
The equivalent graph theory analog of this problem is: What's the minimum number of edges required such that in a graph of 2n+1 (or 2n) vertices there is no isolated group of n+1 (or n) vertices. Here's a few somewhat obvious facts that are important for this proof: Observation: Any tree of at least 2 edges must contain two isolated vertices, any graph with a cycle must contain two isolated vertices, and any tree of at least 4 edges must contain three isolated vertices. The answer for part a is n+2, acheived by letting our graph be the disjoint union of n-1 K_2 and 1 K_3. Pigeonhole says we must have two vertices in a K_2 or K_3 subgraph, which then must be adjacent. WLOG we only need to prove the existence of an isolated group of n+1 vertices in any graph with n+1 edges and 2n+1 vertices. If our graph has at least n+1 connected components, we'd be done. Otherwise, we have exactly n connected components which are all trees. One connected component must have at least 2 edges, and thus contain 2 isolated vertices. Every other connected component has at least 1 isolated vertex, giving n+1 isolated vertices in total. Moving on to part b, the answer is n+3, acheived by letting our graph be the disjoint union of n-3 K_2 and 2 K_3. Pigeonhole says we must have two vertices in a K_2 or K_3 subgraph, which then must be adjacent. WLOG we only need to prove the existence of an isolated group of n vertices in any graph with n+2 edges and 2n vertices. If our graph has at least n connected components, we'd be done. Otherwise, we either have n-2 connected components which are all trees or n-1 connected components with 1 cycle among them. In the first case, we either have two trees with at least 2 edges or 1 tree with at least 4 edges, and either way we can find n isolated vertices. In the second case, we can also find n isolated vertices.
03.01.2021 21:33
The answer is \tfrac{N+3}{2} when N is odd and \tfrac{N}{2}+3 when N is even. First we show these bounds are achievable; if N=2k+1 is odd, then separate the batteries into k-1 pairs and a single group of 3 batteries. There must be some group with at least two batteries; thus by testing every group we can find a good pair in at most k+2 attempts. If N=2k is even, then separate the batteries into k-3 pairs and two groups of 3 batteries. Again, there must be some group containing at least two good batteries, so by testing all the groups, we can find a good pair in at most k+3 attempts. Now we show this is the best we can do; consider the complete graph K_N on N vertices, where each battery is a vertex, and we color an edge red if it corresponds to two good batteries. There's a red complete subgraph of at least \lceil \tfrac{N}{2} \rceil vertices. It's clear that the minimum number of attempts we need is thus the minimum integer t such that we can remove t edges from K_N and the remaining graph has no K_{\lceil N/2 \rceil}. By Turan's theorem, we get \binom{N}{2}-t \le \frac{\lceil N/2 \rceil-2}{\lceil N/2 \rceil - 1} \cdot \frac{N^2}{2}and from here it's not hard to get t > \tfrac{N+1}{2} when N is odd and t > \tfrac{N}{2}+2 when N is even.
22.01.2022 16:04
Can you check if this is true? a) We claim that we need at least n+1 moves to guarantee finding two good lamps. (So the answer is n+2) Assume that with x \le n moves are sufficent. These moves are between two bad lamps or one bad, one good lamp. Otherwise x-1 moves would be sufficient. Assume that we are sure that u,v are good lamps. Let A be the set of lamps we performed a move, let B the set of other lamps. |B|\ge 1 because of our assumption. Call two lamps friends if we performed a move to this pair. \textbf{Claim:} We cannot guarantee that all lamps in B are good. Proof: Assume otherwise. If there exists a bad lamp b in A such that all friends of b are bad, then we can change b with a lamp in B, contradicting with second assumption(not the main one). Otherwise any bad lamp is friend with exactly one good lamp. We can change u with his friend in A without affecting the results, contradicting with main assumption. \square We can change u with a bad lamp in B without affecting the results. Contradiction.
09.08.2022 01:06
We will solve the problem for N batteries for all N\geq3. This is equal to finding the smallest number of edges needed to be removed from a K_N to be left with no K_{\left\lceil\frac N2\right\rceil}. If N=2n, then by Turan's Theorem, the optimal graph is K_{2,2,\ldots,2,3,3}, which removes 6+(n-3)=n+3 vertices for n\geq3. If n=2, then the answer is \binom42=6. If N=2n+1, then the optimal graph is K_{2,2,\ldots,2,3}, which removes 3+(n-1)=n+2 vertices. Therefore, the least number of attempts needed is \boxed{\begin{cases}6&N=4\\n+3&N=2n\\n+2&N=2n+1\end{cases}}.