DeGe

From what I remember while solving it, there were no unresolved elements and each piece fitted in one place only (I have now deleted the file that I used to work this out). The interchangeability between Mike/North and Paul/Fisher is also resolved. I don't remember how exactly I resolved it but it had something to do with there being only 3 girls names... Grace, Karen, and Dot. In case of interchanging Paul/Fisher and Mike/North, some other condition was being violated.

i see the error. Dont have time now but will correct it later

Yes, but for returning also he would need to eat apples So, if he goes 500KM, he would eat 500 while going and 500 while coming back.