Esta pregunta se refiere a la solución que se dará en Peter Winkler de la Matemática-Mente Dobladores para el "Rojo y Azul a los Dados" problema que aparece en la página $23.$
Tiene dos juegos (uno rojo, uno azul) de $n\ n-$caras de los dados, cada uno de los troqueles etiquetados con los números de $1$ a $n.$ sacas todos los $2n$ dados simultáneamente. Demostrar que no debe ser un subconjunto no vacío de los rojos y un subconjunto no vacío de los azules a los dados con la misma suma!
Traté de demostrarlo por inducción. Debe haber un $n$ laminados o podemos eliminar un dado de cada color y obtener un contraejemplo a la $n-1$ caso. Si hay solamente en $n$ laminados, nos lo puede quitar, y cualquier morir de otro color, y de nuevo un contraejemplo. Así que hay al menos dos red $n$'s, dicen. Pero yo no podía llevar la inducción de la idea. He probado hasta a $n=6,$ con la esperanza de ver un patrón, pero todo lo que obtuve fue una colección de argumentación ad hoc. Después de varios días, me di por vencido y miró a la respuesta.
Una solución está dada en las páginas $33-34.$ Winkler aconseja probar una declaración más fuerte.
De hecho, hay una mucho más fuerte declaración de la que se pidió a probar, que es, no obstante, sigue siendo cierto. Organizar la red de dados en línea, en cualquier forma que quieras, y hacer lo mismo con el azul de los dados. Entonces hay una contiguos subconjunto no vacío de cada línea con la misma suma.
Para ponerlo más matemáticamente, dados cualesquiera dos vectores $\langle a_1,\dots,a_n\rangle$ e $\langle b_1,\dots,b_n\rangle$ en $\{1,\dots,n\}^n,$ hay $j\le k$ e $s\le t$ tal que $\sum_{i=j}^k{a_i}=\sum_{i=s}^t{b_i}.$
Para ver esto, vamos a $\alpha_m$ ser la suma de los primeros a$m\ a_i$'s y deje $\beta_m$ ser la suma de los primeros a$m\ b_i$'s. Suponga que $\alpha_n\le\beta_n$ (de lo contrario podemos cambiar los roles de la $a$'s y $b$'s), y para cada una de las $m,$ deje $m'$ ser el mayor índice de que $\beta_{m'}\le\alpha_m.$
Winkler da un diagrama con dos ejemplo de cadenas de caracteres, líneas de unirse a $a_m$ e $b_{m'}$ etiquetado por $\alpha_m-\beta_{m'}$
Es evidente que el $a_i$ son los dados en la parte superior y el $b_i$ aquellos en la parte inferior. Tenga en cuenta que tenemos $\alpha_6=22,\ \beta_6=18,$ contradiciendo $\alpha_n\le\beta_n,$ así que me imagino que el último fue un error de tipeo. También, la línea marcada $3$ unirse a $a_3$ e $b_4$ realmente debería terminar en $b_5$ y ser etiquetados $0,$ pero supongo que esto es sólo un error.
De todos modos, Winkler dice,
Siempre tenemos $\alpha_m-\beta_{m'}\ge0,$ y en la mayoría de las $n-1$ (si $\alpha_m-\beta_{m'}$ eran mayores que o igual a $n,\ m'$ habría sido un mayor índice).
Entonces va a observar que si alguna de las etiquetas es $0$ hemos terminado, así que tenemos $n$ etiquetas de $1$ a $n-1$ y dos son iguales. Entonces la suma de la intervención de los dados debe ser el mismo. Por ejemplo, en la imagen tenemos dos líneas marcadas $2,$ y tenemos $6+5+3=3+2+3+6.$
A mí me parece que hay dos agujeros en esta prueba. La primera es la declaración de que las etiquetas deben ser de menos de $n$. Supongamos que $\alpha_n-\beta_n\ge n.$ Entonces $n'=n,$ y no hay mayor índice. Entonces, quizás $\alpha_n\le\beta_n$ es justo después de todo, y el diagrama que está mal. Pero esto deja el segundo problema, que no dependen de la relación entre el $\alpha_n$ e $\beta_n.$ Supongamos que $a_1<b_1.$ Cómo es $1'$ a ser definido?
Pensé en abandonar la declaración más fuerte, y tratando de resolver el rompecabezas por la organización de las $a_i$ en la disminución de la orden y de la $b_i$ , en orden creciente, pero no veo cómo desechar el caso de $\max{a_i}>\min{b_i}.$ Winkler del argumento no puede ser aplicado, y no veo la manera de deshacerse de ella de otra manera.
No he sido capaz de rescatar a esta prueba. Estoy con vistas a algo? Se puede resolver el rompecabezas?
Nota: Winkler decir que algunos resultados similares se pueden encontrar en un papel por Diaconis, Graham, y Sturmfels. No he probado a leer el papel todavía, pero parece un poco pesado para la solución de un rompecabezas. También, Winkler se dice que el origen del rompecabezas fue David Kempe de la USC, "que necesitaba el resultado en ciencias de la computación de papel", pero no da ninguna referencia adicional.
P. S.
He encontrado una lista de David Kempe publicaciones, pero no puedo decir que es probable que contenga una prueba del teorema.
