Olympiad Maths Prep

Library / /6 of 19

Combinatorics Difficulty 6.0 AIME, harder Prove it Mongolia

GG is a given simple graph. If any 11001100 of the edges of the graph can be represented by 4545 of its vertices, then prove that there exists 4545 vertices that can represent all of its edges (vev \in e, then vv vertices represents edge ee).

(proposed by B. Batbayasgalan)

Solution

Suppose that such 4545 vertices do not exist. If removal of any one of the edges does not interfere with this condition, then remove this edge. Repeating this action until there are no longer any edges to be removed results in the graph such that after a removal of any arbitrary edge, 4545 vertices that represent the remaining edges can be selected but 4545 vertices that represent all of the edges cannot be selected. Suppose that edges of this graph are e1,e2,,eme_1, e_2, \ldots, e_m. Then for each removal of eie_i, those that intersect with every other edge except eie_i, there exists a set such that viG(v)v_i \in G(v), vi=45|v_i| = 45. In other words, when eivi=e_i \cap v_i = \emptyset and iji \neq j, then eivj=e_i \cap v_j = \emptyset.

Consider π\pi combination v(g)={1,2,,n}v(g) = \{1, 2, \ldots, n\} of number 1,2,,n1, 2, \ldots, n. In case of this combination, if the two vertices of eie_i edge is located before all the vertices of set viv_i, then let π\pi be called iith type combination. If iji \neq j, show that π\pi combination cannot at the same time be iith and jjth type. Suppose that for π\pi combination, the last vertices of the eie_i edge is located on the kkth position, after the last vertices of the eje_j edge. Since π\pi is of iith type, all of vertices in set viv_i is located after kk. On the other hand, since vertices vejviv \in e_j \cap v_i \neq \emptyset belongs to eje_j, it must be located before kk. Hence there is a contradiction. Therefore, each combination must belong to only one type.

On the other hand, since the number of iith type combination is Cn472!45!C_n^{47} 2! 45! and the total number of combinations is n!n!, Cn47m2!45!(n47)!n!C_n^{47} m \cdot 2! 45! (n-47)! \leq n!. From here it follows that mC472<1100m \leq C_{47}^2 < 1100 and thus, given the conditions of the problem, there is a contradiction. Therefore 4545 vertices that represent all the edges can be selected/found.

Looking for a route rather than 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.