Pesando arroz (variante)

[carroza]

Tenemos un saco de arroz, con bastante arroz pero con peso indefinido, y una balanza. Nos permiten utilizar cuatro pesas, cuyas masas podemos fijar a priori, pero que no podemos cambiar.
Queremos determinar, en una unica pesada cada vez (un único equilibrio de la balanza), raciones de 100 g, 200, 300, y así consecutivamente.

1) Cuál es la máxima racion que podemos obtener (supuesto que tambien somos capaces de obtener todas las raciones inferiores, de 100 en 100 gramos).

2) Cuales son las masas de las cuatro pesas.

[teclado]

Re: Pesando arroz (variante)

Así de entrada diría que las pesas tendrían que ser de 100g, 200g, 400g y 800g, pudiendo pesar un máximo de 1.5kg de 100g en 100g igual que contamos de 1 en 1 con 4 bits de 0 a 15.

Obviamente debe haber al menos una pesa de 100g... De lo contrario no podrías pesar 100g. Si hubiera más para poder pesar 300g la siguiente tendría que ser de 100g o de 300g. Si fuera de 100 la siguiente debería ser también de 100 para poder pesar el máximo de 400 (menor que 1500). Si fuera de 300 ya podríamos pesar hasta 500g, pero la última tendría que pesar 600 para poder seguir, de modo que podríamos pesar un total de 1100g (menor que 1500g).

De modo que la siguiente debe ser de 200, pues de lo contrario no podríamos pesar 200g. Si hubiera más de una de 200, para poder pesar 600 necesitaríamos una más de 100, que ya dijimos que no era plan, o una cuarta de 200, con lo que haríamos un total de 700g (menor que 1500g).

Habiendo descartado más pesas de 100 y 200 para pesar 400g necesitaríamos una tercera de 400 (o una de 300, lo cual es absurdo porque ya tenemos las de 100 y 200). Con esto ya podemos pesar de 100 en 100 desde 100 hasta 700, de modo que para pesar de 800 en adelante necesitaríamos una nueva pesa, la de 800.

[carroza]

Re: Pesando arroz (variante)

Teclado, esa sería la solución si las pesas estuvieran siempre en un platillo de la balanza, y el arroz en el otro.

Saludos

[teclado]

Re: Pesando arroz (variante)

