You don't actually have to battle any of the sages, you just have to find them. Then the "Detective" will arrest them.
I hope this video help you. :) enter link description here