TR-MO 2015 Problem 4

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$ .