Question: One day Anindya and his friend Faria cooperated to play a fun game. They played to maximize the sum of points they gained throughout the game.
Let $S = \{1,2,\ldots, 100\}$. There are $50$ rounds. In each round of the game, they will decide together to choose two distinct numbers $x,y$ from $S$ such that neither $x$ nor $y$ have been chosen in previous rounds. Let's say Faria's number is $x$ and Anindya's number is $y$. They will then gain $GCD(x,y)$ points, where GCD is the Greatest Common Divisor function.
Find the total (maximized) number of points that they gained in the game.
My solution: My way to achieve this is to choose consecutive pairs of numbers. For example:
Round $1$:
Anindya: $1$
Faria: $2$
$GCD(1, 2) = 1$
Round $2$:
Anindya: $3$
Faria: $4$
$GCD(3, 4) = 1$
...
Round $49$:
Anindya: $97$
Faria: $98$
$GCD(97, 98) = 1$
Round $50$:
Anindya: $99$
Faria: $100$
$GCD(99, 100) = 1$
In each round, the GCD is $1$, and they gain $1$ point. Therefore, in $50$ rounds, they will gain a total of $50$ points.
But when I did some brute force calculation , I was stuck . If we choose round $50$ $(100 , 50 )$ and round $49$ $( 49 , 98 )$ , the total sum will be greater than my previous answer sum .
So what will be actual procedure to solve this problem?
You can solve this as a maximum weight matching problem in a complete graph with node set $\{1,\dots,100\}$ and edge weight $\gcd(i,j)$. The maximum turns out to be $1187$, attained for example by