MathDB

In an exhibition where

2015

paintings are shown, every participant picks a pair of paintings and writes it on the board. Then, Fake Artist (F.A.) chooses some of the pairs on the board, and marks one of the paintings in all of these pairs as "better". And then, Artist's Assistant (A.A.) comes and in his every move, he can mark

A

better then

C

in the pair

(A,C)

on the board if for a painting

B

A

is marked as better than

B

and

B

is marked as better than

C

on the board. Find the minimum possible value of

k

such that, for any pairs of paintings on the board, F.A can compare

k

pairs of paintings making it possible for A.A to compare all of the remaining pairs of paintings.
P.S: A.A can decide

A_1>A_n

if there is a sequence

A_1 > A_2 > A_3 > \dots > A_{n-1} > A_n

where

X>Y

means painting

X

is better than painting

Y

Problem Statement