Suppose that $(a_1,b_1),$ $(a_2,b_2),$ $\dots,$ $(a_{100},b_{100})$ are distinct ordered pairs of nonnegative integers. Let $N$ denote the number of pairs of integers $(i,j)$ satisfying $1\leq i<j\leq 100$ and $|a_ib_j-a_jb_i|=1$. Determine the largest possible value of $N$ over all possible choices of the $100$ ordered pairs. Proposed by Ankan Bhattacharya
Problem
Source: 2020 USOMO Problem 4, USOJMO Problem 5
Tags: USOMO, usojmo, USO(J)MO, 2020 USAMO, 2020 USAJMO
62861
22.06.2020 02:00
Mine! Quote: Let $(a_1, b_1), \dots, (a_{100}, b_{100})$ be 100 different pairs of nonnegative integers. A pair of integers $(k, \ell)$ with $1 \le k < \ell \le 100$ is friendly if $|a_k b_\ell - a_\ell b_k| = 1$. Determine the maximum possible number of friendly pairs. The answer is $197$. An example achieving $197$ friendly pairs is $(0, 1)$, $(1, 1)$, $(1, 2)$, \dots, $(1, 99)$. Now we prove that $197$ is the best possible. In general, we will prove that for $N \ge 2$ points there are no more than $2N - 3$ friendly pairs. We proceed by induction on $N$, the base case $N = 2$ being obvious. Now consider $N+1$ points $P_1, \dots, P_{N+1}$. Let $O = (0, 0)$ be the origin; then friendly pairs $(P_k, P_\ell)$ correspond to triangles $OP_kP_\ell$ with area $\tfrac{1}{2}$. Suppose $P_{N+1}$ has the largest sum of coordinates. If the coordinates of $P_{N+1}$ are not relatively prime, then this point does not belong to any friendly pairs and the result is obvious. Otherwise, it easily follows that no $\overline{P_iP_j}$ is parallel to $\overline{OP_{N+1}}$. Consequently, there are at most two points $P_i$ satisfying $[OP_iP_{N+1}] = \tfrac{1}{2}$ (one on each side of $\overline{OP_{N+1}}$). To summarize, the point $P_{N+1}$ belongs to at most two friendly pairs and the remaining $N$ points form at most $2N - 3$ friendly pairs by inductive hypothesis, and so together the points form at most $2N - 1$ friendly pairs, as desired. Here is an interesting image, which suggests another solution to this problem. Can you find it?
[asy][asy]
int gcd(int a, int b) {
int c = 0;
if (b > a) {
c = a;
a = b;
b = c;
}
while (b > 0) {
c = b;
b = a - quotient(a,b)*b;
a = c;
}
return a;
}
unitsize(25);
int n = 10;
// Sorry for the following ugly code.
draw((0, 1)--(1, 2));
draw((1, 1)--(1, 2));
draw((0, 1)--(1, 3));
draw((1, 2)--(1, 3));
draw((0, 1)--(1, 4));
draw((1, 3)--(1, 4));
draw((0, 1)--(1, 5));
draw((1, 4)--(1, 5));
draw((0, 1)--(1, 6));
draw((1, 5)--(1, 6));
draw((0, 1)--(1, 7));
draw((1, 6)--(1, 7));
draw((0, 1)--(1, 8));
draw((1, 7)--(1, 8));
draw((0, 1)--(1, 9));
draw((1, 8)--(1, 9));
draw((0, 1)--(1, 10));
draw((1, 9)--(1, 10));
draw((1, 2)--(2, 3));
draw((1, 1)--(2, 3));
draw((1, 3)--(2, 5));
draw((1, 2)--(2, 5));
draw((1, 4)--(2, 7));
draw((1, 3)--(2, 7));
draw((1, 5)--(2, 9));
draw((1, 4)--(2, 9));
draw((2, 3)--(3, 4));
draw((1, 1)--(3, 4));
draw((1, 2)--(3, 5));
draw((2, 3)--(3, 5));
draw((2, 5)--(3, 7));
draw((1, 2)--(3, 7));
draw((1, 3)--(3, 8));
draw((2, 5)--(3, 8));
draw((2, 7)--(3, 10));
draw((1, 3)--(3, 10));
draw((3, 4)--(4, 5));
draw((1, 1)--(4, 5));
draw((1, 2)--(4, 7));
draw((3, 5)--(4, 7));
draw((3, 7)--(4, 9));
draw((1, 2)--(4, 9));
draw((4, 5)--(5, 6));
draw((1, 1)--(5, 6));
draw((2, 3)--(5, 7));
draw((3, 4)--(5, 7));
draw((3, 5)--(5, 8));
draw((2, 3)--(5, 8));
draw((1, 2)--(5, 9));
draw((4, 7)--(5, 9));
draw((5, 6)--(6, 7));
draw((1, 1)--(6, 7));
draw((6, 7)--(7, 8));
draw((1, 1)--(7, 8));
draw((3, 4)--(7, 9));
draw((4, 5)--(7, 9));
draw((2, 3)--(7, 10));
draw((5, 7)--(7, 10));
draw((7, 8)--(8, 9));
draw((1, 1)--(8, 9));
draw((8, 9)--(9, 10));
draw((1, 1)--(9, 10));
draw((1, 0)--(2, 1));
draw((1, 1)--(2, 1));
draw((1, 0)--(3, 1));
draw((2, 1)--(3, 1));
draw((1, 0)--(4, 1));
draw((3, 1)--(4, 1));
draw((1, 0)--(5, 1));
draw((4, 1)--(5, 1));
draw((1, 0)--(6, 1));
draw((5, 1)--(6, 1));
draw((1, 0)--(7, 1));
draw((6, 1)--(7, 1));
draw((1, 0)--(8, 1));
draw((7, 1)--(8, 1));
draw((1, 0)--(9, 1));
draw((8, 1)--(9, 1));
draw((1, 0)--(10, 1));
draw((9, 1)--(10, 1));
draw((2, 1)--(3, 2));
draw((1, 1)--(3, 2));
draw((3, 1)--(5, 2));
draw((2, 1)--(5, 2));
draw((4, 1)--(7, 2));
draw((3, 1)--(7, 2));
draw((5, 1)--(9, 2));
draw((4, 1)--(9, 2));
draw((3, 2)--(4, 3));
draw((1, 1)--(4, 3));
draw((2, 1)--(5, 3));
draw((3, 2)--(5, 3));
draw((5, 2)--(7, 3));
draw((2, 1)--(7, 3));
draw((3, 1)--(8, 3));
draw((5, 2)--(8, 3));
draw((7, 2)--(10, 3));
draw((3, 1)--(10, 3));
draw((4, 3)--(5, 4));
draw((1, 1)--(5, 4));
draw((2, 1)--(7, 4));
draw((5, 3)--(7, 4));
draw((7, 3)--(9, 4));
draw((2, 1)--(9, 4));
draw((5, 4)--(6, 5));
draw((1, 1)--(6, 5));
draw((3, 2)--(7, 5));
draw((4, 3)--(7, 5));
draw((5, 3)--(8, 5));
draw((3, 2)--(8, 5));
draw((2, 1)--(9, 5));
draw((7, 4)--(9, 5));
draw((6, 5)--(7, 6));
draw((1, 1)--(7, 6));
draw((7, 6)--(8, 7));
draw((1, 1)--(8, 7));
draw((4, 3)--(9, 7));
draw((5, 4)--(9, 7));
draw((3, 2)--(10, 7));
draw((7, 5)--(10, 7));
draw((8, 7)--(9, 8));
draw((1, 1)--(9, 8));
draw((9, 8)--(10, 9));
draw((1, 1)--(10, 9));
draw((0, 1)--(1, 0));
draw((0, 1)--(1, 1));
draw((1, 1)--(1, 0));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dot((i, j), gcd(i, j) == 1 ? black : gray(0.7));
label("0", (0, 0), dir(225), fontsize(10pt));
for (int i = 1; i <= n; ++i) {
label(string(i), (i, 0), dir(270), fontsize(10pt));
label(string(i), (0, i), dir(180), fontsize(10pt));
}
[/asy][/asy]
spartacle
22.06.2020 02:03
Here's an interesting geometric solution I found. Does that make this an A/C/G/N hybrid?
Replace $100$ with $n$. We claim the answer is $2n-3$. One construction is $(1,1), (1,2), (2,3), \ldots, (n-1,n)$, but I accidentally found the construction $(a_i, b_i) = (F_i, F_{i+1})$ where $F_i$ is the $i$-th Fibonacci number.
WLOG $a_1 + b_1 \le a_2 + b_2 \le \ldots \le a_n + b_n$.
Key claim: Given $a_i, b_i$, there exist at most two pairs of nonnegative integers $a_j, b_j$ with $a_j + b_j \le a_i + b_i$ and $|a_ib_j - a_jb_i| = 1$
Proof: Use the coordinate plane.
Let $A = (0,0), B = (a_i + b_i, 0), C = (0, a_i + b_i), P = (a_i, b_i)$.
Recall that $|x_1y_2 - x_2y_1|$ is twice the area of the triangle formed by $(x_1, y_1)$, $(x_2, y_2)$, and $(0,0)$. Thus the locus of points $(x,y)$ with $|a_1y - xb_1| = 1$ is two lines parallel to $AP$. Call these lines $\ell_1$ and $\ell_2$, and WLOG $\ell_1$ is on the same side of $AP$ as $B$.
Diagram:
[asy][asy]
pair A = origin;
pair B = (5,0);
pair C = (0,5);
pair P = (3,2);
pair L11 = (5,3);
pair L12 = (-1,-1);
pair L21 = (4,3);
pair L22 = (-2,-1);
draw(A--B--C--cycle);
draw(L11--L12, red);
draw(L21--L22, red);
draw(A--P, green);
pair X = extension(L11, L12, A, B);
pair Y = extension(L11, L12, B, C);
dot("$P$", P, dir(35));
dot("$A$", A, dir(215));
dot("$B$", B, dir(330));
dot("$C$", C, dir(90));
dot("$X$", X, dir(315));
dot("$Y$", Y, dir(0));
[/asy][/asy]
Let $\ell_1$ intersect $AB$ and $BC$ at $X$ and $Y$, respectively. It suffices to show that there is at most one lattice point on segment $XY$, since then the analogous statement for $\ell_2$ holds and we are done.
First, note that $\gcd(a_i, b_i) \mid |a_iy - b_jx|$ for all integers $x, y$ so if $\gcd(a_i, b_i) \neq 1$ we are done. Thus assume $\gcd(a_i, b_i) = 1$. This means that there are no lattice points in the interior of $AP$.
Because $XY \parallel AP$, if $XY < AP$, then clearly segment $XY$ contains at most one lattice point. But we have
$$\frac{XY}{AP} = \frac{BX}{AB} < 1$$
so we are done.
Thus the claim is proven. Now, take each pair $(i, j)$ with $i < j$ and $|a_ib_j - a_jb_i| = 1$ and write the number $j$ on a list. By the claim, when the list is complete, it contains each integer at most twice. Further, it clearly doesn't contain the integer $1$, and contains the integer $2$ at most once, so we have
$$N \le 2(n-2) + 0 + 1 = 2n-3$$
and we are done.
Relatively nice problem. It took me longer than average to solve for a P4.
yayups
22.06.2020 02:04
Feels quite similar to RMM 2020/5 in my opinion.
MortemEtInteritum
22.06.2020 02:05
CantonMathGuy wrote: Mine! Quote: Let $(a_1, b_1), \dots, (a_{100}, b_{100})$ be 100 different pairs of nonnegative integers. A pair of integers $(k, \ell)$ with $1 \le k < \ell \le 100$ is friendly if $|a_k b_\ell - a_\ell b_k| = 1$. Determine the maximum possible number of friendly pairs. The answer is $197$. An example achieving $197$ friendly pairs is $(0, 1)$, $(1, 1)$, $(1, 2)$, \dots, $(1, 99)$. Now we prove that $197$ is the best possible. In general, we will prove that for $N \ge 2$ points there are no more than $2N - 3$ friendly pairs. We proceed by induction on $N$, the base case $N = 2$ being obvious. Now consider $N+1$ points $P_1, \dots, P_{N+1}$. Let $O = (0, 0)$ be the origin; then friendly pairs $(P_k, P_\ell)$ correspond to triangles $OP_kP_\ell$ with area $\tfrac{1}{2}$. Suppose $P_{N+1}$ has the largest sum of coordinates. If the coordinates of $P_{N+1}$ are not relatively prime, then this point does not belong to any friendly pairs and the result is obvious. Otherwise, it easily follows that no $\overline{P_iP_j}$ is parallel to $\overline{OP_{N+1}}$. Consequently, there are at most two points $P_i$ satisfying $[OP_iP_{N+1}] = \tfrac{1}{2}$ (one on each side of $\overline{OP_{N+1}}$). To summarize, the point $P_{N+1}$ belongs to at most two friendly pairs and the remaining $N$ points form at most $2N - 3$ friendly pairs by inductive hypothesis, and so together the points form at most $2N - 1$ friendly pairs, as desired. Here is an interesting image, which suggests another solution to this problem. Can you find it?
[asy][asy]
int gcd(int a, int b) {
int c = 0;
if (b > a) {
c = a;
a = b;
b = c;
}
while (b > 0) {
c = b;
b = a - quotient(a,b)*b;
a = c;
}
return a;
}
unitsize(25);
int n = 10;
// Sorry for the following ugly code.
draw((0, 1)--(1, 2));
draw((1, 1)--(1, 2));
draw((0, 1)--(1, 3));
draw((1, 2)--(1, 3));
draw((0, 1)--(1, 4));
draw((1, 3)--(1, 4));
draw((0, 1)--(1, 5));
draw((1, 4)--(1, 5));
draw((0, 1)--(1, 6));
draw((1, 5)--(1, 6));
draw((0, 1)--(1, 7));
draw((1, 6)--(1, 7));
draw((0, 1)--(1, 8));
draw((1, 7)--(1, 8));
draw((0, 1)--(1, 9));
draw((1, 8)--(1, 9));
draw((0, 1)--(1, 10));
draw((1, 9)--(1, 10));
draw((1, 2)--(2, 3));
draw((1, 1)--(2, 3));
draw((1, 3)--(2, 5));
draw((1, 2)--(2, 5));
draw((1, 4)--(2, 7));
draw((1, 3)--(2, 7));
draw((1, 5)--(2, 9));
draw((1, 4)--(2, 9));
draw((2, 3)--(3, 4));
draw((1, 1)--(3, 4));
draw((1, 2)--(3, 5));
draw((2, 3)--(3, 5));
draw((2, 5)--(3, 7));
draw((1, 2)--(3, 7));
draw((1, 3)--(3, 8));
draw((2, 5)--(3, 8));
draw((2, 7)--(3, 10));
draw((1, 3)--(3, 10));
draw((3, 4)--(4, 5));
draw((1, 1)--(4, 5));
draw((1, 2)--(4, 7));
draw((3, 5)--(4, 7));
draw((3, 7)--(4, 9));
draw((1, 2)--(4, 9));
draw((4, 5)--(5, 6));
draw((1, 1)--(5, 6));
draw((2, 3)--(5, 7));
draw((3, 4)--(5, 7));
draw((3, 5)--(5, 8));
draw((2, 3)--(5, 8));
draw((1, 2)--(5, 9));
draw((4, 7)--(5, 9));
draw((5, 6)--(6, 7));
draw((1, 1)--(6, 7));
draw((6, 7)--(7, 8));
draw((1, 1)--(7, 8));
draw((3, 4)--(7, 9));
draw((4, 5)--(7, 9));
draw((2, 3)--(7, 10));
draw((5, 7)--(7, 10));
draw((7, 8)--(8, 9));
draw((1, 1)--(8, 9));
draw((8, 9)--(9, 10));
draw((1, 1)--(9, 10));
draw((1, 0)--(2, 1));
draw((1, 1)--(2, 1));
draw((1, 0)--(3, 1));
draw((2, 1)--(3, 1));
draw((1, 0)--(4, 1));
draw((3, 1)--(4, 1));
draw((1, 0)--(5, 1));
draw((4, 1)--(5, 1));
draw((1, 0)--(6, 1));
draw((5, 1)--(6, 1));
draw((1, 0)--(7, 1));
draw((6, 1)--(7, 1));
draw((1, 0)--(8, 1));
draw((7, 1)--(8, 1));
draw((1, 0)--(9, 1));
draw((8, 1)--(9, 1));
draw((1, 0)--(10, 1));
draw((9, 1)--(10, 1));
draw((2, 1)--(3, 2));
draw((1, 1)--(3, 2));
draw((3, 1)--(5, 2));
draw((2, 1)--(5, 2));
draw((4, 1)--(7, 2));
draw((3, 1)--(7, 2));
draw((5, 1)--(9, 2));
draw((4, 1)--(9, 2));
draw((3, 2)--(4, 3));
draw((1, 1)--(4, 3));
draw((2, 1)--(5, 3));
draw((3, 2)--(5, 3));
draw((5, 2)--(7, 3));
draw((2, 1)--(7, 3));
draw((3, 1)--(8, 3));
draw((5, 2)--(8, 3));
draw((7, 2)--(10, 3));
draw((3, 1)--(10, 3));
draw((4, 3)--(5, 4));
draw((1, 1)--(5, 4));
draw((2, 1)--(7, 4));
draw((5, 3)--(7, 4));
draw((7, 3)--(9, 4));
draw((2, 1)--(9, 4));
draw((5, 4)--(6, 5));
draw((1, 1)--(6, 5));
draw((3, 2)--(7, 5));
draw((4, 3)--(7, 5));
draw((5, 3)--(8, 5));
draw((3, 2)--(8, 5));
draw((2, 1)--(9, 5));
draw((7, 4)--(9, 5));
draw((6, 5)--(7, 6));
draw((1, 1)--(7, 6));
draw((7, 6)--(8, 7));
draw((1, 1)--(8, 7));
draw((4, 3)--(9, 7));
draw((5, 4)--(9, 7));
draw((3, 2)--(10, 7));
draw((7, 5)--(10, 7));
draw((8, 7)--(9, 8));
draw((1, 1)--(9, 8));
draw((9, 8)--(10, 9));
draw((1, 1)--(10, 9));
draw((0, 1)--(1, 0));
draw((0, 1)--(1, 1));
draw((1, 1)--(1, 0));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dot((i, j), gcd(i, j) == 1 ? black : gray(0.7));
label("0", (0, 0), dir(225), fontsize(10pt));
for (int i = 1; i <= n; ++i) {
label(string(i), (i, 0), dir(270), fontsize(10pt));
label(string(i), (0, i), dir(180), fontsize(10pt));
}
[/asy][/asy]
Wow...I spent like 30 minutes finding using $(F_0, F_1), (F_1, F_2), ...(F_{99}, F_{100})$ and proving that worked (where F is fibonacci numbers). Anyways, so I claimed (and proved) that there is some arrangement of the pairs (note that rearranging doesn't affect N) such that for each fixed 1<=j<=100, there are at most 2 values of i less than j such that (i, j) is friendly. Obviously for j=1 there's no friendly pairs where i<j, and for j=2 there's at most 1 pair, but I didn't state this part. Instead just directly went from the claim to "N is at most 199" (oops, 2*98+1=199). Would this be 7- or 0+?
Potato12
22.06.2020 02:05
First, we realize that if we take the equation mod 2, we must have any pair which satisfies the given conditions to be either (1, 1), (0, 1) or (1, 0) mod 2. Furthermore, (0, 0) can never be a possible mod 2 pair satisfying the equation. Thus the graph between pairs (where edges are two pairs which work) must be mostly triangles and no complete graphs with four verticies. By Turan's Theorem the maximum number of edges is $$\left( 1-\frac{2}{3} \right) \cdot 100^2 = 3333 \frac{1}{3}$$, so the answer is 3333.
Emathmaster
22.06.2020 02:07
Extremal principle and solving diophantine. At ech step we add at most 2 expect in a special case 3.
Overall, I liked this problem, altough my solution was too long.
Twistya
22.06.2020 02:08
This was also JMO 5. I did everything without realizing there was a geometric counterpart, fun times. Took way too long to realize Fibonacci is a solution but also (1,1) with (2,3), (3,4), (4,5) etc. works too.
dchenmathcounts
22.06.2020 02:09
I'm dumb. I got the right numerical answer but started walking in circles. I tried to prove that if $(i,j)$ and $(i,k)$ were friendly, then $(j,k)$ was friendly iff two sets were the sum of the third. (think of them as vectors) Expecting 1 at most.
277546
22.06.2020 02:13
Fun fact: Fibonacci sequence for the $(a_i,b_i)$ gives the optimal! So does the Farey sequence!
Tommy2002
22.06.2020 02:14
Hmm I used Farey sequences, which had lots of cancer involved because the fractions were greater than $1$ and the annoying case of $\frac 10$, but overall you can sort by second value in pair and add them in one by one.
TwilightZone
22.06.2020 02:14
how much points do u get if u got the rgight answer showed the construction, and said some other things??
KillerOrca2015
22.06.2020 02:14
Tommy2002 wrote: Hmm I used Farey sequences, which had lots of cancer involved because the fractions were greater than $1$ and the annoying case of $\frac 10$, but overall you can sort by second value in pair and add them in one by one. just consider a/(a+b) instead of a/b, cleans up everything nicely
ETS1331
22.06.2020 02:15
MortemEtInteritum wrote:
CantonMathGuy wrote:
Mine!
Quote:
Let $(a_1, b_1), \dots, (a_{100}, b_{100})$ be 100 different pairs of nonnegative integers. A pair of integers $(k, \ell)$ with $1 \le k < \ell \le 100$ is friendly if $|a_k b_\ell - a_\ell b_k| = 1$. Determine the maximum possible number of friendly pairs.
The answer is $197$. An example achieving $197$ friendly pairs is $(0, 1)$, $(1, 1)$, $(1, 2)$, \dots, $(1, 99)$.
Now we prove that $197$ is the best possible. In general, we will prove that for $N \ge 2$ points there are no more than $2N - 3$ friendly pairs.
We proceed by induction on $N$, the base case $N = 2$ being obvious. Now consider $N+1$ points $P_1, \dots, P_{N+1}$. Let $O = (0, 0)$ be the origin; then friendly pairs $(P_k, P_\ell)$ correspond to triangles $OP_kP_\ell$ with area $\tfrac{1}{2}$.
Suppose $P_{N+1}$ has the largest sum of coordinates. If the coordinates of $P_{N+1}$ are not relatively prime, then this point does not belong to any friendly pairs and the result is obvious.
Otherwise, it easily follows that no $\overline{P_iP_j}$ is parallel to $\overline{OP_{N+1}}$. Consequently, there are at most two points $P_i$ satisfying $[OP_iP_{N+1}] = \tfrac{1}{2}$ (one on each side of $\overline{OP_{N+1}}$).
To summarize, the point $P_{N+1}$ belongs to at most two friendly pairs and the remaining $N$ points form at most $2N - 3$ friendly pairs by inductive hypothesis, and so together the points form at most $2N - 1$ friendly pairs, as desired.
Here is an interesting image, which suggests another solution to this problem. Can you find it?
Image[asy][asy]
int gcd(int a, int b) {
int c = 0;
if (b > a) {
c = a;
a = b;
b = c;
}
while (b > 0) {
c = b;
b = a - quotient(a,b)*b;
a = c;
}
return a;
}
unitsize(25);
int n = 10;
// Sorry for the following ugly code.
draw((0, 1)--(1, 2));
draw((1, 1)--(1, 2));
draw((0, 1)--(1, 3));
draw((1, 2)--(1, 3));
draw((0, 1)--(1, 4));
draw((1, 3)--(1, 4));
draw((0, 1)--(1, 5));
draw((1, 4)--(1, 5));
draw((0, 1)--(1, 6));
draw((1, 5)--(1, 6));
draw((0, 1)--(1, 7));
draw((1, 6)--(1, 7));
draw((0, 1)--(1, 8));
draw((1, 7)--(1, 8));
draw((0, 1)--(1, 9));
draw((1, 8)--(1, 9));
draw((0, 1)--(1, 10));
draw((1, 9)--(1, 10));
draw((1, 2)--(2, 3));
draw((1, 1)--(2, 3));
draw((1, 3)--(2, 5));
draw((1, 2)--(2, 5));
draw((1, 4)--(2, 7));
draw((1, 3)--(2, 7));
draw((1, 5)--(2, 9));
draw((1, 4)--(2, 9));
draw((2, 3)--(3, 4));
draw((1, 1)--(3, 4));
draw((1, 2)--(3, 5));
draw((2, 3)--(3, 5));
draw((2, 5)--(3, 7));
draw((1, 2)--(3, 7));
draw((1, 3)--(3, 8));
draw((2, 5)--(3, 8));
draw((2, 7)--(3, 10));
draw((1, 3)--(3, 10));
draw((3, 4)--(4, 5));
draw((1, 1)--(4, 5));
draw((1, 2)--(4, 7));
draw((3, 5)--(4, 7));
draw((3, 7)--(4, 9));
draw((1, 2)--(4, 9));
draw((4, 5)--(5, 6));
draw((1, 1)--(5, 6));
draw((2, 3)--(5, 7));
draw((3, 4)--(5, 7));
draw((3, 5)--(5, 8));
draw((2, 3)--(5, 8));
draw((1, 2)--(5, 9));
draw((4, 7)--(5, 9));
draw((5, 6)--(6, 7));
draw((1, 1)--(6, 7));
draw((6, 7)--(7, 8));
draw((1, 1)--(7, 8));
draw((3, 4)--(7, 9));
draw((4, 5)--(7, 9));
draw((2, 3)--(7, 10));
draw((5, 7)--(7, 10));
draw((7, 8)--(8, 9));
draw((1, 1)--(8, 9));
draw((8, 9)--(9, 10));
draw((1, 1)--(9, 10));
draw((1, 0)--(2, 1));
draw((1, 1)--(2, 1));
draw((1, 0)--(3, 1));
draw((2, 1)--(3, 1));
draw((1, 0)--(4, 1));
draw((3, 1)--(4, 1));
draw((1, 0)--(5, 1));
draw((4, 1)--(5, 1));
draw((1, 0)--(6, 1));
draw((5, 1)--(6, 1));
draw((1, 0)--(7, 1));
draw((6, 1)--(7, 1));
draw((1, 0)--(8, 1));
draw((7, 1)--(8, 1));
draw((1, 0)--(9, 1));
draw((8, 1)--(9, 1));
draw((1, 0)--(10, 1));
draw((9, 1)--(10, 1));
draw((2, 1)--(3, 2));
draw((1, 1)--(3, 2));
draw((3, 1)--(5, 2));
draw((2, 1)--(5, 2));
draw((4, 1)--(7, 2));
draw((3, 1)--(7, 2));
draw((5, 1)--(9, 2));
draw((4, 1)--(9, 2));
draw((3, 2)--(4, 3));
draw((1, 1)--(4, 3));
draw((2, 1)--(5, 3));
draw((3, 2)--(5, 3));
draw((5, 2)--(7, 3));
draw((2, 1)--(7, 3));
draw((3, 1)--(8, 3));
draw((5, 2)--(8, 3));
draw((7, 2)--(10, 3));
draw((3, 1)--(10, 3));
draw((4, 3)--(5, 4));
draw((1, 1)--(5, 4));
draw((2, 1)--(7, 4));
draw((5, 3)--(7, 4));
draw((7, 3)--(9, 4));
draw((2, 1)--(9, 4));
draw((5, 4)--(6, 5));
draw((1, 1)--(6, 5));
draw((3, 2)--(7, 5));
draw((4, 3)--(7, 5));
draw((5, 3)--(8, 5));
draw((3, 2)--(8, 5));
draw((2, 1)--(9, 5));
draw((7, 4)--(9, 5));
draw((6, 5)--(7, 6));
draw((1, 1)--(7, 6));
draw((7, 6)--(8, 7));
draw((1, 1)--(8, 7));
draw((4, 3)--(9, 7));
draw((5, 4)--(9, 7));
draw((3, 2)--(10, 7));
draw((7, 5)--(10, 7));
draw((8, 7)--(9, 8));
draw((1, 1)--(9, 8));
draw((9, 8)--(10, 9));
draw((1, 1)--(10, 9));
draw((0, 1)--(1, 0));
draw((0, 1)--(1, 1));
draw((1, 1)--(1, 0));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dot((i, j), gcd(i, j) == 1 ? black : gray(0.7));
label("0", (0, 0), dir(225), fontsize(10pt));
for (int i = 1; i <= n; ++i) {
label(string(i), (i, 0), dir(270), fontsize(10pt));
label(string(i), (0, i), dir(180), fontsize(10pt));
}
[/asy][/asy]
Wow...I spent like 30 minutes finding using $(F_0, F_1), (F_1, F_2), ...(F_{99}, F_{100})$ and proving that worked (where F is fibonacci numbers). Anyways, so I claimed (and proved) that there is some arrangement of the pairs (note that rearranging doesn't affect N) such that for each fixed 1<=j<=100, there are at most 2 values of i less than j such that (i, j) is friendly. Obviously for j=1 there's no friendly pairs where i<j, and for j=2 there's at most 1 pair, but I didn't state this part. Instead just directly went from the claim to "N is at most 199" (oops, 2*98+1=199). Would this be 7- or 0+?
I have the exact same question, and almost the exact same solution (I inducted by setting $a_1 < a_2 < a_3 < ... < a_n$ and showing $a_n$ could only have two solutions); could someone answer this question? @(many) below: I also got that the answer was 199; I'm wondering how many points I lose.
Inconsistent
22.06.2020 02:15
Use a graph, induction works if there is never a graph such that all points have degree 3 or more. We take the extremal point $(a_i,b_i)$ such that $a_i$ is maximal, and it is connected to three points. By pigeonhole two of these have the same sign so $\frac{a_i}{b_i}=\frac{a_j-a_k}{b_j-b_k}$ however $a_i$ is maximal and in a irreducible fraction, therefore using some extra casework to deal with extra cases where there are multiple maximal values or 0 values or the two other fraction $a_i$s are equal quickly solves the problem.
Emathmaster
22.06.2020 02:17
TwilightZone wrote: TwilightZone wrote: how much points do u get if u got the rgight answer showed the construction, and said some other things?? I really need to know pleaseeeeeee 1-2
lifeisgood03
22.06.2020 02:17
ETS1331 wrote: I have the exact same question, and almost the exact same solution (I inducted by setting $a_1 < a_2 < a_3 < ... < a_n$ and showing $a_n$ could only have two solutions); could someone answer this question? Yea this is basically correct except you can't say the ineqs are strict, if they are equal you want to sort by y-coordinate.
franchester
22.06.2020 02:17
TwilightZone wrote: TwilightZone wrote: how much points do u get if u got the rgight answer showed the construction, and said some other things?? I really need to know pleaseeeeeee I doubt answer+construction would be worth a point
MortemEtInteritum
22.06.2020 02:18
ETS1331 wrote: MortemEtInteritum wrote:
Wow...I spent like 30 minutes finding using $(F_0, F_1), (F_1, F_2), ...(F_{99}, F_{100})$ and proving that worked (where F is fibonacci numbers). Anyways, so I claimed (and proved) that there is some arrangement of the pairs (note that rearranging doesn't affect N) such that for each fixed 1<=j<=100, there are at most 2 values of i less than j such that (i, j) is friendly. Obviously for j=1 there's no friendly pairs where i<j, and for j=2 there's at most 1 pair, but I didn't state this part. Instead just directly went from the claim to "N is at most 199" (oops, 2*98+1=199). Would this be 7- or 0+
I have the exact same question, and almost the exact same solution (I inducted by setting $a_1 < a_2 < a_3 < ... < a_n$ and showing $a_n$ could only have two solutions); could someone answer this question? Did you make the same mistakes too? Weird coincidence lol. I'm fairly confident that (my) solution would have gotten full points if I hadn't made those mistakes, so if you didn't you should be good. Edit: Oh yeah, can't assume inequalities are strict. I rearranged them so that if we had $a_i=a_j$ for some i<j, then $b_i<b_j$ franchester wrote: TwilightZone wrote: TwilightZone wrote: how much points do u get if u got the rgight answer showed the construction, and said some other things?? I really need to know pleaseeeeeee I doubt answer+construction would be worth a point Really? I thought coming up with just the answer was pretty tricky. Also thought construction was really tricky, but that's just because I did the Fibonacci numbers lol.
awang11
22.06.2020 02:19
oops showed that multiples are bad and then did $\frac{a_1}{b_1} > \frac{a_2}{b_2} > ... > $ but maybe still worked idk
qwerty137
26.06.2020 08:26
Oops I misread djmathman's question and got scared when I realized it so I deleted my previous post. I'm pretty sure Evan's solution along with the construction using Fibonacci numbers can be used to address the version where all points have to be in the first quadrant? I might be misreading things though. There's another variant, which I initially misread the above as before reading the parenthetical text, where you completely disregard any restrictions on where the lattice points can be (i.e. the coordinates just have to be integers), though this one seems quite hard. Here's my progress for that version: There's a way to achieve $4n-12$ for $n\geq 5$: Simply start with $(1, 0)$, $(-1, 0)$, $(0, 1)$, and then start adding $(1, 1)$, $(-1, -1)$, $(2, 1)$, $(-2, -1)$, $\dots$, $(\pm(\lfloor n/2\rfloor -1), \pm 1)$ (where you insert the positive version when $n$ is even, the negative version when $n$ is odd; this is arbitrary but you must add one version right after you add the other version). If we call a pair of points satisfying the condition friendly (as in post 2), note that every pair of points out of the first $5$, besides the two pairs that form a line through the origin, are friendly, and whenever you add $(\pm(\lfloor n/2\rfloor -1), \pm 1)$, $4$ additional friendly pairs are formed, between that point and $(1, 0)$, $(-1, 0)$, $(\lfloor n/2\rfloor -2, 1)$, and $(2-\lfloor n/2\rfloor, -1)$. This is probably anywhere from $0$ to $2$ off from the optimal, depending on if you can form $6$ pairs for the $n=4$ case and/or $9$ or $10$ for the $n=5$ case; you can probably adapt the "farthest point" argument to show that you can only add $4$ additional pairs every step.
opptoinfinity
28.06.2020 10:34
CantonMathGuy wrote: The first solution I found involved Ford circles: throw out any points with $\gcd(x, y) > 1$, apply a (special) linear transform to place all points in the range $0 < y < x$, and identify $(x, y)$ with the Ford circle corresponding to $\tfrac yx$. It's known that Ford circles don't overlap and the circles corresponding to $\tfrac ab$ and $\tfrac cd$ are tangent iff $|ad - bc| = 1$, which implies that the underlying graph is outerplanar. I only noticed the extremal Farey-style argument later. I think it's quite interesting that the infinite graph in #2 is also planar (in the sense that no two drawn edges cross), and the problem can also be solved using this idea. An extension: How many possible sets of $100$ points include both $(1, 0)$ and $(0, 1)$ and give a total of $N = 197$? Can you please discuss what books did you followed during your IMO preparation days ?
mathlogician
30.07.2020 06:41
Solved this a while ago when mocking JMO, but decided to write up now. The answer is $\boxed{197}$, and my construction is the same as everyone else. Now replace $100$ with $n$, and we prove that $N \leq 2n-3$. We do this by induction. The idea is to consider the ordered pair $(a_i,b_i)$, where $b_i$ is the largest possible. It suffices to show that there exists at most two other ordered pairs $(a_k, b_k)$ over all $k$ satisfy $|a_ib_k - a_kb_i| = 1$. Now suppose that $a_ib_k - a_kb_i = 1$, and the other case is handled similarly. I claim that there is only at most one possible ordered pair $(a_k,b_k)$. Note that the equation is equal to $a_ib_k \equiv 1 \pmod {b_i}$. This implies that since $b_i$ is the maximum over all $b$, we know that there is at most $1$ possible value of $b_k$. Now $a_k$ is also determined exclusively by $a_i, b_i, b_k$, and similar idea works for $a_ib_k - a_kb_i = -1$, so we're done.
jj_ca888
05.03.2021 08:47
I put this off for a year. But it's a good problem. We take the geometric interpretation - $100$ lattice points $P_i$ in the nonnegative coordinate plane, maximize the number of triangles $OP_iP_j$ with area $\tfrac12$. I claim our answer for $n$ points in general is $2n-3$. This can be done with the points $(0, 1), (1, 1), (1, 2), \ldots , (1, n-1)$. We will induct on $n$. The base case of $n = 2$ is easy, at most $1$ such triangle exists. Next, suppose the result is true for some $n = k$. We have $k+1$ points $P_1, P_2, \ldots , P_{k+1}$. Pick the point $P_i = (x, y)$ furthest from the origin. It suffices to show that there are at most $2$ other points $P_j, P_k$ that form triangles with area $\tfrac12$ with $O, P_i$. If $\gcd(x, y) \neq 1$, then there are $0$ other points, done. So we may assume $x, y$ are relatively prime. Suppose there are two points $P_a, P_b$ on the same side of segment $OP_i$ that form triangles of area $\tfrac12$ with it. They must both be in the first quadrant, where WLOG $P_a = (a_1, a_2)$ is closer to $O$, then $P_b = (a_1 + kx, a_2 + ky)$ for some positive integer $k$. Then, $|OP_b| > |OP_i|$, contradicting maximality. Hence, there is at most one such point on each side of the segment, for a total of at most $2$ other points $P_j$ and $P_k$. Indeed, among the remaining $k$ points, there are at most $2k-3$ total $\tfrac12$ area triangles, so for this set of $k+1$ points, there is a total of\[T \leq (2k-3) + 2 = 2k-1\]completing our induction. $\blacksquare$
Spacesam
03.04.2021 03:48
We claim that the answer is $197$. As a construction, take $(1, 0), (1, 1), (2, 1), \cdots, (99, 1)$. Because I only do geometry problems, we visualize the problem as asking about the maximum number of area $\frac{1}{2}$ triangles we can make with the origin and two other coordinates. Now, the idea is that we will generalize to $n$ points achieving $2n - 3$ good triangles, and induct down by deleting an element. Take the element with with coordinates $(x, y)$ such that $x + y$ is maximal. If there are more than one achieving the maximal value, then take the one with greatest x coordinate. Also, let $a_i + b_i = k$ be a potential other point that $(x, y)$ can make a good triangle with, and let $x + y = m$. Thus we calculate area: \begin{align*} [\text{good}] &= | x(k - a_i) - a_i(m - x) | \\ &= | kx - xa_i - ma_i + a_ix| \\ &= | kx - ma_i| = 1. \end{align*}From here we have two cases: $kx - ma_i = 1$ which yields $a_i = \frac{kx - 1}{m}$, or $kx - ma_i = -1$ which yields $a_i = \frac{kx + 1}{m}$. Analyze the first case first. For there to be a solution, we require $kx \equiv 1\pmod m$. Let $x^{-1}$ be the modular inverse of $x\pmod m$. Since $k \leq m$, we know that there is at most one value of $k$ for which this is satisfied. Similarly, the other case yields $k(-x) \equiv 1\pmod m$, which also has at most one value of $k$ where it obtains the inverse. Thus the point with maximal $x + y$ for its coordinates is in at most $2$ triangles, so we can delete them and induct downwards. The base cases of $n = 2$ and $n = 3$ are obvious, so we are done.
AwesomeYRY
01.09.2021 19:02
We claim that for $n\geq 2$ points, the optimal number is $2n-3$. The construction is when $(a_i,b_i) = (F_i, F_{i+1})$ where $F_k$ is the Fibonacci sequence. This works because it is well known that \[F_{k-1}F_{k+1}-F_k^2 = (-1)^k\] To prove this is optimal, we proceed with induction. The base case $n=2$ is clearly true, there is only 1 possible pair. Otherwise, we consider the pair $(a_M,b_M)$ with largest $a_i+b_i$, and we claim that it can be involved in at most 2 good triangle. Firstly, if $\gcd(a_M,b_M)>1$, then it cannot be involved in a good triangle. We now claim that there is at most one solution to each of $a_M\cdot y - b_M \cdot x = -1,1$. This is because if we AFTSOC there are two solutions $(x_1,y_1)\leq (x_2,y_2)$, then \[a_M\cdot y_2 - b_M \cdot x_2 = a_M \cdot y_1 - b_M \cdot x_1\Longrightarrow a_M(y_2-y_1) = b_M(x_2-x_1)\]Since $\gcd(a_M,b_M)=1$, we have $y_2-y_1\geq b_M, x_2-x_1\geq a_M$. Since we also have that $x_1,x_2,y_1,y_2\geq 0$, and $(x_1,x_2)$ cannot be $(0,0)$, thus, \[x_2+y_2 \geq b_M+a_M + x_1+y_1 > b_M+a_M\]thus we have a contradiction, so each of $\{-1,1\}$ can only have one solution. Thus, by the inductive hypothesis there are at most $2(n-1)-3+2=2n-3$ good triangles and we are done. $\blacksquare$.
megarnie
25.11.2021 18:41
Call such pairs of $(i,j)$ good. The answer is $\boxed{197}$. A construction for this is \[(0,1), (1,1), (1,2), \ldots, (1,99),\]where if $i=1$, then any $j$ so that $100\ge j>i$ works and if $i>1$, then $j=i+1$ works, which gives a total of $99+98=197$. We will now show that $197$ is the maximum. Replace $100$ with $n$, and we will show that there are no more than $2n-3$ good pairs with $n\ge2$. We will show this by induction (with base case $2$ obvious). Draw $n+1$ points $P_1,P_2,\ldots,P_{n+1}$ in the plane. If any two pairs of points are good, then the area of the triangle formed when connecting these two points and the origin is $\frac{1}{2}$ by Shoelace. Suppose that $P_{n+1}$ has the largest sum of coordinates. If it's coordinates aren't relatively prime, then the result is obvious. So we assume it's coordinates are relatively prime. Claim: There are at most two points $P_k$ that satisfy the area of the triangle formed by connecting this point with $P_{n+1}$ and the origin is equal to $\frac{1}{2}$. Proof: Suppose there are $3$ such points $P_q, P_r, P_s$. Let $\ell$ be the line formed by the origin and $P_{n+1}$. Since at least two of the points are on one side of $\ell$, WLOG those two points are $P_q$ and $P_r$ with $P_r$ having the greater sum of cordinates. So the line formed by the points $P_q$ and $P_r$ must be parallel to $\ell$. Now suppose $P_{n+1}$ has coordinates $(a,b)$, with $a$ and $b$ relatively prime. Then the slope of line $\ell$ is $\frac{b}{a}$. Then if point $P_q=(a_q,b_q)$ and $P_r=(a_r,b_r)$, then $\frac{b_r-b_q}{a_r-a_q}=\frac{b}{a}$. Since $b$ and $a$ are relatively prime, we have $b_r-b_q\ge b$ and $a_r-a_q\ge a$, a contradiction as $b_q\ge0$ and $b_r>b$, which proves our claim. Without the point $P_{n+1}$, there are at most $2n-3$ good pairs, so with the point $P_{n+1}$, there are at most $2n-1=2(n+1)-3$, as desired.
IAmTheHazard
04.03.2022 20:25
Solved with slight spoiler The answer is $N=197$, achievable with $(0,1)$ and $(1,1),(1,2),\ldots,(1,99)$. In general, for $n \geq 2$ points there are at most $2n-3$ pairs. I will prove this with induction, with the base case of $n=2$ being clear. Note that the condition $|a_ib_j-a_jb_i|=1$ translates to the triangle formed by $O=(0,0)$, $P_i=(a_i,b_i)$, and $P_j=(a_j,b_j)$ having area $\tfrac{1}{2}$. Suppose we have $n$ points $P_1=(a_1,b_1),\ldots,P_n=(a_{100},b_{100})$, and pick $i$ such that $a_i+b_i$ is maximal, and let $a_i=a,b_i=b$ for convenience. We wish to show that there are at most two indices $j$ such that $[OP_iP_j]=\tfrac{1}{2}$. Clearly if $\gcd(a,b)>1$, there are in fact no points, so suppose that $a,b$ are coprime. By the base-height triangle area formula, this translates to $P_j$ being a distance $\tfrac{1}{\sqrt{a^2+b^2}}$. Some similar triangle stuff gives the locus of all such points $P_j$ as $$ay=bx+1~\cup~ay=bx-1.$$Actually, each of these lines should contain at most one $P_j$. Indeed, by maximality $P_j$ must lie within the region $R$ bounded by $x+y=0$ and $x+y=a+b$ (where the "lower bound" is exclusive but the "upper bound" is inclusive). Because both of the above lines can be viewed as shifts of $ay=bx$ in the direction perpendicular to the same line, it follows that the multiset of integral $x$-values spanned by $ay=bx+1$ within $R$ is equal to $\{1,2,\ldots,a\}$ when taken modulo $a$—namely, every residue occurs at most once. On the other hand, taking the equation of the line modulo $a$ reveals that we must have $x \equiv -\tfrac{1}{b} \pmod{a}$ if $(x,y)$ is a lattice point on the line, so there is exactly one lattice point on $ay=bx+1$ withie $R$. Since the actual possible locations of $P_j$ form a subset of $R$, it follows that at most one $P_j$ lies on $ay=bx+1$. Likewise, at most one $P_j$ lies on $ay=bx-1$. Then, by inductive hypothesis there are at most $2n-5$ working choices of $(i,j)$ in the remaining $n-1$ points, so there are at most $2n-3$ pairs $(i,j)$ among $n$ points, done. $\blacksquare$ Original diagram from Evan, somewhat heavily edited: [asy][asy] size(10cm); int M = 6; pair P = (3,2); pair O = (0,0); draw((-3,3)--(3,-3),gray); draw((-1,6)--(6,-1),gray); fill((-3,3)--(-3,6)--(-1,6)--(6,-1)--(6,-3)--(3,-3)--cycle, lightgray); draw(O--P, blue); for (real i=-M/2; i<=M; ++i) { draw( (-M/2,i)--(M,i), grey); draw( (i,-M/2)--(i,M), grey); } draw( (-M/2,0)--(M,0), black+1.4, Arrows(TeXHead) ); draw( (0,-M/2)--(0,M), black+1.4, Arrows(TeXHead) ); pair X = (1,1); pair Y = O+P-X; dot("$ay=bx+1$", X, dir(135)+0.2, red); dot("$ay=bx-1$", Y, dir(-45)+0.11, red); pair X1 = X+P; pair X2 = X-P; draw(X1--X2, red+dashed, Arrows); pair Y1 = Y+P; pair Y2 = Y-P; draw(Y1--Y2, red+dashed, Arrows); dot("$O$", O, dir(225), blue); dot("$P=(a,b)$", P, dir(30), blue); [/asy][/asy] In this case, both points fall in the first quadrant, but this is not always the case.
thinker123
04.03.2022 21:19
This problem is of the topic ntcomgeo.
DottedCaculator
04.03.2022 21:28
number theoretic combinational geometry
VicKmath7
27.11.2022 18:42
Here is a proof of the bound only. The answer is $2n-3$ for $n$ pairs. Let the pairs $(a_i, b_i)$ for $i=1,2,\dots, n$ correspond to lattice points $P_i$; a pair of points $(P_i,P_j)$ is good if the area of $\triangle OP_iP_j$ is $\frac{1}{2}$. We will induct by proving that the point $P_{n+1}$ with the largest sum of coordinates participates in at most two good pairs. Suppose that at least three points form good pairs with $P_{n+1}$, so at least two of them (say $P_i,P_j$) lie on the same side wrt $OP_{n+1}$. We get that $P_iP_j \parallel OP_{n+1}$ using the area condition, so the equal slopes imply that $\frac{b_{n+1}}{a_{n+1}}=\frac{b_i-b_j}{a_i-a_j}$. Notice that $(a_{n+1}, b_{n+1})=1$, as otherwise $P_{n+1}$ won't participate in any good pairs. Thus $b_{n+1} \mid b_i-b_j$ and $a_{n+1} \mid a_i-a_j$, so we get a contradiction with the maximality of $a_{n+1}+b_{n+1}$, done.
Leo.Euler
08.04.2023 21:02
The answer is $\boxed{197}$. (In general, let $S_k$ be the set of pairs of integers $(i,j)$ satisfying $1\le i<j \le k$ and $|a_ib_j-a_jb_i|=1$.) Construction: Use the pairs $(0, 1), (1, 1), (1, 2), \ldots, (1, 99)$. Proof of Bound: Assign these ordered pairs to points on the coordinate plane in an obvious way. Label the point $(a_i, b_i)$ as $P_i$ for $1 \le i \le 100$, and let $O$ be the origin. Then the condition $|a_ib_j-a_jb_i|=1$ is equivalent to asserting that $[OP_iP_j]=\tfrac{1}{2}$. We induct on $N$; in particular, we want to show that $N=100$ yields $2N-3=197$ as the largest possible value of $|S_N|$.The base cases $N=2$ is easy. Suppose that $N$ works. Then, we will show that $N+1$ also works. Suppose point $P_{N+1}$ is the point with largest sum of coordinates. We consider two cases. Case 1: Suppose $\gcd(a_{N+1}, b_{N+1}) \neq 1$. Since $\gcd(a_{N+1}, b_{N+1}) \mid |a_{N+1}y-b_{N+1}x|$ for any integers $x$ and $y$, $N+1$ does not belong to any of the pairs in $S_{N+1}$, so we are done from this case. Case 2: Suppose $\gcd(a_{N+1}, b_{N+1}) = 1$. This clearly implies $\overline{P_iP_j}$ is not parallel to $\overline{OP_{N+1}}$ for all $(i,j) \in [N+1]^2$; this fixes an upper bound of $2$ points $P$ from $\{P_1, \ldots, P_N\}$ such that $[OPP_{N+1}]=\tfrac{1}{2}$ due to geometric continuity reasons. This yields an upper bound of \[ |S_{N+1}| \le |S_N|+2 = (2N-3)+2 = 2N-1, \]so this case is complete as well. All in all, $|S_{N+1}| \le 2N-1$, which completes the proof. $\blacksquare$
mathmax12
09.04.2023 15:29
this is nugeobra(nt,algebra,geo), take pairs $(0,1),(1,1).....$ also what is USOMO and what is USOJMO :thinkies:
alsk
15.03.2024 04:16
The answer is $2n-3$ when $100$ is replaced by $n$. Proof: Observe that the problem is asking for the number of pairs of points $(a_i, b_i)$ and $(a_j, b_j)$ such that the area formed by the two points and the origin (denoted $O$) is $\frac 12$. Call such a triangle "minimal". Define the "farthest" point $(a, b)$ to be the point such that no other points $(x, y)$ exist with both $x \geq a, y \geq b$. Claim: The furthest point $P = (m, n)$ is a vertex of at most two distinct minimal triangles. Proof: consider the locus of all points $Q$ such that $[OPQ] = \frac 12$. Clearly for the locus to exist (i.e. not empty), we must have $\gcd(m, n) = 1$. If the locus exists, by $\frac 12 bh$ area formula, the locus consists of two lines parallel to $OP$. Note that because $m, n$ are coprime, the next lattice point is $(a_i + m, b_i + n)$ or $(a_i - m, b_i - n)$. But since $(m, n)$ is the furthest point it is impossible for $(a_i+m, b_i+n)$ to be another point $(a_j, b_j)$. Furthermore, at least one of $(a_i - m, b_i - n)$ is negative, so it cannot be another point $(a_j, b_j)$ either. Thus, for each line $\ell$, there can be at most one marked point on it, so $P$ is used in at most two distinct minimal triangles. Since the base case $n=2$ results in 1 triangle (obvious), so for $n$ points the answer is $2n-3$. Construction: Take points in a staircase: $(1, 0), (1, 1), (2, 1), \dots (50, 50)$ can be easily verified.
avisioner
14.07.2024 23:28
A short Farey fraction and Graph Theory proof of this question! The answer is $197$. The construction is $(0, 1), (1, 1), (1, 2), \dots (1, 99)$. Let the two fractions $\frac{a}{b}, \frac{c}{d}$ represent the relationship between the pairs $(a,b),$ $(c,d)$ Claim/Lemma 1: Any pair of fractions $\frac{a}{b}, \frac{c}{d}$ has $|ad-bc|=1$ if and only if they are adjacent in some $L_i$ (level). Proof: The first direction that all adjacent $\frac{a}{b}, \frac{c}{d}$ has $|ad-bc|=1$ follows quickly from induction. The other direction that $|ad-bc|=1$ only follows from $\frac{a}{b}, \frac{c}{d}$ is simple to see as $|ad-bc|=1$ is equivalent to saying $\frac{c}{d}-\frac{a}{b}$ is equal to $\frac{1}{bd}$ given $\frac{a}{b} < \frac{c}{d}$ which is obviously not true for fractions that are not adjacent. Claim: The graph containing all pairs connected by pairs that satisfy the condition (Farey fractions) is an outerplanar graph. From Lemma 1 Diagram: Connections of Pairs that satisfy the condition (showing lowest level of fraction with first 5 levels). [asy][asy] usepackage("tikz"); usepackage("forest"); label("\begin{forest} for tree={alias/.wrap pgfmath arg={a-#1}{id}, %label/.wrap pgfmath arg={[gray,font=\tiny,inner sep=0pt]above:#1}{id} } [$\frac{1}{1}$ [$\frac{1}{2}$ [$\frac{1}{3}$ [$\frac{1}{4}$ [$\frac{1}{5}$] [$\frac{2}{7}$] ] [$\frac{2}{5}$ [$\frac{3}{8}$] [$\frac{3}{7}$] ] ] [$\frac{2}{3}$ [$\frac{3}{5}$ [$\frac{4}{7}$] [$\frac{5}{8}$] ] [$\frac{3}{4}$ [$\frac{5}{7}$] [$\frac{4}{5}$] ] ] ] [$\frac{2}{1}$ [$\frac{3}{2}$ [$\frac{4}{3}$ [$\frac{5}{4}$] [$\frac{7}{5}$] ] [$\frac{5}{3}$ [$\frac{8}{5}$] [$\frac{7}{4}$] ] ] [$\frac{3}{1}$ [$\frac{5}{2}$ [$\frac{7}{3}$] [$\frac{8}{3}$] ] [$\frac{4}{1}$ [$\frac{7}{2}$] [$\frac{5}{1}$] ] ] ] ] ] \path (current bounding box.north west) node[below right] (tl) {$\frac{0}{1}$} (tl) foreach \x in {2,...,6} {edge (a-\x)} (current bounding box.north east) node[below right] (tr) {$\frac{1}{1}$} (tr) foreach \x in {2,18,26,30,32} {edge (a-\x)} (a-2) foreach \x in {11,15,17,19,20,21} {edge (a-\x)} (a-3) foreach \x in {8,10,12,13} {edge (a-\x)} (a-4) foreach \x in {7,9} {edge (a-\x)} (a-11) foreach \x in {14,16} {edge (a-\x)} (a-18) foreach \x in {23,25,27,28} {edge (a-\x)} (a-19) foreach \x in {22,24} {edge (a-\x)} (a-26) foreach \x in {29,31} {edge (a-\x)}; \end{forest}"); [/asy][/asy] Proof: Notice that, trivially, every fraction can be sent to the outside of the graph. This is achieved as every fraction can be infinitely lowered downwards and thus to the outside of the graph. This fulfills the requirements of being an outerplanar graph. Lemma: All outerplanar graphs have a maximum of $2n-3$ edges given $n$ vertices. Proof: This result follows from induction. Every point can add a maximum of $2$ edges with a base case of $n=2$ giving $1$ edge. We have in the problem that $n=100$ which gives a maximum of $2(100)-3=\boxed{197}$ edges which are the same as pairs that satisfy the condition.