Maths Olympiad Prep

Library / /77 of 115

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Suppose that (a1,b1),(a_1,b_1), (a2,b2),(a_2,b_2), ,\dots, (a100,b100)(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\leq i<j\leq 100 and aibjajbi=1|a_ib_j-a_jb_i|=1. Determine the largest possible value of NN over all possible choices of the 100100 ordered pairs.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine the largest possible value of N N over all possible choices of 100 distinct ordered pairs of nonnegative integers (ai,bi)(a_i, b_i), we analyze pairs (i,j)(i, j) such that 1i<j1001 \leq i < j \leq 100 and aibjajbi=1|a_i b_j - a_j b_i| = 1.

This problem is connected to finding integer solutions of the equation aibjajbi=1|a_i b_j - a_j b_i| = 1, which is reminiscent of properties related to continued fractions and the modular arithmetic concepts stemming from the determinant of a matrix formed by pairs, emphasizing a relationship akin to Bézout's identity.

### Analysis

For aibjajbi=1|a_i b_j - a_j b_i| = 1 to hold, pairs (ai,bi)(a_i, b_i) and (aj,bj)(a_j, b_j) have to lie near each other on the set of rational slopes aibi\frac{a_i}{b_i}. Particularly, examining Farey sequences, which are sequences of fractions in lowest terms ordered by increasing size, provides insight that pairs of consecutive Farey fractions have such a property related to coprimeness (as their cross product results in ±1\pm1).

### Construction

Consider setting (ai,bi)(a_i, b_i) to follow a sequence derived from the Farey sequence properties of order 100100. Here's the reasoning:

1. Continued Fractions and Farey Sequences: Farey sequences from order nn contain pairs of reduced fractions pq\frac{p}{q} and rs\frac{r}{s} such that psqr=1|ps - qr| = 1, where p<rp < r and q<sq < s.

2. Pairs Formation: The largest Farey sequence using integers k \leq k has approximately 3k2π2\frac{3k^2}{\pi^2} members. Given 100 pairs, each would correspond to nearly equal parts in such a sequence, allowing near-optimal integer pair selections.

3. Maximizing N: Ensuring the unique condition aibjajbi=1|a_i b_j - a_j b_i| = 1 for each of the (1002)=4950 \binom{100}{2} = 4950 possible (i,j) (i,j) pairs involves choosing them to fall rightly upon these continued fraction convergents.

### Calculating N

It turns out through setting and calculation with full exposure of pair properties that the optimal count N N of coprime conditions satisfied, after constructing optimally using the Farey sequence logic discussed, maximizes at:

N=2(99)1=197. N = 2(99) - 1 = 197.

The optimal build results in 197 pairs (i,j)(i,j) where 1i<j1001 \leq i < j \leq 100 are such that aibjajbi=1|a_i b_j - a_j b_i| = 1.

Thus, the largest possible value of N N is:
197. \boxed{197}.

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.