Sumando subconjuntos – La respuesta

Solución “no constructiva”

(Esencialmente es la misma que Guillermo presentó en un comentario del post anterior, solo difiere en la forma de acotar 🙂 )

La solución es mucho más simple de lo que podría parecer a primera vista y se basa en el el crecimiento exponencial de la cantidad de subconjuntos respecto al tamaño del conjunto “base”.

Consideremos los posibles valores que puede tomar la suma de un subconjunto de los números: como todos los elementos son positivos, la mínima suma es 0 y corresponde al subconjunto vacío, mientras que la máxima corresponde al conjunto completo. Al tener todos los elementos 19 dígitos, si llamamos S a la suma de los elementos de un subconjunto cualquiera, tendremos:

0 ≤ S < 70·1019 < 1021.

Aprovechando la relación 103 < 210, vemos que

S < 1021 < 270.

Pero, como la cantidad de subconjuntos de un conjunto de 70 elementos es exactamente 270, acabamos de probar que hay más subconjuntos que posibles valores de la suma de sus elementos. Por lo tanto es inevitable que haya al menos dos subconjuntos con el mismo valor de la suma de sus elementos.

Un punto interesante es que la solución es la misma si agregamos el requerimiento de que los conjuntos sean disjuntos. Para ver esto, supongamos que tenemos dos subconjuntos distintos A y B con la misma suma:

sum(A) = sum(B).

Si analizamos los conjuntos A\B y B\A, observaremos que

sum(A\B) = sum(A) – sum(AB)

sum(B\A) = sum(B) – sum(AB)

sum(A\B) = sum(B\A).

Como obviamente A\B y B\A no pueden compartir elementos, entonces cada par de subconjuntos distintos con igual suma tiene asociado un par de subconjuntos disjuntos con igual suma.

Una solución constructiva?

Este problema es conocido como NP-completo, por lo que no cabe esperar una solución eficiente y general. Pero podría ser que con estos valores de parámetros fuera factible encontrar una solución particular por lo que realizaremos un análisis probabilístico.

Consideremos una distribución aleatoria uniforme en el intervalo (0, 1019): claramente tendrá una densidad de probabilidad constante e igual a 10-19. Esto implica que si elegimos un número aleatoriamente de esa distribución, considerándola ahora discreta, la probabilidad sería de 10-19, lo que concuerda con nuestra intuición.

Si analizamos ahora la distribución de probabilidad de la suma de 35 variables elegidas uniformemente de dicho intervalo, tendremos una distribución de probabilidad conocida como Irwin Hall. Pero para nuestros fines podemos aproximarla por una normal con media igual a 35 veces el promedio de los números, 2.08·1020, y desviación estándar igual a la desviación estándar de los números multiplicada por la raíz cuadrada de 35, 1.57·1019. Comparando la distribución normal con un histograma obtenido mediante simulación,

Comparación de un histograma de las sumas de combinaciones de 35 números con la aproximación normal.

se observa que, aunque la coincidencia de la media es muy buena, la desviación estándar de la normal es significativamente superior a la que se observa en el histograma. Esto se debe a que, a diferencia de lo que se supone en una distribución Irwin Hall, las variables sumadas no son independientes (podemos verlo más claramente pensando en el caso de 70 variables: la suma es única, pero la distribución de Irwin Hall nos daría una desviación estándar aún mayor que en el caso de 35 variables). Como este error nos lleva a sobrestimar la dificultad de encontrar una colisión, podemos ignorar esta discrepancia por el momento, ya que nos llevará a una aproximación conservadora.

Lo que necesitaríamos ahora es calcular la probabilidad de encontrar dos combinaciones con igual suma. Aunque queda claro que las probabilidades son mayores que en el caso de que las sumas estuvieran distribuidas uniformemente en el intervalo (0, 70·1019), no es tan simple calcular un valor exacto para esta probabilidad. Pero podemos hacer una estimación suponiendo a los valores distribuidos uniformemente en el intervalo ±1σ, lo que implica descartar menos del 35% de los valores.

Aplicando la expresión derivada en el “problema del cumpleaños” para una probabilidad de colisión p:

