Number of ways to color paired shoes so that each pair will have different color There are 4 pairs of shoes of different sizes. Each of the 8 shoes can be colored with one of the four colors: Black, Brown, White & Red. In how many ways can one color shoes so that in at least three pairs, the left and the right shoes do not have the same color.
My solution:
Any three pair colored in odd fashion (i.e both shoes of same pair are colored with different colors)
$C(4,3) \cdot (4 \cdot 3)^3= 4 \cdot 12^3$
All four pairs having different color:
$(4 \cdot 3)^4 = 12^4$
Adding both we get $16 \cdot 12^3$.
Wrong answer it is.
Help to find the mistake.

The number of ways to color the shoes so that three pairs are odd-colored is 
$$
N = \text{(number of ways to pick three pairs)} * \text{(number of ways to color each odd pair)}^3 * \text{(number of ways to color the one remaining pair)}
$$
which is
$$
N = C(4,3) * (12)^3 * 4 = 4 * 12^3 * 4.
$$
It looks like you forgot the fact that the remaining pair (whose shoes are the same color) can have any one of four colors.
Combined with the case where all four pairs are odd-colored, the answer then works out to be $28 * 12^3 = 48384$.
