uniolympiads English

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

Determine the set of all pairs (a,b)(a, b) of positive integers for which the set of positive integers can be decomposed into two sets AA and BB such that a⋅A=b⋅Ba \cdot A = b \cdot B.

Πρωτότυπο από το επίσημο PDF4. Determine the set of all pairs (a, b) of positive integers for which the set of positive integers can be decomposed into two sets A and B such that a · A = b · B. (20 points)

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

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

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

Επίσημη λύση

Solution. Clearly aa and bb must be different since AA and BB are disjoint.

Let {a,b}\{a, b\} be a solution and consider the sets A,BA, B such that a⋅A=b⋅Ba \cdot A = b \cdot B. Denoting d=(a,b)d = (a, b) the greatest common divisor of aa and bb, we have a=d⋅a1a = d \cdot a_1, b=d⋅b1b = d \cdot b_1, (a1,b1)=1(a_1, b_1) = 1 and a1⋅A=b1⋅Ba_1 \cdot A = b_1 \cdot B. Thus {a1,b1}\{a_1, b_1\} is a solution and it is enough to determine the solutions {a,b}\{a, b\} with (a,b)=1(a, b) = 1.

If 1∈A1 \in A then a∈a⋅A=b⋅Ba \in a \cdot A = b \cdot B, thus bb must be a divisor of aa. Similarly, if 1∈B1 \in B, then aa is a divisor of bb. Therefore, in all solutions, one of numbers a,ba, b is a divisor of the other one.

Now we prove that if n≥2n \ge 2, then (1,n)(1, n) is a solution. For each positive integer kk, let f(k)f(k) be the largest non-negative integer for which nf(k)∣kn^{f(k)} | k. Then let A={k: f(k) is odd}A = \{k : \ f(k) \text{ is odd}\} and B={k: f(k) is even}B = \{k : \ f(k) \text{ is even}\}. This is a decomposition of all positive integers such that A=n⋅BA = n \cdot B.

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

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

Πώς πήγε;