Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a pile you have 100 stones. A partition of the pile in $k$ piles is good if:

1) the small piles have different numbers of stones;

2) for any partition of one of the small piles in 2 smaller piles, among the $k + 1$ piles you get 2 with the same number of stones (any pile has at least 1 stone).

How can I find the maximum and minimal values of $k$ for which this is possible.

share|improve this question
3  
I know you don't intend to be rude, but it is generally considered more polite to say "How can I determine the maximum and minimum values..." instead of "Find the maximum and minimum values...". –  Austin Mohr Sep 6 '11 at 1:14
    
Your answer is $10 \le k \le 13$. Helpful, isn't it? Now show us some work. –  Henning Makholm Sep 6 '11 at 1:23
    
well i would have if i arrived at something, will post if i get something –  Bhargav Sep 6 '11 at 1:31
1  
@168335 By work, we do not necessarily imply that you have any progress. It's ok if you are stuck at the problem. But we still would like to hear your thoughts. Do you have anything to say, even if it is easy/trivial? Where are you stuck? Do you have any approach at all? The approach may or may not work; do not bother about that yet. Tell us something! –  Srivatsan Sep 6 '11 at 1:51
add comment

1 Answer 1

up vote 3 down vote accepted

It’s fairly easy to find the maximum possible $k$. The smallest possible sum of $k$ distinct positive integers is $\sum_{i=1}^k i = \frac{k(k+1)}{2}$. For $k=14$ this is already $105$, which is too big, so the $k$ can’t possibly be more than $13$. $\sum_{i=1}^13 i = 91$, which is too small by $9$, so try increasing the size of the largest pile from $13$ to $13 + 9 = 22$, making piles of $1,2,3,\dots,11,12$ and $22$ stones. Splitting any of these piles in two produces a smaller pile of size at most $11$, matching one of the unsplit piles. Thus, the maximum possible value of $k$ is $13$.

The minimum is fairly easily seen to be at most $10$, using piles of sizes $1,3,5,\dots,17,19$: $\sum_{i=1}^{10} (2k-1) = 100$, and splitting an odd number will always produce a smaller odd number, matching one of the existing piles. The only remaining question is whether any smaller number is good.

Let $k$ be good, with piles of sizes $n_1 < n_2 < \dots < n_k$ witnessing this fact. Consider $n_i$ for some $i>1$. Suppose first that $n_i = 2m$ is even. Then we can split the pile with $n_i$ stones in $m$ different ways, from $1+(n_i-1)$ to $m+m$. The even split $m+m$ takes care of itself, but each of the remaining $m-1$ splits has to include a pile of size $n_j$ for some $j<i$. Thus, we must have $m-1 \le i-1$, $m \le i$, and $n_i = 2m \le 2i$. If $n_i = 2m+1$ is odd, there are still $m$ ways to split the $i$-th pile, from $1+(n_i-1)$ to $m+(m+1)$, but this time all of them have to include a pile matching one of the $i-1$ smaller piles, so we must have $m \le i-1$ and hence $n_i \le 2(i-1)+1 =$ $2i-1$. In both cases we have $n_i \le 2i$.

Suppose now that $k<10$: then by the result of the last paragraph we have $$\sum\limits_{i=1}^k n_i \le 2 \sum\limits_{i=1}^k i = k(k+1) \le 9\cdot 10 = 90 < 100,$$ too few stones altogether. Thus, $10$ is the minimum possible value of $k$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.