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 "2020 USOMO Problems/Problem 4"

(Created page with "===Problem 4=== Suppose that <math>(a_1, b_1), (a_2, b_2), \ldots , (a_{100}, b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N</math> denote the...")
 
(→‎Solution)
Line 35: Line 35:
 
<cmath>0+1+2+\ldots+2</cmath>
 
<cmath>0+1+2+\ldots+2</cmath>
 
<math>a_1</math> has <math>0</math> subtractions that follow condition while <math>a_2</math> has <math>1</math> and then the rest has <math>2</math>.
 
<math>a_1</math> has <math>0</math> subtractions that follow condition while <math>a_2</math> has <math>1</math> and then the rest has <math>2</math>.
−
There are <math>N</math> terms, so our answer be <math>2N-3</math> and in case of <math>N=100</math> that means  
+
There are <math>n</math> terms, so our answer be <math>2n-3</math> and in case of <math>n=100</math> that means  
 
<cmath>\boxed{197}.</cmath>~Lopkiloinm
 
<cmath>\boxed{197}.</cmath>~Lopkiloinm

Revision as of 23:47, 8 December 2020

Problem 4

Suppose that $(a_1, b_1), (a_2, b_2), \ldots , (a_{100}, b_{100})$ are distinct ordered pairs of nonnegative integers. Let $N$ denote the number of pairs of integers $(i, j)$ satisfying $1 \le i < j \le 100$ and $|a_ib_j - a_j b_i|=1$. Determine the largest possible value of $N$ over all possible choices of the $100$ ordered pairs.

Solution

Let's start off with just $(a_1, b_1), (a_2, b_2)$ and suppose that it satisfies the given condition. We could use $(1, 1), (1, 2)$ for example. We should maximize the number of conditions that the third pair satisfies. We find out that the third pair should equal $(a_1+a_2, b_1+b_2)$ or $(|a_1-a_2|, |b_1-b_2|)$

We know this must be true: \[|a_1b_2-a_2b_1| = 1\]

So \[a_1b_2-a_2b_1 = \pm1\]

We require the maximum conditions for $(a_3, b_3)$ \[|a_3b_2-a_2b_3| = 1\] \[|a_3b_1-a_1b_3| = 1\]

Then one case can be: \[a_3b_2-a_2b_3 = 1\] \[a_3b_1-a_1b_3 = -1\]

We try to do some stuff such as solving for $a_3$ with manipulations: \[a_3b_2a_1-a_2b_3a_1 = a_1\] \[a_3b_1a_2-a_1b_3a_2 = -a_2\] \[a_3 = a_1+a_2\] \[b_3 = b_1+b_2\]

We showed that 3 pairs are a complete graph, but 4 pairs are not a complete graph. We will now show that \[a_4 = a_1+2a_2\] \[b_4 = b_1+2b_2\] \[a_1b_1+2a_2b_1-a_1b_1-2a_1b_2 = \pm1\] \[2(a_2b_1-a_1b_2) = \pm1\]

This is clearly impossible because RHS must be even. OK, so we done. Not yet. We not solve answer yet. The answer is clearly that: \[0+1+2+\ldots+2\] $a_1$ has $0$ subtractions that follow condition while $a_2$ has $1$ and then the rest has $2$. There are $n$ terms, so our answer be $2n-3$ and in case of $n=100$ that means \[\boxed{197}.\]~Lopkiloinm

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_USOMO_Problems/Problem_4&oldid=139320"