|
|
| Line 1: |
Line 1: |
| − | ===Problem 4===
| + | #redirect [[2020 USAMO Problems/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 number of pairs of integers <math>(i, j)</math> satisfying <math>1 \le i < j \le 100</math> and <math>|a_ib_j - a_j b_i|=1</math>. Determine the largest possible value of <math>N</math> over all possible choices of the <math>100</math> ordered pairs.
| |
| − | | |
| − | ==Solution==
| |
| − | Let's start off with just <math>(a_1, b_1), (a_2, b_2)</math> and suppose that it satisfies the given condition. We could use <math>(1, 1), (1, 2)</math> for example. We should maximize the number of conditions that the third pair satisfies. We find out that the third pair should equal <math>(a_1+a_2, b_1+b_2)</math> or <math>(|a_1-a_2|, |b_1-b_2|)</math>
| |
| − | | |
| − | We know this must be true:
| |
| − | <cmath>|a_1b_2-a_2b_1| = 1</cmath>
| |
| − | | |
| − | So
| |
| − | <cmath>a_1b_2-a_2b_1 = \pm1</cmath>
| |
| − | | |
| − | We require the maximum conditions for <math>(a_3, b_3)</math>
| |
| − | <cmath>|a_3b_2-a_2b_3| = 1</cmath>
| |
| − | <cmath>|a_3b_1-a_1b_3| = 1</cmath>
| |
| − | | |
| − | Then one case can be:
| |
| − | <cmath>a_3b_2-a_2b_3 = 1</cmath>
| |
| − | <cmath>a_3b_1-a_1b_3 = -1</cmath>
| |
| − | | |
| − | We try to do some stuff such as solving for <math>a_3</math> with manipulations:
| |
| − | <cmath>a_3b_2a_1-a_2b_3a_1 = a_1</cmath>
| |
| − | <cmath>a_3b_1a_2-a_1b_3a_2 = -a_2</cmath>
| |
| − | <cmath>a_3 = a_1+a_2</cmath>
| |
| − | <cmath>b_3 = b_1+b_2</cmath>
| |
| − | | |
| − | We showed that 3 pairs are a complete graph, but 4 pairs are not a complete graph. We will now show that
| |
| − | <cmath>a_4 = a_1+2a_2</cmath>
| |
| − | <cmath>b_4 = b_1+2b_2</cmath>
| |
| − | <cmath>a_1b_1+2a_2b_1-a_1b_1-2a_1b_2 = \pm1</cmath>
| |
| − | <cmath>2(a_2b_1-a_1b_2) = \pm1</cmath>
| |
| − | | |
| − | 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:
| |
| − | <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>.
| |
| − | 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{N=197}.</cmath>~Lopkiloinm
| |
