Maths Olympiad Prep

Library / /85 of 115

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 1i<j1001 \le i < j \le 100 and aibjajbi=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: a1b2a2b1=1|a_1b_2-a_2b_1| = 1
So a1b2a2b1=1a_1b_2-a_2b_1 = 1
We require the maximum conditions for (a3,b3)(a_3, b_3) a3b2a2b3=1|a_3b_2-a_2b_3| = 1 a3b1a1b3=1|a_3b_1-a_1b_3| = 1
Then one case can be: a3b2a2b3=1a_3b_2-a_2b_3 = 1 a3b1a1b3=1a_3b_1-a_1b_3 = -1
We try to do some stuff such as solving for a3a_3 with manipulations: a3b2a1a2b3a1=a1a_3b_2a_1-a_2b_3a_1 = a_1 a3b1a2a1b3a2=a2a_3b_1a_2-a_1b_3a_2 = -a_2 a3(a1b2a2b1)=a1+a2a_3(a_1b_2-a_2b_1) = a_1+a_2 a3=a1+a2a_3 = a_1+a_2 a3b2b1a2b3b1=b1a_3b_2b_1-a_2b_3b_1 = b_1 a3b1b2a1b3b2=b2a_3b_1b_2-a_1b_3b_2 = -b_2 b3(a1b2a2b1)=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+2a2b1a1b12a1b2=1|a_1b_1+2a_2b_1-a_1b_1-2a_1b_2| = 1 2a2b1a1b2=12|a_2b_1-a_1b_2| = 1
This is clearly impossible because 11 is not even and also a2b1a1b2=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 2n32n-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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.