The algorithm of $2n-1$ 1. the algorithm of finding the heaviest coin in $2n-1$ One can find the heaviest coin, if at least $n-1$ weight orders among $2$ coins. Denote n balances (balance 1~balance n). use balance 1,2 to find one weight order. Use balance 3,4 to find the next weight order. next time; 5,6.... Repeat this until we find the wrong balance(by i)).then, use the right balance one times per each weight order. The number of turns would be maximum $2(n-2)+3=2n-1.$(Using i),ii))

To precisely write why $2n-2$ is impossible, we need to mathematically convert the term "Coin $A$ is the heaviest coin". Then we have to consider the all possible situation that satisfies the results of balance(one can be wrong). For example, at first, any of the situation is possible. When we weight some coin $A$ and $B$ with balance $M$ on the frist trial and the result is $A>B$, following situations are possible: (1) Any situation with $A>B$ (2) Any situation with $A<B$ and $M$ is wrong. So yet, the every coin can be the heaviest coin. When every possible has coin $A$ as its heaviest coin, then finally we can say "Coin $A$ is the heaviest coin". So, we also need to control the results of the weighing to track the all possible situation. My original proof was concerning the set of "Possibly heaviest coin" $S_0$ and "Not determined relationship" $T \subset S_0 \times S_0$ and hierarchy between two coins in complement of $S_0$. But since the official solution is a lot simple, I would like to introduce the official version. (http://olympiads.mccme.ru/vmo/) Write the number $1$ to $n$ to each coin. For $2n-3$ weighing, when comparing $i<j$, there can be a situation when every result is $i<j$. Then, there exists $k\ne n$ such that $k$ was on the lighter side at most once. Let $C$ be the balance used at the weighing. Then (1) $1<2<...<n$ (2) $1<2<...<n<k$ and $C$ is wrong is both possible. So we cannot determine the heaviest coin. For the $2n-2$th weighing, 1. Use balance $C$ and compare $i<j$. With result $i<j$, still (1)(2) are both possible. 2. Use balance other than $C$ and compare $i<j$ different from $k$. With result $i<j$, still (1)(2) are both possible. 3. Use balance $D$ other than $C$ and compare some coin $i$ with $k$. With result $i<k$, (1`) $1<2<...<n$ and $D$ is wrong and (2) is both possible. So any of the cases, we cannot determine the heaviest coin and this completes that $2n-1$ is the minimum.

Am I missing something? XbenX wrote: We are given $n$ coins of different weights and $n$ balances, $n>2$. On each turn one can choose one balance, put one coin on the right pan and one on the left pan, and then delete these coins out of the balance. It's known that one balance is wrong (but it's not known ehich exactly), and it shows an arbitrary result on every turn. What is the smallest number of turns required to find the heaviest coin?

We claim the answer is $2n-1$. Indeed, fix three balances $A, B, C$. First, using $(n-1)$ weighings, determine the heaviest coin according to $A$ (this can be done by picking two coins and discarding the one $A$ claims is lighter, successively). Repeat the same process with $B$. Suppose we get two coins $x$ and $y$ after these $2n-2$ moves. If $x=y$ then this is the desired heaviest, since one of the two balances was correct. Else, if $x \ne y$ we know for sure that $C$ is correct, and one of $x$ or $y$ is indeed the heaviest (as one of $A$ or $B$ is correct). Weighing the two against each other on $C$ tells us the heaviest. This process takes at most $2(n-1)+1=2n-1$ moves. Now we prove that in $2n-2$ moves we can’t do any better. Our strategy is as follows: we always reply with an answer, for which there exists a choice of the initial weights such that all our answers at that point are consistent (if either answer is fine, pick randomly). Suppose the opponent is done in $m<2n-1$. Consider a multi directed graph with the $n$ coins as vertices, and $m$ directed edges, where $\overrightarrow{uv}$ is an edge, if in some weighing, $u$ was weighted to be less than $v$. We may also assign to this edge the label of the balance we used for it (this is just cosmetic). Suppose the opponent declares coin $A$ to be the heaviest. Note that if any vertex has no out degree then we have two possible graphs where all our answers are consistent: one where this vertex is heaviest and the other where it is lightest. So we may assume no vertex has zero outdegree. But then, $m<2n-1$ so there exists vertices $B$ and $C$ with outdegree exactly one. Now one of them is not $A$, say $B \ne A$. So we have one valid graph which declares $A$ to be the heaviest. By flipping the outgoing edge from $B$, thus declaring that balance to be the flawed one, and keeping every other edge the same, we can declare $B$ to be the heaviest in this case. Thus, the opponent’s strategy does not work, hence $2n-1$ is optimal.

