One hundred marbles numbered 1 through 100 are in a bowl. The marbles are drawn one at a time without replacement. How many marbles must be drawn to be sure that one of the selected numbers is exactly twice as large as another selected number?I received this problem via WhatsApp. If someone has given a home office problem to her students and they're cheating, then I am sorry but this remote learning is guaranteed to lead to a similar cheating and it's not my fault (and I have fought against the Covid-19 hysteria, lockdowns, home offices, and shutdowns as much as I could). Moreover, you don't know whether my solution is right.

Divide the marbles (numbers 1-100) to the smallest classes in which the potential collision (of a number with its double) may occur. Each class contains all the numbers\[ \{ k\cdot 2^M, \quad M\in\ZZ \} \] for some \(k\in \ZZ\), \(1\leq k\leq 100\). So one of the classes is \(\{1,2,4,8,16,32,64\}\), another class is \(\{3,6,12,24,48,96\}\), and so on. If you want to pick a maximum number of marbles so that the "collision with a doubled value" doesn't occur, these classes may be treated independently.

However, inside each class, if you want to avoid "the marble and its double", there are restrictions. In fact, from each class, you may at most pick one-half of the marbles – or a slightly greater half if the number of marbles in the class is odd. It's because "picking every other marble" clearly leads to the maximum fraction that is selected.

From the class \(\{1,2,4,8,16,32,64\}\) which has 7 elements, you may at most pick 4 elements \(\{1,4,16,64\}\) where each new element is a quadruple (four times!) the previous number (and I include both extrema to have a greater one-half). Similarly, you may pick at most 3 out of the set \(\{3,6,12,24,48,96\}\) which has 6 elements, either \(\{3,12,48\}\) or \(\{6,24,96\}\). And so on.

In the classes with an odd number of elements, I have no choice; in the classes with an even number of elements, I may choose one of the two possible subsets (exactly 50% each). If you don't care about the latter choices, you may decide that you prefer to pick the largest number in each class. If you do so, then all the fifty marbles 51-100 will be picked. You must omit the interval of "roughly halved" marbles but you may include the interval of "rough quarters", and so on, and this choice leads to the subset\[ 1; \quad 4-6; \quad 13-25; \quad 51-100 \] which has \(1+3+13+50=67\) elements. In this set with 67 marbles, there is no pair \(\{Y,2Y\}\). However, in every set with 68 or more marbles, such a pair has to occur because at least one of the classes must have "more than one-half or a slightly greater one-half" marbles that were selected.

For this reason, the minimum solution is 68 marbles (Jaromír Jágr has used the number 68 on his dress to remind everyone of the 1968 Warsaw Pact invasion to Czechoslovakia) – then the doubled pair is unavoidable – but I think that strictly speaking, any number between 68 and 100 (marbles) is a valid solution, too, because you're certain about the overlap when the number of selected marbles is larger than the bare minimum, too. Am I right?

P.S.: The opposite extreme solution, one in which the smallest element of each class is picked instead (these are exactly the odd numbers), may also be written down very explicitly (each group below is equally spaced, "every other" element is omitted; the beginnings of the groups below differ by a factor of four):\[ 1,3,5,\dots 99; \quad 4,12,\dots 100; \quad 16,48,80; \quad 64. \] This subset without a pair of "a marble and its double" has \(50+13+3+1=67\) elements, too. Note that this 67 is "approximately" the sum of a \(q=1/4\) geometric series \[ 50+12.5+3.125+\dots = \frac{50}{1-1/4} = \frac{200}{3}\approx 66.666\dots \] As you can see, the number of classes is 50 (they may be represented e.g. by the smallest elements 1,3,5...99 or by the largest elements 51,52...100). 50 classes therefore have at least 1 element, 25 of them have exactly one element (those with 51,53...99), 12 have exactly 2 elements (those with 27,29...49 or, equivalently, with 54,58...98), 7 have exactly 3 elements (those with 13,15...25; feel free to use doubled or quadrupled values), 3 have 4 elements (7,9,11; the same disclaimed with octuples); 1 has 5 elements (5), 1 has 6 elements (3), and 1 has 7 elements (the class {1,2,4,8,16,32,64}). The total number of classes with an even number of elements is 12+3+1=16. For each of them, a bit may be chosen to determine a maximum, 67-element subset without the doubling pairs. So there exist \(2^{16}=65,536\) solutions with 67 elements.

## No comments:

## Post a Comment