¡Ahá! ¡No había contado con ello! De esta forma cada pesada deja de poder resumirse en un número de base 2, y hace falta una base 3, pero que admite coeficientes negativos (si la pesa se coloca en el lado del arroz resta (-1), si se coloca en el otro suma (1) y si no se coloca no hace nada (0)). Sería interesante elaborar un poco cómo se puede relacionar un número expresado de esta manera (p.ej. +-0-_(3')=17₍₁₀₎) con otro expresado en una base 3 de las de toda la vida (p.ej. 122₍₃₎=17₍₁₀₎), pero por ahora voy a intentar explicar por qué de esta manera podemos pesar de 100 en 100 gramos de manera que podamos pesar la máxima cantidad, así que vayan afilando los cuchillos que va para largo:

Ocultar contenido

Mostrar solución Ocultar solución

Si llamamos x₁, x₂, x₃ y x₄ a las masas de las pesas, una pesada cualquiera p_i estará dada por:

$a_{i1}x_1+a_{i2}x_2+a_{i3}x_3+a_{i4}x_4=p_i,\,\,a_{ij}=-1,0,1,\,\,i=1,...,N$

El número de pesadas posibles N es el de todas las combinaciones de 3 elementos, -1 (la pesa se coloca a un lado de la balanza), 0 (no se coloca la pesa) y 1 (la pesa se coloca al otro lado de la balanza) tomados de 4 en 4 con repeticiónes, a saber N=3⁴=81. Por otro lado si tuviéramos 2 o más pesas iguales habría pesadas distintas que darían medidas p_i iguales. Como queremos abarcar el rango más amplio posible de medidas, si encontramos unas pesas que siendo todas distintas nos permitan pesar de 100 en 100 gramos ya lo tendremos.

Es evidente que hay una simetría en el problema, que consiste en colocar el arroz a un lado u otro de la balanza. Con este planteamiento los resultados de las pesadas (p_i) estarán repartidos entre valores negativos cuando el arroz se ponga en uno de los platos, el 0 y valores positivos cuando el arroz se ponga en el otro. Dicho de otro modo, tendremos (N-1)/2 pesadas negativas, una que valdrá 0 y otras (N-1)/2 positivas, lo que si todo sale bien nos permitirá pesar hasta 4kg de 100 en 100 gramos. Esta simetría además implica que p_i=-p_N-i+1 (supondremos que las ecuaciones de antes están ordenadas en valores crecientes de p_i), y como las pesas x_k son todas distintas, además a_ik=-a_N-i+1,k. Considerando trivial el caso en que p_i=0 (i=(N+1)/2) y expresando los resultados de las pesadas p_i en hectogramos, nos queda el siguiente conjunto de ecuaciones:

$b_{i1}x_1+b_{i2}x_2+b_{i3}x_3+b_{i4}x_4=i,\,\,b_{ij}=a_{\frac{N+1}{2}+i,j}=-1,0,1,\,\,i=1,...,\frac{N-1}{2}$

Nótese que para que i sea entero siempre, todas las pesas deben serlo también. En particular, entre estas ecuaciones siempre estarán las correspondientes a cada pesa sola.

Ahora bien, ordenando las pesas por masa, x₁<x₂<x₃<x₄ tenemos que a la máxima cantidad de arroz que podemos medir, en hectogramos (40) podemos asociarle una ecuación dada por la distribución de estas 4 pesas cuando todas se encuentran en el plato en el que no está el arroz:

$x_1+x_2+x_3+x_4=40$

La medida inmediatamente anterior es necesariamente de 39hg y la única forma de obtenerla debe ser retirando la pesa más pequeña, pues ya las estamos usando todas:

$x_2+x_3+x_4=39$

Es decir, que x₁ debe ser de 100g (o en hectogramos, x₁=1). Si hubiera dos pesas que difirieran en 100g ya tendríamos otra forma de pesar 100g, cosa que queremos evitar, de modo que la diferencia de masas de dos pesas cualesquiera debe ser de al menos 200g. Debido a esto, no puede haber pesas de 200g y debe haber algún par de pesas y solamente uno que difieran en estos 200g para poder medir esta cantidad de forma única. Éstas no pueden ser x₂ y x₄, pues significaría que x₃ difiere con estas dos en 100g, cosa que queríamos evitar. Por el mismo motivo no pueden ser la primera y cualquiera que no sea la segunda. Teniendo en cuenta las últimas ecuaciones, esto plantea 3 soluciones, que dado que estamos buscando la forma de que la descomposición sea única son mutuamente excluyentes:

a) x₃-x₂=2
En este caso podemos medir hasta 300g añadiendo x₁. Sin embargo, al intentar descomponer el 37 (equivalente a medir 3.7kg) podríamos proponer algo como lo siguiente:

37 = 40-3 = 1+x₂+x₃+x₄ - 1+x₂-x₃
= 2x₂+x₄

Para que esta descomposición tenga sentido, dado que los únicos factores viables son -1, 0 y 1, tendremos que tener 2 pesas con la misma masa x₂, cosa que nos habíamos propuesto evitar. De hecho esta pesa no puede ser x₃, pues partimos de la base de que ésta es 200g más pesada que x₂, y si fuera x₄ estaríamos en el mismo problema. La única manera de que esto tuviera sentido sería que x₄=3x₂ (no puede ser x₃ ya que difiere en 2 unidades). De esta manera 2x₂=x₄-x₂, pero seguimos ante el problema de necesitar una quinta pesa x₅=x₄ o x₅=3x₄ para poder seguir usando únicamente los factores -1, 0 y 1.

b) x₄-x₃=2
Este caso es como el anterior. La única diferencia es que la pesa duplicada debería ser x₃.

c) x₂=3
En esta situación podemos continuar y pesar hasta 400g. Las descomposiciones de las pesadas 1 a 4 y 36 a 40 son coherentes con nuestras intenciones:

  i (hg) | ai1 | ai2 | ai3 | ai4 |
       1 |   1 |   0 |   0 |   0 |
       2 |  -1 |   1 |   0 |   0 |
       3 |   0 |   1 |   0 |   0 |
       4 |   1 |   1 |   0 |   0 |
      36 |   0 |   0 |   1 |   1 |
      37 |   1 |   0 |   1 |   1 |
      38 |  -1 |   1 |   1 |   1 |
      39 |   0 |   1 |   1 |   1 |
      40 |   1 |   1 |   1 |   1 |

Dicho esto, en general, dadas -como es el caso- k pesas $\{x_i=3^{i-1}hg\}_{i=1}^k$ que nos permiten pesar de hectogramo en hectogramo desde $l_{inf}=-\frac{3^k-1}{2}hg$ hasta $l_{sup}=\frac{3^k-1}{2}hg$, de forma que cada medida puede descomponerse de forma unívoca en una suma tal que

$\dst p=\sum_{i=1}^ka_ix_i$

Donde a_i toma los valores -1, si la pesa se coloca a la izquierda (digamos), 0 si no se coloca y 1 si se coloca a la derecha de la balanza.

Al añadir una nueva pesa q=fx_k, donde f>1, la cantidad mínima (positiva) que podrá pesarse usando la nueva pesa será (en hg):

$\dst p_{min}=q-\sum_{i=1}^k x_i=f\cdotp3^{k-1}-\frac{3^k-1}{2}$

De modo que podemos distinguir los siguientes casos:

