uniolympiads English

IMC 2007, Ημέρα 1, Θέμα 4

Let GG be a finite group. For arbitrary sets U,V,W⊂GU, V, W \subset G, denote by NUVWN_{UVW} the number of triples (x,y,z)∈U×V×W(x, y, z) \in U \times V \times W for which xyzxyz is the unity.

Suppose that GG is partitioned into three sets AA, BB and CC (i.e. sets A,B,CA, B, C are pairwise disjoint and G=A∪B∪CG = A \cup B \cup C). Prove that NABC=NCBAN_{ABC} = N_{CBA}.

Πρωτότυπο από το επίσημο PDFLet G be a finite group. For arbitrary sets U, V, W ⊂ G, denote by N U V W the number of triples (x, y, z) ∈ U × V × W for which xyz is the unity. Suppose that G is partitioned into three sets A, B and C (i.e. sets A, B, C are pairwise disjoint and G = A ∪ B ∪ C). Prove that N ABC = N CBA .

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

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

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

Επίσημη λύση

Solution. We start with three preliminary observations.

Let U,VU,V be two arbitrary subsets of GG. For each x∈Ux\in U and y∈Vy\in V there is a unique z∈Gz\in G for which xyz=exyz=e. Therefore,

NUVG=∣U×V∣=∣U∣⋅∣V∣.(1)N_{UVG}=|U\times V|=|U|\cdot|V|. \tag{1}
Second, the equation xyz=exyz=e is equivalent to yzx=eyzx=e and zxy=ezxy=e. For arbitrary sets U,V,W⊂GU,V,W\subset G, this implies
{(x,y,z)∈U×V×W: xyz=e}={(x,y,z)∈U×V×W: yzx=e}={(x,y,z)∈U×V×W: zxy=e}\{(x,y,z)\in U\times V\times W:\ xyz=e\}=\{(x,y,z)\in U\times V\times W:\ yzx=e\}=\{(x,y,z)\in U\times V\times W:\ zxy=e\}
and therefore
NUVW=NVWU=NWUV.(2)N_{UVW}=N_{VWU}=N_{WUV}. \tag{2}
Third, if U,V⊂GU,V\subset G and W1,W2,W3W_1,W_2,W_3 are disjoint sets and W=W1∪W2∪W3W=W_1\cup W_2\cup W_3 then, for arbitrary U,V⊂GU,V\subset G,
{(x,y,z)∈U×V×W: xyz=e}={(x,y,z)∈U×V×W1: xyz=e}∪∪{(x,y,z)∈U×V×W2: xyz=e}∪{(x,y,z)∈U×V×W3: xyz=e}\begin{aligned}\{(x,y,z)\in U\times V\times W:\ xyz=e\}&=\{(x,y,z)\in U\times V\times W_1:\ xyz=e\}\cup\\&\cup\{(x,y,z)\in U\times V\times W_2:\ xyz=e\}\cup\{(x,y,z)\in U\times V\times W_3:\ xyz=e\}\end{aligned}
so
NUVW=NUVW1+NUVW2+NUVW3.(3)N_{UVW}=N_{UVW_1}+N_{UVW_2}+N_{UVW_3}. \tag{3}

Applying these observations, the statement follows as

NABC=NABG−NABA−NABB=∣A∣⋅∣B∣−NBAA−NBAB==NBAG−NBAA−NBAB=NBAC=NCBA.\begin{aligned}N_{ABC}&=N_{ABG}-N_{ABA}-N_{ABB}=|A|\cdot|B|-N_{BAA}-N_{BAB}=\\&=N_{BAG}-N_{BAA}-N_{BAB}=N_{BAC}=N_{CBA}.\end{aligned}

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

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

Πώς πήγε;