Maths Olympiad Prep

Library / /17 of 30

, 2023

Combinatorics Difficulty 8.1 Shortlist Prove it Saudi Arabia

In an oral exam, there are 10 examiners and 1024 contestants. Each contestant will be asked by each examiner and receive a result of either “pass” or “fail”. It is given that for any two contestants, there is some examiner who will rate one passed and the other failed. Two contestants are said to be “separative” if they have different results by at least 3 examiners. Prove that it is possible to select 24 pairwise separative contestants.

Solution

Number the examiners from 11 to 1010 and consider the results of contestants as binary sequences of the form x1x2x10x_1x_2\ldots x_{10}, in which xi=0x_i = 0 or 11 if the iith examiner gave pass or fail response for the corresponding candidate. We can directly construct 2424 binary strings that satisfy the “separative” condition. Indeed, choose strings of the form (x1x2x3x4x5x6)(x7x8x9x10)(x_1x_2x_3x_4x_5x_6)(x_7x_8x_9x_{10}), where: x1x2x3x4x5x6x_1x_2x_3x_4x_5x_6 contains exactly 33 zeros and 33 ones; and x7x8x9x10x_7x_8x_9x_{10} will contain all binary strings of length 44. Since (63)=20\binom{6}{3} = 20 and two strings x1x2x3x4x5x6x1x2x3x4x5x6x_1x_2x_3x_4x_5x_6 \neq x'_1x'_2x'_3x'_4x'_5x'_6 would be different at at least 22 positions, so the rest just need to differ by at least 11 position. Since 24=162^4 = 16, there will be 44 repeated strings at the last 44 positions, we just need to choose those strings that differ by at least 33 positions out of the first 66 positions. For detail,
(000111)(0000)(a)(001011)(0001)(b)(001101)(0010)(c)(001110)(0011)(d)(010011)(0100)(010101)(0101)(010110)(0110)(011001)(0111)(011010)(1000)(011100)(1001)(100011)(1010)(100101)(1011)(100110)(1100)(101001)(1101)(101010)(1110)(101100)(1111)(110001)(0011)(d)(110010)(0010)(c)(110100)(0001)(b)(111000)(0000)(a). \begin{array}{lcl} (000111)(0000) & \rightarrow & (a) \\ (001011)(0001) & \rightarrow & (b) \\ (001101)(0010) & \rightarrow & (c) \\ (001110)(0011) & \rightarrow & (d) \\ (010011)(0100) \\ (010101)(0101) \\ (010110)(0110) \\ (011001)(0111) \\ (011010)(1000) \\ (011100)(1001) \\ (100011)(1010) \\ (100101)(1011) \\ (100110)(1100) \\ (101001)(1101) \\ (101010)(1110) \\ (101100)(1111) \\ (110001)(0011) & \rightarrow & (d') \\ (110010)(0010) & \rightarrow & (c') \\ (110100)(0001) & \rightarrow & (b') \\ (111000)(0000) & \rightarrow & (a'). \end{array}
Finally, add 44 more strings as the following:
(000000)(0000),(000000)(1111),(111111)(0000),(111111)(0000). \begin{array}{l} (000000)(0000), (000000)(1111), \\ (111111)(0000), (111111)(0000). \end{array}
It is easy to check that they are pairwise separative and also separative with the other 2020 strings. \square

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.