,
is a prime number. Show that if ![\[-1+\prod_{k=0}^{n-1} P\left(X^{p^k}\right)\]](http://latex.artofproblemsolving.com/5/d/f/5df80f885e63852e4f53a6145dafd18d63dc3526.png)
is divisible by 
.
are positive integers such that for every natural number 
are same. prove that 
.
and let 
be reals such that 
Y by huyaguero1106, Davi-8191, tenplusten, OlympusHero, RedFlame2112, megarnie, Quidditch, OronSH, Adventure10, Mango247, radian_51, and 10 other users
For each positive integer 
, the Bank of Cape Town issues coins of denomination 
. Given a finite collection of such coins (of not necessarily different denominations) with total value at most most 
, prove that it is possible to split this collection into 
or fewer groups, such that each group has total value at most 
.
, the Bank of Cape Town issues coins of denomination 
. Given a finite collection of such coins (of not necessarily different denominations) with total value at most most 
, prove that it is possible to split this collection into 
or fewer groups, such that each group has total value at most 
.This post has been edited 3 times. Last edited by codyj, Jul 12, 2014, 12:54 AM
value. Consider a finite collection of such coins (the coins do not necessarily have different values), having the sum of their values at most 
.
then we can divide the collection into 
groups with the sum of coin values in each group not exceeding 1.
big if 
and small otherwise.
as the product of an odd number and power of two, 
,
(there are 
.
,
since 
value. Let a collection of such finite coins (coins does not neccesarily have different values) which sum of their value is less than 
.
groups such that sum of all coins' value does not exceed 
it is trivial.
.
.
(others)
for 
is each time smaller than one.
such that the sum of values in 
and each new value is maximum 
.
,
,
.
by 
and consider the minimal counterexample, at first minimal by 
(else we may add the lightest coin). So 
,
.
,
and our counterexample is not minimal. Analogously, if there exist 
coins of weight 
.![\[
\sum_{k=1}^{n-1} \left(\frac 1{2k}+\frac{2k-2}{2k-1}\right)\leq 1/2+(n-2)\cdot 1=n-3/2
\]](http://latex.artofproblemsolving.com/c/d/c/cdc3eda12afd0265d02be67d48946426a856d589.png)
and our counterexamples works for 
instead of 
in the problem statement tight? It cannot be raised to 
(there are simple counter examples), but I see no reason why it cannot be raised to 
.
with 
appears twice, then replace it with a single coin of size 
.
appears 
times, group it into a single group and induct downwards.
,
,
.
(clearly there is at most one).
,
(at most 
of the former and at most one of the latter).
in a pile.
,![\[ k \left( 1 - \frac{1}{2k+1} \right) \]](http://latex.artofproblemsolving.com/5/f/d/5fdf9ddd6e9608578dc65980afb06c2654349b41.png)
to 
.
containers with a total sum at most 
.
,
.
and 
coins of the form 
.
,
.
.
-
,
However as 
,
a clear contradiction as we have already fit coins of this form.
we could extend to bounding coins of the form 
for some prime 
to one coin of value 
.
coins irrelevant by decreasing our 
of the coins with denominators 
.
)
this is obvious by multiplying. We can see that this proves the claim.
.
.
.
which obviously has size issues when 
can be split into 
since replacing two of them with one of denomination 
is a more restrictive version of the same problem. Similarly we assume that there are at most 
when 
since it is equivalent to decreasing 
and the situation cannot happen if 
so this will work).
Then we have all groups have total value more than 
so the total value of coins is greater than 
and thus 
so simplifying gives 
But now we can check that the total value of the coins placed before is less than or equal to 
This is less than 
so we must have 
but 
contradiction.
We have all groups have total value more than 
so the total value of coins is more than 
and this is less than or equal to 
Now we can see that the total value of coins placed before is less than or equal to 
which is less than 
so we must have 
but 
contradiction, so we are done.
coins of denomination 
,
coins of denomination 
,
and 
in pile 
,
,
in value, for a total of 
spent; we've used all our coins.
,
coins of value 
value coin into one group. Next, for all 
place all 
coins into one group. By our restrictions, this group has value at most![\[\frac{2n}{2n+1} + \frac{1}{2n+2} < 1\]](http://latex.artofproblemsolving.com/f/b/1/fb1e8377d43420b6fa01f810cf95a9bc39e2db4f.png)
Now we can just shove the rest of the coins that have value 
into any group that still has room. FTSoC, assume we can't do this. Then the total value is at least![\[n \cdot \left(1-\frac{1}{2n+1}\right) > n-\frac{1}{2}\]](http://latex.artofproblemsolving.com/8/7/d/87d37b13263e60afebded15aa5696ba79d459061.png)
a contradiction, which finishes the problem.
coins of denomination 
for a coin of denomination 
coins of denomination 
coins of denomination 
.
can be placed into groups.
which is a contradiction since the sum of the preexisting groups would be 
,
with 
.
with one coin 
.
with 
coins if denominator = 
.
containing the 
coin, and 
containing all coins 
.
etc. Distribute them into the sets, we can do this because the sets have sum less than 1. Suppose we are still left with some "extra" denominations. So, the "sets" each have sum as at least 
.
,
for a coin of denomination 
.
coins of denomination 
and at most ![\[\frac{2k-2}{2k-1}+\frac{1}{2k} = \frac{4k^2-2k-1}{4k^2-2k} < 1.\]](http://latex.artofproblemsolving.com/0/4/a/04a157cb2c54538b2d3cc8c5b2c58a054afb4dec.png)
,
,
,
Now, we have reduced the problem to showing that we can group coins with total value at most 
into at most 
groups, where the coins of even denomination appear at most once, and the coins of denomination 
occur at most 
times.
as well. Then, notice that we are left over with denominations at least 
in denominations. Hence, we are done.
as the total value we can split it into 
into the category labled 
,
)
.
,
occurrences of 
Now, we claim that, for all 
,
and therefore: total sum is at-least: 
But this implies: 
,
for all 
,
.
,
we exchange it for a coin of value 
and whenever we have 
to be separated into 
groups which is guaranteed to be possible by the induction hypothesis. So, assume we have no coins of size 1 after this optimization.
and at most 
,
in Box 
.
is the total value of ![\[S_k \leq \frac{2k-2}{2k-1} +\frac{1}{2k} = \frac{4k^2-4k+2k-1}{4k^2-2k} = \frac{4k^2-2k-1}{4k^2-2k}<1\]](http://latex.artofproblemsolving.com/b/6/b/b6bfc334f7055aee37015873bd96bf0010243928.png)
Thus, we can place all coins of weights 
using this algorithm.
-
from left to right). 
.
is,![\[(n-1)+\frac{1}{2}> S > n\left(1-\frac{1}{r}\right) = n - \frac{n}{r}\]](http://latex.artofproblemsolving.com/3/e/1/3e17a510d0af29ccdcf9887ba900576acc9bdafb.png)
which rearranges to 
.
and are dealing with smaller coins. Thus, this algorithm never breaks and we can reach our goal.
Given 
We will fit them into 
,
t
and 
Of the former type there are at most 
and of the latter type there is at most 
Now all that remains are coins of value less than 
worth of coins. Over all 
which is a contradiction. Q.E.D.
