uniolympiads English

IMC 2006, Ημέρα 1, Θέμα 2

Find the number of positive integers xx satisfying the following two conditions:

  1. x<102006x < 10^{2006};
  2. x2−xx^2 - x is divisible by 10200610^{2006}.
Πρωτότυπο από το επίσημο PDFFind the number of positive integers x satisfying the following two conditions: 1. x < 10 2006 ; 2. x 2 − x is divisible by 10 2006 . (20 points)

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

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

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

Επίσημη λύση

Solution 1. Let Sk={0<x<10k | x2−x is divisible by 10k}S_k=\left\{0<x<10^k\,\middle|\,x^2-x\text{ is divisible by }10^k\right\} and s(k)=∣Sk∣,k≥1s\left(k\right)=\left|S_k\right|,k\ge1. Let x=ak+1ak…a1x=a_{k+1}a_k\dots a_1 be the decimal writing of an integer x∈Sk+1,k≥1x\in S_{k+1},k\ge1. Then obviously y=ak…a1∈Sky=a_k\dots a_1\in S_k. Now, let y=ak…a1∈Sky=a_k\dots a_1\in S_k be fixed. Considering ak+1a_{k+1} as a variable digit, we have x2−x=(ak+110k+y)2−(ak+110k+y)=(y2−y)+ak+110k(2y−1)+ak+12102kx^2-x=\left(a_{k+1}10^k+y\right)^2-\left(a_{k+1}10^k+y\right)=(y^2-y)+a_{k+1}10^k\left(2y-1\right)+a_{k+1}^2 10^{2k}. Since y2−y=10kzy^2-y=10^kz for an iteger zz, it follows that x2−xx^2-x is divisible by 10k+110^{k+1} if and only if z+ak+1(2y−1)≡0(mod10)z+a_{k+1}\left(2y-1\right)\equiv0\pmod{10}. Since y≡3(mod10)y\equiv3\pmod{10} is obviously impossible, the congruence has exactly one solution. Hence we obtain a one-to-one correspondence between the sets Sk+1S_{k+1} and SkS_k for every k≥1k\ge1. Therefore s(2006)=s(1)=3s\left(2006\right)=s\left(1\right)=3, because S1={1,5,6}S_1=\left\{1,5,6\right\}.

Solution 2. Since x2−x=x(x−1)x^2-x=x(x-1) and the numbers xx and x−1x-1 are relatively prime, one of them must be divisible by 220062^{2006} and one of them (may be the same) must be divisible by 520065^{2006}. Therefore, xx must satisfy the following two conditions:

x≡0 or 1(mod22006);x\equiv0\text{ or }1\pmod{2^{2006}};
x≡0 or 1(mod52006).x\equiv0\text{ or }1\pmod{5^{2006}}.
Altogether we have 4 cases. The Chinese remainder theorem yields that in each case there is a unique solution among the numbers 0,1,…,102006−10,1,\dots,10^{2006}-1. These four numbers are different because each two gives different residues modulo 220062^{2006} or 520065^{2006}. Moreover, one of the numbers is 0 which is not allowed.

Therefore there exist 3 solutions.

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

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

Πώς πήγε;