Hay 10 objetos con peso total 20, cada uno de peso siendo un número entero positivo. Dado que ninguno de los pesos exceden 10, probar diez objetos pueden dividirse en dos grupos que equilibra entre sí cuando se coloca en las dos cacerolas de equilibrio. Consejos son apreciados.
Lo siento no sé cómo empezar este problema, por lo que no he mostrado los esfuerzos.
Este resultado se da en el caso general, con $2m$ objetos de peso total $4m$, con ninguno de los pesos superiores a $2m$.
Si una lista de P de los números enteros positivos sumas a$n$, entonces P se denomina partición de $n$. Vamos a |P| denota el número de elementos en P.
Sea S' el conjunto de las particiones P' de $2n$ |P'| = $n$ (es decir, cada partición P' en S "$n$ elementos y P' sumas de dinero a $2n$) con ningún elemento de P' superior a $n$.
Podemos transformar S' en un conjunto S restando 1 de cada elemento de cada uno de los P' en S'. S es entonces el conjunto de todas las particiones P de $n$, excepto para el singleton de la partición [$n$], ya que hemos reducido la suma de cada una de las P'$n$, y cada una |P| $ \le n$. Por el contrario, dado que S podemos recuperar S' mediante la adición de 1 a cada elemento existente en cada P y relleno de cada P con extra para obtener la longitud necesaria.
Así que podemos atacar el problema señalado en la pregunta examinando el conjunto de todas las particiones de 10 (a excepción de la partición de [10]), más que el conjunto de particiones de 20 de longitud 10 con ningún elemento superior a 10.
Dada una partición P de $n$, divida sus elementos en dos listas a y B de aproximadamente sumas iguales. Deje $a$ la suma de los elementos de a, y $b$ la suma de los elementos de B; $a + b = n$. WLOG, suponga $a \ge b$. Queremos minimizar la diferencia de $d = a - b$. Esto puede lograrse mediante un simple "codiciosos" algoritmo.
La prueba de que este algoritmo hace, de hecho, minimizar $d$ se deja como ejercicio para el lector. :)
Ahora sólo tenemos que añadir la $a$ queridos a B y $b$ queridos a Una para obtener equilibrio en pesos. Pero este paso sólo es válida si $|A| \le b$$|B| \le a$, ya que se debe agregar uno a cada elemento existente en a y en B.
$1 \le b \le n/2 \le a \lt n $
$n$ es aún, por lo $n/2$ es un número entero.
Claramente, para cualquier P, la suma de sus elementos debe ser $ \ge |P|$, ya que cada elemento de P es al menos 1.
Por lo $|B| \le b \le a$, lo $|B| \le a$. Sólo queda demostrar que $|A| \le b$.
Si $d = 0$$a = b = n/2$$|A| \le n/2 = b$.
Ahora nos fijamos en el caso de que $d > 0$.
$a + b = n$, que es mucho, por lo $d = a - b$ es también incluso. Y ya es distinto de cero en lo que sigue, su valor mínimo es 2.
Para cualquier elemento $t$ en Una, si $t < d$ podríamos intercambiar $t$ a B a reducir la diferencia:
$$\begin{align} \text{Let }& 0 < t < d\\ \text{Let }d' & = (a-t) - (b+t)\\ & = a - b - 2t\\ d' & = d - 2t\\ -d & < -t < 0\\ -2d & < -2t < 0\\ -d & < d-2t < d\\ -d & < d' < d\\ |d'| & < d \end{align}$$
But A and B have been constructed to minimize $d$, so all elements in A must be $ \ge d$.
Si |A| se $\gt b$, es un valor mínimo sería $b+1$, y el valor mínimo de $a$ así sería
$$\begin{align} (b + 1)d & = bd + d\\ & = bd + a - b\\ & = b(d-1) + a\\ \end{align}$$
But $d$ is an even integer > 0, so $b(d-1) + a \ge b + a = n >$, y tenemos una contradicción.
Por lo tanto $|A| \le b$.
Actualización
Que la prueba indirecta de que $|A| \le b$ ha sido molesto conmigo. :) Así que aquí está una prueba directa.
Cada elemento de a es $ \ge d$, lo $a \ge |A|d$
$$\begin{align} d & > 1\\ bd & > b\\ bd + d & > b + d = a \ge |A|d\\ (b + 1)d & > |A|d\\ b + 1 & > |A|\\ b & \ge |A|\\ \end{align}$$
He encontrado algunos muy algoritmos eficientes para la generación de particiones a través de esta respuesta a la pregunta Algoritmo de generación de particiones de enteros. Usted puede ver el original de código de Python para que el algoritmo de particionamiento en Jerome Kelleher del sitio, y su documento sobre la eficacia de los diversos algoritmos de particionamiento en arXiv la Generación de Todas las Particiones: Una Comparación De Dos Codificaciones. La mayoría de los algoritmos de particionamiento de encontrar en la Red son recursivos, así que es agradable ver a algunos eficiente de los algoritmos iterativos. :) Según Jerónimo de papel, el algoritmo optimizado que aparece en su sitio web es la forma más eficiente de partición algoritmo conocido.
En el cierre, aquí están los resultados de algunos de Python de código que escribí mientras que para abordar este problema. Las particiones son ordenados en d y la partición de los elementos.
Balanced partitions for 10
1: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
0, [1, 1, 1, 1, 1] 5, [1, 1, 1, 1, 1] 5
[2, 2, 2, 2, 2], [2, 2, 2, 2, 2]
2: [2, 1, 1, 1, 1, 1, 1, 1, 1]
0, [2, 1, 1, 1] 5, [1, 1, 1, 1, 1] 5
[3, 2, 2, 2, 1], [2, 2, 2, 2, 2]
3: [2, 2, 1, 1, 1, 1, 1, 1]
0, [2, 1, 1, 1] 5, [2, 1, 1, 1] 5
[3, 2, 2, 2, 1], [3, 2, 2, 2, 1]
4: [2, 2, 2, 1, 1, 1, 1]
0, [2, 2, 1] 5, [2, 1, 1, 1] 5
[3, 3, 2, 1, 1], [3, 2, 2, 2, 1]
5: [2, 2, 2, 2, 1, 1]
0, [2, 2, 1] 5, [2, 2, 1] 5
[3, 3, 2, 1, 1], [3, 3, 2, 1, 1]
6: [3, 1, 1, 1, 1, 1, 1, 1]
0, [3, 1, 1] 5, [1, 1, 1, 1, 1] 5
[4, 2, 2, 1, 1], [2, 2, 2, 2, 2]
7: [3, 2, 1, 1, 1, 1, 1]
0, [3, 1, 1] 5, [2, 1, 1, 1] 5
[4, 2, 2, 1, 1], [3, 2, 2, 2, 1]
8: [3, 2, 2, 1, 1, 1]
0, [3, 1, 1] 5, [2, 2, 1] 5
[4, 2, 2, 1, 1], [3, 3, 2, 1, 1]
9: [3, 2, 2, 2, 1]
0, [3, 2] 5, [2, 2, 1] 5
[4, 3, 1, 1, 1], [3, 3, 2, 1, 1]
10: [3, 3, 1, 1, 1, 1]
0, [3, 1, 1] 5, [3, 1, 1] 5
[4, 2, 2, 1, 1], [4, 2, 2, 1, 1]
11: [3, 3, 2, 1, 1]
0, [3, 2] 5, [3, 1, 1] 5
[4, 3, 1, 1, 1], [4, 2, 2, 1, 1]
12: [3, 3, 2, 2]
0, [3, 2] 5, [3, 2] 5
[4, 3, 1, 1, 1], [4, 3, 1, 1, 1]
13: [4, 1, 1, 1, 1, 1, 1]
0, [4, 1] 5, [1, 1, 1, 1, 1] 5
[5, 2, 1, 1, 1], [2, 2, 2, 2, 2]
14: [4, 2, 1, 1, 1, 1]
0, [4, 1] 5, [2, 1, 1, 1] 5
[5, 2, 1, 1, 1], [3, 2, 2, 2, 1]
15: [4, 2, 2, 1, 1]
0, [4, 1] 5, [2, 2, 1] 5
[5, 2, 1, 1, 1], [3, 3, 2, 1, 1]
16: [4, 3, 1, 1, 1]
0, [4, 1] 5, [3, 1, 1] 5
[5, 2, 1, 1, 1], [4, 2, 2, 1, 1]
17: [4, 3, 2, 1]
0, [4, 1] 5, [3, 2] 5
[5, 2, 1, 1, 1], [4, 3, 1, 1, 1]
18: [4, 4, 1, 1]
0, [4, 1] 5, [4, 1] 5
[5, 2, 1, 1, 1], [5, 2, 1, 1, 1]
19: [5, 1, 1, 1, 1, 1]
0, [5] 5, [1, 1, 1, 1, 1] 5
[6, 1, 1, 1, 1], [2, 2, 2, 2, 2]
20: [5, 2, 1, 1, 1]
0, [5] 5, [2, 1, 1, 1] 5
[6, 1, 1, 1, 1], [3, 2, 2, 2, 1]
21: [5, 2, 2, 1]
0, [5] 5, [2, 2, 1] 5
[6, 1, 1, 1, 1], [3, 3, 2, 1, 1]
22: [5, 3, 1, 1]
0, [5] 5, [3, 1, 1] 5
[6, 1, 1, 1, 1], [4, 2, 2, 1, 1]
23: [5, 3, 2]
0, [5] 5, [3, 2] 5
[6, 1, 1, 1, 1], [4, 3, 1, 1, 1]
24: [5, 4, 1]
0, [5] 5, [4, 1] 5
[6, 1, 1, 1, 1], [5, 2, 1, 1, 1]
25: [5, 5]
0, [5] 5, [5] 5
[6, 1, 1, 1, 1], [6, 1, 1, 1, 1]
26: [2, 2, 2, 2, 2]
2, [2, 2, 2] 6, [2, 2] 4
[3, 3, 3, 1], [3, 3, 1, 1, 1, 1]
27: [3, 3, 3, 1]
2, [3, 3] 6, [3, 1] 4
[4, 4, 1, 1], [4, 2, 1, 1, 1, 1]
28: [4, 2, 2, 2]
2, [4, 2] 6, [2, 2] 4
[5, 3, 1, 1], [3, 3, 1, 1, 1, 1]
29: [4, 3, 3]
2, [3, 3] 6, [4] 4
[4, 4, 1, 1], [5, 1, 1, 1, 1, 1]
30: [4, 4, 2]
2, [4, 2] 6, [4] 4
[5, 3, 1, 1], [5, 1, 1, 1, 1, 1]
31: [6, 1, 1, 1, 1]
2, [6] 6, [1, 1, 1, 1] 4
[7, 1, 1, 1], [2, 2, 2, 2, 1, 1]
32: [6, 2, 1, 1]
2, [6] 6, [2, 1, 1] 4
[7, 1, 1, 1], [3, 2, 2, 1, 1, 1]
33: [6, 2, 2]
2, [6] 6, [2, 2] 4
[7, 1, 1, 1], [3, 3, 1, 1, 1, 1]
34: [6, 3, 1]
2, [6] 6, [3, 1] 4
[7, 1, 1, 1], [4, 2, 1, 1, 1, 1]
35: [6, 4]
2, [6] 6, [4] 4
[7, 1, 1, 1], [5, 1, 1, 1, 1, 1]
36: [7, 1, 1, 1]
4, [7] 7, [1, 1, 1] 3
[8, 1, 1], [2, 2, 2, 1, 1, 1, 1]
37: [7, 2, 1]
4, [7] 7, [2, 1] 3
[8, 1, 1], [3, 2, 1, 1, 1, 1, 1]
38: [7, 3]
4, [7] 7, [3] 3
[8, 1, 1], [4, 1, 1, 1, 1, 1, 1]
39: [8, 1, 1]
6, [8] 8, [1, 1] 2
[9, 1], [2, 2, 1, 1, 1, 1, 1, 1]
40: [8, 2]
6, [8] 8, [2] 2
[9, 1], [3, 1, 1, 1, 1, 1, 1, 1]
41: [9, 1]
8, [9] 9, [1] 1
[10], [2, 1, 1, 1, 1, 1, 1, 1, 1]
Deje que los pesos se $x_1, x_2, ... x_{10}$, de tal manera que $x_1 \neq x_2$. Necesitamos encontrar un subconjunto de es tal que la suma de sus elementos es $10$.
Considerar, $x_1, x_2, x_1+x_2, ..., x_1+x_2+x_3 + .. +x_9$. Tenga en cuenta que si uno de ellos es divisible por $10$, entonces debe ser exactamente $10$, como debe de ser menor que $20$. Por lo tanto, si uno de ellos es divisible por $10$, hemos terminado, si no, por el principio del palomar, dos de ellos tienen el mismo resto$\mod10$.
Si restamos estos dos subconjuntos, tenemos un subconjunto cuya suma es divisible por $10$, pero que no podían ser $0$ o $20$, por lo que debe ser $10$. Tenga en cuenta que estos dos no pueden ser$x_2$$x_1$, ya que implicaría $x_2>10$.
No creo que hay un procedimiento estándar, similar a la de "Maestro Teorema", que puede ser aplicado a su problema. (Tal vez alguien viene con una pigeon-hole-principio de la solución.) Esto significa que tenemos que jugar con el problema buscando en los casos, en orden a conseguir la sensación de que. El objetivo es configurar todo de tal manera que un mínimo de los casos tiene que ser discutido.
Actualización
Un objeto de peso $1$ "bajo peso" $1$, un objeto de peso $2$ tiene un peso normal, y cualquier objeto con peso $w\geq3$ tiene sobrepeso $w-2>0$, que tiene que ser compensada por $w-2$ objetos de tener peso $1$.
Si hay un objeto $A_0$ peso $w\geq6$ hay $\geq4$ objetos de $A_k$ peso $1$. Suplemento$A_0$ $10-w\leq4$ estos $A_k$ a fin de obtener la $10$.
A partir de ahora, podemos suponer que todos los objetos tienen peso $\leq 5$. Si hay dos objetos $A_1$, $A_2$ de peso $3$, $4$, o $5$, y de peso total $w\geq7$, en el total de su peso es $\geq3$, donde hay $\geq3$ objetos de $A_k$ peso $1$. Suplemento $A_0\cup A_1$ $10-w\leq3$ estos $A_k$ a fin de obtener la $10$.
El peso restante patrones son de la forma $$(5,2^6,1^3), \quad (4,2^7,1^2), \quad (3^\alpha,2^{10-2\alpha}, 1^\alpha)$$ con $0\leq\alpha\leq5$, y son fáciles de tratar.
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.
