Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

4 votos

Valor de k satisfacer esta condición

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.

5voto

DiGi Puntos 1925

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 ki=1i=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. 1i=13i=91, que es demasiado pequeño por 9, así que trate de aumentar el tamaño de la más grande de la pila de1313+9=22, haciendo montones de 1,2,3,,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 k13.

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,,17,19: 10i=1(2k1)=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 n1<n2<<nk testigos de este hecho. Considere la posibilidad de ni algunos i>1. Supongamos primero que ni=2m es incluso. A continuación, podemos dividir la pila con ni piedras en m formas diferentes, desde el 1+(ni1)m+m. El incluso dividir el m+m cuida de sí mismo, pero cada uno de los restantes m1 divisiones tiene que incluir una pila de tamaño nj algunos j<i. Por lo tanto, debemos tener m1i1, mi, y ni=2m2i. Si ni=2m+1 es impar, todavía hay m maneras de dividir el i-ésimo de la pila, de1+(ni1)m+(m+1), pero esta vez todos de ellos tienen que incluir un montón de coincidencia de uno de los i1 más pequeños montones, así que debemos tener mi1 y por lo tanto ni2(i1)+1= 2i1. En ambos casos tenemos ni2i.

Supongamos ahora que k<10: a continuación, por el resultado del último párrafo que hemos ki=1ni2ki=1i=k(k+1)910=90<100, too few stones altogether. Thus, 10 is the minimum possible value of k.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X