a) f=3:
$\dst p_{min}=3^k-\frac{3^k-1}{2}=\frac{3^k+1}{2}=l_{sup}+1$
Con este multiplicador obtenemos la masa de la siguiente pesa que nos permite seguir contando.

b) f<3:
En este caso p_min difícilmente será si quiera entero, lo cual ya no nos permite seguir contando de hectogramo en hectogramo, pero aunque lo fuera siempre será menor que l_sup+1, con lo que aparecerían varias formas de pesar algunas cantidades. De hecho si $f<\frac{3}{2}-\frac{1}{2\cdotp 3^{k-1}}$ este valor mínimo colocando la nueva pesa a la derecha será negativo.

c) f>3:
Con esta pesa es más sencillo encontrar la manera de que p_min sea entero (pruébese con potencias de 3), pero siempre será mayor que l_sup+1, de forma que habrá medidas que no podremos pesar.

Lo mismo ocurre con la mayor masa negativa (bueno... medida con el arroz a la derecha) que se puede pesar usando esta nueva pesa.

Dado que con el antiguo juego de pesas $\{x_i=3^{i-1}\}_{i=1}^k$ podíamos contar de 100 en 100 gramos desde $l_{inf}=-\frac{3^k-1}{2}hg$ hasta $l_{sup}=\frac{3^k-1}{2}hg$, incluyendo esta nueva pesa ahora podremos hacerlo además desde $l_{sup}+1$ hasta $\frac{3^{k+1}-1}{2}$ hectogramos (dado que q=3x_k=3^khg) y desde $l_{inf}-1$ hasta $-\frac{3^{k+1}-1}{2}$ hectogramos.

De modo que la forma de no dejar ninguna medida múltiplo de 100g sin poder pesarse usando las 4 pesas y abarcando el mayor rango posible es buscar en alguna parte una pesa de 100g, otra de 300g, otra de 900g y otra de 2700g. La máxima cantidad de arroz que podría pesarse con estas pesas sería de 100g+300g+900g+2700g=4kg. Si quieres seguir teniendo la misma precisión en cualquier medida pero necesitas pesar más de 4kg ya necesitarías una quinta pesa, esta vez de 3 veces la masa de la mayor que tengas, 8.1kg.

Espero no haberme enrollado demasiado y sobre todo haberlo hecho y que haya una forma más fácil o más clara de resolverlo, pero en fin, fue bonito mientras duró.
¡Saludos!

[carroza]

Re: Pesando arroz (variante)

Muy bien, teclado.

Quizas para otra vez puedes usar el entorno solución, [ solucion] aqui pones to solucion, sin el espacio tras el corchete [ /solucion], para que se vea así

Ocultar contenido

Mostrar solución Ocultar solución

aqui pones to solucion, sin el espacio tras el corchete

.

Otro comentario:

Ocultar contenido

Mostrar solución Ocultar solución

Me gusta tu derivación a priori del máximo número de pesadas, como $(3^n - 1)/2$, y tu demostracion de que la pesa más ligera pesa 1 hectogramo.

A partir de ahi puedes ver facilmente que cada pesa debe pesar igual al doble de la suma de las más ligeras que ella más uno. Eso te da la secuencia 1, 3, 9, 27.

saludos

[teclado]

Re: Pesando arroz (variante)

¡Gracias!, había visto a otros poner las soluciones así, pero no sabía cómo se hacía. Lo acabo de cambiar.

También es verdad lo que dices:

Ocultar contenido

Mostrar solución Ocultar solución

Una vez se tienen las masas de k pesas $\{x_i\}_{i=1}^k$ que permiten pesar de hectogramo en hectogramo (a priori no importa mucho hasta cuánto), para pesar el hectogramo siguiente basta encontrar una pesa q tal que:

$\dst q-\sum_{i=1}^kx_i=1+\sum_{i=1}^kx_i$,

es decir,

$\dst q=1+2\sum_{i=1}^kx_i$

De manera que partiendo de una primera pesa x₁=1 se encuentran las otras 3 como:

x₁ = 1
x₂ = 1+2·1 = 3
x₃ = 1+2·(1+3) = 9
x₄ = 1+2·(1+3+9) = 27

De hecho, en general se tiene la sucesión:

$\dst x_k=1+2\sum_{i=1}^{k-1}x_i$

De donde x_k-x_k-1=2x_k-1, o lo que es lo mismo, x_k=3x_k-1. O con x₁=1, x_i=3ⁱ.

Viendo que esta serie nos permite contar no sólo de 100 en 100 gramos, si no además hasta el máximo de $\dst\frac{3^k-1}{2}$ que teníamos a priori ya hemos encontrado una solución que además es la única posible por la forma de obtenerla.

Quizás me enrollé con con lo de que sea única comprobando cada caso por la deformación de mi cabeza intentando resolver otros problemas de lógica de por aquí, pero es de lógica hasta cierto punto, de resto es un problema puramente matemático.

¡Saludos!