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 "2005 IMO Shortlist Problems/N3"

 
(→‎Problem: double comma fixed)
 
Line 2: Line 2:
  
 
(''Mongolia'')
 
(''Mongolia'')
−
Let <math> \displaystyle a,\, b,\, c,\, d,\, e, </math>, and <math> \displaystyle f </math> be positive integers.  Suppose that the sum <math> \displaystyle S = a+b+c+d+e+f </math> divides both <math> \displaystyle abc + def </math> and <math> \displaystyle ab+bc+ca - de-ef-fd </math>.  Prove that <math> \displaystyle S </math> is composite.
+
Let <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math>, <math>e</math>, and <math>f </math> be positive integers.  Suppose that the sum <math>S = a+b+c+d+e+f </math> divides both <math>abc + def </math> and <math>ab+bc+ca - de-ef-fd </math>.  Prove that <math>S </math> is composite.
  
 
''This was also Problem 1 of the 2nd 2006 German TST, and a problem at the 2006 Indian IMO Training Camp.''
 
''This was also Problem 1 of the 2nd 2006 German TST, and a problem at the 2006 Indian IMO Training Camp.''

Latest revision as of 09:13, 29 August 2011

Problem

(Mongolia) Let $a$, $b$, $c$, $d$, $e$, and $f$ be positive integers. Suppose that the sum $S = a+b+c+d+e+f$ divides both $abc + def$ and $ab+bc+ca - de-ef-fd$. Prove that $S$ is composite.

This was also Problem 1 of the 2nd 2006 German TST, and a problem at the 2006 Indian IMO Training Camp.

Solution

For all integers $\displaystyle x$ we have

$(x+a)(x+b)(x+c) \equiv x^3 + (a+b+c)x^2 + (ab+bc+ca)x + abc \equiv x^3 - (d+e+f)x^2 + (de+ef+fd)x - def$ $\equiv (x-d)(x-e)(x-f) \pmod{S}$,

since each coefficient of the first two polynomials is congruent to the corresponding coefficient of the second two polynomials, mod $\displaystyle S$. Now, suppose $\displaystyle S$ is prime. Since

$(d+a)(d+b)(d+c) \equiv (d-d)(d-e)(d-f) \equiv 0 \pmod{S}$,

one of $\displaystyle d+a, d+b, d+c$ is divisible by $\displaystyle S$, say $\displaystyle d+a$. Since $\displaystyle d,a > 0$, this means $d+a \ge S$. But since $a, \ldots, f$ are positive integers, we then have

$S > d+a \ge S$,

a contradiction. ∎


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Shortlist_Problems/N3&oldid=42033"