In both parts we know one to be true, which means it suffices to disprove one possibility for each and that settles the proof.
Part one:
Let's start by assuming the pawn on f2 is white and work our way up to see if we hit any inconsistencies. So here's our diagram:
[title "Assuming f2 pawn is white"]
[fen "r2qk2r/1ppbp1p1/1pn2n2/b2pP3/3P4/2N3P1/PPP2P2/R2QK2R w - - 0 1 "]
First trivial observation is the fact that the black bishop on a5 is a promoted piece as the original dark square bishop could never have escaped from f8. This means either the h or f pawn has promoted on g1 into a bishop that is now on a5. Having a white pawn on f2 also implies that the g3 pawn isn't the h-pawn having made a capture on g3 or else the promoted bishop could never have escaped white's kingside and reach a5, thus, g2-g3 is played at some point, and it was on g2 when black made the promotion (else no escape route). This in turn means the promoted black pawn must have been the h-pawn. But how did it get passed the h pawn? We know that white is down three pieces, the two bishops and the h-pawn. Additionally, we know that one piece was captured on b6 and one on g1 (for black's h-pawn to promote). Now both b6 and g1 are dark squares, but 'h2' pawn couldn't have been captured on either, nor could have the f1 bishop as it is a light square piece. Therefore, white must also have a promoted piece, as nothing else accounts for the missing captured piece, for instance a knight (or any other non-pawn) being captured on g1 by the h7 pawn and the h2 having promoted into a knight. So clearly the h pawn hasn't been captured but has instead been promoted. But therein lies the conflict: one of the h-pawns must have made at least two captures to get passed the other h-pawn. It couldn't have been the white pawn as black has only lost one piece so far, but it cannot be the black h-pawn either, because it must have then made 3 captures, 2 to get passed the white h-pawn and one last capture on g1 to promote into the a5 bishop. Knowing a capture on b6 has also taken place, this accounts for a total of 4 captures, but white has only lost 3 pieces at most. Thus, neither h-pawns could have legally promoted given that the f2 pawn is white, so our starting assumption must be wrong. We conclude the f2 pawn must be a black pawn.
Notice that throughout the analysis, the position of the knight either f3/f4, would have made no discernible difference on the resolution of the f-pawn's conflict, so we were safe to do the analysis independently. The reverse is not true, namely, the knight's position is very much dependent on the fact that the pawn on f2 is black.
Part two: Knowing now that the f2 pawn is a black pawn, let's take the most restrictive case and assume the knight is on f3 and perform a similar analysis to see if we hit any walls. So here's the corresponding diagram:
[title "Assuming the knight is on f3"]
[fen "r2qk2r/1ppbp1p1/1pn2n2/b2pP3/3P4/2N2NP1/PPP2p2/R2QK2R w - - 0 1 "]
It is the most restrictive consideration as it forces the f7 pawn to have made at least 2 captures to reach f2, because the white knight is assumed to be on f3, which means that f7 pawn must have just made a capture on f2 from e3 (that it reached from yet another capture). So far we have accounted for 4 white pieces having been captured and the h7 and h2 having promoted for black and white respectively. The only1 way the latter could have happened is if the h7 pawn (i) made two captures to go around the white h-pawn, or (ii) made only one capture from h3 (so taking something on g2) while white's h2 pawn still untouched. (i) is impossible by just considering the piece count, because so far there has been one capture on b6, two captures by f7 pawn and two by the h7 pawn, and that is already more captures than the number pieces white has lost. So only option is (ii): we know that the h7 pawn must have captured a non-pawn piece on g2 (as the g3 white pawn couldn't have been from either the h pawn which promoted, or the f2 pawn as black only lost one piece and that was the original f8 bishop on its original square). This in turn implies that g2-g3 must have been played by white before h7 captured on g2. But that means the promoted black bishop could not have escaped white's kingside via the g3-e5 diagonal anymore, therefore, it must have escaped from the f2-d4 diagonal instead, which settles the fact that the f7 pawn couldn't have captured a pawn on f2 (from e3), or else the bishop could never have reached a5, had there still been a pawn on f2 just presumably captured by black's f7 pawn.
Now here's the dilemma: what on earth happened to white's f2 pawn in all this? Can we logically account for it knowing black just took a non-pawn piece on f2 and there's a white knight lying on f3 (starting assumption)? It definitely couldn't have been the piece that the f7 pawn captured to reach the e-file either as white only made one capture and that was on f8, so f2-white-pawn couldn't have magically been on the e-file. Trivially, it couldn't have been captured on b6 or g2 either. It couldn't have been promoted either as it would have forced black's king to move (disallowed in the starting description). So f2 pawn couldn't have been promoted, or been accounted for by any of the four captures performed by black, but somehow it isn't on the board, thus, we can conclude that we've reached an inconsistency again, meaning there's no logical set of events that would legally reach the position given above with the knight standing on f3 which was our original assumption, so the knight must be on f4.
Come to think of it, there's a much shorter way of realising that the knight cannot be on f3 without focusing on the fate of the white f2-pawn: quick recap of captures: we know a dark square piece has been captured on b6, two non-pawn pieces captured one on e-file and one on f2, one non-pawn piece also captured on g2. But how many non-pawn pieces has white lost? The two bishops and another non-pawn (we cannot know which because we don't know what piece the h2 pawn promoted into) on the e-file. That's 3, so there's no other non-pawn left for black to have just captured on f2 (we already know it couldn't have been a pawn on f2 captured). And that's another formulation of the same inconsistency. Notice that if we are to assume that the non-pawn captured on f2 was a piece that resulted from the promotion of the f2-pawn, then it implies that the f2 pawn reached f7 with a check and was not captured by anything thus allowed to promote, but that's impossible as we know neither kings have moved yet, in other words, if the f2 pawn were to ever promote it must have gone passed the f7 square without being captured, which is impossible. Anyhow, let's end with the final correct diagram:
[title "Solution"]
[fen "r2qk2r/1ppbp1p1/1pn2n2/b2pP3/3P1N2/2N3P1/PPP2p2/R2QK2R w - - 0 1 "]
If you're interested in these kinds of discussions, have a look into the books of Raymond Smullyan, I even recall similar puzzles in one of his books but I have no copies at my disposal at the moment to check for you, maybe someone else can verify.
1: as the white pawn couldn't have made two captures to go around the black h pawn, because white has only made one capture in this game and that has been the f8 bishop on its original square.
