uniolympiads English

IMC 2003, Ημέρα 2, Θέμα 4

Find all positive integers nn for which there exists a family F\mathcal{F} of three-element subsets of S={1,2,…,n}S = \{1, 2, \dots, n\} satisfying the following two conditions:

(i) for any two different elements a,b∈Sa, b \in S, there exists exactly one A∈FA \in \mathcal{F} containing both a,ba, b;

(ii) if a,b,c,x,y,za, b, c, x, y, z are elements of SS such that if {a,b,x},{a,c,y},{b,c,z}∈F\{a, b, x\}, \{a, c, y\}, \{b, c, z\} \in \mathcal{F}, then {x,y,z}∈F\{x, y, z\} \in \mathcal{F}.

Πρωτότυπο από το επίσημο PDF4. Find all positive integers n for which there exists a family F of three-element subsets of S = {1, 2, . . . , n} satisfying the following two conditions: (i) for any two different elements a, b ∈ S, there exists exactly one A ∈ F containing both a, b; (ii) if a, b, c, x, y, z are elements of S such that if {a, b, x}, {a, c, y}, {b, c, z} ∈ F, then {x, y, z} ∈ F.

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

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

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

Επίσημη λύση

Solution. The condition (i) of the problem allows us to define a (well-defined) operation ∗* on the set SS given by

a∗b=c if and only if {a,b,c}∈F, where a≠b.a * b = c \text{ if and only if } \{a, b, c\} \in F, \text{ where } a \ne b.
We note that this operation is still not defined completely (we need to define a∗aa * a), but nevertheless let us investigate its features. At first, due to (i), for a≠ba \ne b the operation obviously satisfies the following three conditions:

(a) a≠a∗b≠ba \ne a * b \ne b;

(b) a∗b=b∗aa * b = b * a;

(c) a∗(a∗b)=ba * (a * b) = b.

What does the condition (ii) give? It claims that

(e') x∗(a∗c)=x∗y=z=b∗c=(x∗a)∗cx * (a * c) = x * y = z = b * c = (x * a) * c

for any three different x,a,cx, a, c, i.e. that the operation is associative if the arguments are different. Now we can complete the definition of ∗*. In order to save associativity for non-different arguments, i.e. to make b=a∗(a∗b)=(a∗a)∗bb = a * (a * b) = (a * a) * b hold, we will add to SS an extra element, call it 0, and define

(d) a∗a=0a * a = 0 and a∗0=0∗a=aa * 0 = 0 * a = a.

Now it is easy to check that, for any a,b,c∈S∪{0}a, b, c \in S \cup \{0\}, (a),(b),(c) and (d), still hold, and

(e) a∗b∗c:=(a∗b)∗c=a∗(b∗c)a * b * c := (a * b) * c = a * (b * c).

We have thus obtained that (S∪{0},∗)(S \cup \{0\}, *) has the structure of a finite Abelian group, whose elements are all of order two. Since the order of every such group is a power of 2, we conclude that ∣S∪{0}∣=n+1=2m|S \cup \{0\}| = n + 1 = 2^m and n=2m−1n = 2^m - 1 for some integer m≥1m \ge 1.

Given n=2m−1n = 2^m - 1, according to what we have proven till now, we will construct a family of three-element subsets of SS satisfying (i) and (ii). Let us define the operation ∗* in the following manner:

if a=a0+2a1+…+2m−1am−1a = a_0 + 2a_1 + \ldots + 2^{m-1}a_{m-1} and b=b0+2b1+…+2m−1bm−1b = b_0 + 2b_1 + \ldots + 2^{m-1}b_{m-1}, where ai,bia_i, b_i are either 0 or 1, we put a∗b=∣a0−b0∣+2∣a1−b1∣+…+2m−1∣am−1−bm−1∣a * b = |a_0 - b_0| + 2|a_1 - b_1| + \ldots + 2^{m-1}|a_{m-1} - b_{m-1}|.

It is simple to check that this ∗* satisfies (a),(b),(c) and (e'). Therefore, if we include in FF all possible triples a,b,a∗ba, b, a * b, the condition (i) follows from (a),(b) and (c), whereas the condition (ii) follows from (e')

The answer is: n=2m−1n = 2^m - 1.

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

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

Πώς πήγε;