MathDB

Consecutive numbers on edges of the graph

Source: Iran TST 2012-Second exam-1st day-P1

May 12, 2012

inductiongraph theorygreatest common divisorcombinatorics proposedcombinatorics

Problem Statement

Is it possible to put

\binom{n}{2}

consecutive natural numbers on the edges of a complete graph with

n

vertices in a way that for every path (or cycle) of length

3

where the numbers

a,b

and

c

are written on its edges (edge

b

is between edges

c

and

a

b

is divisible by the greatest common divisor of the numbers

a

and

c

?
Proposed by Morteza Saghafian