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 "1999 USAMO Problems/Problem 3"
(→‎Solution: ; formatting, kerning, and another remark)
 
(4 intermediate revisions by 3 users not shown)
Line 6: Line 6:
  
 
== Solution ==
 
== Solution ==
−
We see that <math>\{\frac{ra+rb+rc+rd}{p}\}=0</math> means that <math>p|r(a+b+c+d)</math>. Now, since <math>p</math> does nto divide <math>r</math> and <math>p</math> is prime, their GCD is 1 so <math>p|a+b+c+d</math>.
+
We see that <math>\biggl\{\frac{ra+rb+rc+rd}{p}\biggr\}=0</math> means that <math>p|r(a+b+c+d)</math>. Now, since <math>p</math> does not divide <math>r</math> and <math>p</math> is prime, their GCD is 1 so <math>p\mathrel{|}a+b+c+d</math>.
  
−
Since \{ \frac{ra}p \}+\{ \frac{rb}p \}+\{ \frac{rc}p \}+\{ \frac{rd}p \} =2<math>, then we see that they have to represent mods </math>\mod p<math>, and thus, our possible values of </math>p<math> are all such that </math>k^4 \equiv 1 \pmod(p)<math>  for all </math>k<math>. This happens when </math>p=2, 3<math> or </math>5<math>.  
+
Since <math>\biggl\{\frac{ra}{p}\biggr\}+\biggl\{\frac{rb}{p}\biggr\}+\biggl\{\frac{rc}{p}\biggr\}+\biggl\{\frac{rd}{p}\biggr\}=2</math>, then we see that they have to represent mods <math>\bmod\medspace p</math>, and thus, our possible values of <math>p</math> are all such that <math>k^4 \equiv 1\pmod{p}</math>  for all <math>k</math> that are relatively prime to <math>p</math>. This happens when <math>p=3</math> or <math>5</math>.  
  
−
When </math>p=2<math> then </math>r<math> is odd, meaning </math>ra<math>, </math>rb<math>, </math>rc<math> and </math>rd<math> are all 1 mod 2, or the sum wouldn't be 2. Any pairwise sum is 2.
+
When <math>p=3</math> then <math>r</math> is not divisible by 3, thus two are <math>1</math>, and the other two are <math>2</math>. Thus, four pairwise sums sum to 3.
  
−
When </math>p=3<math> then </math>r<math> is not divisible by 3, thus two are </math>1<math>, and the other two are </math>2<math>. Thus, four pairwise sums sum to 3.
+
When <math>p=5</math> then <math>r</math> is not divisible by 5 so <math>a, b, c, d</math> are <math>1, 2, 3,</math> and <math>4</math>, so two pairwise sums sum to 5.
  
−
When </math>p=5<math> then </math>r<math> is not divisible by 5 so </math>a, b, c, d<math> are </math>1, 2, 3<math> and </math>4$, so two pairwise sums sum to 5.
+
All three possible cases work so we are done.
  
−
All three possible cases work so we are done.
+
(This solution makes absolutely no sense. Why is <math>k^4\equiv 1</math>? And how do we know that only <math>3</math> and <math>5</math> work!?)
  
 
== See Also ==
 
== See Also ==

Latest revision as of 11:17, 18 March 2023

Problem

Let $p > 2$ be a prime and let $a,b,c,d$ be integers not divisible by $p$, such that \[\left\{ \dfrac{ra}{p} \right\} + \left\{ \dfrac{rb}{p} \right\} + \left\{ \dfrac{rc}{p} \right\} + \left\{ \dfrac{rd}{p} \right\} = 2\] for any integer $r$ not divisible by $p$. Prove that at least two of the numbers $a+b$, $a+c$, $a+d$, $b+c$, $b+d$, $c+d$ are divisible by $p$. (Note: $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of $x$.)

Solution

We see that $\biggl\{\frac{ra+rb+rc+rd}{p}\biggr\}=0$ means that $p|r(a+b+c+d)$. Now, since $p$ does not divide $r$ and $p$ is prime, their GCD is 1 so $p\mathrel{|}a+b+c+d$.

Since $\biggl\{\frac{ra}{p}\biggr\}+\biggl\{\frac{rb}{p}\biggr\}+\biggl\{\frac{rc}{p}\biggr\}+\biggl\{\frac{rd}{p}\biggr\}=2$, then we see that they have to represent mods $\bmod\medspace p$, and thus, our possible values of $p$ are all such that $k^4 \equiv 1\pmod{p}$ for all $k$ that are relatively prime to $p$. This happens when $p=3$ or $5$.

When $p=3$ then $r$ is not divisible by 3, thus two are $1$, and the other two are $2$. Thus, four pairwise sums sum to 3.

When $p=5$ then $r$ is not divisible by 5 so $a, b, c, d$ are $1, 2, 3,$ and $4$, so two pairwise sums sum to 5.

All three possible cases work so we are done.

(This solution makes absolutely no sense. Why is $k^4\equiv 1$? And how do we know that only $3$ and $5$ work!?)

See Also

1999 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
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=1999_USAMO_Problems/Problem_3&oldid=191068"