Coins change problem

Revision en5, by bhikkhu, 2015-10-28 12:31:14

Guys, please answer this, it won't take much time for those who have already solved this.

http://codeforces.net/contest/552/problem/C

In this problem, if X ≤ wk for where k is the largest possible, then we don't need to use all coins that have higher power than k + 1, i.e. coins wk + 2, wk + 3, ...wn will not be used.

To start with the proof, I will take wk + 2 first.

I need to prove that wk + 2 is not used in all of the valid solutions which means, wk + 2 doesn't occur either on the left or right side of the equation shown at the top. Now, if I could somehow prove that using wk + 2 in left side or right side, I cannot arrive at a solution I would be complete with my proof. I will first put wk + 2 in the left (along with X) and see. I have X + wk + 2 on the left, I also know that X ≤ wk. I can't work any further.

I am not able to prove how.

Ok, guys I got it!!!! (someone helped me). Here's a more easy proof.

Lets think a different way. What are the coin changes that I can make using wk + 2. What is the smallest such change? The smallest change is equal to when we put wk + 2 on the left and all smaller weights on the right i.e.

wk + 2 - wk + 1 - wk - .... - w0

Unable to parse markup [type=CF_TEX]

— 1)/(w - 1)

But this amount is greater than wk.

Thus, if we use wk + 2, the change must be greater than wk. But, X ≤ wk. So, we can't make any such X. Proof is complete.

Tags coin, change

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English bhikkhu 2015-10-28 12:34:14 25 Tiny change: ' ($w^{k+2}$ — 1)/($w-1$) ' -
en5 English bhikkhu 2015-10-28 12:31:14 561
en4 English bhikkhu 2015-10-27 23:19:29 0 (published)
en3 English bhikkhu 2015-10-27 23:19:16 93 (saved to drafts)
en2 English bhikkhu 2015-10-27 12:35:50 0 (published)
en1 English bhikkhu 2015-10-27 12:35:30 832 Initial revision (saved to drafts)