Coins change problem
Difference between en1 and en2, changed 0 character(s)
http://codeforces.net/contest/552/problem/C↵

In this problem, if $X \le w^k$ 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 $w^{k+2}, w^{k+3}, ...w^n$ will not be used. ↵

To start with the proof, I will take $w^{k+2}$ first.↵

I need to prove that $w^{k+2}$ is not used in all of the valid solutions which means, $w^{k+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 $w^{k+2}$ in left side or right side, I cannot arrive at a solution I would be complete with my proof. I will first put $w^{k+2}$ in the left (along with $X$) and see. I have $X + w^{k+2}$ on the left, I also know that $X \le w^k$. I can't work any further.↵

I am not able to prove how.↵

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)