Find the minimum Adversary's Advantage I am wondering how to solve the problem below:  

Suppose we have a $MAC$ scheme $I=(S,V)$. There is another algorithm that can find a pair of texts $(m0,m1)$, with $m0≠m1$ such that $S(k,m0)=S(k,m1)$ for $1/10$ of the Keys $K$.What is the minimum $Adv$$MAC$$[A,I]$ for every adversary $A$?

MAC defined over $(K,M,T)$ is a pair of efficient algorithms $(S,V)$:  


$S(k,m):$ returns a message athentication code $t$ which belongs to a set $T$  
$V(k,m,t):$ returns a value $true$ or $false$ depending on the correctness of the received authentication code  


$M$ is a set of all possible messages $m$
$K$ is a set of all possible keys $k$
$T$ is a set of all possible authentication codes $t$  

Thanks in advance!
It seems to me that the answer to the question, as literally asked, is $0$.  This is because you're asking for the minimum advantage "for every adversary", and the set of possible adversaries includes e.g. the trivial adversary that simply always outputs an empty message and a random tag $t \in T$, and thus has a probability of exactly $1/|T|$ of successful forgery.

However, that's almost certainly not what the question is trying to ask, if only because the answer above doesn't actually make any use of the extra collision-finding algorithm.  What I suspect the question should ask is something like:


  Let $(S,V)$ be a MAC scheme (as defined above), and let $C$ be an efficient algorithm that will output a pair of distinct messages $m_1 \ne m_2$ such that $S(k, m_1) = S(k, m_2)$ for a randomly chosen key $k \in K$ with probability $1/10$.  Show that for any such triple $(S,V,C)$ there exists an adversary $A$ (with oracle access to $S(k,\cdot)$ and $C$) that can forge a message with advantage at least $a &gt; 0$ independently of the security parameter, and determine the maximum value of $a$ for which this claim holds (assuming that secure MAC schemes exist).


As for solving this problem, consider an adversary $A$ that uses $C$ to generate a message pair $m_1, m_2$, queries the oracle for $t_1 = S(k,m_1)$ and outputs $(m_2, t_1)$.  What is the advantage of such an adversary?

For bonus points, show that, given a secure MAC scheme $(S^*,V^*)$ (i.e. one against which no adversary has more than a negligible advantage), we can construct a triple of efficient algorithms $(S,V,C)$ that has the property described in the question, and against which no adversary can have more than a negligibly higher advantage than the adversary $A$ described in the previous paragraph.