Contradicción prueba de descenso infinito de estrategias de resolución de problema de Arthur Engel Q11 Ch-14

Question

La pregunta va como sigue:

$2n+1$ donde $(n \geq 1)$ integral de los pesos se dan. Si queremos eliminar alguno de los pesos, el resto de las $2n$ pesos se puede dividir en dos montones de igualdad de pesos. Demostrar que todos los pesos son iguales.

Yo estaba discutiendo el libro con mi maestra y ella me dijo que había encontrado una contradicción con la declaración. Básicamente, tome $2n$ peso de peso $1$ (es decir $blue$ pesos) y un peso de peso $2n-1$ (es decir $red$ peso). Aquí, si queremos eliminar un azul de peso, entonces podemos dividir con uno rojo peso de un lado y el resto $2n-1$ azul pesos en el otro. Si queremos eliminar el rojo de peso, entonces podemos dividir el resto azul pesos en dos particiones de tamaño $n$. Esta partición se satisface la condición dada y todos los pesos no son iguales aquí.

Estamos tan mal aquí? ¿Cómo es eso? Porque se me hace difícil de digerir Arthur Engel estar tan mal, porque en la sección de solución, él dice que esto puede ser extendido a la racional y la irracional pesos así. También, si no tenemos, donde está el paso de Arthur Engel prueba que domina nuestro caso?

Voy a poner la solución original aquí, exactamente como se da en PSS:

Deje $w_1,...,w_{2n+1}$ ser la integral de pesos. Desde cualquier $2n$ de los pesos de equilibrio, la suma de cualquiera de las $2n$ de los pesos es incluso. Esto implica que todos ellos son de la misma paridad. Si son iguales, nos pusimos $w_i \leftarrow \frac{w_i}{2}$, y si son impares, nos pusimos $w_i \leftarrow \frac{w_i-1}{2}$. En cada caso se obtiene un nuevo conjunto de pesos con el mismo equilibrio de la propiedad. La aplicación de esta reducción en repetidas ocasiones, vemos que el $w_i$ son congruentes mod $2^k$ todos los $k$. Esto implica que todos los w_i son iguales.

Generalizar el resultado racional pesos, que es fácil, y para irracional de pesos, que es mucho más difícil.

Answer 1

Como se menciono en los comentarios, yo creo que en el problema debemos tener restringido que los dos montones, nos dividimos en tienen el mismo tamaño. Para justificar esto, voy a explicar cómo la solución de la falla sin esta solución, pero trabaja con él.

El paso fundamental es la reducción de la $w_i\leftarrow\frac{w_i-1}{2}$. Engel afirma que "[...] tenemos un nuevo set de pesas con el mismo equilibrio de la propiedad", pero esto no es necesariamente cierto - si lo aplicamos al ejemplo de su maestro dio (con $n=2$), $1,1,1,1,3$, entonces esto tiene el equilibrio de la propiedad como usted menciona, pero después de la reducción no - se $0,0,0,0,1$, y después de quitar un cero que no se puede dividir en dos montones de igualdad de peso, desde que uno tiene que tener peso $0$, otro peso $1$.

Así que vamos a intentar ver por qué una "evidente" el argumento no nos da que el equilibrio de la propiedad se conserva. Después de quitar un peso, decir $w_1$, podemos dividir los otros en dos montones, decir $w_2,\dots, w_{k+1}$ $w_{k+2},\dots,w_{2n+1}$ del tamaño de la $k$$2n-k$, por lo que el $w_2+\dots+w_{k+1}=w_{k+2}+\dots+w_{2n+1}=W$. Esperamos que este equilibrio llevaría a un equilibrio en un nuevo conjunto de pesos. Vamos a ver si se hace: $$\frac{w_2-1}{2}+\dots+\frac{w_{k+1}-1}{2}=\frac{w_2+\dots+w_{k+1}}{2}-\frac{k}{2}=\frac{W}{2}-\frac{k}{2},\\ \frac{w_{k+2}-1}{2}+\puntos+\frac{w_{2n+1}-1}{2}=\frac{w_{k+2}+\dots+w_{2 +1}}{2}-\frac{2n-k}{2}=\frac{W}{2}-\frac{2n-k}{2}.$$ Estos son iguales sólo al $k=2n-k$, es decir, cuando las pilas tengan tamaños iguales. Así que en general, no tenemos garantías de que el nuevo peso el equilibrio de los bienes, a menos que se le agregue la restricción en el problema de que los montones tener tamaños iguales.