Valor de $k$ satisfacer esta condición

Question

En una pila de 100 piedras. Una partición de la pila en $k$ pilotes es buena si:

1) los pequeños montones tienen diferentes números de piedras;

2) para cualquier partición de uno de los pequeños montones en 2 pedazos más pequeños, entre las $k + 1$ montones de obtener 2 con el mismo número de piedras (cualquier pila tiene al menos 1 de piedra).

¿Cómo puedo encontrar el máximo y el mínimo de los valores de $k$ para los que esto es posible.

Answer 1

Es bastante fácil encontrar el máximo número posible de $k$. El más pequeño posible de la suma de $k$ distintos números enteros positivos es $\sum_{i=1}^k i = \frac{k(k+1)}{2}$. Para $k=14$ esto ya es $105$, que es demasiado grande, por lo que el $k$ no puede ser más que $13$. $\sum_{i=1}^13 i = 91$, que es demasiado pequeño por $9$, así que trate de aumentar el tamaño de la más grande de la pila de$13$$13 + 9 = 22$, haciendo montones de $1,2,3,\dots,11,12$ $22$ piedras. La división de cualquiera de estas pilas en dos produce una pequeña pila de tamaño en la mayoría de las $11$, coincidente con uno de los unsplit pilas. Por lo tanto, el valor máximo posible de $k$$13$.

El mínimo es bastante fácilmente visto en la mayoría de las $10$, el uso de pilas de tamaños $1,3,5,\dots,17,19$: $\sum_{i=1}^{10} (2k-1) = 100$, y la división de un número impar siempre producirá un menor número impar, la coincidencia de uno de los montones. La única pregunta que queda es si cualquier número menor que es bueno.

Deje $k$ ser bueno, con pilas de tamaños de $n_1 < n_2 < \dots < n_k$ testigos de este hecho. Considere la posibilidad de $n_i$ algunos $i>1$. Supongamos primero que $n_i = 2m$ es incluso. A continuación, podemos dividir la pila con $n_i$ piedras en $m$ formas diferentes, desde el $1+(n_i-1)$$m+m$. El incluso dividir el $m+m$ cuida de sí mismo, pero cada uno de los restantes $m-1$ divisiones tiene que incluir una pila de tamaño $n_j$ algunos $j<i$. Por lo tanto, debemos tener $m-1 \le i-1$, $m \le i$, y $n_i = 2m \le 2i$. Si $n_i = 2m+1$ es impar, todavía hay $m$ maneras de dividir el $i$-ésimo de la pila, de$1+(n_i-1)$$m+(m+1)$, pero esta vez todos de ellos tienen que incluir un montón de coincidencia de uno de los $i-1$ más pequeños montones, así que debemos tener $m \le i-1$ y por lo tanto $n_i \le 2(i-1)+1 =$ $2i-1$. En ambos casos tenemos $n_i \le 2i$.

Supongamos ahora que $k<10$: a continuación, por el resultado del último párrafo que hemos $$\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$.