USACO Dec06 Fewest Coins Proof?

Правка en1, от szawinis, 2017-03-07 12:10:15

Hi. I'm currently trying to solve this problem, and since I can't solve it, I looked at the editorial.

It said: Let V be the largest coin value, and call this type of coin silver and all other coins brass. It is not difficult to prove that for any change amount of at least V^2, it is possible to use at least one silver coin (hint: consider the partial sums modulo V), and hence that in making change of at least 2V^2 there can be at least V silver coins. Now if Farmer John pays at least 2V^2, and hence pays with V coins, then a similar argument shows that some set of them adds up to a multiple of V and at most V^2, which can be cancelled out with the silver coins in the change. So the change amount can never exceed 2V^2.

What does this mean? And how do we prove this?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский szawinis 2017-03-07 12:10:15 905 Initial revision (published)