Difference between revisions of "1998 USAMO Problems/Problem 1"
(moved 1998 USAMO Problems/Problem 1 to 1998 USAMO Problems/Problem 3: Wrong problem, I fix'd it) |
Centslordm (talk | contribs) m (→See Also: added yt link to venhance newest vid) |
||
(11 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
− | + | == Problem == | |
+ | Suppose that the set <math>\{1,2,\cdots, 1998\}</math> has been partitioned into disjoint pairs <math>\{a_i,b_i\}</math> (<math>1\leq i\leq 999</math>) so that for all <math>i</math>, <math>|a_i-b_i|</math> equals <math>1</math> or <math>6</math>. Prove that the sum <cmath> |a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| </cmath> ends in the digit <math>9</math>. | ||
+ | |||
+ | == Solution == | ||
+ | |||
+ | Notice that <math>|a_i - b_i| \equiv 1 \pmod 5</math>, so <math>S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \equiv 1+1+\cdots + 1 \equiv 999 \equiv 4 \bmod{5}</math>. | ||
+ | |||
+ | Also, for integers <math>M, N</math> we have <math>|M-N| \equiv M-N \equiv M+N \bmod{2}</math>. | ||
+ | |||
+ | Thus, we also have <math>S \equiv a_1+b_1+a_2+b_2+\cdots +a_{999}+b_{999} \equiv 1+2+ \cdots +1998 \equiv 999*1999 \equiv 1 \bmod{2}</math> also, so by the Chinese Remainder Theorem <math>S \equiv 9\bmod{10}</math>. Thus, <math>S</math> ends in the digit 9, as desired. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | FASTEST SOLVE ON STREAM from v_Enhance (:omighty:) | ||
+ | https://www.youtube.com/watch?v=jsw3c3yAn7o | ||
+ | |||
+ | {{USAMO newbox|year=1998|before=First Question|num-a=2}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 10:56, 30 January 2021
Problem
Suppose that the set has been partitioned into disjoint pairs () so that for all , equals or . Prove that the sum ends in the digit .
Solution
Notice that , so .
Also, for integers we have .
Thus, we also have also, so by the Chinese Remainder Theorem . Thus, ends in the digit 9, as desired.
See Also
FASTEST SOLVE ON STREAM from v_Enhance (:omighty:) https://www.youtube.com/watch?v=jsw3c3yAn7o
1998 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.