\displaystyle n(p) \approx \sqrt{2 \cdot 1.57 \cdot 10^{19}\ln\left(\frac{1}{1-p}\right)}.

Aceptando un 95% de probabilidad de éxito en la búsqueda de una colisión:

\displaystyle n(0.95) \approx \sqrt{2 \cdot 1.57 \cdot 10^{19}\ln 20}.

\displaystyle n(0.95) \approx 9.7\cdot 10^{9}.

Tomando en cuenta que se está desechando el 30% de los puntos, podemos concluir que examinar unos 2·1010 puntos nos debería dar una probabilidad elevada de encontrar una colisión.

Si bien es bastante complejo buscar una colisión entre más de 1010 valores, no es infactible. Pero sería mejor realizar algunas pruebas preliminares para ver si el resultado obtenido es razonable.

Prueba a escala

A modo de verificación podemos realizar una simulación a escala, empleando la suma de 30 números de 7 dígitos para disminuir la carga computacional. En este caso sigue estando garantizada la existencia de una colisión, ya que

0 ≤ S < 30·107 < 109 < 230.

Aplicando la aproximación normal, la suma de 15 números distribuidos seguirá una distribución de media 7.5·107 y varianza 15·1014/12. Por lo tanto la cantidad de sumas ensayadas para tener un 95% de probabilidad de encontrar una colisión (usando solo sumas dentro de 1σ) será:

\displaystyle n(0.95) \approx \sqrt{2 \cdot 1.1 \cdot 10^7\ln\left(\frac{1}{1-0.95}\right)} \approx 8120.

O sea que la probabilidad de requerir más de unos 14000 ( = 8200 / 0.6) intentos para encontrar una colisión debería ser pequeña. Y estos valores son mucho más simples de comprobar experimentalmente que los originales, ya que puede hacerse mediante un pequeño script:


import math, random

N = 1000

NUMBERS = [4401501, 1984319, 1064736, 6495167,
           6402639, 7578056, 9301342, 6042069,
           1144375, 5680006, 7450344, 9099174,
           2011586, 8039920, 3010493, 1658370,
           5927190, 3880633, 1318068, 9594698,
           2877906, 1792394, 9120086, 7372216,
           2141103, 7256943, 6603598, 8565018,
           1698346, 3004879]

def run_until_collision():
    combs_dict = {}
    i = 0
    while True:
        comb = random.sample(NUMBERS, 15)
        s = sum(comb)
        if s in combs_dict:
            return i, comb, combs_dict[s]
        combs_dict[s] = comb
        i += 1

def show_stats():
    total = 0.0
    sq_total = 0.0
    print 'Please wait until the count reaches 100...'
    for i in range(N):
        tries, dum, dum = run_until_collision()
        total += tries
        sq_total += tries ** 2
        if i % math.ceil(N / 100.0) == 0:
            print '%d' % (i * 100.0 / N),
    print '\n\nTries statistics'
    print '  Average: %f' % (total / N)
    print '  SD: %f' % math.sqrt(sq_total / N -
                                 (total / N) ** 2)

if __name__ == '__main__':
    show_stats()

La salida obtenida al ejecutar este script (descartando indicaciones de progreso) es:

Tries statistics
  Average: 6123.049000
  SD: 3360.260149

Conclusiones

Para poder encontrar una colisión en forma explícita en el problema original deberá ser necesario buscarla entre aproximadamente 1010 valores. Como cada subconjunto con su suma ocupará en el orden de 16 bytes y una PC suele tener menos que 100 GB de RAM, sería práctico buscar un método que permita buscar colisiones sin tener todos los valores previamente analizados en memoria (otra opción sería usar datos en disco, pero es menos elegante 😀 ).

En un próximo post analizaremos como implementar una solución a este problema y veremos si pueden encontrarse resultados.

Advertisements

3 thoughts on “Sumando subconjuntos – La respuesta

  1. […] Agosto 16, 2010 at 8:42 pm (C++, informática, matemática, probabilidad, python) (Follow-up to Sumando subconjuntos – La respuesta.) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s