Art of Problem Solving
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

1999 USAMO Problems/Problem 3: Difference between revisions

← Older edit
Mathophobia (talk | contribs)
editor
24 edits
 
(4 intermediate revisions by 4 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 <math>\{ \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 \mod(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</math>, 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!?)
why can't you have a,b,c,d = 2,2,2,4 p = 5 r=1? it doesn't say distinct integers


== See Also ==
== See Also ==

Latest revision as of 00:18, 11 November 2024

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!?) why can't you have a,b,c,d = 2,2,2,4 p = 5 r=1? it doesn't say distinct integers

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1999_USAMO_Problems/Problem_3&oldid=233195"