uniolympiads English

IMC 2016, Ημέρα 2, Θέμα 8

Let nn be a positive integer, and denote by Zn\mathbb{Z}_n the ring of integers modulo nn. Suppose that there exists a function f ⁣:Zn→Znf\colon \mathbb{Z}_n \to \mathbb{Z}_n satisfying the following three properties:

(i) f(x)≠xf(x) \ne x,

(ii) f(f(x))=xf(f(x)) = x,

(iii) f(f(f(x+1)+1)+1)=xf(f(f(x+1)+1)+1) = x for all x∈Znx \in \mathbb{Z}_n.

Prove that n≡2(mod4)n \equiv 2 \pmod 4.

Πρωτότυπο από το επίσημο PDFLet n be a positive integer, and denote by Z n the ring of integers modulo n . Problem 8. Suppose that there exists a function f : Z n → Z n satisfying the following three properties: (i) f (x) 6 = x , (ii) f (f (x)) = x , (iii) f (f (f (x + 1) + 1) + 1) = x for all x ∈ Z n . Prove that n ≡ 2 (mod 4) .

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

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

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

Επίσημη λύση

(Proposed by Ander Lamaison Vidarte, Berlin Mathematical School, Germany)

Solution. From property (ii) we can see that ff is surjective, so ff is a permutation of the elements in Zn\mathbb{Z}_n, and its order is at most 22. Therefore, the permutation ff is the product of disjoint transpositions of the form (x,f(x))\big(x,f(x)\big). Property (i) yields that this permutation has no fixed point, so nn is be even, and the number of transpositions is precisely n/2n/2.

Consider the permutation g(x)=f(x+1)g(x) = f(x+1). If gg was odd then g∘g∘gg\circ g\circ g also would be odd. But property (iii) constraints that g∘g∘gg\circ g\circ g is the identity which is even. So gg cannot be odd; gg must be even. The cyclic permutation h(x)=x−1h(x) = x-1 has order nn, an even number, so hh is odd. Then f(x)=g∘hf(x) = g\circ h is odd. Since ff is the product of n/2n/2 transpositions, this shows that n/2n/2 must be odd, so n≡2(mod4)n\equiv 2 \pmod 4.

Remark. There exists a function with properties (i–iii) for every n≡2(mod4)n\equiv 2 \pmod 4. For n=2n = 2 take f(1)=2f(1) = 2, f(2)=1f(2) = 1. Here we outline a possible construction for n≥6n\ge 6.

Let n=4k+2n = 4k+2, take a regular polygon with k+2k+2 sides, and divide it into kk triangles with k−1k-1 diagonals. Draw a circle that intersects each side and each diagonal twice; altogether we have 4k+24k+2 intersections. Label the intersection points clockwise around the circle. On every side and diagonal we have two intersections; let ff send them to each other.

This function ff obviously satisfies properties (i) and (ii). For every xx we either have f(x+1)=xf(x+1) = x or the effect of adding 11 and taking ff three times is going around the three sides of a triangle, so this function satisfies property (iii).

[Figure in the original PDF.]

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

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

Πώς πήγε;