Let $L$ be a set of left and $R$ a set of right shoes. Then the sample space is $$ \Omega = \\{(a,a',b,b',c,c');a\
e b\
e c\
e a\in L,\;a'\
e b'\
e c'\
e a'\in R\\}$$ so $|\Omega|=5^24^23^2$. Now our event is $\overline{A\cup B\cup C}$, where $A$ first man has a pair,... Since $$|A| = |B| = |C|= 5\cdot 4^23^2,$$ $$|A\cap B| = |A\cap C| = |B\cap C| = 5\cdot 4\cdot 3^2$$ and finally $$|A\cap B\cap C| = 5\cdot 4\cdot 3$$
So $$|A\cup B\cup C| = 3(5\cdot 4^23^2)-3( 5\cdot 4\cdot 3^2)+5\cdot 4\cdot 3 $$ so $$ P' ={3( 4\cdot3)-3(3)+1 \over 5\cdot 4\cdot 3} = {7\over 15} $$ so $$P = {8\over 15}$$