MathDB

Anti-GCD problem

Source: Kyiv City MO 2024 Round 2, Problem 7.2/8.1

February 4, 2024

GCDnumber theory

Problem Statement

You are given a positive integer

n

. What is the largest possible number of numbers that can be chosen from the set

\{1, 2, \ldots, 2n\}

so that there are no two chosen numbers

x > y

for which

x - y = (x, y)

?
Here

(x, y)

denotes the greatest common divisor of

x, y

.
Proposed by Anton Trygub