induction-n-cents-postage-problem.md

Problem statement:

There are N kind of stamps with different prices, denoted by pi as price for i-th stamp. Prove that every amount of postage of x cents or more can be formed using just the stamps above (with price pi for each stamp).

Mathematically we can define:

x = c1.p1 + c2.p2 + ... + cN.pN

with ci is the number of i-th stamp with price pi to form postage of x cents.

notes: a configuration is a valid assignment for all ci by some whole number [0,1,2,3,...]

There are two approaches

1. Intuition: manually find some first configuration, i.e. configuration for postage of x cents, x+1 cents, x+2 cents, etc. If we've successfully find m first configuration, which is for x, x+1, x+2, ..., x+(m-1); and we have m-cent stamp, we can actually make all of the following configuration:

   x, x+1, x+2, ..., x+(m-1) [manually found], x+m, x+m+1, x+m+2, ..., x+m+(m-1) [adding m-cent stamp with m first configurations], x+2m, x+2m+1, x+2m+2, ..., x+2m+(m-1) [adding m-cent stamp with m previous configurations], and so on.

   To make our work easier, we can choose m as minimum value of stamp prices, i.e m = min {pi, for 0 < i <= N} So our effort for manually find the configuration will be as minimal as possible.

2. [Draft]This one is a bit more tricky. I don't know how to explain this in general form, so I will try to explain using only two stamps with price p1 and p2, but you should be able to conclude it in general term.

   Suppose you've successfully find a configuration for some x' = c1.p1 + c2.p2. You actually can find a configuration for x'+ 1 by substracting one of the coefficient and adding the other, if the substracted coefficient is enough and p1 and p2 is coprime (there's a theorem about this, but you don't have to understand that theorem for solving this problem).

   Using Pigeon Hole Principle intuition you can make

   Notes: you probably found manually some configuration prior to the PHP intuition

Example: