1998 USAMO Problems/Problem 1: Difference between revisions

Latest revision as of 09:56, 30 January 2021

Problem

Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ( $1\leq i\leq 999$ ) so that for all $i$ , $|a_i-b_i|$ equals $1$ or $6$ . Prove that the sum $|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|$ ends in the digit $9$ .

Solution

Notice that $|a_i - b_i| \equiv 1 \pmod 5$ , so $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}$ .

Also, for integers $M, N$ we have $|M-N| \equiv M-N \equiv M+N \bmod{2}$ .

Thus, we also have $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}$ also, so by the Chinese Remainder Theorem $S \equiv 9\bmod{10}$ . Thus, $S$ ends in the digit 9, as desired.

@@ Line 4: / Line 4: @@
 == Solution ==
-If <math>S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|</math>, then <math>S \equiv 1+1+\cdots + 1 \equiv 999 \equiv 4 (mod 5)</math>.
+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>.
-For integers M, N we have <math>|M-N| \equiv M-N \equiv M+N (mod 2)</math>.
+Also, for integers <math>M, N</math> we have <math>|M-N| \equiv M-N \equiv M+N \bmod{2}</math>.
-So 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 (mod 2)</math> also, so <math>S \equiv 9 (mod 10)</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==
-{{USAMO newbox|year=1998|before=First Problem|num-a=2}}
+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}}

1998 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

1998 USAMO Problems/Problem 1: Difference between revisions

Latest revision as of 09:56, 30 January 2021

Problem

Solution

See Also