Maths Olympiad Prep

Library / USAMO /106 of 156

USAMO

Algebra Difficulty 7.5 National Olympiad, round 2 Find the answer

Suppose that (a1,b1),(a2,b2),…,(a100,b100)(a_1, b_1), (a_2, b_2), \ldots , (a_{100}, b_{100}) are distinct ordered pairs of nonnegative integers. Let NN denote the number of pairs of integers (i,j)(i, j) satisfying 1≤i<j≤1001 \le i < j \le 100 and ∣aibj−ajbi∣=1|a_ib_j - a_j b_i|=1 . Determine the largest possible value of NN over all possible choices of the 100100 ordered pairs.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let's start off with just (a1,b1),(a2,b2)(a_1, b_1), (a_2, b_2) and suppose that it satisfies the given condition. We could use (1,1),(1,2)(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 (a1+a2,b1+b2)(a_1+a_2, b_1+b_2) :
We know this must be true: ∣a1b2−a2b1∣=1|a_1b_2-a_2b_1| = 1
So a1b2−a2b1=1a_1b_2-a_2b_1 = 1
We require the maximum conditions for (a3,b3)(a_3, b_3) ∣a3b2−a2b3∣=1|a_3b_2-a_2b_3| = 1 ∣a3b1−a1b3∣=1|a_3b_1-a_1b_3| = 1
Then one case can be: a3b2−a2b3=1a_3b_2-a_2b_3 = 1 a3b1−a1b3=−1a_3b_1-a_1b_3 = -1
We try to do some stuff such as solving for a3a_3 with manipulations: a3b2a1−a2b3a1=a1a_3b_2a_1-a_2b_3a_1 = a_1 a3b1a2−a1b3a2=−a2a_3b_1a_2-a_1b_3a_2 = -a_2 a3(a1b2−a2b1)=a1+a2a_3(a_1b_2-a_2b_1) = a_1+a_2 a3=a1+a2a_3 = a_1+a_2 a3b2b1−a2b3b1=b1a_3b_2b_1-a_2b_3b_1 = b_1 a3b1b2−a1b3b2=−b2a_3b_1b_2-a_1b_3b_2 = -b_2 b3(a1b2−a2b1)=b1+b2b_3(a_1b_2-a_2b_1) = b_1+b_2 b3=b1+b2b_3 = b_1+b_2
We showed that 3 pairs are a complete graph; however, 4 pairs are not a complete graph. We will now show that: a4=a1+2a2a_4 = a_1+2a_2 b4=b1+2b2b_4 = b_1+2b_2 ∣a1b1+2a2b1−a1b1−2a1b2∣=1|a_1b_1+2a_2b_1-a_1b_1-2a_1b_2| = 1 2∣a2b1−a1b2∣=12|a_2b_1-a_1b_2| = 1
This is clearly impossible because 11 is not even and also ∣a2b1−a1b2∣=1|a_2b_1-a_1b_2| = 1 .
The answer is as follows: 0+1+2+…+20+1+2+\ldots+2 a1a_1 has 00 subtractions that follow condition while a2a_2 has 11 and then the rest has 22 .
There are nn terms, so our answer be 2n−32n-3 and in case of n=100n=100 that means N=197.\boxed{N=197}. ~Lopkiloinm

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.