uniolympiads English

IMC 2009, Ημέρα 1, Θέμα 3

In a town every two residents who are not friends have a friend in common, and no one is a friend of everyone else. Let us number the residents from 11 to nn and let aia_i be the number of friends of the ii-th resident. Suppose that ∑i=1nai2=n2−n\sum_{i=1}^{n} a_i^2 = n^2 - n. Let kk be the smallest number of residents (at least three) who can be seated at a round table in such a way that any two neighbors are friends. Determine all possible values of kk.

Πρωτότυπο από το επίσημο PDFIn a town every two residents who are not friends have a friend in common, and no one is a friend of everyone else. Let the residents from 1 to n and let a i be the number of friends of the i-th resident. Suppose that P n us 2 number 2 − n. Let k be the smallest number of residents (at least three) who can be seated at a round table a = n i=1 i in such a way that any two neighbors are friends. Determine all possible values of k.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. Let us define the simple, undirected graph GG so that the vertices of GG are the town's residents and the edges of GG are the friendships between the residents. Let V(G)={v1,v2,…,vn}V(G) = \{v_1, v_2, \ldots, v_n\} denote the vertices of GG; aia_i is degree of viv_i for every ii. Let E(G)E(G) denote the edges of GG. In this terminology, the problem asks us to describe the length kk of the shortest cycle in GG.

Let us count the walks of length 2 in GG, that is, the ordered triples (vi,vj,vl)(v_i, v_j, v_l) of vertices with vivj,vjvl∈E(G)v_iv_j, v_jv_l \in E(G) (i=li = l being allowed). For a given jj the number is obviously aj2a_j^2, therefore the total number is ∑i=1nai2=n2−n\sum_{i=1}^n a_i^2 = n^2 - n.

Now we show that there is an injection ff from the set of ordered pairs of distinct vertices to the set of these walks. For vivj∉E(G)v_iv_j \notin E(G), let f(vi,vj)=(vi,vl,vj)f(v_i, v_j) = (v_i, v_l, v_j) with arbitrary ll such that vivl,vlvj∈E(G)v_iv_l, v_lv_j \in E(G). For vivj∈E(G)v_iv_j \in E(G), let f(vi,vj)=(vi,vj,vi)f(v_i, v_j) = (v_i, v_j, v_i). ff is an injection since for i≠li \ne l, (vi,vj,vl)(v_i, v_j, v_l) can only be the image of (vi,vl)(v_i, v_l), and for i=li = l, it can only be the image of (vi,vj)(v_i, v_j).

Since the number of ordered pairs of distinct vertices is n2−nn^2 - n, ∑i=1nai2≥n2−n\sum_{i=1}^n a_i^2 \ge n^2 - n. Equality holds iff ff is surjective, that is, iff there is exactly one ll with vivl,vlvj∈E(G)v_iv_l, v_lv_j \in E(G) for every i,ji, j with vivj∉E(G)v_iv_j \notin E(G) and there is no such ll for any i,ji, j with vivj∈E(G)v_iv_j \in E(G). In other words, iff GG contains neither C3C_3 nor C4C_4 (cycles of length 3 or 4), that is, GG is either a forest (a cycle-free graph) or the length of its shortest cycle is at least 5.

It is easy to check that if every two vertices of a forest are connected by a path of length at most 2, then the forest is a star (one vertex is connected to all others by an edge). But GG has nn vertices, and none of them has degree n−1n-1. Hence GG is not forest, so it has cycles. On the other hand, if the length of a cycle CC of GG is at least 6 then it has two vertices such that both arcs of CC connecting them are longer than 2. Hence there is a path connecting them that is shorter than both arcs. Replacing one of the arcs by this path, we have a closed walk shorter than CC. Therefore length of the shortest cycle is 5.

Finally, we must note that there is at least one GG with the prescribed properties – e.g. the cycle C5C_5 itself satisfies the conditions. Thus 5 is the sole possible value of kk.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;