EL PROBLEMA DE LOS MELONES

 

            Llamo así al que me propuso en cierta ocasión mi tío Peret, de Juneda, consistente en repartirnos ocho melones de pesos:

 

                                                MELÓN          PESO (g)

 

                                                  1                    850

                                                  2                    870

                                                  3                    970

                                                  4                    990

                                                  5                    1170

                                                  6                    1230

                                                  7                    1430

                                                  8                    1450

 

                                                Total                9860

 

en dos lotes del mismo peso total cada uno. ¿Cómo hacerlo?

            El problema se resuelve sin grandes esfuerzos por tanteos (la solución, más adelante). Pero, ¿y en el caso general?

            Fácil es ver que, para n melones, pueden hacerse  grupos de k melones, por lo que el número total de grupos posibles es:

 

 

  Se halla fácilmente esta suma observando que es el desarrollo del binomio (1 + 1)n = 2n. Al mismo resultado llegamos planteándolo de otra manera: para formar cada grupo, podemos optar, para cada uno de los melones, entre incluirlo en el grupo o no, por lo que el número total posible de grupos será 2*2*2*...*2 = 2n.

                Esta forma de verlo encierra un nuevo interés, pues muestra que podemos establecer una correspondencia biunívoca entre cada grupo posible y cada entero entre 0 y 2n - 1. La expresión de este entero, en base 2, constará de unos y ceros. En el caso anterior, en que n=8:

COMBINACIÓN

K (BASE 8)

0

0

1

1

2

10

3

11

4

100

5

101

…

…

 

 

252

11111100

253

11111101

254

11111110

255

11111111

 

            Significando esto, por ejemplo, que la combinación definida por el ordinal k=5 se compone del sexto y el octavo melones.

             Por tanto, el peso total de cada combinación distinta de melones resultará de multiplicar el de cada uno por su respectiva cifra en la expresión binaria de la combinación.

            Esto nos proporciona un algoritmo bastante fácil de programar en ordenador: bastará descomponer cada número, entre 0 y 2n, en su expresión binaria, y hallar luego los respectivos pesos por suma de los melones cuyas cifras correspondientes sean la unidad. El problema de mi tío Peret se resuelve así con los melones 2, 4, 5 y 8, cuyos pesos son:

 

            P5 = 870 + 990 + 1170 + 1450 = 4480 g

 

            En el caso general, el problema tendrá por lo común diversas soluciones, pues intuitivamente se ve que, siendo 2n un número de un orden mayor que el de los posibles pesos, habrá una gran abundancia de posibles pesadas. Pero, en determinados casos, puede no tener solución (por ejemplo, si el peso total hubiera sido un número impar de decagramos).

            Podemos ordenar los pesos obtenidos en las 2n distintas combinaciones de menor a mayor y agruparlos en un diagrama de intervalo 2n. La gráfica que obtenemos es de este tipo (pesos totales en decagramos):

 

            ¿Qué nos recuerda esta cuasi curva? Pues la función de Gauss:

 

               

Es bastante lógico llegar a esta curva si, como es habitual, los pesos de los melones responden a una distribución estadística aleatoria uniforme, y aun en el caso general, con ciertas salvedades, pues en virtud del teorema central del límite, si es pm el peso medio de un melón y s su desviación típica, los pesos de la suma de los n elementos tienden a una distribución normal cuyas respectivas suma y desviación típica son:

 

                                                S = npm

 

                                                                s= sÖn

 

            Sin embargo, ¿qué ocurre cuando los melones no siguen una distribución tan corriente? El caso más conocido se da si éstos responden precisamente a las potencias de 2. Es decir, si los pesos hubieran sido por ejemplo 10, 20, 40, 80, 160, 320, 640 y 1280 g. En este caso, la curva de distribución hubiera sido precisamente una recta, lo que responde al conocido hecho de que la combinación más eficaz de las pesas de una balanza, para poder reproducir cualquier pesada, debe ser según una serie de potencias de 2.

 

           

¿Y si los melones siguieran una disposición todavía más creciente? Por ejemplo, las potencias de 3. En este caso, la curva de distribución de los pesos invierte su concavidad, según la gráfica, pues deja de ser válida la consideración anterior sobre la abundancia de pesadas posibles. Queda una amplia zona central inasequible (que sugiere una curva con un punto de inflexión ahí), con otras laterales de amplitudes sucesivamente decrecientes.

            Me gustaría que alguien fuera capaz de obtener las expresiones analíticas de las correspondientes curvas. Este problema creo que es el más difícil propuesto hasta ahora en [C].

 

 

                                                                        Josep M. Albaigès

                                                                                                                                    Barcelona, marzo 1989