Maths Olympiad Prep

Library / /3 of 8

Combinatorics Difficulty 6.3 National olympiad Prove it South Korea

Let UU be a set of mm triangles. Prove that there exists a subset WW of UU satisfying the following conditions.

(i) The number of triangles in WW is at least 0.45m4/50.45m^{4/5}.

(ii) There exist no 6 distinct points A,B,C,D,EA, B, C, D, E, and FF such that WW contains 6 triangles ABC,BCD,CDE,DEF,EFAABC, BCD, CDE, DEF, EFA, and FABFAB.

Solution

Let UU' be a subset of UU by choosing each triangle with the probability pp independently at random. Then the expected number of triangles in UU' is mpmp.

A sequence of 6 distinct points (x1,x2,,x6)(x_1, x_2, \dots, x_6) is called a bad configuration if all 6 triangles x1x2x3,x2x3x4,,x4x5x6,x5x6x1,x6x1x2x_1x_2x_3, x_2x_3x_4, \dots, x_4x_5x_6, x_5x_6x_1, x_6x_1x_2 belong to UU.

The number of bad configurations in UU is at most m(m1)(3!)236m2m(m-1)(3!)^2 \le 36m^2, because it is less than or equal to the number of selecting two triangles, selecting x1,x2,x3x_1, x_2, x_3 from the first triangle, and selecting x4,x5,x6x_4, x_5, x_6 from the second triangle.

If (x1,x2,,x6)(x_1, x_2, \dots, x_6) is a bad configuration, then (xi,xi+1,,xi+6)(x_i, x_{i+1}, \dots, x_{i+6}) and (xi,xi1,,xi6)(x_i, x_{i-1}, \dots, x_{i-6}) are bad configurations and so 62=126 \cdot 2 = 12 bad configurations form a bunch. Thus the number of bunches of bad configurations in UU is at most 36m2/12=3m236m^2/12 = 3m^2.

The probability that a fixed bad configuration of UU is contained in UU' is p6p^6 and therefore the expected number of bunches of bad configurations in UU' is at most 3m2p63m^2p^6.

Thus, the expected number of triangles in UU' minus the number of bunches of bad configurations in UU' is at least mp3m2p6mp - 3m^2p^6.

Take p=cm1/5p = c m^{-1/5}. Then
mp3m2p6cm6/53c6m2m6/5=(c3c6)m4/5. mp - 3m^2p^6 \geq c m^{6/5} - 3c^6 m^2 m^{-6/5} = (c - 3c^6)m^{4/5}.
By taking c=1/2c = 1/2, we deduce mp3m2p6(12364)m4/50.45m4/5mp - 3m^2p^6 \geq (\frac{1}{2} - \frac{3}{64})m^{4/5} \geq 0.45m^{4/5}.

Therefore there exists a subset UU' of UU such that the number of triangles in UU' minus the number of bunches of bad configurations in UU' is at least 0.45m4/50.45m^{4/5}. Let WW be a subset of UU' by discarding one triangle in each bunch of bad configurations. Then WW contains at least 0.45m4/50.45m^{4/5} triangles and no bad configurations, as desired.

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.