There are 100 positive integers written on a board. At each step, Alex composes 50 fractions using each number written on the board exactly once, brings these fractions to their irreducible form, and then replaces the 100 numbers on the board with the new numerators and denominators to create 100 new numbers. Find the smallest positive integer $n{}$ such that regardless of the values of the initial 100 numbers, after $n{}$ steps Alex can arrange to have on the board only pairwise coprime numbers.
Problem
Source: BMO Shortlist 2022, C1
Tags: combinatorics, number theory
Marinchoo
14.05.2023 12:01
Clearly, after $99$ moves Alex could have gone through every pair of integers and made them pairwise coprime (as every move only takes away prime factors, $\gcd(a,b)$ where $a,b$ are any two numbers on the board can't increase and after $99$ moves Alex would have gone through every pair and made their $\gcd$ equal to $1$). On the other hand, $99$ moves are necessary because we can consider the following construction: write a different prime $p_{(i,j)}$ in every cell $(i,j)$ satisfying $i<j$ of an $n\times n$ table. Taking the $k$-th number to be the product of all $p_{(i,j)}$ such that $i=k$ or $j=k$ forces Alex to have made a move on every pair of integers, hence $99$ moves are required.
gghx
14.05.2023 16:17
Marinchoo wrote:
Clearly, after $99$ moves Alex could have gone through every pair of integers and made them pairwise coprime (as every move only takes away prime factors, $\gcd(a,b)$ where $a,b$ are any two numbers on the board can't increase and after $99$ moves Alex would have gone through every pair and made their $\gcd$ equal to $1$). On the other hand, $99$ moves are necessary because we can consider the following construction: write a different prime $p_{(i,j)}$ in every cell $(i,j)$ satisfying $i<j$ of an $n\times n$ table. Taking the $k$-th number to be the product of all $p_{(i,j)}$ such that $i=k$ or $j=k$ forces Alex to have made a move on every pair of integers, hence $99$ moves are required.
The hardest part of the problem is showing that Alex can go through every pair of integers after 99 moves. One way to do this is to put 99 of the numbers in a circle and the last as the center, and for each move we pair a vertex with the center and pair the rest perpendicular to the first.
motannoir
14.05.2023 18:12
Not related to the problem,but can anyone make a collection of all problems from the shortlist ( i am not a moderator and if i search the problems it only appear the problems from 2021 shortlist ) @below: Thanks, Vlad !
oVlad
14.05.2023 19:45
motannoir wrote: Not related to the problem,but can anyone make a collection of all problems from the shortlist ( i am not a moderator and if i search the problems it only appear the problems from 2021 shortlist ) I already made a collection! I posted in "Contests to Add" about it.
dgrozev
15.05.2023 11:09
gghx wrote: Marinchoo wrote:
Clearly, after $99$ moves Alex could have gone through every pair of integers and made them pairwise coprime (as every move only takes away prime factors, $\gcd(a,b)$ where $a,b$ are any two numbers on the board can't increase and after $99$ moves Alex would have gone through every pair and made their $\gcd$ equal to $1$). On the other hand, $99$ moves are necessary because we can consider the following construction: write a different prime $p_{(i,j)}$ in every cell $(i,j)$ satisfying $i<j$ of an $n\times n$ table. Taking the $k$-th number to be the product of all $p_{(i,j)}$ such that $i=k$ or $j=k$ forces Alex to have made a move on every pair of integers, hence $99$ moves are required.
The hardest part of the problem is showing that Alex can go through every pair of integers after 99 moves. One way to do this is to put 99 of the numbers in a circle and the last as the center, and for each move we pair a vertex with the center and pair the rest perpendicular to the first. I don't think it's the hardest part, it's just what round robin tournament stands for. It can be taken for granted. It can be interpreted as a complete graph of $100$ vertices. At every step we take a perfect matching and cancel $\gcd$ of each matched pair. If there is any part at all that deserves attention, it is to give an example why every "edge" is required to be taken as a part of some matching.
gghx
16.05.2023 03:53
dgrozev wrote: I don't think it's the hardest part, it's just what round robin tournament stands for. It can be taken for granted. It can be interpret as a complete graph of $100$ vertices. At every step we take a perfect matching and cancel $\gcd$ of each matched pair. If there is any part at all that deserves attention, it is to give an example why every "edge" is required to be taken as a part of some matching. But is it obvious that we can decompose a $K_{100}$ into 99 perfect matchings? (I mean its a classic problem but I don't think it can be taken for granted)
lian_the_noob12
01.08.2023 12:41
$\color{green} \textbf{Claim :}$ $n \le 99$ $\textbf{proof :}$ Let the numbers are $a_1,a_2,...a_{100}$ There are total $\frac{100\times99}{2}=4950$ pairs of $a_i,a_j, 1\le i,j \le 100$ In each move $50$ pairs become co-prime. So, Maximum number of moves needed to make all the pairs co-prime is $\frac{4950}{50}=99$ $\color{green} \textbf{Construction for}$ $n=99$ $a_1=\prod_{i=1}^{100}{p_{1_{a_i}}}$ $a_2=p_{1_{a_1}} \prod_{i=1}^{99}{p_{2_{a_i}}}$ $a_3=p_{1_{a_2}} p_{2_{a_1}} \prod_{i=1}^{98}{p_{3_{a_i}}}$ $a_4=p_{1_{a_3}} p_{2_{a_2}} p_{3_{a_1}} \prod_{i=1}^{97}{p_{4_{a_i}}}$ . . . $a_{100}=p_{1_{a_{99}}} p_{2_{a_{98}}} p_{3_{a_{97}}}...p_{99_{a_1}} p_{100_{a_1}}$ For Primes $p_{x_{a_i}}, 1\le x,i \le100 \blacksquare$
cursed_tangent1434
09.12.2023 06:40
We claim that the answer is $99$. First, note that there are $99 \cdot 50$ pairs of integers in total. In each round $50$ of these pairs become coprime, and thus, Alex can pair the integers such that in \[\frac{99 \cdot 50}{50}=99\]moves, all of the integers are pairwise coprime to each other. Now, we give a construction which requires $99$ rounds to terminate. Let $a_2,\dots,a_{100}$ be $99$ distinct primes and let $a_1=\prod_{i=2}^{99}a_i$. Say there exists a term $a_i$ which was never paired with $a_1$.Then, it is clear that if $a_i$ for $2\leq I \leq 99$ is paired with any $a_j$ for $j \neq 1$ then the prime $p_i =a_i$ would not have been removed from $a_i$ ($\frac{a_i}{a_j}$ is already in reduced form as they have no common factors so this move has no change on the setup) and thus, $\gcd(a_1,a_i)=p_i$ which is a clear contradiction to the fact that this process has terminated. Thus, at some move $a_1$ must have been paired with each of the other terms, requiring a minimum of $99$ moves to be finished.
Nari_Tom
03.02.2025 10:24
Well well well, stupid C1 again. Construction which requires at least 99 steps. $N_i=p_i$ for $ \le i \le 99$ and $N_100=\prod_{i=1}^{99}{p_i}$, where $p_i$ denotes the $i$-th prime. Proof for the after $99$ steps each pair is connected is easy just by using Round Robin tournament logic.