Difference between revisions of "1999 USAMO Problems/Problem 3"

m (Solution)
(Solution: ; formatting, kerning, and another remark)
 
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 not 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=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=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 does <math>k^4\equiv 1</math>??)
+
(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 10: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 (ProblemsResources)
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