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 "1997 JBMO Problems/Problem 5"
(Solution to Problem 5 — big blue paw print on modular arithmetic)
Line 4: Line 4:
  
 
== Solution ==
 
== Solution ==
 +
 +
In order to prove that at least two numbers are even, we need to prove that it is impossible to have exactly one number even and that it is impossible to have exactly no numbers even.
 +
 +
<br>
 +
'''Lemma 1: Impossible to have exactly 1 number even'''<br>
 +
Assume one of the numbers is even.  If <math>n_{1998}</math> is even, then the left side is congruent to <math>1</math> modulo <math>2</math> while the right side is congruent to <math>0</math> modulo <math>2,</math> which can not happen.  If one of <math>n_1, n_2, \cdots n_{1997}</math> is even, then the left side is congruent to <math>0</math> modulo <math>2</math> while the right side is congruent to <math>1</math> modulo <math>2,</math> which can not happen.  Thus, it is impossible for exactly one of the numbers to be even.
 +
 +
<br>
 +
'''Lemma 2: Impossible to have all numbers odd'''<br>
 +
Assume all numbers are odd (or that there are no even numbers).  If <math>n_i</math> is odd for <math>1 \le i \le 1998,</math> then <math>n_i^2 \equiv 1 \pmod{8}.</math>  That means the left side is congruent to <math>5</math> modulo <math>8</math> while the right side is congruent to <math>1</math> modulo <math>8.</math>  Since this can not happen, it is impossible for none of the numbers to be even.
 +
 +
<br>
 +
Since it’s impossible to have exactly one or zero even numbers, at least two of the integers must be even.
  
 
== See also ==
 
== See also ==
Line 9: Line 22:
 
{{JBMO box|year=1997|num-b=4|after=Last Problem}}
 
{{JBMO box|year=1997|num-b=4|after=Last Problem}}
  
−
[[Category:Intermediate Number Theory Problems]]
+
[[Category:Olympiad Number Theory Problems]]

Revision as of 20:16, 5 August 2018

Problem

Let $n_1$, $n_2$, $\ldots$, $n_{1998}$ be positive integers such that \[n_1^2 + n_2^2 + \cdots + n_{1997}^2 = n_{1998}^2.\] Show that at least two of the numbers are even.

Solution

In order to prove that at least two numbers are even, we need to prove that it is impossible to have exactly one number even and that it is impossible to have exactly no numbers even.


Lemma 1: Impossible to have exactly 1 number even
Assume one of the numbers is even. If $n_{1998}$ is even, then the left side is congruent to $1$ modulo $2$ while the right side is congruent to $0$ modulo $2,$ which can not happen. If one of $n_1, n_2, \cdots n_{1997}$ is even, then the left side is congruent to $0$ modulo $2$ while the right side is congruent to $1$ modulo $2,$ which can not happen. Thus, it is impossible for exactly one of the numbers to be even.


Lemma 2: Impossible to have all numbers odd
Assume all numbers are odd (or that there are no even numbers). If $n_i$ is odd for $1 \le i \le 1998,$ then $n_i^2 \equiv 1 \pmod{8}.$ That means the left side is congruent to $5$ modulo $8$ while the right side is congruent to $1$ modulo $8.$ Since this can not happen, it is impossible for none of the numbers to be even.


Since it’s impossible to have exactly one or zero even numbers, at least two of the integers must be even.

See also

1997 JBMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5
All JBMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_JBMO_Problems/Problem_5&oldid=96800"