The inductive step allows you to stipulate what seems like a strong assumption, in this case that all horses in sets of size N have the same color. I think you're reacting to that seeming like it's the problem, because at first that seems like where the "cheating" is occuring: you can obviously have a set of horses that aren't all the same color.
But actually that's part the power of the inductive step: you do have the freedom to choose whatever assumptions you want. The question is whether it's true for N+1, for all N. In this case, it's not: the inductive step fails. But there's nothing flawed with the starting premise per se (aside from it being intuitively obvious that it will never work). The interest here is that it seems you can get further than you should be able to, and it's a little tricky to figure out where the logic falls apart.
But actually that's part the power of the inductive step: you do have the freedom to choose whatever assumptions you want. The question is whether it's true for N+1, for all N. In this case, it's not: the inductive step fails. But there's nothing flawed with the starting premise per se (aside from it being intuitively obvious that it will never work). The interest here is that it seems you can get further than you should be able to, and it's a little tricky to figure out where the logic falls apart.