I didn't say that a proof wasn't in principle accessible to them; I said that it wasn't obvious. In particular, if the students in question didn't indicate that they were going through some such proof - and surely, previous posters would have remarked on it if they had - then I don't believe they had a proof in mind. (In fact, if your kids go to a school where many 3rd graders would be capable of producing one, I expect many people here would be envious!)
Admittedly, now that I reread the earlier post, I see that some of the students described as being weak at problem-solving apparently didn't understand what they were being asked to do, which speaks against my hypothesis that they might actually have had a better understanding of the problem than those who leapt at an algorithm and (I surmise) didn't engage with the question of why their algorithm worked.
Incidentally, DH pointed out to me that the UK's pre-decimalisation coin system had the property that the greedy algorithm did not always work.
