4
$\begingroup$

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.

  • 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!2011-09-06

1 Answers 1

3

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. 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$.