MathDB
Set formed from the gcds of another set

Source: Question 2 - Brazilian Mathematical Olympiad 2017

December 7, 2017
number theorygreatest common divisorcombinatoricsBrazilian Math OlympiadBrazilian Math Olympiad 2017

Problem Statement

2. Let n≥3n \geq 3 be an integer. Prove that for all integers kk, with 1≤k≤(n2)1 \leq k \leq \binom{n}{2}, there exists a set AA with nn distinct positive integer elements such that the set B={gcd⁡(x,y):x,y∈A,x≠y}B = \{\gcd(x, y): x, y \in A, x \neq y \} (gotten from the greatest common divisor of all pairs of distinct elements from AA) contains exactly kk distinct elements.
Back to ProblemsView on AoPS