@above "Note that if any vertex has no out degree then we have two possible graphs where all our answers are consistent: one where this vertex is heaviest and the other where it is lightest. So we may assume no vertex has zero outdegree." If there is in degree then it cannot be the lightest. What am I missing?

The answer is $\boxed{2n-1}$. Construction: Pick any two coins. Compare them with two weights. If both of them show same sign, then we are sure about their sign. We then throw away the lighter. If they show different, we pick compare them with a third balance. That balance is correct for sure. Later, we will only need to compare with this third balance. So $2(n-1) + 1$ suffice. Other direction: Now we show at least $2n-1$ turns have to be used. At start, we make all balances to tell truth. Consider a directed graph $G$ with coins corresponding to vertices and draw $u \to v$ if balances tell $W(u) > W(v)$ (where $W(u)$ is weight of $u$). Also, the edges have one of the $n$ colors. Suppose one can determine some coin $H$ with max weight from $G$. Claim: Each vertex of $G \setminus \{H\}$ has indegree at least $2$. Proof: Assume contrary that for some vertex $u$, its indegree is $\le 1$ and $C$ is the only color for which $v \to u$ has color $C$. We consider the situation in which color $C$ is defective while weight of $u$ is increased even more than $H$. One should still conclude $H$ is heaviest, but instead it is $u$, contradiction. $\square$ Now assume contrary that $G$ has $2n-2$ edges. Then all vertices other than $H$ will have indegree precisely $2$. Consider the vertex $u$ such that last edge was $v_1 \to u$ (i.e. $u,v_1$ were balanced at last). Suppose $v_2 \to u$ was before at some point. Say $v_1 \to u, v_2 \to u$ have colors $C_1,C_2$. Instead of replying $u \to v_1$ at last, we reply $v_1 \to u$ instead. This can possible happen if $C_1$. So one must have concluded $H$ as the largest here too. But if weight of $u$ is increased to be even more than $H$ and $C_2$ is defected, then one must still conclude $H$ to the heaviest, which is a contradiction as $u$ is heaviest. $\blacksquare$

We claim the answer $2n-1.$ We leave only three balances $A,B,C$, at most one of which is wrong. Construction. We present the algorithm inductively. For base case with three coins $x,y,z$ we firstly compare $x,y$ on $A,B$ by two turns. If results are the same (WLOG $y$ is heavier), then the heaviest coin is either $y,$ or $z.$ Comparing them on $A,B,C$ by three turns we get at least two same results - then it's right results, so we are done. If results are distinct, then $C$ is a right balance. Compare $x,y$ on $C$ - compare the heavier one with left. For $n>3$ we firstly compare two coins $x,y$ on $A,B$ by two moves. If results are the same, then we know the heaviest one of $x,y$ and reduce the problem to case $n-1,$ with $2n-3$ moves. Otherwise $C$ is a right balance. Then we clearly may finish by $n-1$ moves, comparing the heaviest known (or arbitrary, if none is known) coin with any, which wasn't used. Bound. Assume FTSOC that $2n-2$ moves are sufficent. Numerate all coins by $1,2,\dots ,n$ and perform $2n-3$ first turns of algorithm. Suppose that on any turn the coin with a bigger number was shown heavier. By PHP some coin numbered $k$ was shown lighter on at most one turn. We claim, that two following cases are indistinguishable: $i-$th coin is heavier than the $j-$th iff $i>j;$ all balances gave right result. $i-$th coin is heavier than the $j-$th iff $i>j$ or $i=k;$ all balances gave right result, except for the one which showed $k-$th coin lighter. Indeed, we present situations for two cases, when we can't distinguish cases above, as follows. If $k-$ th coin isn't used in last turn, we suppose that on this turn the coin with the bigger number is shown heavier. If $k-$th coin is used in last turn, we can't distinguish, either the result is right, or not, and both cases above are possible.