Coins change problem

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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

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

In this problem, if X ≤ 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ⁿ 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 ≤ w^k. 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 w^k + 2. What is the smallest such change? The smallest change is equal to when we put w^k + 2 on the left and all smaller weights on the right i.e.

w^k + 2 - w^k + 1 - w^k - .... - w⁰

w^k + 2 — (w^k + 2 - 1) / (w - 1)

But this amount is greater than w^k.

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

Comments (5)

Write comment?

bhikkhu

8 years ago, # |

Auto comment: topic has been updated by bhikkhu (previous revision, new revision, compare).

→ Reply

brighterstill

← Rev. 2 →

One thing to notice in the question is that you have exactly 1 weight of each power (k from 0 to 100.) suppose we place w^(k+2) on the left side along with the weight X. Now to counter-balance this on the right side even if you take all lower powers (that is from w^0 to w^(k+1) it wont be enough to match w^(k+2) , (this comes by the GP summation formula), and definitely not w^(k+2)+X. so we have to take w^(k+3) on the right side. Now balancing left side will be a problem . How? Suppose you place all weights of all lower available powers on left pan (w^0 to w^(k+1)). Now as X<= w^k, further summation of all weights from i=0 to i=k-1 will be less than w^(k)(Again by GP summation). if to this we add X we have a currentsum< w^(k+1) , along with this we are still left with w^(k+1) and w^(k+2). to current sum if we add w^(k+1) new current sum will be less than w^(k+2),and we are left with w^(k+2) on adding this to current sum we can say that the final sum on left pan will be less than w^(k+3)(Similar argument as for w^(k+2)). So we will have to take assistance of w^(k+4) on left pan to counter right pan. You can notice by induction that it will be a never ending procedure and as limit of k is finite(100),if we don't arrive at a solution with powers<=k+1 , we will never arrive at the solution. Hope it helps. (Sorry it went that long) :).

8 years ago, # ^ |

← Rev. 3 →

What I have found is that, if there is a solution using w^k + 2 or higher coins, then there will be a solution without using w^k + 2 or higher coins. So, if i use the coin to arrive at a solution(if there is a solution using that coin), i could have not used the coin and arrived at the solution too.

It is not the case that you won't have solution using w^k + 2 or higher coins.

I don't know if I am correct on this.

bhikkhu's blog