Maths Olympiad Prep

Library /

Combinatorics Difficulty 6.6 National olympiad Prove it Brazil

We have four charged batteries, four uncharged batteries and a radio which needs two charged batteries to work.
Suppose we don't know which batteries are charged and which ones are uncharged. Find the least number of attempts sufficient to make sure the radio will work. An attempt consists in putting two batteries in the radio and check if the radio works or not.

Solutions — 2

Solution 1

Let's generalize this problem to 2n2n batteries, nn of them charged. The number of charged batteries needed to turn on the radio is still two.

One can see that the order of the attempts doesn't matter and that a set of attempts is always successful if and only if in every set of nn batteries there is an attempt with two of these batteries, that is, no set of nn batteries is "pairwise untested". Indeed, if there is a set SS of nn pairwise untested batteries, you can be unlucky enough: the working batteries might be these in SS. Conversely, if every set of nn batteries has two tested batteries, we will choose at some moment two charged batteries and the radio will work.

So consider a graph GG in which each battery is a vertex and we connect two batteries iff we do not test these batteries. The number of attempts is the number of disconnected pairs, that is (2n2)E\binom{2n}{2} - |E|, where EE is the set of edges of GG. Since we want to minimize the number of attempts, we must maximize E|E|, that is, we need to have the maximum number of edges. But the only restriction is that we don't have a set SS of nn pairwise untested batteries, which speaking "graph-wise", is the same as GG not having a nn-clique. But, by Turán's Theorem, the graph with the maximum number of edges without a nn-clique is the most balanced (n1)(n-1)-partite graph. In this case, the partition sets of vertices of GG must contain 33, 33, 22, 22, ..., 22 vertices (where we have n3n-3 twos). So the least number of attempts is the number of disconnected pairs of vertices, that is, 23+(n3)=n+32 \cdot 3 + (n-3) = n + 3.

Solution 2

Let's generalize this problem to 2n2n batteries, nn of them charged. The number of charged batteries needed is still two.
One can see that the order of the attempts doesn't matter and that a set of attempts is always successful if and only if in every set of nn batteries there is an attempt with two of these batteries, that is, no set of nn batteries is "pairwise untested". Indeed, if there is a set SS of nn pairwise untested batteries, you can be unlucky enough: the working batteries might be these in SS. Conversely, if every set of nn batteries has two tested batteries, we will choose at some moment two charged batteries and the radio will work.
So consider a graph GG in which each battery is a vertex and we connect two batteries iff we do not test these batteries. The number of attempts is the number of disconnected pairs, that is (2n)E(2^n) - |E|, where EE is the set of edges of GG. Since we want to minimize the number of attempts, we must maximize E|E|, that

is, we need to have the maximum number of edges. But the only restriction is that we don't have a set S of n pairwise untested batteries, which speaking "graph-wise", is the same as G not having a n-clique. But, by Túran's Theorem, the graph with the maximum number of edges without a n-clique is the most balanced (n1)(n - 1)-partite graph. In this case, the partition sets of vertices of GG must contain 3,3,2,2,,23, 3, 2, 2, \ldots, 2 vertices (where we have n3n - 3 twos). So the least number of attempts is the number of disconnected pairs of vertices, that is, 23+(n3)=n+32 \cdot 3 + (n - 3) = n + 3.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.