Maths Olympiad Prep

Library / /23 of 29

Combinatorics Difficulty 6.0 National Olympiad Prove it Croatia

A bag contained 255255 balls numbered 1,2,,2551, 2, \ldots, 255, and then NN students each took one ball from the bag. It turned out that none of the drawn numbers was exactly twice as big as any other drawn number. Determine the maximum possible NN. (Ana Prlić)

Solution

Group the observed numbers into sets:
A0={1},A1={2,3},A2={4,5,6,7},A3={8,9,,15},A4={16,17,,31},A5={32,33,,63},A6={64,65,,127},A7={128,129,,255}. A_0 = \{1\}, A_1 = \{2, 3\}, A_2 = \{4, 5, 6, 7\}, A_3 = \{8, 9, \dots, 15\}, A_4 = \{16, 17, \dots, 31\}, \\ A_5 = \{32, 33, \dots, 63\}, A_6 = \{64, 65, \dots, 127\}, A_7 = \{128, 129, \dots, 255\}.
The number of elements of AkA_k is 2k2^k, for k=0,1,,7k = 0, 1, \dots, 7.
Notice that, for each nn, numbers nn and 2n2n belong to AkA_k and Ak+1A_{k+1} respectively for some kk. If all numbers from the sets A1,A3,A5A_1, A_3, A_5 and A7A_7 are drawn, the number of these numbers is 2+8+32+128=1702 + 8 + 32 + 128 = 170 and none of them is twice as big as any other.
Let us show that it is not possible to choose more than 170170 numbers that satisfy the condition. Let aka_k numbers from AkA_k be drawn, for k=0,1,2,,7k = 0, 1, 2, \dots, 7.
Observe the sets AkA_k and Ak+1A_{k+1}. For every mAkm \in A_k, 2m2m is in Ak+1A_{k+1}. The number of these pairs (m,2m)(m, 2m) is 2k2^k. Clearly at most one number is drawn from every pair. Except those numbers, set Ak+1A_{k+1} has another 2k2^k odd numbers, so at most 2k+2k=2k+12^k + 2^k = 2^{k+1} numbers are drawn from AkA_k and Ak+1A_{k+1}.
That means that a0+a121,a2+a323,a4+a525,a6+a727a_0 + a_1 \le 2^1, a_2 + a_3 \le 2^3, a_4 + a_5 \le 2^5, a_6 + a_7 \le 2^7.
Adding up those inequalities we get a0+a1++a7170a_0 + a_1 + \dots + a_7 \le 170. Thereby the maximum possible NN is 170170.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.