People crossing a bridge (a proof for a greedy algorithm)
The reason you can't prove that the greedy algorithm is correct is because it isn't.

Suppose the people cross the bridge in times 1, 2, 5 and 10 minutes.  The greedy solution involves the one-minute person walking backwards and forwards every time and takes 10+1+5+1+2=19 minutes.  The optimal solution is 17 minutes (spoiler, since it's a famous puzzle that people might want to try on their own).


   1 and 2 cross, 2 returns with the flashlight, then 5 and 10 cross and 1 returns with the flashlight to collect 2: total time 2+2+10+1+2=17 minutes.