How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?

# Understand the problem

[/et_pb_text][et_pb_text _builder_version="4.0" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]Suppose 91 distinct positive integers greater than 1 are given such that there are at least 456 pairs among
them which are relatively prime. Show that one can find four integers a, b, c, d among them such that
gcd(a, b) = gcd(b, c) = gcd(c, d) = gcd(d, a) = 1.

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="4.0"]Regional Math Olympiad, 2019 Problem 6

[/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]Combinatorics

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]Do you really need a hint? Try it first!

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]The clue: Consider the numbers as points in a graph, and some edges between the points based on their gcd. Let us consider a graph G with 91 vertices (91 distinct numbers) and connect each pair of these vertices. which corresponds to co-prime pairs implies at least 456 edges i.e. e $\geq$ 456. Here e = number of edges. Now getting four number a,b, c, d such that gcd (a, b) = gcd (b, c) = gcd(c,d) = gcd (d,a) = 1 implies existence at a cycle of length 4.  [/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]We will follow the contradiction method. Let us assume there is no cycle of length '4'. Our aim is to find a bound on e, which contradicts the 456 bound on e. Let vertex set of G be V =  {$v_1, v_2,...,v_{91}$}, let degree of $v_i = d_i$. Now, observe that the number of vertex pairs {$v_k, v_l$}, adjacent to $v_i$ is ${d_i}\choose{2}$. Now observe that a vertex pair {$v_k, v_l$} cannot be common to two vertices say $v_i$ and $v_j$ both, because if so, $v_i, v_k, v_j, v_l, v_i$ will form a cycle.[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

So, the sum of all such vertex pairs corresponding to a vertex over all the vertex set $\leq$ the total number of vertex pairs. $\sum_{i=1}^{91} ({d_i}\choose{2}) \leq {{91}\choose{2}} \rightarrow$ $\sum_{i=1}^{91} ({d_i}^2 - d_i)\leq 91.90 \rightarrow$  $\sum_{i=1}^{91} {d_i}^2 \leq 2e + {{91}\choose{2}}$ -> (1)  as $\sum_{i=1}^{91} d_i = 2e$.

We will try to find a lower bound on  $\sum_{i=1}^{91} {d_i}^2$ w.r.t e.

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

By RMS - AM inequality, $\sum_{i=1}^{91} {d_i}^2 \geq \frac{( \sum_{i=1}^{91} {d_i})^2 }{91} = \frac{4e^2}{91}$ -> (2) Using (1) and (2), we get $\frac{2e^2}{91} - e \leq 91.45$ From here, by solving we get $e \leq 91x5 =455$. This gives the contradiction.

# Similar Problems

[/et_pb_text][et_pb_post_slider include_categories="9" _builder_version="3.22.4"][/et_pb_post_slider][et_pb_divider _builder_version="3.22.4" background_color="#0c71c3"][/et_pb_divider][/et_pb_column][/et_pb_row][/et_pb_section]