1998 USAMO Problems/Problem 1: Difference between revisions

Revision as of 12:34, 4 July 2013

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

If $S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|$ , then $S \equiv 1+1+\cdots + 1 \equiv 999 \equiv 4 \bmod{5}$ .

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

So 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 $S \equiv 9\bmod{10}$ .

Revision as of 08:03, 13 September 2012 view source 1=2 (talk \| contribs) 4,129 edits m →See Also ← Older edit		Revision as of 12:34, 4 July 2013 view source Nathan wailes (talk \| contribs) 2,960 edits No edit summary Newer edit →
Line 14:		Line 14:

	[[Category:Olympiad Number Theory Problems]]		[[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

Revision as of 12:34, 4 July 2013

Problem

Solution

See Also