Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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)
 
m (→‎See Also: added yt link to venhance newest vid)
 
(11 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
#REDIRECT [[1998 USAMO Problems/Problem 3]]
+
== 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 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.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_USAMO_Problems/Problem_1&oldid=144040"